Optimization with First-Order Surrogate Functions
This work provides a unified framework for optimization techniques, potentially benefiting researchers and practitioners in machine learning dealing with large-scale problems, though it appears incremental in nature.
The paper tackles the problem of unifying and improving first-order optimization methods by proposing algorithmic variants and a new incremental scheme, which experimentally matches or outperforms state-of-the-art solvers for large-scale machine learning problems.
In this paper, we study optimization methods consisting of iteratively minimizing surrogates of an objective function. By proposing several algorithmic variants and simple convergence analyses, we make two main contributions. First, we provide a unified viewpoint for several first-order optimization techniques such as accelerated proximal gradient, block coordinate descent, or Frank-Wolfe algorithms. Second, we introduce a new incremental scheme that experimentally matches or outperforms state-of-the-art solvers for large-scale optimization problems typically arising in machine learning.