93 citations · 178 across the 18 of their papers we have counts for
5 papers · 1 filter
A Gapped Scale-Sensitive Dimension and Lower Bounds for Offset Rademacher Complexity
Zeyu Jia, Yury Polyanskiy, Alexander Rakhlin
We study gapped scale-sensitive dimensions of a function class in both sequential and non-sequential settings. We demonstrate that covering numbers for any uniformly bounded class…
Online Estimation via Offline Estimation: An Information-Theoretic Framework
Dylan J. Foster, Yanjun Han, Jian Qian +1
The classical theory of statistical estimation aims to estimate a parameter of interest under data generated from a fixed design ("offline estimation"), while the contemporary t…
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…
Online Nonparametric Regression with General Loss Functions
Alexander Rakhlin, Karthik Sridharan
This paper establishes minimax rates for online regression with arbitrary classes of functions and general losses. We show that below a certain threshold for the complexity of the…
Online Learning: Beyond Regret
Alexander Rakhlin, Karthik Sridharan, Ambuj Tewari
We study online learnability of a wide class of problems, extending the results of (Rakhlin, Sridharan, Tewari, 2010) to general notions of performance measure well beyond external…