Convergence of Distributed Stochastic Variance Reduced Methods without Sampling Extra Data

Abstract

Stochastic variance reduced methods have gained a lot of interest recently for empirical risk minimization due to its appealing run time complexity. When the data size is large and disjointly stored on different machines, it becomes imperative to distribute the implementation of such variance reduced methods. In this paper, we consider a general framework that directly distributes popular stochastic variance reduced methods in the master/slave model, by assigning outer loops to the parameter server, and inner loops to worker machines. This framework is natural and friendly to implement, but its theoretical convergence is not well understood. We obtain a comprehensive understanding of algorithmic convergence with respect to data homogeneity by measuring the smoothness of the discrepancy between the local and global loss functions. We establish the linear convergence of distributed versions of a family of stochastic variance reduced algorithms, including those using accelerated and recursive gradient updates, for minimizing strongly convex losses. Our theory captures how the convergence of distributed algorithms behaves as the number of machines and the size of local data vary. Furthermore, we show that when the data are less balanced, regularization can be used to ensure convergence at a slower rate. We also demonstrate that our analysis can be further extended to handle nonconvex loss functions.

References in corpus (24)

• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning
• Federated Optimization:Distributed Optimization Beyond the Datacenter
• Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
• Gradient Sparsification for Communication-Efficient Distributed Optimization
• D${}^2$: Decentralized Training over Decentralized Data
• A Universal Catalyst for First-Order Optimization
• DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
• AIDE: Fast and Communication Efficient Distributed Optimization
• CoCoA: A General Framework for Communication-Efficient Distributed Optimization
• A Simple Stochastic Variance Reduced Algorithm with Fast Convergence Rates
• GIANT: Globally Improved Approximate Newton Method for Distributed Optimization
• SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms
• Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch-Prox
• Finite-Sum Smooth Optimization with SARAH
• SCOPE: Scalable Composite Optimization for Learning on Spark
• Dissipativity Theory for Accelerating Stochastic Variance Reduction: A Unified Analysis of SVRG and Katyusha Using Semidefinite Programs
• Efficient Distributed SGD with Variance Reduction

Cited by in corpus (8)

• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data
• A Field Guide to Federated Optimization
• Parallel Restarted SPIDER -- Communication Efficient Distributed Nonconvex Optimization with Optimal Computation Complexity
• Communication-Efficient Distributed Optimization in Networks with Gradient Tracking and Variance Reduction
• ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation
• Fast decentralized non-convex finite-sum optimization with recursive variance reduction
• Byzantine-Robust Decentralized Stochastic Optimization over Static and Time-Varying Networks