First Order Methods for Distributed Network Optimization
Talkat Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013) · 2013-10-21..10-24·
summary
Proposes distributed first‑order methods for minimizing the sum of node objectives over time‑varying directed graphs while removing the hard requirement of doubly stochastic weights by using push-sum / ratio consensus (maintain X and Y, take X/Y). Uses column-stochastic iterations with bounded subgradients and step size ~1/√T, proves convergence with a generic rate of O(log T / sqrt(T)) for convex problems (1/T for strongly convex), is asynchronous/broadcast‑friendly, and shows simulations up to ~9,000 nodes with scaling left inconclusive.
AI-written summary · about
chapters (14)
- 0:00Start
- 1:22Distributed Optimization Problems: Challenges
- 2:15Example: Computing Aggregates in P2P Networks
- 4:06Support Vector Machine (SVM) - Decentralized Case
- 5:03Consensus Problem
- 6:55Dynamic Network Topology
- 7:53Weight Matrices
- 9:09Basic Result
- 10:42General Multi-Agent Model
- 11:05Distributed Optimization Algorithm
- 15:21Model without Doubly Stochastic Weights
- 17:53Convergence Result
- 21:03Related Work: Static Network
- 21:40Convergence Rate
related talks
19mDistributed load balancing: a new framework and improved guarantees
17mSolving Max-Min Fair Resource Allocations Quickly on Large Graphs
43mLimited Communication Gradient Methods for Distributed Resource Allocation Optimization
31mNear-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems
51mExploiting Similarity in Federated Learning
39mSketching and Randomization for Distributed Submodular and Coverage Optimization
46mDistributed Graph Techniques in the MPC Model
53mOptimal Power Flow: Relaxation, Online Algorithm, Fast Dynamics