Timezone: »

 
Poster
Distributed Optimization for Overparameterized Problems: Achieving Optimal Dimension Independent Communication Complexity
Bingqing Song · Ioannis Tsaknakis · Chung-Yiu Yau · Hoi-To Wai · Mingyi Hong

Tue Nov 29 09:00 AM -- 11:00 AM (PST) @ Hall J #809
in Poster Session 1 »
Decentralized optimization are playing an important role in applications such as training large machine learning models, among others. Despite its superior practical performance, there has been some lack of fundamental understanding about its theoretical properties. In this work, we address the following open research question: To train an overparameterized model over a set of distributed nodes, what is the {\it minimum} communication overhead (in terms of the bits got exchanged) that the system needs to sustain, while still achieving (near) zero training loss? We show that for a class of overparameterized models where the number of parameters $D$ is much larger than the total data samples $N$, the best possible communication complexity is ${\Omega}(N)$, which is independent of the problem dimension $D$. Further, for a few specific overparameterized models (i.e., the linear regression, and certain multi-layer neural network with one wide layer), we develop a set of algorithms which uses certain linear compression followed by adaptive quantization, and show that they achieve dimension independent, and sometimes near optimal, communication complexity. To our knowledge, this is the first time that dimension independent communication complexity has been shown for distributed optimization.
Keywords: Quantization · Overparameterized Problem · Distributed Optimization

Author Information

Bingqing Song (University of Minnesota)
Ioannis Tsaknakis (University of Minnesota, Minneapolis)
Chung-Yiu Yau (The Chinese University of Hong Kong)
Hoi-To Wai (The Chinese University of Hong Kong)
Mingyi Hong (University of Minnesota)

More from the Same Authors