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

DOI10.1145/3188745.3188776zbMath1434.62147arXiv1711.01328OpenAlexW2963388608MaRDI QIDQ5230368

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

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

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

Mathematics Subject Classification ID

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

Related Items (5)

Iteratively reweighted least squares and slime mold dynamics: connection and convergence ⋮ Unit Capacity Maxflow in Almost $m^{4/3}$ Time ⋮ Accelerate the warm-up stage in the Lasso computation via a homotopic approach ⋮ Optimal Algorithms for Stochastic Complementary Composite Minimization ⋮ Dual Space Preconditioning for Gradient Descent

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