# Online Robust Mean Estimation

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 45 references that are in the map.
- First posted on arXiv 24 Oct 2023.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Robust Aggregation for Federated Learning](https://mlsanity.com/paper/1912.13445/) (2019)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [RSA: Byzantine-Robust Stochastic Aggregation Methods for Distributed Learning from Heterogeneous Datasets](https://mlsanity.com/paper/1811.03761/) (2018)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [Better Algorithms for Stochastic Bandits with Adversarial Corruptions](https://mlsanity.com/paper/1902.08647/) (2019)
- [CRFL: Certifiably Robust Federated Learning against Backdoor Attacks](https://mlsanity.com/paper/2106.08283/) (2021)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [Robust Estimation via Robust Gradient Estimation](https://mlsanity.com/paper/1802.06485/) (2018)
- [Efficient Algorithms and Lower Bounds for Robust Linear Regression](https://mlsanity.com/paper/1806.00040/) (2018)
- [Efficient Algorithms for Outlier-Robust Regression](https://mlsanity.com/paper/1803.03241/) (2018)
- [List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians](https://mlsanity.com/paper/1711.07211/) (2017)
- [Stochastic Linear Bandits Robust to Adversarial Attacks](https://mlsanity.com/paper/2007.03285/) (2020)
- [Robust Linear Regression: Optimal Rates in Polynomial Time](https://mlsanity.com/paper/2007.01394/) (2020)
- [Settling the Robust Learnability of Mixtures of Gaussians](https://mlsanity.com/paper/2011.03622/) (2020)
- [Robustly Learning any Clusterable Mixture of Gaussians](https://mlsanity.com/paper/2005.06417/) (2020)
- [Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination](https://mlsanity.com/paper/2010.04157/) (2020)
- [Best Arm Identification for Contaminated Bandits](https://mlsanity.com/paper/1802.09514/) (2018)
- [Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation](https://mlsanity.com/paper/2106.08537/) (2021)
- [Outlier-Robust Clustering of Non-Spherical Mixtures](https://mlsanity.com/paper/2005.02970/) (2020)
- [Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination](https://mlsanity.com/paper/2111.07458/) (2021)
- [Robust Online and Distributed Mean Estimation Under Adversarial Data Corruption](https://mlsanity.com/paper/2209.09624/) (2022)

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

- [Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate](https://mlsanity.com/paper/2410.01186/) (2024)
- [Revisiting Active Sequential Prediction-Powered Mean Estimation](https://mlsanity.com/paper/2604.18569/) (2026)
- [LARP: Learner-Agnostic Robust Data Prefiltering](https://mlsanity.com/paper/2506.20573/) (2025)

## Abstract (arXiv)

We study the problem of high-dimensional robust mean estimation in an online setting. Specifically, we consider a scenario where n sensors are measuring some common, ongoing phenomenon. At each time step t=1,2,ldots,T, the ith sensor reports its readings x(i)t for that time step. The algorithm must then commit to its estimate μt for the true mean value of the process at time t. We assume that most of the sensors observe independent samples from some common distribution X, but an ε-fraction of them may instead behave maliciously. The algorithm wishes to compute a good approximation μ to the true mean μ^ast := E[X]. We note that if the algorithm is allowed to wait until time T to report its estimate, this reduces to the well-studied problem of robust mean estimation. However, the requirement that our algorithm produces partial estimates as the data is coming in substantially complicates the situation. We prove two main results about online robust mean estimation in this model. First, if the uncorrupted samples satisfy the standard condition of (ε,δ)-stability, we give an efficient online algorithm that outputs estimates μt, t ∈ [T], such that with high probability it holds that |μ-μ^ast|2 = O(δ log(T)), where μ = (μt)t ∈ [T]. We note that this error bound is nearly competitive with the best offline algorithms, which would achieve ℓ2-error of O(δ). Our second main result shows that with additional assumptions on the input (most notably that X is a product distribution) there are inefficient algorithms whose error does not depend on T at all.