Online Robust Mean Estimation
Not on the map. Why?
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.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 25 of its 45 references that are in the map. First posted on arXiv 24 Oct 2023.
Builds on
25 of 45 references.
References · 25
- 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
- 2019Advances and Open Problems in Federated Learningcited by 3,021
- 2019Robust Aggregation for Federated Learningcited by 314
- 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
- 2018RSA: Byzantine-Robust Stochastic Aggregation Methods for Distributed Learning from Heterogeneous Datasetscited by 148
- 2016Agnostic Estimation of Mean and Covariancecited by 131
- 2018Sever: A Robust Meta-Algorithm for Stochastic Optimizationcited by 123
- 2018Stochastic bandits robust to adversarial corruptionscited by 118
- 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 91
- 2021CRFL: Certifiably Robust Federated Learning against Backdoor Attackscited by 91
- 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
- 2018Robust Estimation via Robust Gradient Estimationcited by 76
13 more
- 2018Efficient Algorithms and Lower Bounds for Robust Linear Regressioncited by 76
- 2018Efficient Algorithms for Outlier-Robust Regressioncited by 72
- 2017List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussianscited by 70
- 2020Stochastic Linear Bandits Robust to Adversarial Attackscited by 65
- 2020Robust Linear Regression: Optimal Rates in Polynomial Timecited by 42
- 2020Settling the Robust Learnability of Mixtures of Gaussianscited by 32
- 2020Robustly Learning any Clusterable Mixture of Gaussianscited by 28
- 2020Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contaminationcited by 26
- 2018Best Arm Identification for Contaminated Banditscited by 23
- 2021Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimationcited by 21
- 2020Outlier-Robust Clustering of Non-Spherical Mixturescited by 19
- 2021Mean-based Best Arm Identification in Stochastic Bandits under Reward Contaminationcited by 6
- 2022Robust Online and Distributed Mean Estimation Under Adversarial Data Corruptioncited by 5
Built on by
Citing papers per year: 2024: 1; 2025: 1; 2026: 1.
3 papers.