6 papers · 1 filter
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…
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…