{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,19]],"date-time":"2026-08-19T17:20:41Z","timestamp":1787160041183,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":59,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451001","type":"proceedings-article","created":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T21:26:13Z","timestamp":1623792373000},"page":"102-115","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["Robust linear regression: optimal rates in polynomial time"],"prefix":"10.1145","author":[{"given":"Ainesh","family":"Bakshi","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adarsh","family":"Prasad","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"List-Decodable Subspace Recovery via Sum-of-Squares. arXiv preprint arXiv:2002.05139","author":"Bakshi Ainesh","year":"2020","unstructured":"Ainesh Bakshi and Pravesh Kothari. 2020. List-Decodable Subspace Recovery via Sum-of-Squares. arXiv preprint arXiv:2002.05139, 2020."},{"key":"e_1_3_2_1_2_1","volume-title":"Outlier-Robust Clustering of Non-Spherical Mixtures. arXiv preprint arXiv:2005.02970","author":"Bakshi Ainesh","year":"2020","unstructured":"Ainesh Bakshi and Pravesh Kothari. 2020. Outlier-Robust Clustering of Non-Spherical Mixtures. arXiv preprint arXiv:2005.02970, 2020."},{"key":"e_1_3_2_1_3_1","unstructured":"Boaz Barak. [n.d.]. Proofs beliefs and algorithms through the lens of sum-of-squares. [n.\\tmspace +\\thinmuskip .1667emd.]."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Boaz Barak Jonathan A. Kelner and David Steurer. 2015. Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method. In STOC. ACM. Pages 143\u2013151.","DOI":"10.1145\/2746539.2746605"},{"key":"e_1_3_2_1_5_1","unstructured":"Kush Bhatia Prateek Jain Parameswaran Kamalaruban and Purushottam Kar. 2017. Consistent robust regression. In Advances in Neural Information Processing Systems. Pages 2110\u20132119."},{"key":"e_1_3_2_1_6_1","unstructured":"Kush Bhatia Prateek Jain and Purushottam Kar. 2015. Robust regression via hard thresholding. In Advances in Neural Information Processing Systems. Pages 721\u2013729."},{"key":"e_1_3_2_1_7_1","first-page":"1","article-title":"Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere","volume":"31","author":"Bhattiprolu Vijay V. S. P.","year":"2017","unstructured":"Vijay V. S. P. Bhattiprolu, Venkatesan Guruswami, and Euiwoong Lee. 2017. Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere. In APPROX-RANDOM. LIPIcs. 81, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. Pages 31:1\u201331:20.","journal-title":"APPROX-RANDOM. LIPIcs. 81, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. Pages"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Moses Charikar Jacob Steinhardt and Gregory Valiant. 2017. Learning from untrusted data. In STOC. ACM. Pages 47\u201360.","DOI":"10.1145\/3055399.3055491"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.171"},{"key":"e_1_3_2_1_10_1","first-page":"757","volume-title":"Faster Algorithms for High-Dimensional Robust Covariance Estimation. In Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA. Proceedings of Machine Learning Research. 99","author":"Cheng Yu","year":"2019","unstructured":"Yu Cheng, Ilias Diakonikolas, Rong Ge, David P. Woodruff, Alina Beygelzimer, and Daniel Hsu. 2019. Faster Algorithms for High-Dimensional Robust Covariance Estimation. In Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA. Proceedings of Machine Learning Research. 99, PMLR. Pages 727\u2013757. http:\/\/proceedings.mlr.press\/v99\/cheng19a.html"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384329"},{"key":"e_1_3_2_1_12_1","volume-title":"List Decodable Mean Estimation in Nearly Linear Time. arXiv preprint arXiv:2005.09796","author":"Cherapanamjeri Yeshwanth","year":"2020","unstructured":"Yeshwanth Cherapanamjeri, Sidhanth Mohanty, and Morris Yau. 2020. List Decodable Mean Estimation in Nearly Linear Time. arXiv preprint arXiv:2005.09796, 2020."},{"key":"e_1_3_2_1_13_1","volume-title":"Robustly Learning any Clusterable Mixture of Gaussians. arXiv preprint arXiv:2005.06417","author":"Diakonikolas Ilias","year":"2020","unstructured":"Ilias Diakonikolas, Samuel B Hopkins, Daniel Kane, and Sushrut Karmalkar. 2020. Robustly Learning any Clusterable Mixture of Gaussians. arXiv preprint arXiv:2005.06417, 2020."},{"key":"e_1_3_2_1_14_1","first-page":"1606","volume-title":"Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA. Proceedings of Machine Learning Research. 97","author":"Diakonikolas Ilias","year":"2019","unstructured":"Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Jacob Steinhardt, Alistair Stewart, Kamalika Chaudhuri, and Ruslan Salakhutdinov. 2019. Sever: A Robust Meta-Algorithm for Stochastic Optimization. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA. Proceedings of Machine Learning Research. 97, PMLR. Pages 1596\u20131606. http:\/\/proceedings.mlr.press\/v97\/diakonikolas19a.html"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.85"},{"key":"e_1_3_2_1_16_1","first-page":"1008","volume-title":"Proceedings of Machine Learning Research. 70","author":"Diakonikolas Ilias","year":"2017","unstructured":"Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. 2017. Being Robust (in High Dimensions) Can Be Practical. In ICML. Proceedings of Machine Learning Research. 70, PMLR. Pages 999\u20131008."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.171"},{"key":"e_1_3_2_1_18_1","volume-title":"Sever: A Robust Meta-Algorithm for Stochastic Optimization. arXiv preprint arXiv:1803.02815","author":"Diakonikolas Ilias","year":"2018","unstructured":"Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Jacob Steinhardt, and Alistair Stewart. 2018. Sever: A Robust Meta-Algorithm for Stochastic Optimization. arXiv preprint arXiv:1803.02815, 2018."},{"key":"e_1_3_2_1_19_1","volume-title":"Recent Advances in Algorithmic High-Dimensional Robust Statistics. arXiv preprint arXiv:1911.05911","author":"Diakonikolas Ilias","year":"2019","unstructured":"Ilias Diakonikolas and Daniel M Kane. 2019. Recent Advances in Algorithmic High-Dimensional Robust Statistics. arXiv preprint arXiv:1911.05911, 2019."},{"key":"e_1_3_2_1_20_1","volume-title":"Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures","author":"Diakonikolas Ilias","unstructured":"Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. 2017. Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures. In FOCS. IEEE Computer Society. Pages 73\u201384."},{"key":"e_1_3_2_1_21_1","volume-title":"Efficient algorithms and lower bounds for robust linear regression. arXiv preprint arXiv:1806.00040","author":"Diakonikolas Ilias","year":"2018","unstructured":"Ilias Diakonikolas, Weihao Kong, and Alistair Stewart. 2018. Efficient algorithms and lower bounds for robust linear regression. arXiv preprint arXiv:1806.00040, 2018."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.170"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Noah Fleming Pravesh Kothari and Toniann Pitassi. 2019. Semialgebraic Proofs and Efficient Algorithm Design.. now the essence of knowledge.","DOI":"10.1561\/9781680836370"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"e_1_3_2_1_25_1","volume-title":"Sub-Gaussian Mean Estimation in Polynomial Time. arXiv preprint arXiv:1809.07425","author":"Hopkins Samuel B","year":"2018","unstructured":"Samuel B Hopkins. 2018. Sub-Gaussian Mean Estimation in Polynomial Time. arXiv preprint arXiv:1809.07425, 2018."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188748"},{"key":"e_1_3_2_1_27_1","volume-title":"Conference on Learning Theory. Pages 1683\u20131722","author":"Hopkins Samuel B","year":"2019","unstructured":"Samuel B Hopkins, Tselil Schramm, and Jonathan Shi. 2019. A Robust Spectral Algorithm for Overcomplete Tensor Decomposition. In Conference on Learning Theory. Pages 1683\u20131722."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177703732"},{"key":"e_1_3_2_1_29_1","volume-title":"International Encyclopedia of Statistical Science","author":"Huber Peter J","unstructured":"Peter J Huber. 2011. Robust statistics. In International Encyclopedia of Statistical Science. Springer. Pages 1248\u20131251."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177692377"},{"key":"e_1_3_2_1_31_1","unstructured":"Sushrut Karmalkar Adam Klivans and Pravesh Kothari. 2019. List-decodable linear regression. In Advances in Neural Information Processing Systems. Pages 7423\u20137432."},{"key":"e_1_3_2_1_32_1","volume-title":"Efficient Algorithms for Outlier-Robust Regression. arXiv preprint arXiv:1803.03241","author":"Klivans Adam","year":"2018","unstructured":"Adam Klivans, Pravesh K Kothari, and Raghu Meka. 2018. Efficient Algorithms for Outlier-Robust Regression. arXiv preprint arXiv:1803.03241, 2018."},{"key":"e_1_3_2_1_33_1","first-page":"1430","volume-title":"Efficient Algorithms for Outlier-Robust Regression. In Conference On Learning Theory, COLT 2018","author":"Klivans Adam R.","year":"2018","unstructured":"Adam R. Klivans, Pravesh K. Kothari, and Raghu Meka. 2018. Efficient Algorithms for Outlier-Robust Regression. In Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018. Pages 1420\u20131430. http:\/\/proceedings.mlr.press\/v75\/klivans18a.html"},{"key":"e_1_3_2_1_34_1","volume-title":"Kothari and Jacob Steinhardt","author":"Pravesh","year":"2017","unstructured":"Pravesh K. Kothari and Jacob Steinhardt. 2017. Better Agnostic Clustering via Relaxed Tensor Norms. 2017."},{"key":"e_1_3_2_1_35_1","volume-title":"Kothari and David Steurer","author":"Pravesh","year":"2017","unstructured":"Pravesh K. Kothari and David Steurer. 2017. Outlier-robust moment-estimation via sum-of-squares. CoRR, abs\/1711.11581, 2017. arxiv:1711.11581"},{"key":"e_1_3_2_1_36_1","volume-title":"Outlier-robust moment-estimation via sum-of-squares. arXiv preprint arXiv:1711.11581","author":"Kothari Pravesh K","year":"2017","unstructured":"Pravesh K Kothari and David Steurer. 2017. Outlier-robust moment-estimation via sum-of-squares. arXiv preprint arXiv:1711.11581, 2017."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.76"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0279-7_18"},{"key":"e_1_3_2_1_39_1","unstructured":"Jerry Zheng Li. 2018. Principled approaches to robust machine learning and beyond."},{"key":"e_1_3_2_1_40_1","volume-title":"Polynomial-Time Tensor Decompositions with Sum-of-Squares","author":"Ma Tengyu","unstructured":"Tengyu Ma, Jonathan Shi, and David Steurer. 2016. Polynomial-Time Tensor Decompositions with Sum-of-Squares. In FOCS. IEEE Computer Society. Pages 438\u2013446."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3216-0_17"},{"key":"e_1_3_2_1_42_1","unstructured":"Pablo A Parrilo. 2000. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1111\/rssb.12364"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Prasad Raghavendra Satish Rao and Tselil Schramm. 2017. Strongly refuting random CSPs below the spectral threshold. In STOC. ACM. Pages 121\u2013131.","DOI":"10.1145\/3055399.3055417"},{"key":"e_1_3_2_1_45_1","volume-title":"High-dimensional estimation via sum-of-squares proofs. arXiv preprint arXiv:1807.11419, 6","author":"Raghavendra Prasad","year":"2018","unstructured":"Prasad Raghavendra, Tselil Schramm, and David Steurer. 2018. High-dimensional estimation via sum-of-squares proofs. arXiv preprint arXiv:1807.11419, 6, 2018."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.10"},{"key":"e_1_3_2_1_47_1","unstructured":"Prasad Raghavendra and Morris Yau. 2020. List Decodable Subspace Recovery."},{"key":"e_1_3_2_1_48_1","volume-title":"Robust and nonlinear time series analysis","author":"Rousseeuw Peter","unstructured":"Peter Rousseeuw and Victor Yohai. 1984. Robust regression by means of S-estimators. In Robust and nonlinear time series analysis. Springer. Pages 256\u2013272."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1984.10477105"},{"key":"e_1_3_2_1_50_1","first-page":"1793","volume-title":"COLT. Proceedings of Machine Learning Research. 65","author":"Schramm Tselil","year":"2017","unstructured":"Tselil Schramm and David Steurer. 2017. Fast and robust tensor decomposition with applications to dictionary learning. In COLT. Proceedings of Machine Learning Research. 65, PMLR. Pages 1760\u20131793."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1968.10480934"},{"key":"e_1_3_2_1_52_1","first-page":"1987","article-title":"Quadratic optimization problems","volume":"1","author":"Shor N. Z.","year":"1987","unstructured":"N. Z. Shor. 1987. Quadratic optimization problems. Izv. Akad. Nauk SSSR Tekhn. Kibernet., 1, 1987. Pages 128\u2013139, 222. issn:0002-3388","journal-title":"Izv. Akad. Nauk SSSR Tekhn. Kibernet."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/AAI28115249"},{"key":"e_1_3_2_1_54_1","volume-title":"Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers. CoRR, abs\/1703.04940","author":"Steinhardt Jacob","year":"2017","unstructured":"Jacob Steinhardt, Moses Charikar, and Gregory Valiant. 2017. Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers. CoRR, abs\/1703.04940, 2017."},{"key":"e_1_3_2_1_55_1","volume-title":"Adaptive hard thresholding for near-optimal consistent robust regression. arXiv preprint arXiv:1903.08192","author":"Suggala Arun Sai","year":"2019","unstructured":"Arun Sai Suggala, Kush Bhatia, Pradeep Ravikumar, and Prateek Jain. 2019. Adaptive hard thresholding for near-optimal consistent robust regression. arXiv preprint arXiv:1903.08192, 2019."},{"key":"e_1_3_2_1_56_1","volume-title":"Henri Theil\u2019s contributions to economics and econometrics","author":"Theil Henri","unstructured":"Henri Theil. 1992. A rank-invariant method of linear and polynomial regression analysis. In Henri Theil\u2019s contributions to economics and econometrics. Springer. Pages 345\u2013381."},{"key":"e_1_3_2_1_57_1","volume-title":"Applied linear regression. 528","author":"Weisberg Sanford","unstructured":"Sanford Weisberg. 2005. Applied linear regression. 528, John Wiley & Sons."},{"key":"e_1_3_2_1_58_1","volume-title":"Generalized resilience and robust statistics. arXiv preprint arXiv:1909.08755","author":"Zhu Banghua","year":"2019","unstructured":"Banghua Zhu, Jiantao Jiao, and Jacob Steinhardt. 2019. Generalized resilience and robust statistics. arXiv preprint arXiv:1909.08755, 2019."},{"key":"e_1_3_2_1_59_1","volume-title":"Robust estimation via generalized quasi-gradients. arXiv preprint arXiv:2005.14073","author":"Zhu Banghua","year":"2020","unstructured":"Banghua Zhu, Jiantao Jiao, and Jacob Steinhardt. 2020. Robust estimation via generalized quasi-gradients. arXiv preprint arXiv:2005.14073, 2020."}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451001","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451001","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:01:44Z","timestamp":1750183304000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451001"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":59,"alternative-id":["10.1145\/3406325.3451001","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451001","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}