On the Convergence Rate of Incremental Aggregated Gradient Algorithms

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

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

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

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

• An inertial parallel and asynchronous forward-backward iteration for distributed convex optimization
• 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
• Global Convergence Rate of Proximal Incremental Aggregated Gradient Methods
• Communication-efficient algorithms for decentralized and stochastic optimization
• IQN: An Incremental Quasi-Newton Method with Local Superlinear Convergence Rate
• 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
• Proximal-Like Incremental Aggregated Gradient Method with Linear Convergence Under Bregman Distance Growth Conditions
• Stochastic subgradient algorithm for nonsmooth nonconvex optimization
• On variance reduction for stochastic smooth convex optimization with multiplicative noise
• On Stochastic and Deterministic Quasi-Newton Methods for Nonstrongly Convex Optimization: Asymptotic Convergence and Rate Analysis
• An incremental aggregated proximal ADMM for linearly constrained nonconvex optimization with application to sparse logistic regression problems
• 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
• Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods
• Convergence Rate of Incremental Gradient and Incremental Newton Methods
• Distributed Deterministic Asynchronous Algorithms in Time-Varying Graphs Through Dykstra Splitting
• Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
• Surpassing Gradient Descent Provably: A Cyclic Incremental Method with Linear Convergence Rate
• 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
• Fully asynchronous policy evaluation in distributed reinforcement learning over networks
• Convergence rates of subgradient methods for quasi-convex optimization problems
• Optimization Methods for Large-Scale Machine Learning
• GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning
• Linear convergence of cyclic SAGA
• Convergence on thresholding-based algorithms for dictionary-sparse recovery
• Inertial proximal incremental aggregated gradient method with linear convergence guarantees
• Proximal variable smoothing method for three-composite nonconvex nonsmooth minimization with a linear operator

   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 👍 👎

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)