research-article

Open access

Robustness meets algorithms

Authors:

Ilias Diakonikolas,

Daniel M. Kane,

Alistair StewartAuthors Info & Claims

Communications of the ACM, Volume 64, Issue 5

Pages 107 - 115

https://doi.org/10.1145/3453935

Published: 26 April 2021 Publication History

All formats PDF

Abstract

In every corner of machine learning and statistics, there is a need for estimators that work not just in an idealized model, but even when their assumptions are violated. Unfortunately, in high dimensions, being provably robust and being efficiently computable are often at odds with each other.

We give the first efficient algorithm for estimating the parameters of a high-dimensional Gaussian that is able to tolerate a constant fraction of corruptions that is independent of the dimension. Prior to our work, all known estimators either needed time exponential in the dimension to compute or could tolerate only an inverse-polynomial fraction of corruptions. Not only does our algorithm bridge the gap between robustness and algorithms, but also it turns out to be highly practical in a variety of settings.

References

[1]

Awasthi, P., Balcan, M.F., Long, P.M. The power of localization for efficiently learning linear separators with noise. In Proceedings of the 46^th Annual ACM Symposium on the Theory of Computing, STOC '14 (New York, NY, USA, 2014), ACM, 449--458.

Digital Library

[2]

Balakrishnan, S., Du, S.S., Li, J., Singh, A. Computationally efficient robust sparse estimation in high dimensions. In Proceedings of the 30^th Annual Conference on Learning Theory, COLT '17 (2017), 169--212.

[3]

Charikar, M., Steinhardt, J., Valiant, G. Learning from untrusted data. In Proceedings of the 49^th Annual ACM Symposium on the Theory of Computing, STOC '17 (New York, NY, USA, 2017), ACM, 47--60.

Digital Library

[4]

Diakonikolas, I., Kamath, G., Kane, D.M., Li, J., Moitra, A., Stewart, A. Robust estimators in high dimensions without the computational intractability. In Proceedings of the 57^th Annual IEEE Symposium on Foundations of Computer Science, FOCS '16 (Washington, DC, USA, 2016), IEEE Computer Society, 655--664.

[5]

Diakonikolas, I., Kamath, G., Kane, D.M., Li, J., Moitra, A., Stewart, A. Being robust (in high dimensions) can be practical. In Proceedings of the 34^th International Conference on Machine Learning, ICML '17 (2017), JMLR, Inc., 999--1008.

[6]

Diakonikolas, I., Kamath, G., Kane, D.M., Li, J., Moitra, A., Stewartz, A. Robustly learning a Gaussian: Getting optimal error, efficiently. In Proceedings of the 29^th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '18 (Philadelphia, PA, USA, 2018), SIAM.

[7]

Diakonikolas, I., Kamath, G., Kane, D.M., Li, J., Steinhardt, J., Stewart, A. Sever: A robust meta-algorithm for stochastic optimization. In Proceedings of the 36^th International Conference on Machine Learning, ICML '19 (2019), JMLR, Inc., 1596--1606.

[8]

Diakonikolas, I., Kane, D.M. Recent advances in algorithmic high-dimensional robust statistics. CoRR, abs/1911.05911, 2019.

[9]

Diakonikolas, I., Kane, D.M., Stewart, A. Statistical query lower bounds for robust estimation of high-dimensional Gaussians and Gaussian mixtures. In Proceedings of the 58^th Annual IEEE Symposium on Foundations of Computer Science, FOCS '17 (Washington, DC, USA, 2017), IEEE Computer Society, 73--84.

[10]

Diakonikolas, I., Kane, D.M., Stewart, A. List-decodable robust mean estimation and learning mixtures of spherical Gaussians. In Proceedings of the 50^th Annual ACM Symposium on the Theory of Computing, STOC '18 (New York, NY, USA, 2018), ACM, 1047--1060.

Digital Library

[11]

Fischler, M.A., Bolles, R.C. Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM 6, 24 (1981), 381--395.

[12]

Fisher, R.A. On the mathematical foundations of theoretical statistics. Phil. Trans. R. Soc. Lond. Ser. A 594--604, 222 (1922), 309--368.

[13]

Hampel, F.R., Ronchetti, E.M., Rousseeuw, P.J., Stahel, W.A. Robust Statistics: The Approach Based on Influence Functions. Wiley, Hoboken, New Jersey, 2011.

[14]

Hopkins, S.B., Li, J. Mixture models, robustness, and sum of squares proofs. In Proceedings of the 50^th Annual ACM Symposium on the Theory of Computing, STOC '18 (New York, NY, USA, 2018), ACM, Hoboken, New Jersey, 1021--1034.

Digital Library

[15]

Huber, P.J., Ronchetti, E.M. Robust Statistics. Wiley, 2009.

[16]

Johnson, D.S., Preparata, F.P. The densest hemisphere problem. Theor. Comp. Sci. 1, 6 (1978), 93--107.

[17]

Kearns, M.J., Schapire, R.E., Sellie, L.M. Towards efficient agnostic learning. Mach. Learn. 2--3, 17 (1994), 115--141.

Digital Library

[18]

