Fast algorithms for _p-regression

DOI10.1145/3686794MaRDI QIDQ6993544zbMATH OpenFDO

Authors Deeksha Adil, Rasmus Kyng, Richard Peng, Sushant Sachdeva

Publication date 25 April 2025

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3686794

zbMATH Keywords

\(\ell_p\)-regressionIRLSiterative refinement

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Learning and adaptive systems in artificial intelligence (68T05) Convex programming (90C25)

Cites work

• A faster cutting plane method and its implications for combinatorial and convex optimization
• An homotopy method for l _p regression provably beyond self-concordance and in input-sparsity time
• Analysis and algorithms for \(\ell_p\)-based semi-supervised learning on graphs
• Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data
• Construction of nearest points in the \(L^ p\), p even, and \(L^ \infty\) norms. I
• Decoding by Linear Programming
• Efficient inverse maintenance and faster algorithms for linear programming
• Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
• Faster p-norm minimizing flows, via smoothed q-norm problems
• Flows in almost linear time via adaptive preconditioning
• Graph implementations for nonsmooth convex programs
• scientific article; zbMATH DE number 3915531 (Why is no real title available?)
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• scientific article; zbMATH DE number 3186062 (Why is no real title available?)
• Improved iteration complexities for overconstrained p -norm regression
• Iterative refinement for \(\ell_p\)-norm regression
• Maximum flow and minimum-cost flow in almost-linear time
• Much faster algorithms for matrix scaling
• Natural algorithms for flow problems
• On the p-Laplacian and -Laplacian on graphs with applications in image and data processing
• On the game p-Laplacian on weighted graphs with applications in image processing and data clustering
• Path finding methods for linear programming: solving linear programs in \(\widetilde{O}(\sqrt{rank})\) iterations and faster algorithms for maximum flow
• Runtime guarantees for regression problems
• Unit capacity maxflow in almost \(O(m^{4/3})\) time

Cited in

(1)

• Acceleration meets inverse maintenance: faster _-regression

This page was built for publication: Fast algorithms for \(\ell_p\)-regression

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6993544)