5 papers
Compact Conformal Subgraphs
Sreenivas Gollapudi, Kostas Kollias, Kamesh Munagala +1
Conformal prediction provides rigorous, distribution-free uncertainty guarantees, but often yields prohibitively large prediction sets in structured domains such as routing, planni…
Low-Degree Method Fails to Predict Robust Subspace Recovery
He Jia, Aravindan Vijayaraghavan
The low-degree polynomial framework has been highly successful in predicting computational versus statistical gaps for high-dimensional problems in average-case analysis and machin…
Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals
Anxin Guo, Aravindan Vijayaraghavan
We consider the problem of learning an arbitrarily-biased ReLU activation (or neuron) over Gaussian marginals with the squared loss objective. Despite the ReLU neuron being the bas…
New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries
Aditya Bhaskara, Eric Evert, Vaidehi Srinivas +1
We develop new techniques for proving lower bounds on the least singular value of random matrices with limited randomness. The matrices we consider have entries that are given by p…
Efficient Certificates of Anti-Concentration Beyond Gaussians
Ainesh Bakshi, Pravesh Kothari, Goutham Rajendran +2
A set of high dimensional points in isotropic position is said to be -anti concentrated if for every direction , the fraction of poi…