13 citations · 50 across the 14 of their papers we have counts for
15 papers
Flexible Routing via Uncertainty Decomposition
Charlotte Peale, Siddartha Devic, Parikshit Gopalan +2
A key strategy for balancing performance and cost in modern machine learning systems is to dynamically route queries to either a low-cost model or a more expensive oracle (such as…
Trace Length is a Simple Uncertainty Signal in Reasoning Models
Siddartha Devic, Charlotte Peale, Arwen Bradley +3
Uncertainty quantification for LLMs is a key research direction towards addressing hallucination and other issues that limit their reliable deployment. In this work, we show that r…
When does a predictor know its own loss?
Aravind Gollakota, Parikshit Gopalan, Aayush Karan +2
Given a predictor and a loss function, how well can we predict the loss that the predictor will incur on an input? This is the problem of loss prediction, a key computational task…
Provable Uncertainty Decomposition via Higher-Order Calibration
Gustaf Ahdritz, Aravind Gollakota, Parikshit Gopalan +2
We give a principled method for decomposing the predictive uncertainty of a model into aleatoric and epistemic components with explicit semantics relating them to the real-world da…
Agnostically Learning Single-Index Models using Omnipredictors
Aravind Gollakota, Parikshit Gopalan, Adam R. Klivans +1
We give the first result for agnostically learning Single-Index Models (SIMs) with arbitrary monotone and Lipschitz activations. All prior work either held only in the realizable s…
Ambient Diffusion: Learning Clean Distributions from Corrupted Data
Giannis Daras, Kulin Shah, Yuval Dagan +3
We present the first diffusion-based framework that can learn an unknown distribution using only highly-corrupted samples. This problem arises in scientific applications where acce…
Tester-Learners for Halfspaces: Universal Algorithms
Aravind Gollakota, Adam R. Klivans, Konstantinos Stavropoulos +1
We give the first tester-learner for halfspaces that succeeds universally over a wide class of structured distributions. Our universal tester-learner runs in fully polynomial time…
An Efficient Tester-Learner for Halfspaces
Aravind Gollakota, Adam R. Klivans, Konstantinos Stavropoulos +1
We give the first efficient algorithm for learning halfspaces in the testable learning model recently defined by Rubinfeld and Vasilyan (2023). In this model, a learner certifies t…
A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity
Aravind Gollakota, Adam R. Klivans, Pravesh K. Kothari
A remarkable recent paper by Rubinfeld and Vasilyan (2022) initiated the study of \emph{testable learning}, where the goal is to replace hard-to-verify distributional assumptions (…
Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks
Sitan Chen, Aravind Gollakota, Adam R. Klivans +1
We give superpolynomial statistical query (SQ) lower bounds for learning two-hidden-layer ReLU networks with respect to Gaussian inputs in the standard (noise-free) model. No gener…
On the Hardness of PAC-learning Stabilizer States with Noise
Aravind Gollakota, Daniel Liang
We consider the problem of learning stabilizer states with noise in the Probably Approximately Correct (PAC) framework of Aaronson (2007) for learning quantum states. In the noisel…
The Polynomial Method is Universal for Distribution-Free Correlational SQ Learning
Aravind Gollakota, Sushrut Karmalkar, Adam Klivans
We consider the problem of distribution-free learning for Boolean function classes in the PAC and agnostic models. Generalizing a beautiful work of Malach and Shalev-Shwartz (2022)…
Statistical-Query Lower Bounds via Functional Gradients
Surbhi Goel, Aravind Gollakota, Adam Klivans
We give the first statistical-query lower bounds for agnostically learning any non-polynomial activation with respect to Gaussian marginals (e.g., ReLU, sigmoid, sign). For the spe…
Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent
Surbhi Goel, Aravind Gollakota, Zhihan Jin +2
We prove the first superpolynomial lower bounds for learning one-layer neural networks with respect to the Gaussian distribution using gradient descent. We show that any classifier…
Packing tree degree sequences
Aravind Gollakota, William Hardt, Istvan Miklos
We consider packing tree degree sequences in this paper. We set up a conjecture that any arbitrary number of tree degree sequences without common leaves have edge disjoint tree rea…