Beating the Curse of Dimensionality in High-Dimensional Optimal Stopping

on YouTube ↗36m

" summary

Claims a closed-form infinite sum representation of the optimal stopping value and shows truncating after K terms yields a tight error ≤ 1/K guarantee for bounded rewards. Each term is computed by straightforward nested generative-model simulation, so for any fixed additive ε the randomized algorithm runs in time polynomial in the horizon and effectively independent of state dimension. The theory recasts optimal stopping duality as a Max-Flow Min-Cut mapping on a huge tree and yields fast, implementable randomized methods; prototype implementations and financial-application optimizations are under development.

AI-written summary · about

" chapters (12)

1. 0:00Intro
2. 1:16Outline
3. 1:44Motivation
4. 6:44Punchline
5. 13:13RL Connection (cont.)
6. 17:52Model + Prob. Statement
7. 21:25Main intuition
8. 25:52Fast convergence
9. 26:55Algorithmic implications
10. 27:43The max-flow connection and mart. duality
11. 28:37The max-flow connection (cont.)
12. 29:33Future research cont

" related talks

• 01h 01mRobustness, Stochastics, Uncertainty 2Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 01h 00mMin-Max Optimization from a Dynamical Systems ViewpointPanayotis Mertikopoulos · Adversarial Approaches in Machine Learning 2022
• 29mHigh Dimensional Calibration for Rational Decision MakingAaron Roth · Online and Matching-Based Market Design 2023
• 48mComputational-Statistical Tradeoffs in Robust High-Dimensional EstimationIlias Diakonikolas · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 01h 07mOptimization Crash Course (continued)Ashia Wilson · Geometric Methods in Optimization and Sampling Boot Camp
• 54mExact Asymptotics and Universality for Gradient Flows and Empirical Risk MinimizersAndrea Montanari · Deep Learning Theory Symposium 2021
• 42mWhat (Doesn't) Make Learning Algorithms Generalize?Roi Livni · Lower Bounds, Learning, and Average-Case Complexity
• 12mIterative Methods and High-Dimensional StatisticsKevin Tian · Meet the Fellows Welcome Event