Data-Dependent Convergence for Consensus Stochastic Optimization
By Avleen Singh Bijral, Anand D. Sarwate, Nati Srebro. 2016
26 citations recorded by the source corpus.
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 datasets, we show that adding more machines can help when minimizing twice-differentiable losses.
Subfields: Artificial Intelligence, Computer Networks and Communications
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Jianyu Wang
- Gauri Joshi
- Martin Jaggi
- Sebastian U. Stich
- Tao Lin
- Peter Richtárik
- Dominic Richards
- Patrick Rebeschini
In Computer Networks and Communications
- Sebastian U. Stich
- Jianyu Wang
- Martin Jaggi
- Gauri Joshi
- Tao Lin
- Dominic Richards
- Patrick Rebeschini
- Suhas N. Diggavi
Citations in the corpus
- Don't Use Large Mini-Batches, Use Local SGD (2018, background): “Also in [10] the authors argue to average more frequently at the beginning.”
- Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms (2018, background): “uted and consensus optimization community (Tsitsiklis et al., 1986; Nedic & Ozdaglar, 2009; Duchi et al., 2012; Tsianos et al., 2012; Zeng & Yin, 2016; Yuan et al., 2016; Sirb & Ye, 2018; Bijral et al., 2017). Most of these works are for gradient descent or dual averaging methods rather ”
- Local SGD Converges Fast and Communicates Little (2018, background): “[22] for perceptron training (iterative parameter mixing), see also [7], [5, 46, 48] for the training of deep neural networks (model averaging) or in federated learning [23].”
- Optimal Statistical Rates for Decentralised Non-Parametric Regression with Linear Speed-Up (2019, background): “The authors in [6] investigate the interplay between the spectral norm of the data-generating distribution and the inverse spectral gap of the communication matrix for Distributed Stochastic Gradient Descent in the case of strongly convex losses.”