# Exploring Local Norms in Exp-concave Statistical Learning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 51 references that are in the map.
- First posted on arXiv 21 Feb 2023.

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

- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [Sharper bounds for uniformly stable algorithms](https://mlsanity.com/paper/1910.07833/) (2019)
- [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)
- [Logistic Regression: Tight Bounds for Stochastic and Online Optimization](https://mlsanity.com/paper/1405.3843/) (2014)
- [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)
- [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)
- [Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the O(1/T) Convergence Rate](https://mlsanity.com/paper/1901.09344/) (2019)
- [Sequential Probability Assignment with Binary Alphabets and Large Classes of Experts](https://mlsanity.com/paper/1501.07340/) (2015)
- [An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning](https://mlsanity.com/paper/2106.02720/) (2021)
- [Suboptimality of Constrained Least Squares and Improvements via Non-Linear Predictors](https://mlsanity.com/paper/2009.09304/) (2020)
- [Exponential Tail Local Rademacher Complexity Risk Bounds Without the Bernstein Condition](https://mlsanity.com/paper/2202.11461/) (2022)
- [Efficient online algorithms for fast-rate regret bounds under sparsity](https://mlsanity.com/paper/1805.09174/) (2018)
- [Localization, Convexity, and Star Aggregation](https://mlsanity.com/paper/2105.08866/) (2021)
- [A Regret-Variance Trade-Off in Online Learning](https://mlsanity.com/paper/2206.02656/) (2022)
- [Average Stability is Invariant to Data Preconditioning. Implications to Exp-concave Empirical Risk Minimization](https://mlsanity.com/paper/1601.04011/) (2016)
- [A Simple Analysis for Exp-concave Empirical Minimization with Arbitrary Convex Regularizer](https://mlsanity.com/paper/1709.02909/) (2017)

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

- [High-Probability Risk Bounds via Sequential Predictors](https://mlsanity.com/paper/2308.07588/) (2023)
- [Hardness, Structural Knowledge, and Opportunity: An Analytical Framework for Modular Performance Modeling](https://mlsanity.com/paper/2509.11000/) (2025)

## Abstract (arXiv)

We consider the problem of stochastic convex optimization with exp-concave losses using Empirical Risk Minimization in a convex class. Answering a question raised in several prior works, we provide a O( d / n + log( 1 / δ) / n ) excess risk bound valid for a wide class of bounded exp-concave losses, where d is the dimension of the convex reference set, n is the sample size, and δ is the confidence level. Our result is based on a unified geometric assumption on the gradient of losses and the notion of local norms.