On Data Dependence in Distributed Stochastic Optimization

Abstract

We study a distributed consensus-based stochastic gradient descent (SGD) algorithm and show that the rate of convergence involves the spectral properties of two matrices: the standard spectral gap of a weight matrix from the network topology and a new term depending on the spectral norm of the sample covariance matrix of the data. This data-dependent convergence rate shows that distributed SGD algorithms perform better on datasets with small spectral norm. Our analysis method also allows us to find data-dependent convergence rates as we limit the amount of communication. Spreading a fixed amount of data across more nodes slows convergence; for asymptotically growing data sets we show that adding more machines can help when minimizing twice-differentiable losses.

References in corpus (3)

• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Parallel Coordinate Descent for L1-Regularized Loss Minimization
• DSA: Decentralized Double Stochastic Averaging Gradient Algorithm

Cited by in corpus (6)

• Don't Use Large Mini-Batches, Use Local SGD
• Local SGD Converges Fast and Communicates Little
• Communication-Efficient Distributed Deep Learning: A Comprehensive Survey
• Local SGD With a Communication Overhead Depending Only on the Number of Workers
• Communication-efficient SGD: From Local SGD to One-Shot Averaging
• Oscars: Adaptive Semi-Synchronous Parallel Model for Distributed Deep Learning with Global View