An Incremental Gradient(-Projection) Method with Momentum Term and Adaptive Stepsize Rule

By Paul Tseng. 1998

How researchers see this paper

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

In Optimization & Training

Citations in the corpus

Learning to learn by gradient descent by gradient descent (2016, background): “These include momentum [Nesterov, 1983, Tseng, 1998], Rprop [Riedmiller and Braun, 1993], Adagrad [Duchi et al., 2011], Adadelta [Zeiler, 2012], RMSprop [Tieleman and Hinton, 2012], and ADAM [Kingma and Ba, 2015].”
Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, methodology): “Similar methods have also been explored empirically in prior work [86, 85].”
Hogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent (2011, background): “Some theoretical work which has at least demonstrated convergence of these protocols can be found in [21, 29].”
Minimizing finite sums with the stochastic average gradient (2013, neutral): “SG methods that incorporate a momentum term use iterations of the form xk+1 = xk − αk f ′ ik (xk) + βk(x − xk−1), see [62].”
Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron (2018, neutral): “Other related work has used the strong growth condition to prove convergence rates for incremental gradient methods [34, 38].”
Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition (2013, neutral): “Under condition (5), Solodov [1998] and Tseng [1998] have analyzed convergence properties of deterministic incremental gradient methods.”
Learned Optimizers that Scale and Generalize (2017, background): “Momentum with an exponential moving average is typically motivated in terms of averaging away minibatch noise or high frequency oscillations, and is often a very effective feature (Nesterov, 1983b; Tseng, 1998).”
Coresets for Data-efficient Training of Machine Learning Models (2019, methodology): “Convergence of IG methods has been long studied under various conditions (Zhi-Quan & Paul, 1994; Mangasari-any & Solodovy, 1994; Bertsekas, 1996; Solodov, 1998; Tseng, 1998), however IG’s convergence rate has been characterized only more recently (see (Bertsekas, 2015b) for a survey).”
Parallel stochastic gradient algorithms for large-scale matrix completion (2013, background): “2 Sensitivity to μ in random matrix completion experiments.”
A Stochastic Variational Framework for Fitting and Diagnosing Generalized Linear Mixed Models (2012, methodology): “riety of approaches have been developed to enhance the rate of convergence of stochastic approximation algorithms, and examples include iterate averaging (Polyak and Juditsky, 1992), momentum method (Tseng, 1998) and gradient averaging (Xiao, 2010). See Roux et al. (2012) for the stochastic average ”
SGD with shuffling: optimal rates without component convexity and large epoch requirements (2020, methodology): “Next, we introduce a standard assumption for analyzing incremental methods, extensively used in the prior works [6, 7, 11, 14, 20] (see e.”
Approximation accuracy, gradient methods, and error bound for structured convex optimization (2010, background): “,m} and stepsize αk > 0 either constant or adjusted dynamically; see [16,71,79,86,91,129,139] and references therein.”
On the linear convergence of the projected stochastic gradient method with constant step-size (2017, methodology): “..,n})(∀x ∈ C) k∇fi(x)k2 ≤ Mk∇f(x)k2. (3.5) 4 Conclusions The strong growth condition is used in [14] where the incremental gradient method converges with a suﬃciently small constant step size and in [12] where incremental gradient method converges linearly with a suﬃciently small constant step size”
Non-convex Finite-Sum Optimization Via SCSG Methods (2017, background): “Early work focused on the asymptotic performance of algorithms [11, 7, 29], with non-asymptotic complexity bounds emerging more recently [24].”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, methodology): “For a review of key works on incremental methods and a detailed presentation of the connections with stochastic gradient descent, we refer the interested reader to the excellent survey of Bertsekas [11]; see also the work of Tseng [188].”