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

arXiv: https://arxiv.org/abs/1711.01328 · HTML: https://mlsanity.com/paper/1711.01328/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Nov 2017.

## Built on by (most cited first, 4 of 4)

- [Complementary Composite Minimization, Small Gradients in General Norms, and Applications](https://mlsanity.com/paper/2101.11041/) (2021)
- [Optimal Excess Risk Bounds for Empirical Risk Minimization on p-Norm Linear Regression](https://mlsanity.com/paper/2310.12437/) (2023)
- [Optimal Algorithms for Stochastic Complementary Composite Minimization](https://mlsanity.com/paper/2211.01758/) (2022)
- [A conversion theorem and minimax optimality for continuum contextual bandits](https://mlsanity.com/paper/2406.05714/) (2024)

## Abstract (arXiv)

We consider the problem of linear regression where the ℓ2n norm loss (i.e., the usual least squares loss) is replaced by the ℓpn norm. We show how to solve such problems up to machine precision in O^*(n|1/2 - 1/p|) (dense) matrix-vector products and O^*(1) matrix inversions, or alternatively in O^*(n|1/2 - 1/p|) calls to a (sparse) linear system solver. This improves the state of the art for any pnot∈ 1,2,+∞. Furthermore we also propose a randomized algorithm solving such problems in em input sparsity time, i.e., O^*(Z + poly(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 ℓpn unit ball has self-concordance parameter tildeOmega(n).