Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Survey

By Dimitri P. Bertsekas. arXiv.org, 2015

459 citations recorded by the source corpus.

We survey incremental methods for minimizing a sum P m=1 fi(x) consisting of a large number of convex component functions fi. 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 fi. 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.

Subfields: Artificial Intelligence, Computational Mechanics

View Paper: https://www.semanticscholar.org/paper/2615fe784137854810679a6deb0403a9009b26e7

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

Citations in the corpus

New Convergence Aspects of Stochastic Gradient Algorithms (2018, methodology): “Lemma 5 (Bertsekas (2015)) Let Yk, Zk, and Wk, k = 0, 1, . . . , be three sequences of random variables and let {Fk}k≥0 be a filtration, that is, σ-algebras such that Fk ⊂ Fk+1 for all k. Suppose that: • The random variables Yk, Zk, and Wk are nonnegative, and Fk-measurable.”
Streaming PCA and Subspace Tracking: The Missing Data Case (2018, methodology): “GROUSE implements a first-order incremental gradient procedure [61] to minimize this objective with respect to the subspace variable U constrained to the Grassmannian [62], the manifold of all subspaces with a fixed rank, given as”
Coresets for Data-efficient Training of Machine Learning Models (2019, methodology): “However, in practice, the convergence rate of IG is known to be quite sensitive to the order of processing the functions (Bertsekas, 2015a; Gur-buzbalaban et al., 2017).”
Personalized Federated Learning: An Attentive Collaboration Approach (2020, methodology): “Assumption 1 There exists a constant B > 0 such that for every k , Assumption 1 is widely used in the study of incremental and stochastic optimization algorithms; see, e.g. , [40, 46].”
A Unified Convergence Analysis for Shuffling-Type Gradient Methods (2020, methodology): “To establish Theorem 4, we will use the following lemma from (Bertsekas, 2015).”
A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach (2014, background): “It is worth noting that Algorithm 1 can be modiﬁed to resemble the more traditional incremental algorithm [53], where each iteration only those variables with “fresh” gradients are updated.”
ActiveClean: Interactive Data Cleaning While Learning Convex Loss Models (2016, background): “The convergence rates of SGD are also well analyzed [11, 8, 39].”
Generalized Low Rank Models (2014, background): “afeguards on step sizes we propose are quite important in practice: without these checks, we observe divergence when the initial step sizes are chosen too large. Motivated by the convergence proof in [Ber11], for each row, we seek a step size on the order of 1=kg ik 2, where g i is the gradient of t”
NESTT: A Nonconvex Primal-Dual Splitting Method for Distributed and Stochastic Optimization (2016, methodology): “When the problem becomes nonconvex, the well-known incremental based algorithm can be used [3, 24], but these methods generally lack convergence rate guarantees.”
GraB: Finding Provably Better Data Permutations than Random Reshuffling (2022, methodology): “Random Reshuffling (RR) [13] and the related shuffle-once (SO) method [14, 15] are among the most popular data permutation methods.”
Visualizing Deep Network Training Trajectories with PCA (2016, background): “In convex optimization, there is a strong theoretical understanding of the path that different optimization methods take and how fast they converge to the global optimum (Bertsekas, 2011), but deep neural network loss functions are very non-convex.”
Active Sampler: Light-weight Accelerator for Complex Data Analytics at Scale (2015, methodology): “Even though gradient descent [3, 1] has been widely used for decades, evaluating the full gradient over all the training samples (i.e. batch gradient descent [29]) is extremely To reduce the computational cost at every iteration, Stochastic Gradient Descent (SGD) [22, 2] optimizes the objective…”
Why random reshuffling beats stochastic gradient descent (2015, unknown): “hnology, 77 Massachusetts Avenue, Cambridge, Massachusetts 02139. E-mail: parrilo@mit.edu. 1 arXiv:1510.08560v3 [math.OC] 8 Jan 2019 error between the output and the prediction of a parametric model) [2,3,5,12], minimization of an expected value of a function (where the expectation is taken over a n”
Kalman-Based Stochastic Gradient Method with Stop Condition and Insensitivity to Conditioning (2015, methodology): “umber ofcomponent functions, N, is large, proximaland SGD methods are believed to require fewer memory and computing resources in comparison to classical methods (e.g. gradient descent, quasi-Newton) [5, 10]. However, proximal and SGD methods’ computational beneﬁts are reduced by two algorithmic cha”
Balancing Communication and Computation in Distributed Optimization (2017, methodology): “This class of methods includes augmented Lagrangian methods and alternating direction method of multiplier [3], [35]–[46].”