Fast decentralized non-convex finite-sum optimization with recursive variance reduction

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 $O\left(\max \right\{N^{\frac{1}{2}},n(1-\lambda {)}^{-2},n^{\frac{2}{3}}{m}^{\frac{1}{3}}(1-\lambda {)}^{-1}\left\}L{\epsilon }^{-2}\right)$ 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^{\frac{1}{2}}(1-\lambda {)}^3)$, this gradient complexity furthers reduces to $O(N^{\frac{1}{2}}L{\epsilon }^{-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.

Accepted in SIAM Journal on Optimization

References in corpus (8)

• DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
• Stochastic Gradient Push for Distributed Deep Learning
• Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence
• An improved convergence analysis for decentralized online stochastic non-convex optimization
• On the Influence of Bias-Correction on Distributed Stochastic Optimization
• A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent
• Convergence of Distributed Stochastic Variance Reduced Methods without Sampling Extra Data
• Lower Bounds for Smooth Nonconvex Finite-Sum Optimization

Cited by in corpus (5)

• A Hybrid Variance-Reduced Method for Decentralized Stochastic Non-Convex Optimization
• A Stochastic Proximal Gradient Framework for Decentralized Non-Convex Composite Optimization: Topology-Independent Sample Complexity and Communication Efficiency
• Decentralized Riemannian Gradient Descent on the Stiefel Manifold
• A fast randomized incremental gradient method for decentralized non-convex optimization
• A general framework for decentralized optimization with first-order methods