First-Order Methods for Convex Optimization
This survey provides a comprehensive overview of first-order optimization methods for researchers and practitioners working on large-scale convex optimization problems in fields like machine learning, signal processing, imaging, and control theory.
This survey paper reviews key developments in first-order methods for convex optimization, which have become prominent in the last 20 years due to their ability to provide low-accuracy solutions with low computational complexity for large-scale problems. It covers non-Euclidean extensions of proximal gradient methods, accelerated versions, projection-free methods, and proximal primal-dual schemes.
First-order methods for solving convex optimization problems have been at the forefront of mathematical optimization in the last 20 years. The rapid development of this important class of algorithms is motivated by the success stories reported in various applications, including most importantly machine learning, signal processing, imaging and control theory. First-order methods have the potential to provide low accuracy solutions at low computational complexity which makes them an attractive set of tools in large-scale optimization problems. In this survey we cover a number of key developments in gradient-based optimization methods. This includes non-Euclidean extensions of the classical proximal gradient method, and its accelerated versions. Additionally we survey recent developments within the class of projection-free methods, and proximal versions of primal-dual schemes. We give complete proofs for various key results, and highlight the unifying aspects of several optimization algorithms.