$\texttt{DoubleSqueeze}$: Parallel Stochastic Gradient Descent with Double-pass Error-Compensated Compression
Hanlin Tang · Chen Yu · Xiangru Lian · Tong Zhang · Ji Liu

Thu Jun 13th 10:10 -- 10:15 AM @ Room 104

A standard approach in large scale machine learning is distributed stochastic gradient training, which requires the computation of aggregated stochastic gradients over multiple nodes on a network. Communication is a major bottleneck in such applications, and in recent years, compressed stochastic gradient methods such as QSGD (quantized SGD) and sparse SGD have been proposed to reduce communication. It was also shown that error compensation can be combined with compression to achieve better convergence in a scheme that each node compresses its local stochastic gradient and broadcast the result to all other nodes over the network in a single pass. However, such a single pass broadcast approach is not realistic in many practical implementations. For example, under the popular parameter-server model for distributed learning, the worker nodes need to send the compressed local gradients to the parameter server, which performs the aggregation. The parameter server has to compress the aggregated stochastic gradient again before sending it back to the worker nodes. In this work, we provide a detailed analysis on this two-pass communication model, with error-compensated compression both on the worker nodes and on the parameter server. We show that the error-compensated stochastic gradient algorithm admits three very nice properties: 1) it is compatible with an \emph{arbitrary} compression technique; 2) it admits an improved convergence rate than the non error-compensated stochastic gradient method such as QSGD and sparse SGD; 3) it admits linear speedup with respect to the number of workers. The empirical study is also conducted to validate our theoretical results.

Author Information

Hanlin Tang (University of Rochester)
Chen Yu (University of Rochester)
Xiangru Lian (University of Rochester)
Tong Zhang (Tecent AI Lab)
Tong Zhang

Tong Zhang is a professor of Computer Science and Mathematics at the Hong Kong University of Science and Technology. His research interests are machine learning, big data and their applications. He obtained a BA in Mathematics and Computer Science from Cornell University, and a PhD in Computer Science from Stanford University. Before joining HKUST, Tong Zhang was a professor at Rutgers University, and worked previously at IBM, Yahoo as research scientists, Baidu as the director of Big Data Lab, and Tencent as the founding director of AI Lab. Tong Zhang was an ASA fellow and IMS fellow, and has served as the chair or area-chair in major machine learning conferences such as NIPS, ICML, and COLT, and has served as associate editors in top machine learning journals such as PAMI, JMLR, and Machine Learning Journal.

Ji Liu (Kwai Seattle AI lab, University of Rochester)

Ji Liu is an Assistant Professor in Computer Science, Electrical and Computer Engineering, and Goergen Institute for Data Science at University of Rochester (UR). He received his Ph.D. in Computer Science from University of Wisconsin-Madison. His research interests focus on distributed optimization and machine learning. He also has rich experiences in various data analytics applications in healthcare, bioinformatics, social network, computer vision, etc. His recent research focus is on asynchronous parallel optimization, sparse learning (compressed sensing) theory and algorithm, structural model estimation, online learning, abnormal event detection, feature / pattern extraction, etc. He published more than 40 papers in top CS journals and conferences including JMLR, SIOPT, TPAMI, TIP, TKDD, NIPS, ICML, UAI, SIGKDD, ICCV, CVPR, ECCV, AAAI, IJCAI, ACM MM, etc. He won the award of Best Paper honorable mention at SIGKDD 2010 and the award of Best Student Paper award at UAI 2015.

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors