Consensus-Based Distributed Online Prediction and Optimization
Talkat Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013) · 2013-10-21..10-24·
summary
Claims order O(√M) regret when using distributed mini‑batches with only approximate averaging, builds on Nesterov dual averaging and replaces exact all‑reduce with gossip‑based approximate averaging. Uses per‑round mini‑batches size B and runs K gossip iterations so the consensus error stays below Δ; K scales with log(1/Δ) and with √N/(1−λ2) (spectral gap). For good graphs (expanders) latency μ is ≈ O(log N) and the algorithm matches the serial rate.
AI-written summary · about
chapters (12)
- 0:00Intro
- 0:28Stochastic Online Prediction
- 1:59Problem Formalization
- 3:11Distributed Online Prediction
- 5:55Mini-batch Updates
- 7:34Distributed Mini-Batch Algorithm
- 11:35Approximate Distributed Averaging
- 13:06Gossip Algorithms
- 18:11Distributed Dual Averaging with Approximate Mini-Batches (DDA-AMB)
- 20:37When do Approximate Mini-Batches Work? Theorem (Tsianos & MR): Run DDA-AMB with
- 24:35Distributed Stochastic Optimization
- 27:03Conclusions
related talks
44mParsimonious Learning-Augmented Algorithms
30mOnline Paging with a Vanishing Regret
01h 01mRobustness, Stochastics, Uncertainty 2
58mMemory-Regret Tradeoff for Online Learning
49mOracle-Efficient Online Learning or: How to Use Non-Robust Optimization for Robust Learning
33mTradeoffs in Large Scale Learning: Statistical Accuracy vs. Numerical Precision
01h 28mMulti-Distribution Learning, for Robustness, Fairness, and Collaboration
33mOnline Multivalid Learning: Means, Moments, and Prediction Intervals