# Robust Linear Predictions: Analyses of Uniform Concentration, Fast Rates and Model Misspecification

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 70 references that are in the map.
- First posted on arXiv 6 Jan 2022.

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

- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [Adapting to Misspecification in Contextual Bandits](https://mlsanity.com/paper/2107.05745/) (2021)
- [Tensor Regression Networks](https://mlsanity.com/paper/1707.08308/) (2017)
- [Empirical risk minimization for heavy-tailed losses](https://mlsanity.com/paper/1406.2462/) (2014)
- [Fast Rates for General Unbounded Loss Functions: from ERM to Generalized Bayes](https://mlsanity.com/paper/1605.00252/) (2016)
- [When OT meets MoM: Robust estimation of Wasserstein Distance](https://mlsanity.com/paper/2006.10325/) (2020)
- [Distribution-Free Robust Linear Regression](https://mlsanity.com/paper/2102.12919/) (2021)
- [Lecture Notes: Selected topics on robust statistical learning theory](https://mlsanity.com/paper/1908.10761/) (2019)
- [Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond](https://mlsanity.com/paper/1912.11071/) (2019)
- [Robust k-means Clustering for Distributions with Two Moments](https://mlsanity.com/paper/2002.02339/) (2020)
- [Regularization, sparse recovery, and median-of-means tournaments](https://mlsanity.com/paper/1701.04112/) (2017)
- [Fast rates in structured prediction](https://mlsanity.com/paper/2102.00760/) (2021)
- [Variance Reduced Median-of-Means Estimator for Byzantine-Robust Distributed Inference](https://mlsanity.com/paper/2103.02860/) (2021)
- [Uniform Concentration Bounds toward a Unified Framework for Robust Clustering](https://mlsanity.com/paper/2110.14148/) (2021)
- [Excess risk bounds in robust empirical risk minimization](https://mlsanity.com/paper/1910.07485/) (2019)
- [A General Method for Robust Bayesian Modeling](https://mlsanity.com/paper/1510.05078/) (2015)
- [K-bMOM: a robust Lloyd-type clustering algorithm based on bootstrap Median-of-Means](https://mlsanity.com/paper/2002.03899/) (2020)
- [Robust Estimation in Generalised Linear Models : The Density Power Divergence Approach](https://mlsanity.com/paper/1403.6606/) (2014)
- [Robust Principal Component Analysis: A Median of Means Approach](https://mlsanity.com/paper/2102.03403/) (2021)
- [Generalized Linear Model Regression under Distance-to-set Penalties](https://mlsanity.com/paper/1711.01341/) (2017)
- [Dynamic quantile linear models: a Bayesian approach](https://mlsanity.com/paper/1711.00162/) (2017)

## Abstract (arXiv)

The problem of linear predictions has been extensively studied for the past century under pretty generalized frameworks. Recent advances in the robust statistics literature allow us to analyze robust versions of classical linear models through the prism of Median of Means (MoM). Combining these approaches in a piecemeal way might lead to ad-hoc procedures, and the restricted theoretical conclusions that underpin each individual contribution may no longer be valid. To meet these challenges coherently, in this study, we offer a unified robust framework that includes a broad variety of linear prediction problems on a Hilbert space, coupled with a generic class of loss functions. Notably, we do not require any assumptions on the distribution of the outlying data points (O) nor the compactness of the support of the inlying ones (I). Under mild conditions on the dual norm, we show that for misspecification level ε, these estimators achieve an error rate of O(maxleft|O|1/2n-1/2, |I|1/2n-1 right+ε), matching the best-known rates in literature. This rate is slightly slower than the classical rates of O(n-1/2), indicating that we need to pay a price in terms of error rates to obtain robust estimates. Additionally, we show that this rate can be improved to achieve so-called "fast rates" under additional assumptions.