Near-optimal algorithms for gaussians with huber contamination: mean estimation and linear regression
Article No.: 1879, Pages 43384 - 43422
Abstract
We study the fundamental problems of Gaussian mean estimation and linear regression with Gaussian covariates in the presence of Huber contamination. Our main contribution is the design of the first sample near-optimal and almost linear-time algorithms with optimal error guarantees for both these problems. Specifically, for Gaussian robust mean estimation on ℝd with contamination parameter ε ∈ (0, ε0) for a small absolute constant εo, we give an algorithm with sample complexity n = Õ(d/ε2) and almost linear runtime that approximates the target mean within ℓ2-error O(ε). This improves on prior work that achieved this error guarantee with polynomially suboptimal sample and time complexity. For robust linear regression, we give the first algorithm with sample complexity n = Õ(d/ε2) and almost linear runtime that approximates the target regressor within ℓ2-error O(ε). This is the first polynomial sample and time algorithm achieving the optimal error guarantee, answering an open question in the literature. At the technical level, we develop a methodology that yields almost-linear time algorithms for multi-directional filtering that may be of broader interest.
References
[1]
D. F. Andrews, P. J. Bickel, F. R. Hampel, P. J. Huber, W. H. Rogers, and J. W. Tukey. Robust Estimates of Location: Survey and Advances. Princeton, NJ, USA: Princeton University Press, 1972.
[2]
M. Brennan, G. Bresler, S. B. Hopkins, J. Li, and T.Schramm. "Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent". In: CoRR abs/2009.06107 (2020).
[3]
S. Balakrishnan, S. S. Du, J. Li, and A. Singh. "Computationally Efficient Robust Sparse Estimation in High Dimensions". In: Proc. 30th Annual Conference on Learning Theory (COLT). Vol. 65. 2017, pp. 1-44.
[4]
D. S. Bernstein. Scalar, Vector, and Matrix Mathematics: Theory, Facts, and Formulas. Revised and expanded edition. Princeton: Princeton University Press, 2018.
[5]
R. Bhatia. Matrix analysis. Vol. 169. Springer Science & Business Media, 2013.
[6]
S. Boucheron, G. Lugosi, and P. Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013.
[7]
A. Bakshi and A. Prasad. "Robust Linear Regression: Optimal Rates in Polynomial Time". In: Proc. 53rd Annual ACM Symposium on Theory of Computing (STOC). ACM Press, 2021, pp. 102-115.
[8]
Y. Cherapanamjeri, E. Aras, N. Tripuraneni, M. I. Jordan, N. Flammarion, and P. L. Bartlett. "Optimal Robust Linear Regression in Nearly Linear Time". In: abs/2007.08137 (2020).
[9]
Y. Cheng, I. Diakonikolas, and R. Ge. "High-Dimensional Robust Mean Estimation in Nearly-Linear Time". In: Proc. 30th Annual Symposium on Discrete Algorithms (SODA). SIAM, 2019, pp. 2755-2771.
[10]
Y. Cheng, I. Diakonikolas, R. Ge, and M. Soltanolkotabi. "High-Dimensional Robust Mean Estimation via Gradient Descent". In: Proc. 37th International Conference on Machine Learning (ICML). 2020.
[11]
Y. Cheng, I. Diakonikolas, R. Ge, and D. P. Woodruff. "Faster Algorithms for High-Dimensional Robust Covariance Estimation". In: Proc. 32nd Annual Conference on Learning Theory (COLT). 2019.
[12]
Y. Cheng, I. Diakonikolas, D. M. Kane, R. Ge, S. Gupta, and M. Soltanolkotabi. "Outlier-Robust Sparse Estimation via Non-Convex Optimization". In: Advances in Neural Information Processing Systems 35 (NeurIPS). 2022.
[13]
Y. Cherapanamjeri, N. Flammarion, and P. L. Bartlett. "Fast Mean Estimation with Sub-Gaussian Rates". In: Proc. 32nd Annual Conference on Learning Theory (COLT). 2019.
[14]
M. Chen, C. Gao, and Z. Ren. "A General Decision Theory for Huber's $\epsilon$-Contamination Model". In: Electronic Journal of Statistics 10.2 (2016), pp. 37523774.
[15]
M. Chen, C. Gao, and Z. Ren. "Robust Covariance and Scatter Matrix Estimation under Huber's Contamination Model". In: The Annals of Statistics 46 (2018), pp. 1932-1960.
[16]
Y. Cherapanamjeri, S. Mohanty, and M. Yau. "List decodable mean estimation in nearly linear time". In: Proc. 61st IEEE Symposium on Foundations of Computer Science (FOCS). 2020.
[17]
Y. Cherapanamjeri, N. Tripuraneni, P. L. Bartlett, and M. I. Jordan. "Optimal Mean Estimation without a Variance". In: Proc. 35th Annual Conference on Learning Theory (COLT). 2022.
[18]
J. Depersin. "A Spectral Algorithm for Robust Regression with Subgaussian Rates". In: CoRR abs/2007.06072 (2020).
[19]
Y. Dong, S. B. Hopkins, and J. Li. "Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection". In: Advances in Neural Information Processing Systems 32 (NeurIPS). 2019.
[20]
I. Diakonikolas and D. M. Kane. "Recent Advances in Algorithmic High-Dimensional Robust Statistics". In: CoRR abs/1911.05911 (2019).
[21]
I. Diakonikolas and D. M. Kane. Algorithmic High-Dimensional Robust Statistics. https://sites.google.com/view/ars-book/. Cambridge University Press, 2023.
[22]
I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart. "Robust Estimators in High Dimensions without the Computational Intractability". In: Proc. 57th IEEE Symposium on Foundations of Computer Science (FOCS). 2016, pp. 655-664.
[23]
I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart. "Being Robust (in High Dimensions) Can Be Practical". In: Proceedings of the 34th International Conference on Machine Learning, ICML 2017. 2017, pp. 999-1008.
[24]
I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart. "Robustly Learning a Gaussian: Getting Optimal Error, Efficiently". In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. Full version available at https://arxiv.org/abs/1704.03866. 2018, pp. 2683-2702.
[25]
I. Diakonikolas, G. Kamath, D. Kane, J. Li, J. Steinhardt, and A. Stewart. "Sever: A Robust Meta-Algorithm for Stochastic Optimization". In: Proceedings of the 36th International Conference on Machine Learning, ICML 2019. 2019, pp. 1596-1606.
[26]
I. Diakonikolas, D. M. Kane, D. Kongsgaard, J. Li, and K. Tian. "List-decodable mean estimation in nearly-pca time". In: Advances in Neural Information Processing Systems 34 (NeurIPS). Vol. 34. 2021.
[27]
I. Diakonikolas, D. M. Kane, D. Kongsgaard, J. Li, and K. Tian. "Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation". In: Proc. 54th Annual ACM Symposium on Theory of Computing (STOC). 2022.
[28]
I. Diakonikolas, D. M. Kane, S. Karmalkar, A. Pensia, and T. Pittas. "Robust Sparse Mean Estimation via Sum of Squares". In: Proc. 35th Annual Conference on Learning Theory (COLT). 2022.
[29]
I. Diakonikolas, D. M. Kane, S. Karmalkar, E. Price, and A. Stewart. "Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering". In: Advances in Neural Information Processing Systems 32 (NeurIPS). 2019.
[30]
I. Diakonikolas, D. M. Kane, J. C. H. Lee, and A. Pensia. "Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions". In: Advances in Neural Information Processing Systems 35 (NeurIPS). 2022.
[31]
I. Diakonikolas, D. M. Kane, and A. Pensia. "Outlier Robust Mean Estimation with Subgaussian Rates via Stability". In: Advances in Neural Information Processing Systems 33 (NeurIPS). 2020.
[32]
I. Diakonikolas, D. M. Kane, A. Pensia, and T. Pittas. "Streaming algorithms for high-dimensional robust statistics". In: International Conference on Machine Learning. PMLR. 2022, pp. 5061-5117.
[33]
I. Diakonikolas, D. M. Kane, A. Pensia, and T. Pittas. "Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA". In: Proc. 40th International Conference on Machine Learning (ICML). 2023.
[34]
I. Diakonikolas, D. M. Kane, and A. Stewart. "Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures". In: 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017. Full version at http://arxiv.org/abs/1611.03473. 2017, pp. 73-84.
[35]
I. Diakonikolas, W. Kong, and A. Stewart. "Efficient Algorithms and Lower Bounds for Robust Linear Regression". In: Proc. 30th Annual Symposium on Discrete Algorithms (SODA). 2019.
[36]
J. Depersin and G. Lecué. "Robust Sub-Gaussian Estimation of a Mean Vector in Nearly Linear Time". In: The Annals of Statistics 50.1 (Feb. 2022), pp. 511-536.
[37]
A. S. Dalalyan and A. Minasyan. "All-In-One Robust Estimator of the Gaussian Mean". In: The Annals of Statistics 50 (2022).
[38]
S. B. Hopkins, J. Li, and F. Zhang. "Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization". In: Advances in Neural Information Processing Systems 33 (NeurIPS). 2020.
[39]
P. J. Huber and E. M. Ronchetti. Robust Statistics. John Wiley & Sons, 2009. L. Hu and O. Reingold. "Robust Mean Estimation on Highly Incomplete Data with Arbitrary Outliers". In: Proc. 24th International Conference on Artificial Intelligence and Statistics (AISTATS). 2021.
[40]
P. J. Huber. "Robust Estimation of a Location Parameter". In: The Annals of Mathematical Statistics 35.1 (Mar. 1964), pp. 73-101.
[41]
A. Jambulapati, J. Li, and K. Tian. "Robust sub-gaussian principal component analysis and width-independent schatten packing". In: Advances in Neural Information Processing Systems 33 (NeurIPS) (2020). arxiv preprint at https://arxiv.org/abs/2006.06980.
[42]
A. Klivans, P. K. Kothari, and R. Meka. "Efficient Algorithms for Outlier-Robust Regression". In: Proc. 31st Annual Conference on Learning Theory (COLT). 2018. W. Kong, R. Somani, S. Kakade, and S. Oh. "Robust Meta-learning for Mixed Linear Regression with Small Batches". In: Advances in Neural Information Processing Systems 33 (NeurIPS). 2020.
[43]
P. K. Kothari, J. Steinhardt, and D. Steurer. "Robust Moment Estimation and Improved Clustering via Sum of Squares". In: Proc. 50th Annual ACM Symposium on Theory of Computing (STOC). ACM Press, 2018, pp. 1035-1046.
[44]
Z. Lei, K. Luh, P. Venkat, and F. Zhang. "A Fast Spectral Algorithm for Mean Estimation with Sub-Gaussian Rates". In: Proc. 33rd Annual Conference on Learning Theory (COLT). 2020.
[45]
G. Lugosi and S. Mendelson. "Robust Multivariate Mean Estimation: The Optimality of Trimmed Mean". In: The Annals of Statistics 49.1 (2021), pp. 393-410.
[46]
K. A. Lai, A. B. Rao, and S. Vempala. "Agnostic Estimation of Mean and Covariance". In: Proceedings of FOCS'16. 2016.
[47]
J. Li and G. Ye. "Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time". In: Advances in Neural Information Processing Systems 33 (NeurIPS). 2020.
[48]
C. Musco and C. Musco. "Randomized block krylov methods for stronger and faster approximate singular value decomposition". In: Advances in neural information processing systems 28 (2015).
[49]
A. Prasad, S. Balakrishnan, and P. Ravikumar. "A Unified Approach to Robust Mean Estimation". In: CoRR abs/1907.00927 (July 2019).
[50]
A. Pensia, V. Jog, and P. Loh. "Robust Regression with Covariate Filtering: Heavy Tails and Adversarial Contamination". In: CoRR abs/2009.12976 (Sept. 2020).
[51]
J. W. Tukey. "A survey of sampling from contaminated distributions". In: Contributions to probability and statistics 2 (1960), pp. 448-485.
[52]
R. Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press, 2018.
[53]
M. J. Wainwright. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press, 2019.
[54]
H. Xu, C. Caramanis, and S. Mannor. "Outlier-Robust PCA: The High-Dimensional Case". In: IEEE Transactions on Information Theory 59.1 (2013), pp. 546-572.
[55]
B. Zhu, J. Jiao, and J. Steinhardt. "Robust Estimation via Generalized Quasi-Gradients". In: Information and Inference: A Journal of the IMA 11.2 (2022), pp. 581-636.
Recommendations
Robust sparse estimation for gaussians with optimal error under huber contamination
ICML'24: Proceedings of the 41st International Conference on Machine LearningWe study Gaussian sparse estimation tasks in Huber's contamination model with a focus on mean estimation, PCA, and linear regression. For each of these tasks, we give the first sample and computationally efficient robust estimators with optimal error ...
Near-optimal algorithms for unique games
STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of ComputingUnique games are constraint satisfaction problems that can be viewed as a generalization of Max-Cut to a larger domain size. The Unique Games Conjecture states that it is hard to distinguish between instances of unique games where almost all constraints ...
A Variant of Huber Robust Regression
In this paper, we develop a variant of Huber robust regression. Our approach is inspired by Huber's M estimates; however, we deal with the scale estimate differently. The class of estimators we develop includes least squares and least absolute residuals ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2023 Neural Information Processing Systems Foundation, Inc.
Publisher
Curran Associates Inc.
Red Hook, NY, United States
Publication History
Published: 10 December 2023
Qualifiers
- Research-article
- Research
- Refereed limited
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Jan 2025