When Cyclic Coordinate Descent Outperforms Randomized Coordinate Descent
When Cyclic Coordinate Descent Outperforms Randomized Coordinate Descent
复制标题
DOI：
--
复制
发表时间：
2017-12
期刊：
影响因子：
--
通讯作者：
M. Gürbüzbalaban;A. Ozdaglar;P. Parrilo;N. D. Vanli
中科院分区：
文献类型：
--
作者：
M. Gürbüzbalaban;A. Ozdaglar;P. Parrilo;N. D. Vanli
坐标下降(CD)方法是一种经典的优化算法，由于其在机器学习应用中的竞争性能而重新引起人们的兴趣。最近的一些论文提供了在更新坐标的选择上不同的确定性(循环)和随机化变体的收敛速度估计。这些估计表明，随机坐标下降(RCD)比循环坐标下降(CCD)表现更好，尽管数值实验并没有为这种比较提供明确的理由。在这篇文章中，我们给出了例子和更一般的问题类，对于这些问题，在渐近的最坏情况下收敛速度是比RCD快的。此外，我们还给出了相对于RCD的CCD率的改善量的下界和上界，这取决于所使用的确定性顺序。我们还根据目标函数的海森矩阵的组合性质，给出了最佳确定序(导致最大收敛速度改善)的刻画。
The coordinate descent (CD) method is a classical optimization algorithm that has seen a revival of interest because of its competitive performance in machine learning applications. A number of recent papers provided convergence rate estimates for their deterministic (cyclic) and randomized variants that differ in the selection of update coordinates. These estimates suggest randomized coordinate descent (RCD) performs better than cyclic coordinate descent (CCD), although numerical experiments do not provide clear justification for this comparison. In this paper, we provide examples and more generally problem classes for which CCD (or CD with any deterministic order) is faster than RCD in terms of asymptotic worst-case convergence. Furthermore, we provide lower and upper bounds on the amount of improvement on the rate of CCD relative to RCD, which depends on the deterministic order used. We also provide a characterization of the best deterministic order (that leads to the maximum improvement in convergence rate) in terms of the combinatorial properties of the Hessian matrix of the objective function.