Optimization in High Dimensions via Accelerated, Parallel, and Proximal Coordinate Descent
Optimization in High Dimensions via Accelerated, Parallel, and Proximal Coordinate Descent
复制标题
DOI：
10.1137/16m1085905
复制
发表时间：
2016-11
期刊：
影响因子：
--
通讯作者：
Olivier Fercoq;Peter Richtárik
中科院分区：
文献类型：
--
作者：
Olivier Fercoq;Peter Richtárik
我们提出了一个新的随机坐标下降法，用于最小化凸函数的和，每个凸函数只依赖于少量的坐标。我们的方法（APPROX）同时加速，并行和PROXALITY，这是第一次提出这样的方法。在处理器数目等于坐标数目的特殊情况下，该方法以速率$2\bar{\omega}\bar{L} R^2/（k+1）^2 $收敛，其中$k$是迭代计数器，$\bar{\omega}$是损失函数的数据加权平均可分性程度，$\bar{L}$是与和中的坐标和单个函数相关联的Lipschitz常数的平均值，$R$是初始点到最小值的距离。我们表明，该方法可以实现，而不需要执行全维向量运算，这是加速坐标下降的主要瓶颈，使其不切实际。该方法依赖于平均可分性度的事实。
We propose a new randomized coordinate descent method for minimizing the sum of convex functions, each of which depends on a small number of coordinates only. Our method (APPROX) is simultaneously Accelerated, Parallel, and PROXimal; this is the first time such a method has been proposed. In the special case when the number of processors is equal to the number of coordinates, the method converges at the rate $2\bar{\omega}\bar{L} R^2/(k+1)^2 $, where $k$ is the iteration counter, $\bar{\omega}$ is a data-weighted average degree of separability of the loss function, $\bar{L}$ is the average of Lipschitz constants associated with the coordinates and individual functions in the sum, and $R$ is the distance of the initial point from the minimizer. We show that the method can be implemented without the need to perform full-dimensional vector operations, which is the major bottleneck of accelerated coordinate descent, rendering it impractical. The fact that the method depends on the average degree of separabili...