# Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Oct 2020.

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

- [Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination](https://mlsanity.com/paper/2107.02237/) (2021)
- [A Model Selection Approach for Corruption Robust Reinforcement Learning](https://mlsanity.com/paper/2110.03580/) (2021)
- [A New Approach to Learning Linear Dynamical Systems](https://mlsanity.com/paper/2301.09519/) (2023)
- [Learning GMMs with Nearly Optimal Robustness Guarantees](https://mlsanity.com/paper/2104.09665/) (2021)
- [Minimax Rates for Robust Community Detection](https://mlsanity.com/paper/2207.11903/) (2022)
- [Split Conformal Prediction under Data Contamination](https://mlsanity.com/paper/2407.07700/) (2024)
- [ReLU Regression with Massart Noise](https://mlsanity.com/paper/2109.04623/) (2021)
- [Insufficient Statistics Perturbation: Stable Estimators for Private Least Squares](https://mlsanity.com/paper/2404.15409/) (2024)
- [Kalman Filtering with Adversarial Corruptions](https://mlsanity.com/paper/2111.06395/) (2021)
- [Trimmed Maximum Likelihood Estimation for Robust Learning in Generalized Linear Models](https://mlsanity.com/paper/2206.04777/) (2022)
- [On Private and Robust Bandits](https://mlsanity.com/paper/2302.02526/) (2023)
- [Outlier-Robust Gromov-Wasserstein for Graph Data](https://mlsanity.com/paper/2302.04610/) (2023)
- [A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise](https://mlsanity.com/paper/2501.09691/) (2025)
- [SQ Lower Bounds for Learning Single Neurons with Massart Noise](https://mlsanity.com/paper/2210.09949/) (2022)
- [Robust Online Convex Optimization in the Presence of Outliers](https://mlsanity.com/paper/2107.01881/) (2021)
- [Robust estimation algorithms don't need to know the corruption level](https://mlsanity.com/paper/2202.05453/) (2022)
- [Corruption-Robust Offline Two-Player Zero-Sum Markov Games](https://mlsanity.com/paper/2403.07933/) (2024)
- [Testing Noise Assumptions of Learning Algorithms](https://mlsanity.com/paper/2501.09189/) (2025)
- [Online Robust Mean Estimation](https://mlsanity.com/paper/2310.15932/) (2023)
- [Non-Stationary Latent Auto-Regressive Bandits](https://mlsanity.com/paper/2402.03110/) (2024)
- [Robust Voting Rules from Algorithmic Robust Statistics](https://mlsanity.com/paper/2112.06380/) (2021)
- [Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions](https://mlsanity.com/paper/2309.11657/) (2023)
- [A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval](https://mlsanity.com/paper/2409.04733/) (2024)
- [Computation-Utility-Privacy Tradeoffs in Bayesian Estimation](https://mlsanity.com/paper/2603.18254/) (2026)
- [Robust and differentially private stochastic linear bandits](https://mlsanity.com/paper/2304.11741/) (2023)
- [LEARN: An Invex Loss for Outlier Oblivious Robust Online Optimization](https://mlsanity.com/paper/2408.06297/) (2024)

## Abstract (arXiv)

In this work we revisit two classic high-dimensional online learning problems, namely linear regression and contextual bandits, from the perspective of adversarial robustness. Existing works in algorithmic robust statistics make strong distributional assumptions that ensure that the input data is evenly spread out or comes from a nice generative model. Is it possible to achieve strong robustness guarantees even without distributional assumptions altogether, where the sequence of tasks we are asked to solve is adaptively and adversarially chosen? We answer this question in the affirmative for both linear regression and contextual bandits. In fact our algorithms succeed where conventional methods fail. In particular we show strong lower bounds against Huber regression and more generally any convex M-estimator. Our approach is based on a novel alternating minimization scheme that interleaves ordinary least-squares with a simple convex program that finds the optimal reweighting of the distribution under a spectral constraint. Our results obtain essentially optimal dependence on the contamination level η, reach the optimal breakdown point, and naturally apply to infinite dimensional settings where the feature vectors are represented implicitly via a kernel map.