Optimization with First-Order Surrogate Functions

Understand

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.