# Localization, Convexity, and Star Aggregation

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 28 references that are in the map.
- First posted on arXiv 19 May 2021.

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

- [Fast rates in statistical and online learning](https://mlsanity.com/paper/1507.02592/) (2015)
- [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)
- [Logistic Regression: Tight Bounds for Stochastic and Online Optimization](https://mlsanity.com/paper/1405.3843/) (2014)
- [Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordance](https://mlsanity.com/paper/1902.03046/) (2019)
- [An improper estimator with optimal excess risk in misspecified density estimation and logistic regression](https://mlsanity.com/paper/1912.10784/) (2019)
- [Empirical entropy, minimax regret and minimax risk](https://mlsanity.com/paper/1308.1147/) (2013)
- [Efficient improper learning for online logistic regression](https://mlsanity.com/paper/2003.08109/) (2020)
- [Online Nonparametric Regression with General Loss Functions](https://mlsanity.com/paper/1501.06598/) (2015)

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

- [High-Probability Risk Bounds via Sequential Predictors](https://mlsanity.com/paper/2308.07588/) (2023)
- [Exponential Tail Local Rademacher Complexity Risk Bounds Without the Bernstein Condition](https://mlsanity.com/paper/2202.11461/) (2022)
- [Regularized DeepIV with Model Selection](https://mlsanity.com/paper/2403.04236/) (2024)
- [Local Risk Bounds for Statistical Aggregation](https://mlsanity.com/paper/2306.17151/) (2023)
- [Ratio Covers of Convex Sets and Optimal Mixture Density Estimation](https://mlsanity.com/paper/2602.16142/) (2026)
- [Exploring Local Norms in Exp-concave Statistical Learning](https://mlsanity.com/paper/2302.10726/) (2023)
- [Star algorithm for NN ensembling](https://mlsanity.com/paper/2206.00255/) (2022)

## Abstract (arXiv)

Offset Rademacher complexities have been shown to provide tight upper bounds for the square loss in a broad class of problems including improper statistical learning and online learning. We show that the offset complexity can be generalized to any loss that satisfies a certain general convexity condition. Further, we show that this condition is closely related to both exponential concavity and self-concordance, unifying apparently disparate results. By a novel geometric argument, many of our bounds translate to improper learning in a non-convex class with Audibert's star algorithm. Thus, the offset complexity provides a versatile analytic tool that covers both convex empirical risk minimization and improper learning under entropy conditions. Applying the method, we recover the optimal rates for proper and improper learning with the p-loss for 1 < p < ∞, and show that improper variants of empirical risk minimization can attain fast rates for logistic regression and other generalized linear models.