Abstract
Motivated by the statistical analysis of the discrete optimal transport problem, we prove distributional limits for the solutions of linear programs with random constraints. Such limits were first obtained by Klatt, Munk, & Zemel (2022), but their expressions for the limits involve a computationally intractable decomposition of Rm into a possibly exponential number of convex cones. We give a new expression for the limit in terms of auxiliary linear programs, which can be solved in polynomial time. We also leverage tools from random convex geometry to give distributional limits for the entire set of random optimal solutions, when the optimum is not unique. Finally, we describe a simple, data-driven method to construct asymptotically valid confidence sets in polynomial time.
Original language | English (US) |
---|---|
Pages (from-to) | 3919-3940 |
Number of pages | 22 |
Journal | Proceedings of Machine Learning Research |
Volume | 195 |
State | Published - 2023 |
Event | 36th Annual Conference on Learning Theory, COLT 2023 - Bangalore, India Duration: Jul 12 2023 → Jul 15 2023 |
Keywords
- Linear programming
- confidence sets
- distributional inference
ASJC Scopus subject areas
- Artificial Intelligence
- Software
- Control and Systems Engineering
- Statistics and Probability