Fast decentralized nonconvex finite-sum optimization with recursive variance reduction

DOI10.1137/20M1361158MaRDI QIDQ5026835zbMATH OpenOpenAlexFDO

Authors Ran Xin, Usman A. Khan, Soummya Kar

Publication date 8 February 2022

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

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

zbMATH Keywords

decentralized optimizationgradient trackingnonconvex optimizationstochastic optimizationvariance reduction

Mathematics Subject Classification ID

Stochastic programming (90C15) Nonconvex programming, global optimization (90C26) Multi-agent systems (93A16)

Abstract: This paper considers decentralized minimization of $N:=nm$ smooth non-convex cost functions equally divided over a directed network of $n$ nodes. Specifically, we describe a stochastic first-order gradient method, called GT-SARAH, that employs a SARAH-type variance reduction technique and gradient tracking (GT) to address the stochastic and decentralized nature of the problem. We show that GT-SARAH, with appropriate algorithmic parameters, finds an $epsilon$-accurate first-order stationary point with $$ gradient complexity, where $(1-lambda)in(0,1]$ is the spectral gap of the network weight matrix and $L$ is the smoothness parameter of the cost functions. This gradient complexity outperforms that of the existing decentralized stochastic gradient methods. In particular, in a big-data regime such that $n=O(N^{frac12}(1-lambda{)}^3)$, this gradient complexity furthers reduces to $O(N^{frac12}Lepsilo{n}^{-2})$, independent of the network topology, and matches that of the centralized near-optimal variance-reduced methods. Moreover, in this regime GT-SARAH achieves a non-asymptotic linear speedup, in that, the total number of gradient computations at each node is reduced by a factor of $1/n$ compared to the centralized near-optimal algorithms that perform all gradient computations at a single node. To the best of our knowledge, GT-SARAH is the first algorithm that achieves this property. In addition, we show that appropriate choices of local minibatch size balance the trade-offs between the gradient and communication complexity of GT-SARAH. Over infinite time horizon, we establish that all nodes in GT-SARAH asymptotically achieve consensus and converge to a first-order stationary point in the almost sure and mean-squared sense.

Recommendations

• Finite-sum smooth optimization with SARAH
• Communication-efficient algorithms for decentralized and stochastic optimization
• DSA: decentralized double stochastic averaging gradient algorithm
• EXTRA: an exact first-order algorithm for decentralized consensus optimization
• On the convergence of decentralized gradient descent

Cites work

• A Decentralized Proximal-Gradient Method With Network Independent Step-Sizes and Separated Convergence Rates
• A proximal stochastic gradient method with progressive variance reduction
• Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
• An Improved Convergence Analysis for Decentralized Online Stochastic Non-Convex Optimization
• Asymptotic properties of primal-dual algorithm for distributed stochastic optimization over random networks with imperfect communications
• Communication-efficient algorithms for decentralized and stochastic optimization
• Convergence of Distributed Stochastic Variance Reduced Methods Without Sampling Extra Data
• Decentralized Frank–Wolfe Algorithm for Convex and Nonconvex Problems
• Diffusion Adaptation Strategies for Distributed Optimization and Learning Over Networks
• Distributed nonconvex constrained optimization over time-varying digraphs
• Distributed stochastic gradient tracking methods
• Distributed stochastic subgradient projection algorithms for convex optimization
• Distributed strategies for generating weight-balanced and doubly stochastic digraphs
• Distributed subgradient-free stochastic optimization algorithm for nonsmooth convex functions over time-varying networks
• DSA: decentralized double stochastic averaging gradient algorithm
• EXTRA: an exact first-order algorithm for decentralized consensus optimization
• Harnessing Smoothness to Accelerate Distributed Optimization
• scientific article; zbMATH DE number 7255141 (Why is no real title available?)
• scientific article; zbMATH DE number 7307473 (Why is no real title available?)
• Inexact SARAH algorithm for stochastic optimization
• Lectures on convex optimization
• On convergence rate of distributed stochastic gradient algorithm for convex optimization with inequality constraints
• On the convergence of decentralized gradient descent
• On the Influence of Bias-Correction on Distributed Stochastic Optimization
• On the Learning Behavior of Adaptive Networks—Part I: Transient Analysis
• Optimization methods for large-scale machine learning
• Penalized likelihood regression for generalized linear models with non-quadratic penalties
• Probability with Martingales
• Robust Stochastic Approximation Approach to Stochastic Programming
• Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
• Stochastic nested variance reduction for nonconvex optimization
• Swarming for faster convergence in stochastic optimization
• Variance-Reduced Decentralized Stochastic Optimization With Accelerated Convergence
• Variance-Reduced Stochastic Learning by Networked Agents Under Random Reshuffling

Cited in

(7)

• Distributed stochastic gradient tracking methods with momentum acceleration for non-convex optimization
• DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimization
• A stochastic averaging gradient algorithm with multi‐step communication for distributed optimization
• Graph Topology Invariant Gradient and Sampling Complexity for Decentralized and Stochastic Optimization
• A variance-reduced stochastic gradient tracking algorithm for decentralized optimization with orthogonality constraints
• Constrained distributed online convex optimization with bandit feedback for unbalanced digraphs
• Clipped stochastic gradient tracking for locally smooth functions

Describes a project that uses

Uses Software

• SpiderBoost
• Saga
• ProxSARAH

This page was built for publication: Fast decentralized nonconvex finite-sum optimization with recursive variance reduction

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