Improved Iteration Complexities for Overconstrained p-Norm Regression

In this paper we obtain improved iteration complexities for solving ℓp regression. We provide methods which given any full-rank A ∈ ℝn × d with n ≥ d, b ∈ ℝn, and p ≥ 2 solve minx ∈ ℝd left|A x - bright|p to high precision in time dominated by that of solving widetildeOp(d^fracp-23p-2) linear systems in A^top D A for positive diagonal matrices D. This improves upon the previous best iteration complexity of widetildeOp(n^fracp-23p-2) (Adil, Kyng, Peng, Sachdeva 2019). As a corollary, we obtain an widetildeO(d1/3ε-2/3) iteration complexity for approximate ℓ_∞ regression. Further, for q ∈ (1, 2] and dual norm q = p/(p-1) we provide an algorithm that solves ℓq regression in widetildeO(d^fracp-22p-2) iterations. To obtain this result we analyze row reweightings (closely inspired by ℓp-norm Lewis weights) which allow a closer connection between ℓ2 and ℓp regression. We provide adaptations of two different iterative optimization frameworks which leverage this connection and yield our results. The first framework is based on iterative refinement and multiplicative weights based width reduction and the second framework is based on highly smooth acceleration. Both approaches yield widetildeOp(d^fracp-23p-2) iteration methods but the second has a polynomial dependence on p (as opposed to the exponential dependence of the first algorithm) and provides a new alternative to the previous state-of-the-art methods for ℓp regression for large p.