On the Convergence Rate of Incremental Aggregated Gradient Algorithms

DOI10.1137/15M1049695zbMATH Open1366.90195arXiv1506.02081OpenAlexW3104398353MaRDI QIDQ5266533FDOQ5266533

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

Publication date: 16 June 2017

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

Abstract: Motivated by applications to distributed optimization over networks and large-scale data processing in machine learning, we analyze the deterministic incremental aggregated gradient method for minimizing a finite sum of smooth functions where the sum is strongly convex. This method processes the functions one at a time in a deterministic order and incorporates a memory of previous gradient values to accelerate convergence. Empirically it performs well in practice; however, no theoretical analysis with explicit rate results was previously given in the literature to our knowledge, in particular most of the recent efforts concentrated on the randomized versions. In this paper, we show that this deterministic algorithm has global linear convergence and characterize the convergence rate. We also consider an aggregated method with momentum and demonstrate its linear convergence. Our proofs rely on a careful choice of a Lyapunov function that offers insight into the algorithm's behavior and simplifies the proofs considerably.

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

Recommendations

• Global convergence rate of proximal incremental aggregated gradient methods
• Convergence rate of incremental subgradient algorithms
• Convergence rate of incremental gradient and incremental Newton methods
• On stochastic accelerated gradient with convergence rate
• On the rates of convergence of parallelized averaged stochastic gradient algorithms
• On the convergence of a block-coordinate incremental gradient method
• Inertial proximal incremental aggregated gradient method with linear convergence guarantees
• Convergence rates of an inertial gradient descent algorithm under growth and flatness conditions
• On the asymptotic convergence and acceleration of gradient methods
• Nonconvex proximal incremental aggregated gradient method with linear convergence

zbMATH Keywords

first-order methodsconvex optimizationconvergence analysislarge-scale optimization

Mathematics Subject Classification ID

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

Cites Work

• Introductory lectures on convex optimization. A basic course.
• Title not available (Why is that?)
• Analysis and design of optimization algorithms via integral quadratic constraints
• Title not available (Why is that?)
• Title not available (Why is that?)
• Incremental gradient algorithms with stepsizes bounded away from zero
• An Incremental Gradient(-Projection) Method with Momentum Term and Adaptive Stepsize Rule
• A Convergent Incremental Gradient Method with a Constant Step Size
• On‐line learning for very large data sets
• Incremental Least Squares Methods and the Extended Kalman Filter
• Incrementally updated gradient methods for constrained and regularized optimization
• Convex optimization algorithms
• A globally convergent incremental Newton method
• Convergence rate of incremental gradient and incremental Newton methods
• The incremental Gauss-Newton algorithm with adaptive stepsize rule
• Why random reshuffling beats stochastic gradient descent

Cited In (42)

• An inertial parallel and asynchronous forward-backward iteration for distributed convex optimization
• An accelerated distributed gradient method with local memory
• Accelerating incremental gradient optimization with curvature information
• On the convergence of a block-coordinate incremental gradient method
• On the convergence analysis of aggregated heavy-ball method
• Communication-efficient algorithms for decentralized and stochastic optimization
• A Convergent Incremental Gradient Method with a Constant Step Size
• Heavy-ball-based optimal thresholding algorithms for sparse linear inverse problems
• Heavy-ball-based hard thresholding algorithms for sparse signal recovery
• An incremental mirror descent subgradient algorithm with random sweeping and proximal step
• Stochastic subgradient algorithm for nonsmooth nonconvex optimization
• On variance reduction for stochastic smooth convex optimization with multiplicative noise
• Non-asymptotic convergence analysis of inexact gradient methods for machine learning without strong convexity
• An incremental aggregated proximal ADMM for linearly constrained nonconvex optimization with application to sparse logistic regression problems
• GADMM: fast and communication efficient framework for distributed machine learning
• Optimization methods for large-scale machine learning
• Incremental quasi-Newton algorithms for solving a nonconvex, nonsmooth, finite-sum optimization problem
• A distributed accelerated optimization algorithm over time‐varying directed graphs with uncoordinated step‐sizes
• Linear convergence of proximal incremental aggregated gradient method for nonconvex nonsmooth minimization problems
• Linear convergence of primal-dual gradient methods and their performance in distributed optimization
• Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods
• IQN: an incremental quasi-Newton method with local superlinear convergence rate
• Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
• Global convergence rate of proximal incremental aggregated gradient methods
• On stochastic and deterministic quasi-Newton methods for nonstrongly convex optimization: asymptotic convergence and rate analysis
• Proximal-like incremental aggregated gradient method with linear convergence under Bregman distance growth conditions
• Primal-dual incremental gradient method for nonsmooth and convex optimization problems
• Incremental without replacement sampling in nonconvex optimization
• Variable smoothing incremental aggregated gradient method for nonsmooth nonconvex regularized optimization
• Random-reshuffled SARAH does not need full gradient computations
• An asynchronous subgradient-proximal method for solving additive convex optimization problems
• A distributed proximal gradient method with time-varying delays for solving additive convex optimizations
• Convergence rate of incremental gradient and incremental Newton methods
• Fully asynchronous policy evaluation in distributed reinforcement learning over networks
• An aggregate and iterative disaggregate algorithm with proven optimality in machine learning
• Convergence rates of subgradient methods for quasi-convex optimization problems
• Linear convergence of cyclic SAGA
• Convergence on thresholding-based algorithms for dictionary-sparse recovery
• Distributed deterministic asynchronous algorithms in time-varying graphs through Dykstra splitting
• Inertial proximal incremental aggregated gradient method with linear convergence guarantees
• 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

This page was built for publication: On the Convergence Rate of Incremental Aggregated Gradient Algorithms

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