2019/01/21 by Adil, Deeksha, Kyng, Rasmus, Peng, Richard +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Numerical Analysis (math.NA) #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.1901.06764
We give improved algorithms for the ℓp-regression problem, minx ‖x‖p such that A x=b, for all p ∈ (1,2) ∪ (2,∞). Our algorithms obtain a high accuracy solution in Op(m(|p-2|)/(2p + |p-2|)) ≤ Op(m(1)/(3)) iterations, where each iteration requires solving an m × m linear system, m being the dimension of the ambient space. By maintaining an approximate inverse of the linear systems that we solve in each iteration, we give algorithms for solving ℓp-regression to 1 / poly(n) accuracy that run in time Op(m^max\ω, 7/3\), where ω is the matrix multiplication constant. For the current best value of ω> 2.37, we can thus solve ℓp regression as fast as ℓ2 regression, for all constant p bounded away from 1. Our algorithms can be combined with fast graph Laplacian linear equation solvers to give minimum ℓp-norm flow / voltage solutions to 1 / poly(n) accuracy on an undirected graph with m edges in Op(m1 + (|p-2|)/(2p + |p-2|)) ≤ Op(m(4)/(3)) time. For sparse graphs and for matrices with similar dimensions, our iteration counts and running times improve on the p-norm regression algorithm by [Bubeck-Cohen-Lee-Li STOC`18] and general-purpose convex optimization algorithms. At the core of our algorithms is an iterative refinement scheme for ℓp-norms, using the smoothed ℓp-norms introduced in the work of Bubeck et al. Given an initial solution, we construct a problem that seeks to minimize a quadratically-smoothed ℓp norm over a subspace, such that a crude solution to this problem allows us to improve the initial solution by a constant factor, leading to algorithms with fast convergence.