Convergence rate of incremental gradient and incremental Newton methods

DOI10.1137/17M1147846MaRDI QIDQ5237308zbMATH OpenOpenAlexWikidataFDO

Authors Mert Gürbüzbalaban, Asuman Ozdaglar, Pablo A. Parrilo

Publication date 17 October 2019

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.08562

zbMATH Keywords

first-order methodsconvex optimizationconvergence rateincremental algorithms

Mathematics Subject Classification ID

Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Nonlinear programming (90C30)

Abstract: The incremental gradient method is a prominent algorithm for minimizing a finite sum of smooth convex functions, used in many contexts including large-scale data processing applications and distributed optimization over networks. It is a first-order method that processes the functions one at a time based on their gradient information. The incremental Newton method, on the other hand, is a second-order variant which exploits additionally the curvature information of the underlying functions and can therefore be faster. In this paper, we focus on the case when the objective function is strongly convex and present fast convergence results for the incremental gradient and incremental Newton methods under the constant and diminishing stepsizes. For a decaying stepsize rule $alph{a}_k=Theta(1/k^s)$ with $sin(0,1]$, we show that the distance of the IG iterates to the optimal solution converges at rate $calO(1/k^s)$ (which translates into $calO(1/k^{2s})$ rate in the suboptimality of the objective value). For $s>1/2$, this improves the previous $calO(1/sqrtk)$ results in distances obtained for the case when functions are non-smooth. We show that to achieve the fastest $calO(1/k)$ rate, incremental gradient needs a stepsize that requires tuning to the strong convexity parameter whereas the incremental Newton method does not. The results are based on viewing the incremental gradient method as a gradient descent method with gradient errors, devising efficient upper bounds for the gradient error to derive inequalities that relate distances of the consecutive iterates to the optimal solution and finally applying Chung's lemmas from the stochastic approximation literature to these inequalities to determine their asymptotic behavior. In addition, we construct examples to show tightness of our rate results.

Recommendations

• On the Convergence Rate of Incremental Aggregated Gradient Algorithms
• A globally convergent incremental Newton method
• A Convergent Incremental Gradient Method with a Constant Step Size
• Convergence rate of incremental subgradient algorithms
• Incrementally updated gradient methods for constrained and regularized optimization

Cites work

• scientific article; zbMATH DE number 1818892 (Why is no real title available?)
• A Collaborative Training Algorithm for Distributed Learning
• A Convergent Incremental Gradient Method with a Constant Step Size
• A New Class of Incremental Gradient Methods for Least Squares Problems
• A globally convergent incremental Newton method
• Acceleration of Stochastic Approximation by Averaging
• Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression
• An Adaptive Associative Memory Principle
• An Incremental Gradient(-Projection) Method with Momentum Term and Adaptive Stepsize Rule
• Convergence rate of incremental subgradient algorithms
• Convex optimization algorithms
• Distributed Subgradient Methods for Multi-Agent Optimization
• Distributed optimization and statistical learning via the alternating direction method of multipliers
• EXTRA: an exact first-order algorithm for decentralized consensus optimization
• Global convergence rate of proximal incremental aggregated gradient methods
• Gradient Convergence in Gradient methods with Errors
• Incremental Least Squares Methods and the Extended Kalman Filter
• Incremental gradient algorithms with stepsizes bounded away from zero
• Incremental subgradient methods for nondifferentiable optimization
• Introductory lectures on convex optimization. A basic course.
• Logarithmic regret algorithms for online convex optimization
• On a Stochastic Approximation Method
• On the Convergence Rate of Incremental Aggregated Gradient Algorithms
• On‐line learning for very large data sets
• Parallel stochastic gradient algorithms for large-scale matrix completion
• Robust Stochastic Approximation Approach to Stochastic Programming
• The incremental Gauss-Newton algorithm with adaptive stepsize rule
• Why random reshuffling beats stochastic gradient descent

Cited in

(14)

• Surpassing gradient descent provably: a cyclic incremental method with linear convergence rate
• Proximal variable smoothing method for three-composite nonconvex nonsmooth minimization with a linear operator
• Accelerating incremental gradient optimization with curvature information
• Rate of convergence of a generalization of Newton's method
• A globally convergent incremental Newton method
• Convergence rate of the gradient descent method with dilatation of the space
• Incremental quasi-Newton algorithms for solving a nonconvex, nonsmooth, finite-sum optimization problem
• IQN: an incremental quasi-Newton method with local superlinear convergence rate
• Convergence of Random Reshuffling under the Kurdyka–Łojasiewicz Inequality
• Variable smoothing incremental aggregated gradient method for nonsmooth nonconvex regularized optimization
• Why random reshuffling beats stochastic gradient descent
• On the Convergence Rate of Incremental Aggregated Gradient Algorithms
• scientific article; zbMATH DE number 7626722 (Why is no real title available?)
• scientific article; zbMATH DE number 3917581 (Why is no real title available?)

Describes a project that uses

Uses Software

• Saga
• Jellyfish

This page was built for publication: Convergence rate of incremental gradient and incremental Newton methods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5237308)