# Fast rates in statistical and online learning

arXiv: https://arxiv.org/abs/1507.02592 · HTML: https://mlsanity.com/paper/1507.02592/

## Key facts

- Cited by 47 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jul 2015.

## Built on by (most cited first, 30 of 47)

- [Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)](https://mlsanity.com/paper/2103.12024/) (2021)
- [PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classes](https://mlsanity.com/paper/2106.09683/) (2021)
- [A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits](https://mlsanity.com/paper/2407.13977/) (2024)
- [Generalization Bounds via Convex Analysis](https://mlsanity.com/paper/2202.04985/) (2022)
- [MetaGrad: Adaptation using Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/2102.06622/) (2021)
- [Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games](https://mlsanity.com/paper/2111.08911/) (2021)
- [Online-to-PAC Conversions: Generalization Bounds via Regret Analysis](https://mlsanity.com/paper/2305.19674/) (2023)
- [Faster Rates of Private Stochastic Convex Optimization](https://mlsanity.com/paper/2108.00331/) (2021)
- [Mixability made efficient: Fast online multiclass logistic regression](https://mlsanity.com/paper/2110.03960/) (2021)
- [Fast rates in structured prediction](https://mlsanity.com/paper/2102.00760/) (2021)
- [On the Generalization for Transfer Learning: An Information-Theoretic Analysis](https://mlsanity.com/paper/2207.05377/) (2022)
- [Localization, Convexity, and Star Aggregation](https://mlsanity.com/paper/2105.08866/) (2021)
- [PAC-Bayes Bounds for Bandit Problems: A Survey and Experimental Comparison](https://mlsanity.com/paper/2211.16110/) (2022)
- [Reshuffling Resampling Splits Can Improve Generalization of Hyperparameter Optimization](https://mlsanity.com/paper/2405.15393/) (2024)
- [Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixability](https://mlsanity.com/paper/2506.10616/) (2025)
- [Fast Rate Generalization Error Bounds: Variations on a Theme](https://mlsanity.com/paper/2205.03131/) (2022)
- [Sequential Counterfactual Risk Minimization](https://mlsanity.com/paper/2302.12120/) (2023)
- [The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective](https://mlsanity.com/paper/2501.15910/) (2025)
- [Coverage Improvement and Fast Convergence of On-policy Preference Learning](https://mlsanity.com/paper/2601.08421/) (2026)
- [Fast Rate Information-theoretic Bounds on Generalization Errors](https://mlsanity.com/paper/2303.14658/) (2023)
- [Statistical learning theory and Occam's razor: The core argument](https://mlsanity.com/paper/2312.13842/) (2023)
- [Sharp error bounds for imbalanced classification: how many examples in the minority class?](https://mlsanity.com/paper/2310.14826/) (2023)
- [Contextual Multinomial Logit Bandits with General Value Functions](https://mlsanity.com/paper/2402.08126/) (2024)
- [Information Processing Equalities and the Information-Risk Bridge](https://mlsanity.com/paper/2207.11987/) (2022)
- [Provably Efficient Interactive-Grounded Learning with Personalized Reward](https://mlsanity.com/paper/2405.20677/) (2024)
- [A Solver-Free Training Method for Predict-then-Optimize](https://mlsanity.com/paper/2606.19587/) (2026)
- [Posterior concentration and fast convergence rates for generalized Bayesian learning](https://mlsanity.com/paper/2111.10243/) (2021)
- [Constant regret for sequence prediction with limited advice](https://mlsanity.com/paper/2210.02256/) (2022)
- [The Geometry of Mixability](https://mlsanity.com/paper/2302.11905/) (2023)
- [Learning to Abstain From Uninformative Data](https://mlsanity.com/paper/2309.14240/) (2023)

## Abstract (arXiv)

The speed with which a learning algorithm converges as it is presented with more data is a central problem in machine learning --- a fast rate of convergence means less data is needed for the same level of performance. The pursuit of fast rates in online and statistical learning has led to the discovery of many conditions in learning theory under which fast learning is possible. We show that most of these conditions are special cases of a single, unifying condition, that comes in two forms: the central condition for 'proper' learning algorithms that always output a hypothesis in the given model, and stochastic mixability for online algorithms that may make predictions outside of the model. We show that under surprisingly weak assumptions both conditions are, in a certain sense, equivalent. The central condition has a re-interpretation in terms of convexity of a set of pseudoprobabilities, linking it to density estimation under misspecification. For bounded losses, we show how the central condition enables a direct proof of fast rates and we prove its equivalence to the Bernstein condition, itself a generalization of the Tsybakov margin condition, both of which have played a central role in obtaining fast rates in statistical learning. Yet, while the Bernstein condition is two-sided, the central condition is one-sided, making it more suitable to deal with unbounded losses. In its stochastic mixability form, our condition generalizes both a stochastic exp-concavity condition identified by Juditsky, Rigollet and Tsybakov and Vovk's notion of mixability. Our unifying conditions thus provide a substantial step towards a characterization of fast rates in statistical learning, similar to how classical mixability characterizes constant regret in the sequential prediction with expert advice setting.