D${}^2$: Decentralized Training over Decentralized Data

Abstract

While training a machine learning model using multiple workers, each of which collects data from their own data sources, it would be most useful when the data collected from different workers can be {\em unique} and {\em different}. Ironically, recent analysis of decentralized parallel stochastic gradient descent (D-PSGD) relies on the assumption that the data hosted on different workers are {\em not too different}. In this paper, we ask the question: {\em Can we design a decentralized parallel stochastic gradient descent algorithm that is less sensitive to the data variance across workers?} In this paper, we present D${}^2$, a novel decentralized parallel stochastic gradient descent algorithm designed for large data variance \xr{among workers} (imprecisely, "decentralized" data). The core of D${}^2$ is a variance blackuction extension of the standard D-PSGD algorithm, which improves the convergence rate from $O\left(\frac{\sigma }{\sqrt{nT}}+\frac{(n{\zeta }^2{)}^{\frac{1}{3}}}{T^{2/3}}\right)$ to $O\left(\frac{\sigma }{\sqrt{nT}}\right)$ where ${\zeta }^2$ denotes the variance among data on different workers. As a result, D${}^2$ is robust to data variance among workers. We empirically evaluated D${}^2$ on image classification tasks where each worker has access to only the data of a limited set of labels, and find that D${}^2$ significantly outperforms D-PSGD.

References in corpus (10)

• MXNet: A Flexible and Efficient Machine Learning Library for Heterogeneous Distributed Systems
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates
• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
• Asynchronous Decentralized Parallel Stochastic Gradient Descent
• Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions
• Dynamic Safe Interruptibility for Decentralized Multi-Agent Reinforcement Learning
• Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Development

Cited by in corpus (73)

• Federated Variance-Reduced Stochastic Gradient Descent with Robustness to Byzantine Attacks
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence
• An improved convergence analysis for decentralized online stochastic non-convex optimization
• Federated Multi-Task Learning under a Mixture of Distributions
• Variance Reduced Local SGD with Lower Communication Complexity
• Communication-Efficient Distributed Deep Learning: A Comprehensive Survey
• The Non-IID Data Quagmire of Decentralized Machine Learning
• On the Influence of Bias-Correction on Distributed Stochastic Optimization
• Asynchronous Decentralized Parallel Stochastic Gradient Descent
• A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learning
• Throughput-Optimal Topology Design for Cross-Silo Federated Learning
• The OARF Benchmark Suite: Characterization and Implications for Federated Learning Systems
• Distributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problems
• A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
• Moniqua: Modulo Quantized Communication in Decentralized SGD
• Hierarchical Federated Learning through LAN-WAN Orchestration
• Can Primal Methods Outperform Primal-dual Methods in Decentralized Dynamic Optimization?
• Communication-Efficient Local Decentralized SGD Methods
• Decentralized Bayesian Learning over Graphs
• Convergence of Distributed Stochastic Variance Reduced Methods without Sampling Extra Data
• Decentralized Stochastic Gradient Tracking for Non-convex Empirical Risk Minimization
• Asynchronous Accelerated Proximal Stochastic Gradient for Strongly Convex Distributed Finite Sums
• On the Utility of Gradient Compression in Distributed Training Systems
• Fully Asynchronous Distributed Optimization with Linear Convergence in Directed Networks
• BROADCAST: Reducing Both Stochastic and Compression Noise to Robustify Communication-Efficient Federated Learning
• An Accelerated Decentralized Stochastic Proximal Algorithm for Finite Sums
• Linear Convergent Decentralized Optimization with Compression
• BlueFog: Make Decentralized Algorithms Practical for Optimization and Deep Learning
• Improving the Sample and Communication Complexity for Decentralized Non-Convex Optimization: A Joint Gradient Estimation and Tracking Approach
• Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD
• Fast decentralized non-convex finite-sum optimization with recursive variance reduction
• Federated Learning over Wireless Device-to-Device Networks: Algorithms and Convergence Analysis
• Straggler-Resilient Distributed Machine Learning with Dynamic Backup Workers
• Fully Decentralized Joint Learning of Personalized Models and Collaboration Graphs
• Variance-Reduced Decentralized Stochastic Optimization with Gradient Tracking--Part I: GT-SAGA
• A Hybrid Variance-Reduced Method for Decentralized Stochastic Non-Convex Optimization
• Distributed Optimization over Block-Cyclic Data
• Heterogeneity-Aware Asynchronous Decentralized Training
• Distributed Deep Learning with Event-Triggered Communication
• RelaySum for Decentralized Deep Learning on Heterogeneous Data
• A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problems
• Clustering with Distributed Data
• A Stochastic Proximal Gradient Framework for Decentralized Non-Convex Composite Optimization: Topology-Independent Sample Complexity and Communication Efficiency
• Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Data
• Improving the Transient Times for Distributed Stochastic Gradient Methods
• On the Convergence of Decentralized Adaptive Gradient Methods
• A fast randomized incremental gradient method for decentralized non-convex optimization
• Trends and Advancements in Deep Neural Network Communication
• Efficient and Less Centralized Federated Learning
• Decentralized Composite Optimization with Compression
• D-SPIDER-SFO: A Decentralized Optimization Algorithm with Faster Convergence Rate for Nonconvex Problems
• MixML: A Unified Analysis of Weakly Consistent Parallel Learning
• Accelerating Gossip SGD with Periodic Global Averaging
• A Primal-Dual Framework for Decentralized Stochastic Optimization
• Communication-efficient Decentralized Machine Learning over Heterogeneous Networks
• PPT: A Privacy-Preserving Global Model Training Protocol for Federated Learning in P2P Networks
• Optimal Complexity in Decentralized Training
• A general framework for decentralized optimization with first-order methods
• Step-Ahead Error Feedback for Distributed Training with Compressed Gradient
• Asynchrony and Acceleration in Gossip Algorithms
• On the Convergence of Consensus Algorithms with Markovian Noise and Gradient Bias
• ResIST: Layer-Wise Decomposition of ResNets for Distributed Training
• A Distributed Training Algorithm of Generative Adversarial Networks with Quantized Gradients
• Matrix Sketching for Secure Collaborative Machine Learning
• On the Convergence of NEAR-DGD for Nonconvex Optimization with Second Order Guarantees
• Federated Submodel Optimization for Hot and Cold Data Features
• Byzantine-Robust Decentralized Stochastic Optimization over Static and Time-Varying Networks
• Communication Efficient Generalized Tensor Factorization for Decentralized Healthcare Networks
• Asynchronous Parallel Nonconvex Optimization Under the Polyak-Lojasiewicz Condition
• Nested Distributed Gradient Methods with Stochastic Computation Errors
• An Empirical Study on Compressed Decentralized Stochastic Gradient Algorithms with Overparameterized Models
• Asymptotic Network Independence and Step-Size for A Distributed Subgradient Method