Stability and Convergence Trade-Off of Iterative Optimization Algorithms

on YouTube ↗28m

" summary

Paper proves a quantitative trade-off between algorithmic stability and optimization convergence, using jackknife-style data perturbations, Le Cam minimax lower bounds and empirical plots on logistic regression. Stability upper bounds show stability scales linearly with T for gradient descent but scales as T^2 for Nesterov/accelerated and heavy‑ball (quadratic or piecewise‑quadratic losses), so early stopping choices differ: T ≈ √n for GD versus T ≈ n1/4 for accelerated methods to reach the same estimation error. Empirically stability tracks test error on large problems while uniform bounds do not.

AI-written summary · about

" chapters (20)

1. 0:00Intro
2. 1:24Stability of Knowledge
3. 2:37Stability Principle
4. 4:54Iterative Learning Algorithms
5. 6:58Supervised Learning Setting
6. 7:51Excess Risk Decomposition
7. 9:53Generalization error bounds
8. 10:51Algorithmic stability
9. 11:20Main Results (Tradeoff)
10. 12:27Convergence Rate and Stability Rate
11. 12:40Tradeoff for GD and NAG
12. 15:14Convergence Lower Bound
13. 16:01Types of Lower Bound
14. 16:58Case study: Gradient Descent
15. 17:44Stability and Convergence Trade-off under Convex Smooth Loss
16. 18:09Outline
17. 19:36Stability vs. Uniform Convergence
18. 20:18Small-scale Logistic regression
19. 21:42Large-scale Logistic regression
20. 23:18Summary

" related talks

• 01h 18mOptimization IBen Recht · Big Data Boot Camp 2013
• 13mNon-Parametric Convergence Rates for Plain Vanilla Stochastic Gradient DescentRaphaël Berthier · Deep Learning Theory Symposium 2021
• 01h 01mRobustness, Stochastics, Uncertainty 2Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 01h 23mImplicit Regularization IINati Srebro · Deep Learning Boot Camp 2019
• 05mNon-monotonic convergence of gradient descent with large stepsizeJingfeng Wu · 9th Annual Simons Institute Industry Day
• 01h 07mOptimization Crash Course (continued)Ashia Wilson · Geometric Methods in Optimization and Sampling Boot Camp
• 41mGeneralization Bounds for Uniformly Stable AlgorithmsVitaly Feldman · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 58mContinuous Methods 2Maryam Fazel, Lorenzo Orecchia, Stefanie Jegelka · Bridging Continuous and Discrete Optimization Boot Camp 2017