Robust Optimization and Generalization

on YouTube ↗01h 17m

" summary

A production LP with tiny input shifts (about 0.5%–2%) shows losses of 15%–20% when reusing the same plan; a robust LP that enforces rowwise perturbations certifies at most ~6% loss. Chance constraints get a convex safe approximation via the hinge/perspective transform, giving CVaR as the tight surrogate and analyzable SOCP penalties like sqrt(sum Ui^2 xi^2)·sqrt(2 log(1/δ)). Distributionally robust sets (Wasserstein balls) recover familiar regularizers and offer provable but sometimes conservative generalization certificates.

AI-written summary · about

" chapters (8)

1. 0:00Robust optimization intro
2. 1:31Classical robust foundations
3. 28:52Robust linear programming
4. 42:31Chance constrained techniques
5. 57:55Portfolio optimization
6. 1:00:44Distributionally robust overview
7. 1:13:18Key takeaways
8. 1:15:05Q&A

" related talks

• 34mDistributional Robustness, Learning, and Empirical LikelihoodJohn Duchi · Optimization, Statistics and Uncertainty
• 46mCan Non-Convex Optimization be Robust?Rong Ge · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 01h 01mRobustness, Stochastics, Uncertainty 2Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 12mDistribution-Free RobustnessSitan Chen · Meet the Fellows Welcome Event
• 09mLearning Under RequirementsLuiz Chamon · Meet the Fellows Welcome Event
• 01h 01mRobustness, Stochastics, Uncertainty 1Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 35mOnline Optimization and Learning Under Long-Term Convex Constraints and ObjectivesNikhil Devanur · Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016)
• 01h 24mAdversarial ExamplesSebastien Bubeck · Deep Learning Boot Camp 2019