EUVIMEDEUVIMED entdecken
Crossref

Fast Algorithms for ℓ p -Regression

Deeksha Adil, Rasmus Kyng, Richard Peng, Sushant Sachdeva

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →