Coordinate Descent Algorithms
Stephen J. Wright
Abstract
Coordinate descent algorithms solve optimization problems by successively performing approximate minimization along coordinate directions or coordinate hyperplanes. They have been used in applications for many years, and their popularity continues to grow because of their usefulness in data analysis, machine learning, and other areas of current interest. This paper describes the fundamentals of the coordinate descent approach, together with variants and extensions and their convergence properties, mostly with reference to convex objectives. We pay particular attention to a certain problem structure that arises frequently in machine learning applications, showing that efficient implementations of accelerated coordinate descent algorithms are possible for problems of this type. We also present some parallel variants and discuss their convergence properties under several models of parallel execution.
中文速览
坐标下降法（coordinate descent, CD）是优化领域的经典算法，但长期被认为"太简单"而遭研究者忽视；随着机器学习和数据分析中大规模稀疏优化问题的爆发式增长，如何让它又快又好地工作重新成为热点。这篇综述系统梳理了坐标下降法的理论基础、多种变体（包括随机选坐标、加速版本、块坐标更新）及其收敛性分析，重点关注机器学习中常见的"光滑损失加可分离正则项"结构，证明在该结构下加速坐标下降可以高效实现。文章还专门讨论了同步和异步两种并行执行模型下并行坐标下降的收敛保证，并揭示了坐标下降与随机梯度法、Kaczmarz投影法、Gauss-Seidel迭代等经典方法之间的内在联系。这项工作为从业者提供了一份系统的方法论地图，也为理解现代大规模优化算法的设计原则提供了统一视角。
原文 arXiv:1502.04759;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1502.04759v1