From Predictions to Decisions: Limitations and Possibilities of Optimization from Samples

on YouTube ↗48m

" summary

Shows that coverage functions (and many submodular examples like influence maximization) are PMAC-learnable yet provably fail to yield good decisions when optimization uses only random samples: there is no constant-factor approximation from samples and the construction gives an explicit n^{-1/4} lower bound (exponential universe; compact universe still non‑constant), built via partitioned coverage primitives, binomial-based gadgets, a matrix invertibility/Hadamard argument and a curvature parameter; additive and unit‑demand exceptions and an n^{-1/3} upper bound for submodular cases also appear.

AI-written summary · about

" chapters (24)

1. 0:00Intro
2. 1:07DECIDING HOW TO DRIVE TO MIT
3. 2:39SHORTEST PATHS IS ROBUST TO SMALL ESTIMATION ERRORS
4. 3:08DECIDING WHO TO SELECT TO SPREAD INFORMATION
5. 5:07INFLUENCE MAXIMIZATION IS NOT ROBUST TO ESTIMATION ERRORS
6. 7:31FROM OBSERVATIONS TO DECISIONS
7. 8:37THE MAIN QUESTION
8. 8:57LEARNABILITY OF FUNCTIONS
9. 10:42ALL HELL BREAKS LOOSE IN THE PRESENCE OF ERORR
10. 12:40OPTIMAL GUARANTEES ARE ACHIEVABLE UNDER NOISE
11. 16:00DATA-DRIVEN OPTIMIZATION
12. 16:50FORMULATING A MEANINGFUL QUESTION
13. 18:56MAIN RESULT:OPTIMIZATION FROM SAMPLES IS GENERALLY IMPOSSIBLE
14. 30:15INFORMATION-THEORETIC LOWER
15. 31:56BOUNDS FOR COVERAGE IN OPS
16. 35:58GOOD AND BAD VIA A SYSTEM OF LINEAR EQUATIONS
17. 37:11CONSTRUCTING C
18. 37:41COMPACT COVERAGE FUNCTIONS
19. 38:01FROM UNIFORM TO GENERAL DISTRIBUTIONS
20. 38:19MAIN RESULT: OPTIMIZATION FROM SAMPLES IS HARD
21. 39:18TIGHT RESULTS FOR XOS FUNCTIONS
22. 39:51ADDITIVE AND UNIT DEMAND ARE OPS
23. 42:09TIGHT BOUNDS FOR CURVATURE
24. 42:30CONCLUSIONS

" related talks

• 01h 04mSubmodularity: Theory and Applications IStefanie Jegelka · Foundations of Machine Learning Boot Camp 2017
• 01h 04mSubmodularity: Theory and Applications IIAndreas Krause · Foundations of Machine Learning Boot Camp 2017
• 34mPandora's Box with Correlations: Learning and ApproximationShuchi Chawla · Mathematics of Online Decision Making 2020
• 42mLearning What Works Best WhenSwati Gupta · Real-Time Decision Making 2018
• 33mA Few Connections Between Optimization and ProbabilitySasha Rakhlin · Optimization, Statistics and Uncertainty
• 29mPure Exploration ProblemsWouter Koolen · Mathematics of Online Decision Making 2020
• 28mConfounding-Robust Policy Evaluation In Infinite-Horizon Reinforcement LearningAngela Zhou · Algorithmic Aspects of Causal Inference 2022
• 45mCharting the Landscape of Memory/Data Tradeoffs in Continuous Optimization: ...Gregory Valiant · Rigorous Evidence for Information-Computation Trade-offs