Convergence rate of incremental gradient and incremental Newton methods

DOI10.1137/17M1147846zbMATH Open1428.90119arXiv1510.08562OpenAlexW2980820424WikidataQ127020296 ScholiaQ127020296MaRDI QIDQ5237308FDOQ5237308

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)

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.

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

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

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)

Cites Work

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

Cited In (14)

• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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

Uses Software

• Jellyfish
• Saga

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)