DSA: Decentralized Double Stochastic Averaging Gradient Algorithm

Abstract

This paper considers convex optimization problems where nodes of a network have access to summands of a global objective. Each of these local objectives is further assumed to be an average of a finite set of functions. The motivation for this setup is to solve large scale machine learning problems where elements of the training set are distributed to multiple computational elements. The decentralized double stochastic averaging gradient (DSA) algorithm is proposed as a solution alternative that relies on: (i) The use of local stochastic averaging gradients. (ii) Determination of descent steps as differences of consecutive stochastic averaging gradients. Strong convexity of local functions and Lipschitz continuity of local gradients is shown to guarantee linear convergence of the sequence generated by DSA in expectation. Local iterates are further shown to approach the optimal argument for almost all realizations. The expected linear convergence of DSA is in contrast to the sublinear rate characteristic of existing methods for decentralized stochastic optimization. Numerical experiments on a logistic regression problem illustrate reductions in convergence time and number of feature vectors processed until convergence relative to these other alternatives.

References in corpus (6)

• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Convex Optimization for Big Data
• DILAND: An Algorithm for Distributed Sensor Localization with Noisy Distance Measurements
• Network Newton-Part II: Convergence Rate and Implementation
• Network Newton-Part I: Algorithm and Convergence

Cited by in corpus (62)

• Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• D${}^2$: Decentralized Training over Decentralized Data
• Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence
• Variance Reduced Local SGD with Lower Communication Complexity
• Asynchronous Decentralized Parallel Stochastic Gradient Descent
• On the Influence of Bias-Correction on Distributed Stochastic Optimization
• Supervised Learning Under Distributed Features
• A Primal-Dual Quasi-Newton Method for Exact Consensus Optimization
• A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
• Multi-consensus Decentralized Accelerated Gradient Descent
• Networked Signal and Information Processing
• Convergence of Distributed Stochastic Variance Reduced Methods without Sampling Extra Data
• Decentralized Stochastic Gradient Tracking for Non-convex Empirical Risk Minimization
• Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networks
• Asynchronous Accelerated Proximal Stochastic Gradient for Strongly Convex Distributed Finite Sums
• Recurrent Averaging Inequalities in Multi-Agent Control and Social Dynamics Modeling
• Dualize, Split, Randomize: Toward Fast Nonsmooth Optimization Algorithms
• Variance-Reduced Stochastic Quasi-Newton Methods for Decentralized Learning: Part I
• An Accelerated Decentralized Stochastic Proximal Algorithm for Finite Sums
• A Decentralized Proximal Point-type Method for Saddle Point Problems
• Stochastic Proximal Gradient Consensus Over Random Networks
• Communication-Efficient Distributed Strongly Convex Stochastic Optimization: Non-Asymptotic Rates
• (Corrected Version) Push-LSVRG-UP: Distributed Stochastic Optimization over Unbalanced Directed Networks with Uncoordinated Triggered Probabilities
• Distributed Stochastic Gradient Descent: Nonconvexity, Nonsmoothness, and Convergence to Local Minima
• Decentralized Submodular Maximization: Bridging Discrete and Continuous Settings
• Improving the Sample and Communication Complexity for Decentralized Non-Convex Optimization: A Joint Gradient Estimation and Tracking Approach
• Fast decentralized non-convex finite-sum optimization with recursive variance reduction
• Communication-Efficient Distributed Optimization in Networks with Gradient Tracking and Variance Reduction
• An introduction to decentralized stochastic optimization with gradient tracking
• Federated Composite Optimization
• Stochastic Optimization from Distributed, Streaming Data in Rate-limited Networks
• Graph-Dependent Implicit Regularisation for Distributed Stochastic Subgradient Descent
• Variance-Reduced Decentralized Stochastic Optimization with Gradient Tracking--Part I: GT-SAGA
• Robust and Communication-Efficient Collaborative Learning
• Revisiting EXTRA for Smooth Distributed Optimization
• A Hybrid Variance-Reduced Method for Decentralized Stochastic Non-Convex Optimization
• Decentralized Consensus Algorithm with Delayed and Stochastic Gradients
• On Data Dependence in Distributed Stochastic Optimization
• Primal-Dual Distributed Temporal Difference Learning
• Gradient tracking and variance reduction for decentralized optimization and machine learning
• Optimal Statistical Rates for Decentralised Non-Parametric Regression with Linear Speed-Up
• Variance Reduction for Distributed Stochastic Gradient Descent
• Dual-Free Stochastic Decentralized Optimization with Variance Reduction
• PMGT-VR: A decentralized proximal-gradient algorithmic framework with variance reduction
• D-SPIDER-SFO: A Decentralized Optimization Algorithm with Faster Convergence Rate for Nonconvex Problems
• A fast randomized incremental gradient method for decentralized non-convex optimization
• A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!
• Decentralized Composite Optimization with Compression
• Primal-Dual Algorithm for Distributed Constrained Optimization
• FlexPD: A Flexible Framework Of First-Order Primal-Dual Algorithms for Distributed Optimization
• GT-STORM: Taming Sample, Communication, and Memory Complexities in Decentralized Non-Convex Learning
• Asynchrony and Acceleration in Gossip Algorithms
• A general framework for decentralized optimization with first-order methods
• A Unification and Generalization of Exact Distributed First Order Methods
• Variance-Reduced Stochastic Learning by Networked Agents under Random Reshuffling
• A Stochastic Large-scale Machine Learning Algorithm for Distributed Features and Observations
• Decentralized Learning with Lazy and Approximate Dual Gradients
• Distributed Policy Gradient with Variance Reduction in Multi-Agent Reinforcement Learning
• Byzantine-Robust Decentralized Stochastic Optimization over Static and Time-Varying Networks
• Data Dependent Convergence for Distributed Stochastic Optimization
• Distributed Networked Learning with Correlated Data