{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:02:36Z","timestamp":1750309356360,"version":"3.41.0"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2024,10,5]],"date-time":"2024-10-05T00:00:00Z","timestamp":1728086400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Post Graduate Schlarship (PGSD) by NSERC (Natural Sciences and Engineering Research Council of Canada) and Sushant Sachdeva\u2019s NSERC Discovery"},{"name":"Algorithms and complexity for high-accuracy flows and convex optimization","award":["200021 204787"],"award-info":[{"award-number":["200021 204787"]}]},{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Science Foundation","award":["1846218"],"award-info":[{"award-number":["1846218"]}]},{"name":"NSERC Discovery","award":["RGPIN-2022-03207"],"award-info":[{"award-number":["RGPIN-2022-03207"]}]},{"DOI":"10.13039\/100006778","name":"Georgia Institute of Technology","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100006778","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSERC Discovery","award":["RGPIN-2018-06398"],"award-info":[{"award-number":["RGPIN-2018-06398"]}]},{"name":"Ontario Early Researcher Award","award":["ER21-16-283"],"award-info":[{"award-number":["ER21-16-283"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2024,10,31]]},"abstract":"\n The\n \n \\(\\ell _p\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -norm regression problem is a classic problem in optimization with wide ranging applications in machine learning and theoretical computer science. The goal is to compute\n \n \\(\\boldsymbol {\\mathit {x}}^{\\star } =\\arg \\min _{\\boldsymbol {\\mathit {A}}\\boldsymbol {\\mathit {x}}=\\boldsymbol {\\mathit {b}}}\\Vert \\boldsymbol {\\mathit {x}}\\Vert _p^p\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , where\n \n \\(\\boldsymbol {\\mathit {x}}^{\\star }\\in \\mathbb {R}^n,\\boldsymbol {\\mathit {A}}\\in \\mathbb {R}^{d\\times n},\\boldsymbol {\\mathit {b}}\\in \\mathbb {R}^d\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n \\(d\\le n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . Efficient\n high-accuracy<\/jats:italic>\n algorithms for the problem have been challenging both in theory and practice and the state-of-the-art algorithms require\n \n \\(poly(p)\\cdot n^{\\frac{1}{2}-\\frac{1}{p}}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n linear system solves for\n \n \\(p\\ge 2\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . In this article, we provide new algorithms for\n \n \\(\\ell _p\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -regression (and a more general formulation of the problem) that obtain a\n high-accuracy<\/jats:italic>\n solution in\n \n \\(O(p n^{ {(p-2)}{(3p-2)}})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n linear system solves. We further propose a new\n inverse maintenance<\/jats:italic>\n procedure that speeds-up our algorithm to\n \n \\(\\widetilde{O}(n^{\\omega })\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n total runtime, where\n \n \\(O(n^{\\omega })\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n denotes the running time for multiplying\n \n \\(n \\times n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n matrices. Additionally, we give the first\n Iteratively Reweighted Least Squares (IRLS)<\/jats:italic>\n algorithm that is guaranteed to converge to an optimum in a few iterations. Our IRLS algorithm has shown exceptional practical performance, beating the currently available implementations in MATLAB\/CVX by 10\u201350\u00d7.\n <\/jats:p>","DOI":"10.1145\/3686794","type":"journal-article","created":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T10:20:57Z","timestamp":1723026057000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Fast Algorithms for\n \n \u2113\n p<\/sub>\n <\/i>\n -Regression"],"prefix":"10.1145","volume":"71","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-7520-0696","authenticated-orcid":false,"given":"Deeksha","family":"Adil","sequence":"first","affiliation":[{"name":"Institute for Theoretical Studies, ETH Z\u00fcrich, Zurich, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8268-6258","authenticated-orcid":false,"given":"Rasmus","family":"Kyng","sequence":"additional","affiliation":[{"name":"ETH Zurich Department of Computer Science, Zurich, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5407-7965","authenticated-orcid":false,"given":"Richard","family":"Peng","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Waterloo, Waterloo, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5393-9324","authenticated-orcid":false,"given":"Sushant","family":"Sachdeva","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, Canada"}]}],"member":"320","published-online":{"date-parts":[[2024,10,5]]},"reference":[{"key":"e_1_3_3_2_2","volume-title":"Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP\u201921)","author":"Adil Deeksha","year":"2021","unstructured":"Deeksha Adil, Brian Bullins, Rasmus Kyng, and Sushant Sachdeva. 2021. Almost-linear-time weighted \\(\\ell _p\\) -norm solvers in slightly dense graphs via sparsification. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP\u201921). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_3_3_2","first-page":"19122","volume-title":"Proceedings of the Advances in Neural Information Processing Systems","author":"Adil Deeksha","year":"2021","unstructured":"Deeksha Adil, Brian Bullins, and Sushant Sachdeva. 2021. Unifying width-reduced methods for quasi-self-concordant optimization. In Proceedings of the Advances in Neural Information Processing Systems. 19122\u201319133."},{"key":"e_1_3_3_4_2","doi-asserted-by":"crossref","first-page":"1405","DOI":"10.1137\/1.9781611975482.86","volume-title":"Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Adil Deeksha","year":"2019","unstructured":"Deeksha Adil, Rasmus Kyng, Richard Peng, and Sushant Sachdeva. 2019. Iterative refinement for \\(\\ell _p\\) -norm regression. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1405\u20131424."},{"key":"e_1_3_3_5_2","first-page":"14189","volume-title":"Proceedings of the Advances in Neural Information Processing Systems","author":"Adil Deeksha","year":"2019","unstructured":"Deeksha Adil, Richard Peng, and Sushant Sachdeva. 2019. Fast, provably convergent IRLS algorithm for p-norm linear regression. In Proceedings of the Advances in Neural Information Processing Systems. 14189\u201314200."},{"key":"e_1_3_3_6_2","unstructured":"Deeksha Adil Richard Peng and Sushant Sachdeva. 2019. pIRLS. Retrieved 25 October 2022 from https:\/\/github.com\/fast-algos\/pIRLS"},{"key":"e_1_3_3_7_2","first-page":"892","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Adil Deeksha","year":"2020","unstructured":"Deeksha Adil and Sushant Sachdeva. 2020. Faster p-norm minimizing flows, via smoothed q-norm problems. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 892\u2013910."},{"key":"e_1_3_3_8_2","first-page":"379","article-title":"Phase transition in the family of p-resistances","volume":"24","author":"Alamgir Morteza","year":"2011","unstructured":"Morteza Alamgir and Ulrike Luxburg. 2011. Phase transition in the family of p-resistances. Advances in Neural Information Processing Systems 24 (2011), 379\u2013387.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_3_9_2","doi-asserted-by":"crossref","first-page":"890","DOI":"10.1109\/FOCS.2017.87","volume-title":"Proceedings of the 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS\u201917)","author":"Allen-Zhu Zeyuan","year":"2017","unstructured":"Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Oliveira, and Avi Wigderson. 2017. Much faster algorithms for matrix scaling. In Proceedings of the 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS\u201917). IEEE, 890\u2013901."},{"key":"e_1_3_3_10_2","first-page":"III\u2013545","volume-title":"Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing ICASSP\u201994.","author":"Barreto Jose Antonio","year":"1994","unstructured":"Jose Antonio Barreto and C. Sidney Burrus. 1994. L\/sub p\/-complex approximation using iterative reweighted least squares for FIR digital filters. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing ICASSP\u201994. IEEE, III\u2013545."},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188776"},{"key":"e_1_3_3_12_2","unstructured":"Brian Bullins. 2018. Fast minimization of structured convex quartics. arXiv:1812.10349. Retrieved from https:\/\/arxiv.org\/abs\/1812.10349"},{"key":"e_1_3_3_13_2","unstructured":"C. Sidney Burrus. 2012. Iterative reweighted least squares. OpenStax CNX. Available online: http:\/\/cnx.org\/contents\/92b90377-2b34-49e4-b26f-7fe572db78a1 12 (2012) 6."},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/18M1199241"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.858979"},{"key":"e_1_3_3_16_2","first-page":"19052","volume-title":"Proceedings of the Advances in Neural Information Processing Systems","volume":"33","author":"Carmon Yair","year":"2020","unstructured":"Yair Carmon, Arun Jambulapati, Qijia Jiang, Yujia Jin, Yin Tat Lee, Aaron Sidford, and Kevin Tian. 2020. Acceleration with a ball optimization oracle. In Proceedings of the Advances in Neural Information Processing Systems. H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (Eds.), Vol. 33. Curran Associates, Inc., 19052\u201319063. Retrieved from https:\/\/proceedings.neurips.cc\/paper\/2020\/file\/dba4c1a117472f6aca95211285d0587e-Paper.pdf"},{"key":"e_1_3_3_17_2","first-page":"3869","volume-title":"Proceedings of the 2008 IEEE International Conference on Acoustics, Speech, and Signal Processing","author":"Chartrand Rick","year":"2008","unstructured":"Rick Chartrand and Wotao Yin. 2008. Iteratively reweighted algorithms for compressive sensing. In Proceedings of the 2008 IEEE International Conference on Acoustics, Speech, and Signal Processing. IEEE, 3869\u20133872."},{"key":"e_1_3_3_18_2","doi-asserted-by":"crossref","first-page":"612","DOI":"10.1109\/FOCS54457.2022.00064","volume-title":"IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)","author":"Chen Li","year":"2022","unstructured":"Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. 2022. In IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). 612\u2013623."},{"key":"e_1_3_3_19_2","first-page":"806","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Chierichetti Flavio","year":"2017","unstructured":"Flavio Chierichetti, Sreenivas Gollapudi, Ravi Kumar, Silvio Lattanzi, Rina Panigrahy, and David P. Woodruff. 2017. Algorithms for \\(\\ell _p\\) low-rank approximation. In Proceedings of the International Conference on Machine Learning. PMLR, 806\u2013814."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422469"},{"key":"e_1_3_3_21_2","first-page":"273","volume-title":"Proceedings of the 43rd Annual ACM Symposium on Theory of Computing","author":"Christiano Paul","year":"2011","unstructured":"Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, and Shang-Hua Teng. 2011. Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing. 273\u2013282."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0956792517000122"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1022793"},{"key":"e_1_3_3_24_2","first-page":"1794","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Ene Alina","year":"2019","unstructured":"Alina Ene and Adrian Vladu. 2019. Improved convergence for \\(\\ell _1\\) and \\(\\ell _{\\infty }\\) regression via iteratively reweighted least squares. In Proceedings of the International Conference on Machine Learning. PMLR, 1794\u20131801."},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/78.558475"},{"key":"e_1_3_3_26_2","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/978-1-84800-155-8_7","volume-title":"Proceedings of the Recent Advances in Learning and Control","author":"Grant M.","year":"2008","unstructured":"M. Grant and S. Boyd. 2008. Graph implementations for nonsmooth convex programs. In Proceedings of the Recent Advances in Learning and Control. V. Blondel, S. Boyd, and H. Kimura (Eds.), Springer-Verlag Limited, 95\u2013110. Retrieved from http:\/\/stanford.edu\/boyd\/graph_dcp.html"},{"key":"e_1_3_3_27_2","unstructured":"M. Grant and S. Boyd. 2014. CVX: Matlab Software for Disciplined Convex Programming version 2.1. March 2014 Retrieved from http:\/\/cvxr.com\/cvx"},{"key":"e_1_3_3_28_2","unstructured":"Yosra Hafiene Jalal Fadili and Abderrahim Elmoataz. 2018. Nonlocal p-laplacian variational problems on graphs. arXiv:1810.12817. Retrieved from https:\/\/arxiv.org\/abs\/1810.12817"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519971"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9045(70)90019-5"},{"key":"e_1_3_3_31_2","first-page":"119","volume-title":"Proceedings of the 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS\u201920)","author":"Kathuria Tarun","year":"2020","unstructured":"Tarun Kathuria, Yang P. Liu, and Aaron Sidford. 2020. Unit capacity maxflow in almost \\(O(m^{4\/3})\\) time. In Proceedings of the 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS\u201920). IEEE, 119\u2013130."},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316410"},{"key":"e_1_3_3_33_2","volume-title":"Proceedings of the COLT","author":"Kyng R.","year":"2015","unstructured":"R. Kyng, A. B. Rao, S. Sachdeva, and D. A Spielman. 2015. Algorithms for Lipschitz learning on graphs. In Proceedings of the COLT."},{"key":"e_1_3_3_34_2","article-title":"Contribution to the Theory of Linear Least Maximum Approximation","author":"Lawson Charles Lawrence","year":"1961","unstructured":"Charles Lawrence Lawson. 1961. Contribution to the Theory of Linear Least Maximum Approximation. Ph. D. Dissertation. University of California.","journal-title":"Ph. D. Dissertation. University of California."},{"key":"e_1_3_3_35_2","first-page":"424","volume-title":"Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS)","author":"Lee Yin Tat","year":"2014","unstructured":"Yin Tat Lee and Aaron Sidford. 2014. Path finding methods for linear programming: Solving linear programs in \\(\\tilde{O}(\\sqrt {rank})\\) iterations and faster algorithms for maximum flow. In Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 424\u2013433."},{"key":"e_1_3_3_36_2","first-page":"230","volume-title":"Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17\u201320 October, 2015","author":"Lee Yin Tat","year":"2015","unstructured":"Yin Tat Lee and Aaron Sidford. 2015. Efficient inverse maintenance and faster algorithms for linear programming. In Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17\u201320 October, 2015. 230\u2013249."},{"key":"e_1_3_3_37_2","first-page":"1049","volume-title":"Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science","author":"Lee Yin Tat","year":"2015","unstructured":"Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. 2015. A faster cutting plane method and its implications for combinatorial and convex optimization. In Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. IEEE, 1049\u20131065."},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970791"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.5555\/536676"},{"key":"e_1_3_3_40_2","volume-title":"The Approximation of Functions","author":"Rice John Rischard","year":"1964","unstructured":"John Rischard Rice. 1964. The Approximation of Functions. Addison-Wesley Reading, Mass."},{"key":"e_1_3_3_41_2","unstructured":"M. F. Rios. 2019. Laplacian \\(\\_\\) Lp \\(\\_\\) Graph \\(\\_\\) SSL. Retrieved 25 October 2022 from https:\/\/github.com\/mauriciofloresML\/Laplacian_Lp_Graph_SSL"},{"key":"e_1_3_3_42_2","first-page":"77","volume-title":"Applied and Computational Harmonic Analysis","author":"Flores Mauricio","year":"2022","unstructured":"Mauricio Flores, Jeff Calder, and Gilad Lerman. 2022. Analysis and algorithms for \\(\\ell _p\\) -based semi-supervised learning on graphs. Applied and Computational Harmonic Analysis 60 (2022), 77\u2013122."},{"key":"e_1_3_3_43_2","unstructured":"Damian Straszak and Nisheeth K. Vishnoi. 2016. IRLS and slime mold: Equivalence and convergence. arXiv:1601.02712. Retrieved from https:\/\/arxiv.org\/abs\/1601.02712"},{"key":"e_1_3_3_44_2","first-page":"1868","volume-title":"Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Straszak Damian","year":"2016","unstructured":"Damian Straszak and Nisheeth K. Vishnoi. 2016. Natural algorithms for flow problems. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1868\u20131883."},{"key":"e_1_3_3_45_2","article-title":"On a natural dynamics for linear programming","author":"Straszak Damian","year":"2016","unstructured":"Damian Straszak and Nisheeth K. Vishnoi. 2016. On a natural dynamics for linear programming. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science.","journal-title":"In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science."},{"key":"e_1_3_3_46_2","volume-title":"Solving Linear Equations with Diagonally Dominant Matrices by Constructing Good Preconditioners","author":"Vaidya P.","year":"1990","unstructured":"P. Vaidya. 1990. Solving Linear Equations with Diagonally Dominant Matrices by Constructing Good Preconditioners. Technical Report. Technical report, Department of Computer Science, University of Illinois."},{"key":"e_1_3_3_47_2","first-page":"1129","volume-title":"Proceedings of the 1999 IEEE International Conference on Acoustics, Speech, and Signal Processing ICASSP\u201999.","author":"Vargas Ricardo A.","year":"1999","unstructured":"Ricardo A. Vargas and Charles S. Burrus. 1999. Adaptive iterative reweighted least squares design of L\/sub p\/FIR filters. In Proceedings of the 1999 IEEE International Conference on Acoustics, Speech, and Signal Processing ICASSP\u201999. IEEE, 1129\u20131132."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3686794","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3686794","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:05:52Z","timestamp":1750291552000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3686794"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,5]]},"references-count":46,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,10,31]]}},"alternative-id":["10.1145\/3686794"],"URL":"https:\/\/doi.org\/10.1145\/3686794","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2024,10,5]]},"assertion":[{"value":"2022-10-27","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-07-27","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-10-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}