Contextual Inverse Optimization: Offline and Online Learning

on YouTube ↗43m

" summary

Characterizes offline performance by fitting costs on the unit sphere and computing an uncertainty angle (circumcenter gives the minimax proxy); develops an online algorithm that replaces polyhedral knowledge sets with ellipsoidal cones, uses shallow cuts and subspace projections, and proves the first regret bound that is logarithmic in the horizon (previous work had O(sqrt(T)); bound scales roughly like d^2 log T times a geometry factor). Assumes noiseless, adversarial feedback and shows simulations outperform prior methods.

AI-written summary · about

" chapters (15)

1. 0:00Intro
2. 0:39Contextual Inverse Optimization
3. 3:06Problem Formulation
4. 4:32Related Literature: Inverse Optimization
5. 6:46Offline Setting: The Data
6. 9:20Offline Learning in an Adversarial Setting
7. 15:06Online Setting: The Data
8. 16:16The Decision-Maker Does Not Control the Feedback
9. 18:42The Circumcenter Policy Fails in the Online Setting
10. 20:33What Control Do We Have?
11. 22:37Inverse Exploration
12. 23:16The Circumcenter Trap
13. 29:35Summary of Online Learning Results
14. 30:47Takeaways
15. 38:16Marketplace Interference (w/ Ido Bright, Arthur Delarue)

" related talks

• 35mOnline Optimization and Learning Under Long-Term Convex Constraints and ObjectivesNikhil Devanur · Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016)
• 35mOnline Learning with A Lot of Batch DataShie Mannor · Reinforcement Learning from Batch Data and Simulation
• 43mOnline Learning via Offline Greedy Algorithms: Applications in Market Design and OptimizationNegin Golrezaei · Data-Driven Decision Processes Boot Camp 2022
• 31mOnline Reinforcement Learning With The Help Of Confounded Offline DataUri Shalit · Learning from Interventions 2022
• 48mOnline Adversarial Multicalibration And (Multi)CalibeatingAaron Roth · Adversarial Approaches in Machine Learning 2022
• 01h 01mRobustness, Stochastics, Uncertainty 2Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 34mUniform Offline Policy Evaluation (OPE) and Offline Learning in Tabular RLYu-Xiang Wang · Reinforcement Learning from Batch Data and Simulation
• 42mBypassing the Impossibility of Online Learning Thresholds: Unbounded Losses and Transductive PriorsNikita Zhivotovskiy · Joint IFML/MPG Symposium 2024