A Hybrid Variance-Reduced Method for Decentralized Stochastic Non-Convex Optimization

Abstract

This paper considers decentralized stochastic optimization over a network of $n$ nodes, where each node possesses a smooth non-convex local cost function and the goal of the networked nodes is to find an $\epsilon$-accurate first-order stationary point of the sum of the local costs. We focus on an online setting, where each node accesses its local cost only by means of a stochastic first-order oracle that returns a noisy version of the exact gradient. In this context, we propose a novel single-loop decentralized hybrid variance-reduced stochastic gradient method, called GT-HSGD, that outperforms the existing approaches in terms of both the oracle complexity and practical implementation. The GT-HSGD algorithm implements specialized local hybrid stochastic gradient estimators that are fused over the network to track the global gradient. Remarkably, GT-HSGD achieves a network topology-independent oracle complexity of $O(n^{-1}{\epsilon }^{-3})$ when the required error tolerance $\epsilon$ is small enough, leading to a linear speedup with respect to the centralized optimal online variance-reduced approaches that operate on a single node. Numerical experiments are provided to illustrate our main technical results.

arXiv commentAccepted in ICML 2021

References in corpus (16)

• A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• D${}^2$: Decentralized Training over Decentralized Data
• 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
• Distributed Algorithms for Composite Optimization: Unified Framework and Convergence Analysis
• On the Influence of Bias-Correction on Distributed Stochastic Optimization
• Quantized Decentralized Stochastic Learning over Directed Graphs
• Variance Reduced EXTRA and DIGing and Their Optimal Acceleration for Strongly Convex Decentralized Optimization
• Fast decentralized non-convex finite-sum optimization with recursive variance reduction
• A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization
• An Optimal Hybrid Variance-Reduced Algorithm for Stochastic Composite Nonconvex Optimization
• A fast randomized incremental gradient method for decentralized non-convex optimization
• A Primal-Dual Framework for Decentralized Stochastic Optimization

Cited by in corpus (1)

• Optimal Complexity in Decentralized Training