Klivans, A.R., Long, P.M., Servedio, R.A. Learning halfspaces with malicious noise. J. Mach. Learn. Res., 10 (2009), 2715--2740.

Digital Library

[19]

Kothari, P., Steinhardt, J., Steurer, D. Robust moment estimation and improved clustering via sum of squares. In Proceedings of the 50^th Annual ACM Symposium on the Theory of Computing, STOC '18 (New York, NY, USA, 2018), ACM, 1035--1046.

Digital Library

[20]

Lai, K.A., Rao, A.B., Vempala, S. Agnostic estimation of mean and covariance. In Proceedings of the 57^th Annual IEEE Symposium on Foundations of Computer Science, FOCS '16 (Washington, DC, USA, 2016), IEEE Computer Society, 665--674.

[21]

Novembre, J., Johnson, T., Bryc, K., Kutalik, Z., Boyko, A.R., Auton, A., Indap, A., King, K.S., Bergmann, S., Nelson, M.R., Stephens, M., Bustamante, C.D. Genes mirror geography within Europe. Nature 7218, 456 (2008), 98--101.

[22]

Prasad, A., Suggala, A.S., Balakrishnan, S., Ravikumar, P. Robust estimation via robust gradient estimation. arXiv preprint arXiv:1802.06485 (2018).

[23]

Rousseeuw, P. Multivariate estimation with high breakdown point. Math. Statist. Appl., 8 (1985), 283--297.

[24]

Tukey, J.W. A survey of sampling from contaminated distributions. In Contributions to Probability and Statistics: Essays in Honor of Harold Hotelling, Stanford University Press, Stanford, California, 1960, 448--485.

[25]

Tukey, J.W. Mathematics and the picturing of data. In Proceedings of the International Congress of Mathematicians (1975), American Mathematical Society, 523--531.

Cited By

Zhang CSun BLing X(2024)Establishing a Digital-Driven Framework for Evaluating Digital Assets2024 10th International Conference on Big Data and Information Analytics (BigDIA)10.1109/BigDIA63733.2024.10808968(629-635)Online publication date: 25-Oct-2024
https://doi.org/10.1109/BigDIA63733.2024.10808968
Meyer AAlbarghouthi AD'Antoni L(2023)The Dataset Multiplicity Problem: How Unreliable Data Impacts PredictionsProceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency10.1145/3593013.3593988(193-204)Online publication date: 12-Jun-2023
https://dl.acm.org/doi/10.1145/3593013.3593988
Cheng YDiakonikolas IGe RGupta SKane DSoltanolkotabi MKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)Outlier-robust sparse estimation via non-convex optimizationProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3600801(7318-7327)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3600801

Index Terms

Robustness meets algorithms
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Adversarial training and robustness for multiple perturbations
NIPS'19: Proceedings of the 33rd International Conference on Neural Information Processing Systems

Defenses against adversarial examples, such as adversarial training, are typically tailored to a single perturbation type (e.g., small ℓ_∞-noise). For other perturbations, these defenses offer no guarantees and, at times, even increase the model's ...
Adversarial robustness of streaming algorithms through importance sampling
NIPS '21: Proceedings of the 35th International Conference on Neural Information Processing Systems

Robustness against adversarial attacks has recently been at the forefront of algorithmic design for machine learning tasks. In the adversarial streaming model, an adversary gives an algorithm a sequence of adaptively chosen updates u₁, ..., u_n as a data ...
Robustness between the worst and average case
NIPS '21: Proceedings of the 35th International Conference on Neural Information Processing Systems

Several recent works in machine learning have focused on evaluating the test-time robustness of a classifier: how well the classifier performs not just on the target domain it was trained upon, but upon perturbed examples. In these settings, the focus ...

Comments

Information & Contributors

Information

Published In

cover image Communications of the ACM

Communications of the ACM Volume 64, Issue 5

May 2021

112 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/3462701

Editor:
Andrew A. Chien
Association for Computing Machinery, New York, NY

Issue’s Table of Contents

Copyright © 2021 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 April 2021

Published in CACM Volume 64, Issue 5

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
17,094
Total Downloads

Downloads (Last 12 months)2,085
Downloads (Last 6 weeks)163

Reflects downloads up to 28 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang CSun BLing X(2024)Establishing a Digital-Driven Framework for Evaluating Digital Assets2024 10th International Conference on Big Data and Information Analytics (BigDIA)10.1109/BigDIA63733.2024.10808968(629-635)Online publication date: 25-Oct-2024
https://doi.org/10.1109/BigDIA63733.2024.10808968
Meyer AAlbarghouthi AD'Antoni L(2023)The Dataset Multiplicity Problem: How Unreliable Data Impacts PredictionsProceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency10.1145/3593013.3593988(193-204)Online publication date: 12-Jun-2023
https://dl.acm.org/doi/10.1145/3593013.3593988
Cheng YDiakonikolas IGe RGupta SKane DSoltanolkotabi MKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)Outlier-robust sparse estimation via non-convex optimizationProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3600801(7318-7327)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3600801

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Digital Edition

View this article in digital edition.

Digital Edition

Magazine Site

View this article on the magazine site (external)

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents