More Like this

1. Is local SGD better than minibatch SGD?

   Woodworth, Blake; Patel, Kumar Kshitij; Stich, Sebastian U; Dai, Zhen; Bullins, Brian; McMahan, H. Brendan; Shamir, Ohad; Srebro, Nathan (November 2020, International Conference on Machine Learning)

   null (Ed.)
2. Fitting ReLUs via SGD and Quantized SGD

   Mousavi Kalan, Seyed Mohammadreza; Soltanolkotabi, Mahdi; Avestimehr, Salman (January 2019, IEEE International Symposium on Information Theory (ISIT))

   In this paper we focus on the problem of finding the optimal weights of the shallowest of neural networks consisting of a single Rectified Linear Unit (ReLU). These functions are of the form x → max(0,⟨w,x⟩) with w ∈ Rd denoting the weight vector. We focus on a planted model where the inputs are chosen i.i.d. from a Gaussian distribution and the labels are generated according to a planted weight vector. We first show that mini-batch stochastic gradient descent when suitably initialized, converges at a geometric rate to the planted model with a number of samples that is optimal up to numerical constants. Next we focus on a parallel implementation where in each iteration the mini-batch gradient is calculated in a distributed manner across multiple processors and then broadcast to a master or all other processors. To reduce the communication cost in this setting we utilize a Quanitzed Stochastic Gradient Scheme (QSGD) where the partial gradients are quantized. Perhaps unexpectedly, we show that QSGD maintains the fast convergence of SGD to a globally optimal model while significantly reducing the communication cost. We further corroborate our numerical findings via various experiments including distributed implementations over Amazon EC2. 

   more » « less
3. SQuARM-SGD: Communication-Efficient Momentum SGD for Decentralized Optimization

   https://doi.org/10.1109/JSAIT.2021.3103920  

   Singh, Navjot; Data, Deepesh; George, Jemin; Diggavi, Suhas (September 2021, IEEE Journal on Selected Areas in Information Theory)
4. SQuARM-SGD: Communication-Efficient Momentum SGD for Decentralized Optimization

   Singh, Navjot; Data, Deepesh; George, Jemin; Diggavi, Suhas N. (July 2021, IEEE International Symposium on Information Theory (ISIT))

   null (Ed.)

   In this paper, we study communication-efficient decentralized training of large-scale machine learning models over a network. We propose and analyze SQuARM-SGD, a decentralized training algorithm, employing momentum and compressed communication between nodes regulated by a locally computable triggering rule. In SQuARM-SGD, each node performs a fixed number of local SGD (stochastic gradient descent) steps using Nesterov's momentum and then sends sparisified and quantized updates to its neighbors only when there is a significant change in its model parameters since the last time communication occurred. We provide convergence guarantees of our algorithm for strongly-convex and non-convex smooth objectives. We believe that ours is the first theoretical analysis for compressed decentralized SGD with momentum updates. We show that SQuARM-SGD converges at rate O(1/nT) for strongly-convex objectives, while for non-convex objectives it converges at rate O(1/√nT), thus matching the convergence rate of \emphvanilla distributed SGD in both these settings. We corroborate our theoretical understanding with experiments and compare the performance of our algorithm with the state-of-the-art, showing that without sacrificing much on the accuracy, SQuARM-SGD converges at a similar rate while saving significantly in total communicated bits. 

   more » « less
5. Pipe-SGD: A {Decentralized Pipelined SGD Framework for Distributed Deep Net Training

   Li, Youjie and (January 2018, Neural Information Processing Systems (NurIPS))