Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Survey
Provides a comprehensive theoretical framework and novel algorithmic combinations for practitioners working on large-scale convex optimization problems.
This survey unifies and analyzes incremental gradient, subgradient, and proximal methods for minimizing a sum of convex functions, introducing new combined subgradient-proximal variants. It demonstrates convergence and rate advantages of randomized component selection, with applications in machine learning and large-scale optimization.
We survey incremental methods for minimizing a sum $\sum_{i=1}^mf_i(x)$ consisting of a large number of convex component functions $f_i$. Our methods consist of iterations applied to single components, and have proved very effective in practice. We introduce a unified algorithmic framework for a variety of such methods, some involving gradient and subgradient iterations, which are known, and some involving combinations of subgradient and proximal methods, which are new and offer greater flexibility in exploiting the special structure of $f_i$. We provide an analysis of the convergence and rate of convergence properties of these methods, including the advantages offered by randomization in the selection of components. We also survey applications in inference/machine learning, signal processing, and large-scale and distributed optimization.