Limited Communication Gradient Methods for Distributed Resource Allocation Optimization

on YouTube ↗43m

" summary

Distributed dual-gradient methods can run with very low communication by broadcasting aggregate imbalance and quantized gradient directions: a one-bit broadcast (sign of imbalance) suffices in 1-D and normalized gradient descent is necessary and sufficient when quantization directions form an angular cover. Minimal per-iteration cost in K dimensions is log2(K+1) bits. Convergence slows to O(1/√T) for fixed low-bit quantization versus unquantized rates, while time-varying coding yields error ~2^{-B}. Enforcing primal feasibility impossible with finite bits; relaxed objective-only guarantees work and simulations (including one-bit voltage control) validate the approach.

AI-written summary · about

" chapters (14)

1. 0:00Introduction and challenges
2. 4:41System modeling
3. 7:19Communication reduction
4. 8:24Resource allocation problem
5. 12:14Quantization techniques
6. 15:40High dimension analysis
7. 18:33Performance limits
8. 20:48Design and convergence
9. 24:03Minimal quantization results
10. 27:37Simulation and constraints
11. 30:42Time varying quantization
12. 35:28Complexity and optimal design
13. 38:23Primal feasibility
14. 40:39Conclusion

" related talks

• 01h 14mDistributed and concurrent optimization for machine learningDan Alistarh · Hydra 2020
• 29mFirst Order Methods for Distributed Network OptimizationAngelia Nedich · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 33mDistributed Learning, Communication Complexity, and PrivacyNina Balcan · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 17mZEN: Empowering Distributed Training with Sparsity-driven Data SynchronizationYuke Wang, T. S. Eugene Ng, Zhuang Wang, Zhaozhuo Xu, Jingyi Xi, Anshumali Shrivastava · OSDI '25
• 26mOn the O(1/k) Convergence of the Asynchronous Distributed Alternating Direction Method of Mult...Ermin Wei · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 30mConsensus-Based Distributed Online Prediction and OptimizationMichael Rabbat · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 31mNear-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking ProblemsShiri Antaki, Quanquan C. Liu, Shay Solomon · ITCS 2022
• 30mOptimal Lower Bounds for Distributed and Streaming Spanning Forest ComputationHuacheng Yu · Interactive Complexity 2018