{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:47:26Z","timestamp":1781077646283,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":32,"publisher":"ACM","funder":[{"name":"NSF","award":["DMS-2022448"],"award-info":[{"award-number":["DMS-2022448"]}]},{"name":"ERC","award":["815464"],"award-info":[{"award-number":["815464"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718218","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T22:24:47Z","timestamp":1750026287000},"page":"2341-2349","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Sample-Optimal Private Regression in Polynomial Time"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-4012-3696","authenticated-orcid":false,"given":"Prashanti","family":"Anderson","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-0225-8588","authenticated-orcid":false,"given":"Ainesh","family":"Bakshi","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9304-2872","authenticated-orcid":false,"given":"Mahbod","family":"Majid","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-9719-0036","authenticated-orcid":false,"given":"Stefan","family":"Tiegel","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.2478\/popets-2022-0041"},{"key":"e_1_3_2_1_2_1","volume-title":"International Conference on Machine Learning. 1121\u20131146","author":"Asi Hilal","year":"2023","unstructured":"Hilal Asi, Jonathan Ullman, and Lydia Zakynthinou. 2023. From robustness to privacy and back. In International Conference on Machine Learning. 1121\u20131146."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451001"},{"key":"e_1_3_2_1_4_1","volume-title":"Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th annual symposium on foundations of computer science. 464\u2013473","author":"Bassily Raef","unstructured":"Raef Bassily, Adam Smith, and Abhradeep Thakurta. 2014. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th annual symposium on foundations of computer science. 464\u2013473."},{"key":"e_1_3_2_1_5_1","volume-title":"Covariance-aware private mean estimation without private covariance estimation. Advances in neural information processing systems, 34","author":"Brown Gavin","year":"2021","unstructured":"Gavin Brown, Marco Gaboardi, Adam Smith, Jonathan Ullman, and Lydia Zakynthinou. 2021. Covariance-aware private mean estimation without private covariance estimation. Advances in neural information processing systems, 34 (2021), 7950\u20137964."},{"key":"e_1_3_2_1_6_1","volume-title":"Insufficient Statistics Perturbation: Stable Estimators for Private Least Squares Extended Abstract. In The Thirty Seventh Annual Conference on Learning Theory. 750\u2013751","author":"Brown Gavin","year":"2024","unstructured":"Gavin Brown, Jonathan Hayase, Samuel Hopkins, Weihao Kong, Xiyang Liu, Sewoong Oh, Juan C Perdomo, and Adam Smith. 2024. Insufficient Statistics Perturbation: Stable Estimators for Private Least Squares Extended Abstract. In The Thirty Seventh Annual Conference on Learning Theory. 750\u2013751."},{"key":"e_1_3_2_1_7_1","volume-title":"The Thirty Sixth Annual Conference on Learning Theory. 5578\u20135579","author":"Brown Gavin","year":"2023","unstructured":"Gavin Brown, Samuel Hopkins, and Adam Smith. 2023. Fast, sample-efficient, affine-invariant private mean and covariance estimation for subgaussian distributions. In The Thirty Sixth Annual Conference on Learning Theory. 5578\u20135579."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Ilias Diakonikolas Samuel B Hopkins Ankit Pensia and Stefan Tiegel. 2024. SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics Subspace Distortion and More. arXiv preprint arXiv:2412.21203.","DOI":"10.1145\/3717823.3718293"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1126680"},{"key":"e_1_3_2_1_10_1","unstructured":"Ilias Diakonikolas and Daniel M Kane. 2019. Recent Advances in Algorithmic High-Dimensional Robust Statistics. arXiv preprint arXiv:1911.05911."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.170"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_3_2_1_13_1","volume-title":"Privacy induces robustness: Information-computation gaps and sparse mean estimation. Advances in neural information processing systems, 35","author":"Georgiev Kristian","year":"2022","unstructured":"Kristian Georgiev and Samuel Hopkins. 2022. Privacy induces robustness: Information-computation gaps and sparse mean estimation. Advances in neural information processing systems, 35 (2022), 6829\u20136842."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585115"},{"key":"e_1_3_2_1_15_1","volume-title":"Conference on learning theory. 1649\u20131682","author":"Hopkins Samuel B","year":"2019","unstructured":"Samuel B Hopkins and Jerry Li. 2019. How hard is robust mean estimation? In Conference on learning theory. 1649\u20131682."},{"key":"e_1_3_2_1_16_1","volume-title":"Conference on Learning Theory. 1853\u20131902","author":"Kamath Gautam","year":"2019","unstructured":"Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan Ullman. 2019. Privately learning high-dimensional distributions. In Conference on Learning Theory. 1853\u20131902."},{"key":"e_1_3_2_1_17_1","volume-title":"New lower bounds for private estimation and a generalized fingerprinting lemma. Advances in neural information processing systems, 35","author":"Kamath Gautam","year":"2022","unstructured":"Gautam Kamath, Argyris Mouzakis, and Vikrant Singhal. 2022. New lower bounds for private estimation and a generalized fingerprinting lemma. Advances in neural information processing systems, 35 (2022), 24405\u201324418."},{"key":"e_1_3_2_1_18_1","volume-title":"Finite Sample Differentially Private Confidence Intervals. In 9th Innovations in Theoretical Computer Science Conference (ITCS","author":"Karwa Vishesh","year":"2018","unstructured":"Vishesh Karwa and Salil Vadhan. 2018. Finite Sample Differentially Private Confidence Intervals. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)."},{"key":"e_1_3_2_1_19_1","volume-title":"Conference on Learning Theory. 25\u20131.","author":"Kifer Daniel","year":"2012","unstructured":"Daniel Kifer, Adam Smith, and Abhradeep Thakurta. 2012. Private convex empirical risk minimization and high-dimensional regression. In Conference on Learning Theory. 25\u20131."},{"key":"e_1_3_2_1_20_1","volume-title":"Conference On Learning Theory. 1420\u20131430","author":"Klivans Adam","year":"2018","unstructured":"Adam Klivans, Pravesh K Kothari, and Raghu Meka. 2018. Efficient algorithms for outlier-robust regression. In Conference On Learning Theory. 1420\u20131430."},{"key":"e_1_3_2_1_21_1","volume-title":"International Conference on Algorithmic Learning Theory. 638\u2013667","author":"Kothari Pravesh K","year":"2022","unstructured":"Pravesh K Kothari, Peter Manohar, and Brian Hu Zhang. 2022. Polynomial-time sum-of-squares can robustly estimate mean and covariance of gaussians optimally. In International Conference on Algorithmic Learning Theory. 638\u2013667."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188970"},{"key":"e_1_3_2_1_23_1","volume-title":"The Thirty Sixth Annual Conference on Learning Theory. 2511\u20132551","author":"Kuditipudi Rohith","year":"2023","unstructured":"Rohith Kuditipudi, John Duchi, and Saminul Haque. 2023. A pretty fast algorithm for adaptive private mean estimation. In The Thirty Sixth Annual Conference on Learning Theory. 2511\u20132551."},{"key":"e_1_3_2_1_24_1","unstructured":"Xiyang Liu Prateek Jain Weihao Kong Sewoong Oh and Arun Sai Suggala. 2023. Near optimal private and robust linear regression. arXiv preprint arXiv:2301.13273."},{"key":"e_1_3_2_1_25_1","volume-title":"Conference on Learning Theory. 1167\u20131246","author":"Liu Xiyang","year":"2022","unstructured":"Xiyang Liu, Weihao Kong, and Sewoong Oh. 2022. Differential privacy and robust statistics in high dimensions. In Conference on Learning Theory. 1167\u20131246."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.66"},{"key":"e_1_3_2_1_27_1","first-page":"1","article-title":"Robust regression with covariate filtering: Heavy tails and adversarial contamination","author":"Pensia Ankit","year":"2024","unstructured":"Ankit Pensia, Varun Jog, and Po-Ling Loh. 2024. Robust regression with covariate filtering: Heavy tails and adversarial contamination. J. Amer. Statist. Assoc., 1\u201312.","journal-title":"J. Amer. Statist. Assoc."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1111\/rssb.12364"},{"key":"e_1_3_2_1_29_1","volume-title":"International Conference on Machine Learning. 3105\u20133114","author":"Sheffet Or","year":"2017","unstructured":"Or Sheffet. 2017. Differentially private ordinary least squares. In International Conference on Machine Learning. 3105\u20133114."},{"key":"e_1_3_2_1_30_1","volume-title":"Conference on Learning Theory. 1126\u20131166","author":"Varshney Prateek","year":"2022","unstructured":"Prateek Varshney, Abhradeep Thakurta, and Prateek Jain. 2022. (Nearly) Optimal Private Linear Regression for Sub-Gaussian Data via Adaptive Clipping. In Conference on Learning Theory. 1126\u20131166."},{"key":"e_1_3_2_1_31_1","unstructured":"Yu-Xiang Wang. 2018. Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain. arXiv preprint arXiv:1803.02596."},{"key":"e_1_3_2_1_32_1","volume-title":"International Conference on Machine Learning. 2493\u20132502","author":"Wang Yu-Xiang","year":"2015","unstructured":"Yu-Xiang Wang, Stephen Fienberg, and Alex Smola. 2015. Privacy for free: Posterior sampling and stochastic gradient monte carlo. In International Conference on Machine Learning. 2493\u20132502."}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","location":"Prague Czechia","acronym":"STOC '25","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718218","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:44:14Z","timestamp":1750693454000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718218"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":32,"alternative-id":["10.1145\/3717823.3718218","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718218","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}