Inexact Coordinate Descent: Complexity and Preconditioning
Rachael Tappenden Peter Richtárik Jacek Gondzio School of Mathematics University of Edinburgh United Kingdom
Abstract
In this paper we consider the problem of minimizing a convex function using a randomized block coordinate descent method. One of the key steps at each iteration of the algorithm is determining the update to a block of variables. Existing algorithms assume that in order to compute the update, a particular subproblem is solved exactly. In this work we relax this requirement, and allow for the subproblem to be solved inexactly, leading to an inexact block coordinate descent method. Our approach incorporates the best known results for exact updates as a special case. Moreover, these theoretical guarantees are complemented by practical considerations: the use of iterative techniques to determine the update as well as the use of preconditioning for further acceleration.
中文速览
随机块坐标下降（block coordinate descent）方法在求解大规模凸优化问题时，每次迭代都需要精确解一个子问题来确定更新方向，但这在很多实际场景中代价高昂甚至不可行。本文提出了一种"不精确块坐标下降"（Inexact Coordinate Descent, ICD）方法，允许每次迭代只近似求解子问题，并用两个参数严格控制不精确程度。理论上，作者证明了ICD在凸和强凸目标函数下均具有高概率的迭代复杂度保证，且当不精确参数归零时自动退化为已有的精确方法结果；实践上，文章还探讨了如何用共轭梯度等迭代算法求解子问题，并引入预条件技术进一步加速，数值实验表明这种策略能显著降低整体运行时间。这一工作大幅扩展了坐标下降方法的适用范围，为机器学习、压缩感知等领域中维度极高、精确求解子问题不现实的大规模问题提供了有理论支撑的高效解法。
原文 arXiv:1304.5530;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1304.5530v2