Faster Convex Lipschitz Regression via 2-block ADMM
Faster Convex Lipschitz Regression via 2-block ADMM
复制标题
通过 2 块 ADMM 实现更快的凸 Lipschitz 回归
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Brian Kulis
中科院分区：
文献类型：
--
作者：
Ali Siahkamari;D. A. E. Acar;Christopher Liao;Kelly Geyer;Venkatesh Saligrama;Brian Kulis
逼近任意凸函数的任务出现在几个学习问题中，例如凸回归、利用凸（DC）函数的差异进行学习以及逼近Bregman分歧。在本文中，我们展示了如何通过2块ADMM方法来解决一类广泛的凸函数学习问题，其中每个块的更新可以以封闭形式计算。对于凸Lipschitz回归的任务，我们建立了我们提出的算法收敛，对于数据集X ∈ Rn × d且（cid：15）> 0，迭代复杂度为O（n d/（cid：15））。结合每次迭代的计算复杂度，我们的方法收敛速度为O（n3 d1。5 /（cid：15）+ n 2 d 2。5 /（cid：15）+ nd 3 /（cid：15））。如果d = o（n 4），这个新的速率提高了内点方法的最新速率O（n 5 d 2 /（cid：15））。此外，我们还为DC回归和Breg-man发散学习提供了类似的求解器。与以前的方法不同，我们的方法适用于GPU的使用。我们在回归和度量学习实验中证明，我们的方法比现有方法快30倍，并且产生的结果与最先进的方法相当。
The task of approximating an arbitrary convex function arises in several learning problems such as convex regression, learning with a difference of convex (DC) functions, and approximating Bregman divergences. In this paper, we show how a broad class of convex function learning problems can be solved via a 2-block ADMM approach, where updates for each block can be computed in closed form. For the task of convex Lipschitz regression, we establish that our proposed al-gorithm converges with iteration complexity of O ( n √ d/(cid:15) ) for a dataset X ∈ R n × d and (cid:15) > 0. Combined with per-iteration computation complexity, our method converges with the rate O ( n 3 d 1 . 5 /(cid:15) + n 2 d 2 . 5 /(cid:15) + nd 3 /(cid:15) ). This new rate improves the state of the art rate of O ( n 5 d 2 /(cid:15) ) available by interior point methods if d = o ( n 4 ). Further we provide similar solvers for DC regression and Breg-man divergence learning. Unlike previous approaches, our method is amenable to the use of GPUs. We demonstrate on regression and metric learning experiments that our approach is up to 30 times faster than the existing method, and produces results that are comparable to state-of-the-art.
DOI：
10.1137/18m117337x
发表时间：
2018-03
期刊：
SIAM J. Optim.
影响因子：
--
作者：
Ying Cui;J. Pang;B. Sen
通讯作者：
Ying Cui;J. Pang;B. Sen