A Universal Catalyst for First-Order Optimization
Hongzhou Lin1, Julien Mairal1 and Zaid Harchaoui1,2 1Inria 2NYU
Abstract
We introduce a generic scheme for accelerating first-order optimization methods in the sense of Nesterov, which builds upon a new analysis of the accelerated proximal point algorithm. Our approach consists of minimizing a convex objective by approximately solving a sequence of well-chosen auxiliary problems, leading to faster convergence. This strategy applies to a large class of algorithms, including gradient descent, block coordinate descent, SAG, SAGA, SDCA, SVRG, Finito/MISO, and their proximal variants. For all of these methods, we provide acceleration and explicit support for non-strongly convex objectives. In addition to theoretical speed-up, we also show that acceleration is useful in practice, especially for ill-conditioned problems where we measure significant improvements.
中文速览
机器学习里大量优化问题都依赖梯度类算法，但 SAG、SVRG、SDCA、Finito/MISO 等主流增量算法一直缺乏系统性的加速手段，甚至是否能被加速都是悬而未决的开放问题。这篇文章提出了一个名为"Catalyst"的通用加速框架：核心思路是把原优化目标反复替换成加了二次正则项的辅助子问题，再用 Nesterov 的外推（extrapolation）技巧串联这些子问题的近似解，从而把任何对强凸问题具有线性收敛速率的一阶算法都"包裹"成加速版本。理论上，Catalyst 对上述所有增量算法都给出了明确的加速收敛率，并且自动支持非强凸目标函数，无需事先手动添加小正则项；实验上，在病态（ill-conditioned）问题上观测到了显著的实际加速效果。这一工作统一解答了增量优化算法能否加速的问题，为大规模机器学习优化提供了一套即插即用的加速工具。
原文 arXiv:1506.02186;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1506.02186v2