Pandora's Box with Correlations: Learning and Approximation
summary
Shows that with only sample access to an unknown joint distribution over costs it is possible to learn a partially adaptive probing policy that is provably near optimal using polynomially many samples and efficient computation. Uses an LP over sampled scenarios plus rounding to produce a fixed probe order paired with a myopic stopping rule that guarantees a factor-two approximation and extends to up to K selections and matroids with a logarithmic dependence. Overall yields polynomial sample complexity and matching hardness bounds.
AI-written summary · about
chapters (10)
- 0:00Intro
- 2:22PANDORA'S BOX PROBLEM: MINIMIZATION VERSION
- 3:12WEITZMAN'S SOLUTION
- 5:47FULLY ADAPTIVE SOLUTIONS
- 7:38BUT CORRELATED COSTS ARE HOPELESS!
- 10:48PARTIALLY ADAPTIVE PROBING STRATEGIES
- 14:08MAIN RESULT
- 21:23EFFICIENT OPTIMIZATION OVER C
- 26:24A RECAP OF OUR RESULTS
- 30:48CONCLUDING THOUGHTS
related talks
48mFrom Predictions to Decisions: Limitations and Possibilities of Optimization from Samples
38mMulti-objective Learning: An Algorithmic Toolbox for Optimal Predictions Anytime Anywhere!
31mLearning to Control Unknown Systems
40mApproximation Algorithms for Optimization under Uncertainty
01h 08mData Driven Optimization Models and Algorithms
30mBuying Data Over Time: Approximately Optimal Strategies for Dynamic Data-Driven Decisions
01h 14mCompetitive Analysis Meets Stochastic Input: Secretary Problems And Prophet Inequalities
45mCharting the Landscape of Memory/Data Tradeoffs in Continuous Optimization: ...