Iterative Refinement for ℓp-norm Regression
Iterative Refinement for ℓp-norm Regression
复制标题
ℓp-范数回归的迭代细化
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Sushant Sachdeva
中科院分区：
文献类型：
--
作者：
Deeksha Adil;Rasmus Kyng;Richard Peng;Sushant Sachdeva
我们给出了 lp 回归问题的改进算法，minx ‖x‖p 使得 Ax = b，对于所有 p ∈ (1, 2) ∪ (2,∞)。我们的算法在 Õp(m |p−2| 2p+|p−2| ) ≤ Õp(m 1) 次迭代中获得高精度解，其中每次迭代需要求解 m×m 线性系统，其中 m 是环境空间的维度。结合维持每次迭代需要求解的线性系统的近似逆的过程，我们给出了将 lp 回归求解到 1/poly(n) 精度的算法，该算法在时间 Õp(m ) 内运行，其中 ω 是矩阵乘法常数。对于 ω > 2.37 的当前最佳值，这意味着对于所有远离 1 的常数 p，我们可以像 l2 回归一样快地求解 lp 回归。我们的算法可以与图拉普拉斯中的线性系统的近线性时间求解器结合使用，在 Õp(m 1+ |p−2| 2p+|p−2| 中具有 m 个边的无向图上给出 1/poly(n) 精度的最小 lp 范数流量/电压解。 ) ≤ Õp(m4) 时间。对于稀疏图和具有相似维度的矩阵，我们的迭代计数和运行时间改进了 [Bubeck-Cohen-Lee-Li STOC'18] 的 p 范数回归算法以及通用凸优化算法。我们算法的核心是 lp 范数的迭代细化方案，使用 Bubeck 等人的工作中引入的二次平滑 lp 范数。形式上，给定初始解，我们构建一个问题，寻求最小化子空间上的二次平滑 lp 范数，这样该问题的粗略解决方案允许我们通过常数因子改进初始解，从而导致算法快速收敛。该论文已发表于 SODA 2019 [Adi+]，并于 2018 年 7 月 12 日首次提交至 SODA。多伦多大学。 deeksha@cs.toronto.edu。得到安大略省研究生奖学金和 Sushant Sachdeva 的康诺特新研究员奖的支持。哈佛。 rjkyng@gmail.com。由 ONR 拨款 N00014-18-1-2562 支持。佐治亚理工学院。 richard.peng@gmail.com。部分由多伦多大学国家科学基金会资助，拨款号：1718533。 sachdeva@cs.toronto.edu。研究部分由加拿大自然科学与工程研究委员会 (NSERC) 和康诺特新研究员奖支持。
We give improved algorithms for the lp-regression problem, minx ‖x‖p such that Ax = b, for all p ∈ (1, 2) ∪ (2,∞). Our algorithms obtain a high accuracy solution in Õp(m |p−2| 2p+|p−2| ) ≤ Õp(m 1) iterations, where each iteration requires solving an m×m linear system, with m being the dimension of the ambient space. Incorporating a procedure for maintaining an approximate inverse of the linear systems that we need to solve at each iteration, we give algorithms for solving lp-regression to 1/poly(n) accuracy that runs in time Õp(m ), where ω is the matrix multiplication constant. For the current best value of ω > 2.37, this means that we can solve lp regression as fast as l2 regression, for all constant p bounded away from 1. Our algorithms can be combined with nearly-linear time solvers for linear systems in graph Laplacians to give minimum lp-norm flow / voltage solutions to 1/poly(n) accuracy on an undirected graph with m edges in Õp(m 1+ |p−2| 2p+|p−2| ) ≤ Õp(m4) time. For sparse graphs and for matrices with similar dimensions, our iteration counts and running times improve upon the p-norm regression algorithm by [Bubeck-Cohen-Lee-Li STOC‘18], as well as general purpose convex optimization algorithms. At the core of our algorithms is an iterative refinement scheme for lp-norms, using the quadratically-smoothed lp-norms introduced in the work of Bubeck et al. Formally, given an initial solution, we construct a problem that seeks to minimize a quadratically-smoothed lp 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. This paper has been published at SODA 2019 [Adi+], and was initially submitted to SODA on July 12, 2018. University of Toronto. deeksha@cs.toronto.edu. Supported by an Ontario Graduate Scholarship, and by a Connaught New Researcher award to Sushant Sachdeva. Harvard. rjkyng@gmail.com. Supported by ONR grant N00014-18-1-2562. Georgia Tech. richard.peng@gmail.com. Supported in part by the National Science Foundation under Grant No. 1718533. University of Toronto. sachdeva@cs.toronto.edu. Research supported in part by the Natural Sciences and Engineering Research Council of Canada (NSERC), and a Connaught New Researcher award.