9 papers
Oracle-Efficient and Parameter-Free Agnostic Smoothed Online Learning
Sasha Voitovych, Adam Block, Alexander Rakhlin +1
Online learning is an attractive framework in many domains because it permits well-defined learning even when data are dependent or chosen adversarially. This generality, however,…
An Empirical Bayes Perspective on Heteroskedastic Mean Estimation
Yanjun Han, Abhishek Shetty, Jacob Shkrob
Towards understanding the fundamental limits of estimation from data of varied quality, we study the problem of estimating a mean parameter from heteroskedastic Gaussian observatio…
Partition Function Estimation under Bounded f-Divergence
Adam Block, Abhishek Shetty
We study the statistical complexity of estimating partition functions given sample access to a proposal distribution and an unnormalized density ratio for a target distribution. Wh…
Is Multi-Distribution Learning as Easy as PAC Learning: Sharp Rates with Bounded Label Noise
Rafael Hanashiro, Abhishek Shetty, Patrick Jaillet
Towards understanding the statistical complexity of learning from heterogeneous sources, we study the problem of multi-distribution learning. Given data sources, the goal is to…
Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness
Moïse Blanchard, Abhishek Shetty, Alexander Rakhlin
Understanding minimal assumptions that enable learning and generalization is perhaps the central question of learning theory. Several celebrated results in statistical learning the…
Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks
Omar Montasser, Abhishek Shetty, Nikita Zhivotovskiy
We revisit online binary classification by shifting the focus from competing with the best-in-class binary loss to competing against relaxed benchmarks that capture smoothed notion…
Small Loss Bounds for Online Learning Separated Function Classes: A Gaussian Process Perspective
Adam Block, Abhishek Shetty
In order to develop practical and efficient algorithms while circumventing overly pessimistic computational lower bounds, recent work has been interested in developing oracle-effic…
On the Performance of Empirical Risk Minimization with Smoothed Data
Adam Block, Alexander Rakhlin, Abhishek Shetty
In order to circumvent statistical and computational hardness results in sequential decision-making, recent work has considered smoothed online learning, where the distribution of…
Oracle-Efficient Differentially Private Learning with Public Data
Adam Block, Mark Bun, Rathin Desai +2
Due to statistical lower bounds on the learnability of many function classes under privacy constraints, there has been recent interest in leveraging public data to improve the perf…