# Exponential Tail Local Rademacher Complexity Risk Bounds Without the Bernstein Condition

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 98 references that are in the map.
- First posted on arXiv 23 Feb 2022.

## Builds on (most cited first, 20 of 20)

- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Early stopping and non-parametric regression: An optimal data-dependent stopping rule](https://mlsanity.com/paper/1306.3574/) (2013)
- [Learning without Concentration](https://mlsanity.com/paper/1401.0304/) (2014)
- [Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)](https://mlsanity.com/paper/2103.12024/) (2021)
- [Logistic Regression: The Importance of Being Improper](https://mlsanity.com/paper/1803.09349/) (2018)
- [Learning with Square Loss: Localization through Offset Rademacher Complexity](https://mlsanity.com/paper/1502.06134/) (2015)
- [Optimal learning with Bernstein Online Aggregation](https://mlsanity.com/paper/1404.1356/) (2014)
- [Logistic Regression: Tight Bounds for Stochastic and Online Optimization](https://mlsanity.com/paper/1405.3843/) (2014)
- [Early stopping for kernel boosting algorithms: A general analysis with localized complexities](https://mlsanity.com/paper/1707.01543/) (2017)
- [An improper estimator with optimal excess risk in misspecified density estimation and logistic regression](https://mlsanity.com/paper/1912.10784/) (2019)
- [Exponential Savings in Agnostic Active Learning through Abstention](https://mlsanity.com/paper/2102.00451/) (2021)
- [Empirical entropy, minimax regret and minimax risk](https://mlsanity.com/paper/1308.1147/) (2013)
- [The Statistical Complexity of Early-Stopped Mirror Descent](https://mlsanity.com/paper/2002.00189/) (2020)
- [Distribution-Free Robust Linear Regression](https://mlsanity.com/paper/2102.12919/) (2021)
- [The Sample Complexity of Learning Linear Predictors with the Squared Loss](https://mlsanity.com/paper/1406.5143/) (2014)
- [Fast classification rates without standard margin assumptions](https://mlsanity.com/paper/1910.12756/) (2019)
- [Learning without Concentration for General Loss Functions](https://mlsanity.com/paper/1410.3192/) (2014)
- [Iterative Regularization for Learning with Convex Loss Functions](https://mlsanity.com/paper/1503.08985/) (2015)
- [Suboptimality of Constrained Least Squares and Improvements via Non-Linear Predictors](https://mlsanity.com/paper/2009.09304/) (2020)
- [Localization, Convexity, and Star Aggregation](https://mlsanity.com/paper/2105.08866/) (2021)

## Built on by (most cited first, 9 of 9)

- [High-Probability Risk Bounds via Sequential Predictors](https://mlsanity.com/paper/2308.07588/) (2023)
- [A Regret-Variance Trade-Off in Online Learning](https://mlsanity.com/paper/2206.02656/) (2022)
- [DRM Revisited: A Complete Error Analysis](https://mlsanity.com/paper/2407.09032/) (2024)
- [Local Risk Bounds for Statistical Aggregation](https://mlsanity.com/paper/2306.17151/) (2023)
- [Exploring Local Norms in Exp-concave Statistical Learning](https://mlsanity.com/paper/2302.10726/) (2023)
- [On the Efficiency of ERM in Feature Learning](https://mlsanity.com/paper/2411.12029/) (2024)
- [Reweighting Improves Conditional Risk Bounds](https://mlsanity.com/paper/2501.02353/) (2025)
- [Stochastic Trace Optimization of Parameter Dependent Matrices Based on Statistical Learning Theory](https://mlsanity.com/paper/2508.05764/) (2025)
- [Sample Complexity of Scientific Discovery: PAC Learnability of Compositional Function Trees](https://mlsanity.com/paper/2606.29331/) (2026)

## Abstract (arXiv)

The local Rademacher complexity framework is one of the most successful general-purpose toolboxes for establishing sharp excess risk bounds for statistical estimators based on the framework of empirical risk minimization. Applying this toolbox typically requires using the Bernstein condition, which often restricts applicability to convex and proper settings. Recent years have witnessed several examples of problems where optimal statistical performance is only achievable via non-convex and improper estimators originating from aggregation theory, including the fundamental problem of model selection. These examples are currently outside of the reach of the classical localization theory. In this work, we build upon the recent approach to localization via offset Rademacher complexities, for which a general high-probability theory has yet to be established. Our main result is an exponential-tail excess risk bound expressed in terms of the offset Rademacher complexity that yields results at least as sharp as those obtainable via the classical theory. However, our bound applies under an estimator-dependent geometric condition (the "offset condition") instead of the estimator-independent (but, in general, distribution-dependent) Bernstein condition on which the classical theory relies. Our results apply to improper prediction regimes not directly covered by the classical theory.