Fast Algorithms for ℓ p -Regression
Journal of the ACM · 31.10.2024 · 71 (5) · 1-45
DOI: 10.1145/3686794 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of the ACM, online erschienen am 05.10.2024. Verfasst von Deeksha Adil und 3 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 46 Literaturangaben. Gefördert von: Post Graduate Schlarship (PGSD) by NSERC (Natural Sciences and Engineering Research Council of Canada) and Sushant Sachdeva’s NSERC Discovery, Algorithms and complexity for high-accuracy flows and convex optimization, Swiss National Science Foundation.
Abstract (Originalsprache)
The \(\ell _p\) -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 \(\boldsymbol {\mathit {x}}^{\star } =\arg \min _{\boldsymbol {\mathit {A}}\boldsymbol {\mathit {x}}=\boldsymbol {\mathit {b}}}\Vert \boldsymbol {\mathit {x}}\Vert _p^p\) , where \(\boldsymbol {\mathit {x}}^{\star }\in \mathbb {R}^n,\boldsymbol {\mathit {A}}\in \mathbb {R}^{d\times n},\boldsymbol {\mathit {b}}\in \mathbb {R}^d\) and \(d\le n\) . Efficient high-accuracy algorithms for the problem have been challenging both in theory and practice and the state-of-the-art algorithms require \(poly(p)\cdot n^{\frac{1}{2}-\frac{1}{p}}\) linear system solves for \(p\ge 2\) . In this article, we provide new algorithms for \(\ell _p\) -regression (and a more general formulation of the problem) that obtain a high-accuracy solution in \(O(p n^{ {(p-2)}{(3p-2)}})\) linear system solves. We further propose a new inverse maintenance procedure that speeds-up our algorithm to \(\widetilde{O}(n^{\omega })\) total runtime, where \(O(n^{\omega })\) denotes the running time for multiplying \(n \times n\) matrices. Additionally, we give the first Iteratively Reweighted Least Squares (IRLS) 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–50×.
Förderung
- Post Graduate Schlarship (PGSD) by NSERC (Natural Sciences and Engineering Research Council of Canada) and Sushant Sachdeva’s NSERC Discovery
- Algorithms and complexity for high-accuracy flows and convex optimization
- Swiss National Science Foundation
- National Science Foundation
- NSERC Discovery
- Georgia Institute of Technology
- Ontario Early Researcher Award
Zitieren
APA
Adil, D., Kyng, R., Peng, R., & Sachdeva, S. (2024). Fast Algorithms for ℓ p -Regression. Journal of the ACM, 71(5), 1-45. https://doi.org/10.1145/3686794
Vancouver
Adil D, Kyng R, Peng R, Sachdeva S. Fast Algorithms for ℓ p -Regression. Journal of the ACM. 2024;71(5):1-45. doi:10.1145/3686794
BibTeX
@article{Adil2024,
author = {Adil, Deeksha and Kyng, Rasmus and Peng, Richard and Sachdeva, Sushant},
title = {Fast Algorithms for ℓ p -Regression},
journal = {Journal of the ACM},
year = {2024},
volume = {71},
number = {5},
pages = {1--45},
doi = {10.1145/3686794}
}
EUVIMED