论文标题
原始双坐标下降的随机外推
Random extrapolation for primal-dual coordinate descent
论文作者
论文摘要
我们引入了一种随机外推的偶层坐标下降方法，该方法适应了数据矩阵的稀疏性和目标函数的有利结构。我们的方法仅更新具有稀疏数据的原始变量和双重变量的子集，并且它使用具有密集数据的大台阶尺寸，从而保留了为每种情况设计的特定方法的好处。除了适应稀疏性外，我们的方法还可以在有利的情况\ textit {而无需任何修改}的情况下获得快速收敛保证。特别是，我们证明了公制次级性的线性收敛，该度适用于强烈凸出的凹面问题和分段线性二次函数。在一般的凸 - 孔隙案例中，我们显示了原始双差距和客观值的序列和最佳sublinear收敛速率的几乎确定的收敛性。数值证据证明了我们方法在稀疏和致密的设置中的最新经验性能，从而匹配和改进了现有方法。
We introduce a randomly extrapolated primal-dual coordinate descent method that adapts to sparsity of the data matrix and the favorable structures of the objective function. Our method updates only a subset of primal and dual variables with sparse data, and it uses large step sizes with dense data, retaining the benefits of the specific methods designed for each case. In addition to adapting to sparsity, our method attains fast convergence guarantees in favorable cases \textit{without any modifications}. In particular, we prove linear convergence under metric subregularity, which applies to strongly convex-strongly concave problems and piecewise linear quadratic functions. We show almost sure convergence of the sequence and optimal sublinear convergence rates for the primal-dual gap and objective values, in the general convex-concave case. Numerical evidence demonstrates the state-of-the-art empirical performance of our method in sparse and dense settings, matching and improving the existing methods.
