A Few Connections Between Optimization and Probability

on YouTube ↗33m

" summary

Claims an iff equivalence: a martingale inequality holds for all martingale difference sequences exactly when there exists a function U satisfying domination, U(empty)<0 and an averaging (concavity) property, with U definable as a supremum over random continuations. Uses the Burkholder method to convert that U into an online predictor (predict = gradient of U at zero) that attains regret matching the empirical Rademacher complexity rather than the looser sqrt(sum of squared gradients) from mirror descent. Shows the needed decoupling/zigzag concavity for matrix completion and suggests SOS search to find usable U.

AI-written summary · about

" chapters (9)

1. 0:00Introduction to Burkholder
2. 0:36Motivation: Online Learning
3. 4:36Limitations of Convex Methods
4. 9:01The Need for New Geometry
5. 11:24Burkholder Method Explained
6. 13:59Martingale Inequalities
7. 20:30Example: Smoothness
8. 25:27Rademacher Bound Derivation
9. 29:49Conclusion and Q&A

" related talks

• 01h 01mRobustness, Stochastics, Uncertainty 2Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 34mMatrix Martingales in Randomized Numerical Linear AlgebraRasmus Kyng · Randomized Numerical Linear Algebra and Applications 2018
• 01h 01mRobustness, Stochastics, Uncertainty 1Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 01h 18mOptimization IBen Recht · Big Data Boot Camp 2013
• 01h 00mMin-Max Optimization from a Dynamical Systems ViewpointPanayotis Mertikopoulos · Adversarial Approaches in Machine Learning 2022
• 22mA formalization of Doob's martingale convergence theorems in mathlibKexing Ying, Rémy Degenne · CPP 2023
• 57mBlackwell’s Approachability TheoremRakesh Vohra · Data-Driven Decision Processes Boot Camp 2022
• 48mFrom Predictions to Decisions: Limitations and Possibilities of Optimization from SamplesYaron Singer · Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016)