First-Order Optimization and Online Learning Techniques in the Design of Fast Spectral Algorithms

on YouTube ↗01h 05m

" summary

First-order iterative methods combine multiplicative weight updates and gradient descent (plus regularizers like entropy or sqrt(p)) to convert Laplacian-based graph tasks into cheap black‑box queries of value and gradient. Claims: non‑smooth needs Θ(1/ε^2) iterations, smooth gradient descent Θ(1/ε), and a primal‑dual blend (Nesterov) achieves Θ(1/√ε). Tools: smoothness/strong convexity, potential‑function regret analysis, regularization. Concrete outcomes: recovers matrix concentration proofs, yields BSS‑style linear sparsifiers via a special regularizer, and improves packing LPs from 1/ε^2 to 1/ε.

AI-written summary · about

" chapters (25)

1. 0:00Intro
2. 1:02Applying the Laplacian Paradigm
3. 3:34A Modern Design Toolkit
4. 7:22Convex Optimization Setup: Analysis COMPUTATIONAL MODEL
5. 8:23Convex Optimization Setup: Assumptions
6. 12:28Outline
7. 15:57Gradient Descent Step
8. 17:19Example: Euclidean Gradient Descent
9. 17:56Smooth Convex Optimization
10. 20:04Gradient Descent Iteration
11. 21:27Analysis of Gradient Descent
12. 24:40Limitations of Gradient Descent
13. 25:15Limitations : Conceptual Example
14. 26:49Conceptual Example + Dual Averaging
15. 27:37Non-Smooth Setup: Dual Approach
16. 29:02Duality Gap for Dual Averaging
17. 30:31Reduction to Online Linear Minimization
18. 35:18Simplex Case: Learning with Experts
19. 36:13Simplex Case: Multiplicative Weight Updates
20. 44:55Regularization 101
21. 49:42Regularized Update: Definition
22. 51:54Completing the Analysis
23. 52:16Follow the Regularized Leader
24. 53:53Different Regularizers in Algorithm Design QUESTION
25. 58:26Nesterov's Algorithm: Review

" related talks

• 58mFirst-Order Stochastic OptimizationRachel Ward · Foundations of Data Science Boot Camp 2018
• 01h 18mOptimization IBen Recht · Big Data Boot Camp 2013
• 29mImplicit Regularization in Nonconvex Statistical EstimationYuxin Chen · Optimization, Statistics and Uncertainty
• 01h 01mRobustness, Stochastics, Uncertainty 2Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 46mSmooth Nonconvex Min-Max OptimizationMeisam Razaviyayn · Adversarial Approaches in Machine Learning 2022
• 01h 07mOptimization Crash Course (continued)Ashia Wilson · Geometric Methods in Optimization and Sampling Boot Camp
• 01h 12mStochastic Second Order Optimization Methods IIFred Roosta · Foundations of Data Science Boot Camp 2018
• 01h 05mOptimization for Machine Learning IElad Hazan · Foundations of Machine Learning Boot Camp 2017