Robustness, Stochastics, Uncertainty 2

on YouTube ↗01h 01m

" summary

Shows that projected SGD and online linear optimization give a deterministic 1/√N regret for bounded gradients and that an adaptive stepsize (Adagrad-style) yields an upper bound matching the empirical Rademacher complexity for L2 geometry. Uses two-line projection proofs, dynamic-programming min–max rollbacks and softmax relaxations to recover exponential weights and √(log D / N) expert bounds. Points out a remaining gap: existence of an optimal Burkholder function is known for spectral norm but an efficient algorithm to evaluate it for matrix completion is still open.

AI-written summary · about

" chapters (8)

1. 0:00Introduction
2. 11:17The Grand Goal
3. 27:05Onlinesupervised learning
4. 28:47Dynamic programming
5. 46:00Results
6. 47:26MinMax
7. 53:20Randomization
8. 55:13Online Linear Optimization

" related talks

• 58mFirst-Order Stochastic OptimizationRachel Ward · Foundations of Data Science Boot Camp 2018
• 01h 18mOptimization IBen Recht · Big Data Boot Camp 2013
• 01h 07mOptimization Crash Course (continued)Ashia Wilson · Geometric Methods in Optimization and Sampling Boot Camp
• 01h 05mOptimization for Machine Learning IElad Hazan · Foundations of Machine Learning Boot Camp 2017
• 33mTradeoffs in Large Scale Learning: Statistical Accuracy vs. Numerical PrecisionSham Kakade · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 46mSmooth Nonconvex Min-Max OptimizationMeisam Razaviyayn · Adversarial Approaches in Machine Learning 2022
• 42mWhat (Doesn't) Make Learning Algorithms Generalize?Roi Livni · Lower Bounds, Learning, and Average-Case Complexity
• 01h 04mOptimization for Machine Learning IIElad Hazan · Foundations of Machine Learning Boot Camp 2017