An homotopy method for l p regression provably beyond self-concordance and in input-sparsity time

DOI10.1145/3188745.3188776MaRDI QIDQ5230368zbMATH OpenOpenAlexFDO

Authors Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, Yuanzhi Li

Publication date 22 August 2019

Published in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.01328

zbMATH Keywords

\(l_p\) coneinput sparsity timeNesterov-Nemirovski's theory of interior point methodsregressionself-concordance

Mathematics Subject Classification ID

Computational methods for problems pertaining to statistics (62-08) Linear regression; mixed models (62J05) Interior-point methods (90C51)

Abstract: We consider the problem of linear regression where the $el{l}_2^n$ norm loss (i.e., the usual least squares loss) is replaced by the $el{l}_p^n$ norm. We show how to solve such problems up to machine precision in $O^{\ast }(n^{|1/2-1/p|})$ (dense) matrix-vector products and $O^{\ast }(1)$ matrix inversions, or alternatively in $O^{\ast }(n^{|1/2-1/p|})$ calls to a (sparse) linear system solver. This improves the state of the art for any $potin1,2,+infty$. Furthermore we also propose a randomized algorithm solving such problems in {em input sparsity time}, i.e., $O^{\ast }(Z+mathrmpoly(d))$ where $Z$ is the size of the input and $d$ is the number of variables. Such a result was only known for $p=2$. Finally we prove that these results lie outside the scope of the Nesterov-Nemirovski's theory of interior point methods by showing that any symmetric self-concordant barrier on the $el{l}_p^n$ unit ball has self-concordance parameter $ildeOmega(n)$.

Recommendations

• Fast exact conformalization of the Lasso using piecewise linear homotopy
• Homotopy Based Algorithms for $\ell _{\scriptscriptstyle 0}$-Regularized Least-Squares
• The L_p convergence for projection pursuit regression
• An efficient method for \(l^\infty\) regression
• Homotopy perturbation sparsity regularization method with applications
• A proximal-gradient homotopy method for the sparse least-squares problem
• On a conjecture of Huber concerning the convergence of projection pursuit regression
• Learning and estimation applications of an online homotopy algorithm for a generalization of the LASSO

Cited in

(11)

• Iteratively reweighted least squares and slime mold dynamics: connection and convergence
• Unit Capacity Maxflow in Almost $m^{4/3}$ Time
• Iterative refinement for \(\ell_p\)-norm regression
• Dual space preconditioning for gradient descent
• Accelerate the warm-up stage in the Lasso computation via a homotopic approach
• Optimal Algorithms for Stochastic Complementary Composite Minimization
• Complementary composite minimization, small gradients in general norms, and applications
• High-accuracy multicommodity flows via iterative refinement
• The bit complexity of dynamic algebraic formulas and their determinants
• Fast algorithms for _p-regression
• Almost-linear-time weighted _p-norm solvers in slightly dense graphs via sparsification

This page was built for publication: An homotopy method for l _p regression provably beyond self-concordance and in input-sparsity time

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