mlsanityData to 7 Oct 2026

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

arXiv 2201.01973 ↗First posted 6 Jan 2022stat.ML cs.LG math.STcited by 0

Not on the map. Why?

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.

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

Builds on

23 of 70 references.

References · 23

  1. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 195
  2. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
  3. 2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 123
  4. 2021Adapting to Misspecification in Contextual Banditscited by 81
  5. 2017Tensor Regression Networkscited by 44
  6. 2014Empirical risk minimization for heavy-tailed lossescited by 37
  7. 2016Fast Rates for General Unbounded Loss Functions: from ERM to Generalized Bayescited by 27
  8. 2020When OT meets MoM: Robust estimation of Wasserstein Distancecited by 23
  9. 2021Distribution-Free Robust Linear Regressioncited by 19
  10. 2019Lecture Notes: Selected topics on robust statistical learning theorycited by 17
  11. 2019Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyondcited by 14
  12. 2020Robust k-means Clustering for Distributions with Two Momentscited by 14
11 more
  1. 2017Regularization, sparse recovery, and median-of-means tournamentscited by 11
  2. 2021Fast rates in structured predictioncited by 11
  3. 2021Variance Reduced Median-of-Means Estimator for Byzantine-Robust Distributed Inferencecited by 11
  4. 2021Uniform Concentration Bounds toward a Unified Framework for Robust Clusteringcited by 10
  5. 2019Excess risk bounds in robust empirical risk minimizationcited by 9
  6. 2015A General Method for Robust Bayesian Modelingcited by 7
  7. 2020K-bMOM: a robust Lloyd-type clustering algorithm based on bootstrap Median-of-Meanscited by 7
  8. 2014Robust Estimation in Generalised Linear Models : The Density Power Divergence Approachcited by 5
  9. 2021Robust Principal Component Analysis: A Median of Means Approachcited by 4
  10. 2017Generalized Linear Model Regression under Distance-to-set Penaltiescited by 2
  11. 2017Dynamic quantile linear models: a Bayesian approachcited by 1

Built on by

Not cited yet.