# On Misspecification in Prediction Problems and Robustness via Improper Learning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 42 references that are in the map.
- First posted on arXiv 13 Jan 2021.

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

- [The Landscape of Empirical Risk for Non-convex Losses](https://mlsanity.com/paper/1607.06534/) (2016)
- [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)
- [Asymptotic Optimality in Stochastic Optimization](https://mlsanity.com/paper/1612.05612/) (2016)
- [Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression](https://mlsanity.com/paper/1303.6149/) (2013)
- [Logistic Regression: Tight Bounds for Stochastic and Online Optimization](https://mlsanity.com/paper/1405.3843/) (2014)
- [Efficient improper learning for online logistic regression](https://mlsanity.com/paper/2003.08109/) (2020)

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

- [The Bias-Variance Tradeoff in Data-Driven Optimization: A Local Misspecification Perspective](https://mlsanity.com/paper/2510.18215/) (2025)

## Abstract (arXiv)

We study probabilistic prediction games when the underlying model is misspecified, investigating the consequences of predicting using an incorrect parametric model. We show that for a broad class of loss functions and parametric families of distributions, the regret of playing a "proper" predictor -- one from the putative model class -- relative to the best predictor in the same model class has lower bound scaling at least as √γ n, where γ is a measure of the model misspecification to the true distribution in terms of total variation distance. In contrast, using an aggregation-based (improper) learner, one can obtain regret d log n for any underlying generating distribution, where d is the dimension of the parameter; we exhibit instances in which this is unimprovable even over the family of all learners that may play distributions in the convex hull of the parametric family. These results suggest that simple strategies for aggregating multiple learners together should be more robust, and several experiments conform to this hypothesis.