Tight analyses of first-order methods with error feedback, in homogeneous and heterogeneous setups
summary
Provides tight, sometimes numerically exact, convergence rates for compressed gradient descent, EF and EF21 by searching for optimal Lyapunov functions via performance estimation, SDP lifting and interpolation constraints, then turning SDP solutions into closed forms with rank heuristics and symbolic regression. Builds a PePIt-based UI plus Mathematica certificates that verify hundreds to thousands of cases; empirical laws match high‑degree polynomial roots. Key surprise: EF and EF21 dominated by compressed GD in many setups, and the method exposes the exact dual multipliers used in proofs.
AI-written summary · about
chapters (8)
- 0:00Computer-assisted optimization proofs
- 9:53Tight optimization theory
- 13:39Performance estimation crash course
- 28:24Lyapunov functions and dual certificates
- 39:19Error feedback in federated learning
- 44:49Rate computation UI
- 48:28Error feedback results
- 52:07Numerical and formal verification
related talks
01h 13mTutorial: Federated Optimization, Part II
01h 01mRobustness, Stochastics, Uncertainty 2
01h 18mOptimization I
01h 07mOptimization Crash Course (continued)
42mOptimization Crash Course
01h 05mFirst-Order Optimization and Online Learning Techniques in the Design of Fast Spectral Algorithms
01h 06mAnalytic Methods for Supervised Learning III
01h 05mTutorial: Federated Optimization, Part III