On the O(1/k) Convergence of the Asynchronous Distributed Alternating Direction Method of Mult...
Talkat Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013) · 2013-10-21..10-24·
summary
Proves an asynchronous distributed ADMM that converges to the optimal solution almost surely and achieves O(1/k) in expectation under convex (not smooth) Fi, with each edge governed by independent Poisson clocks and the mild assumption that every constraint wakes infinitely often. Key tools are a local z-variable decoupling with a closed-form z update, analysis in a probability-weighted norm to handle varying update frequencies, and comparisons showing ADMM needs ~70–140 iterations versus gossip’s 250–700 on small graphs; an image denoising demo takes 87 iterations (35s).
AI-written summary · about
chapters (13)
- 0:00Introduction and motivation
- 1:21Problem formulation
- 3:41Distributed optimization
- 6:06The ADMM framework
- 7:47Standard ADMM mechanics
- 10:01Asynchronous ADMM design
- 12:29Algorithm implementation
- 14:22Computation and communication
- 17:08Convergence analysis
- 18:49Convergence rates
- 20:51Simulation results
- 23:21Application in image denoising
- 24:42Conclusion and future work
related talks
01h 18mOptimization I
58mContinuous Methods 2
01h 02mContinuous Methods 1
10mDumbo-MPC: Efficient Fully Asynchronous MPC with Optimal Resilience
01h 31mIncremental Approximate Message Passing
51mExploiting Similarity in Federated Learning
01h 05mTutorial: Federated Optimization, Part III
58mFirst-Order Stochastic Optimization