# Regularization, sparse recovery, and median-of-means tournaments

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jan 2017.

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

- [On Empirical Risk Minimization with Dependent and Heavy-Tailed Data](https://mlsanity.com/paper/2109.02224/) (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)
- [Byzantine-Robust Federated Linear Bandits](https://mlsanity.com/paper/2204.01155/) (2022)
- [Robust Methods for High-Dimensional Linear Learning](https://mlsanity.com/paper/2208.05447/) (2022)
- [Robust Principal Component Analysis: A Median of Means Approach](https://mlsanity.com/paper/2102.03403/) (2021)
- [Computationally Efficient and Statistically Optimal Robust High-Dimensional Linear Regression](https://mlsanity.com/paper/2305.06199/) (2023)
- [DeepMoM: Robust Deep Learning With Median-of-Means](https://mlsanity.com/paper/2105.14035/) (2021)
- [Robust empirical risk minimization via Newton's method](https://mlsanity.com/paper/2301.13192/) (2023)
- [Robust Linear Predictions: Analyses of Uniform Concentration, Fast Rates and Model Misspecification](https://mlsanity.com/paper/2201.01973/) (2022)
- [Convex Clustering Redefined: Robust Learning with the Median of Means Estimator](https://mlsanity.com/paper/2511.14784/) (2025)

## Abstract (arXiv)

A regularized risk minimization procedure for regression function estimation is introduced that achieves near optimal accuracy and confidence under general conditions, including heavy-tailed predictor and response variables. The procedure is based on median-of-means tournaments, introduced by the authors in [8]. It is shown that the new procedure outperforms standard regularized empirical risk minimization procedures such as lasso or slope in heavy-tailed problems.