Asymptotic confidence sets for random linear programs

Shuyu Liu, Florentina Bunea, Jonathan Niles-Weed
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3919-3940, 2023.

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 $\mathbb{R}^m$ 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-liu23d, title = {Asymptotic confidence sets for random linear programs}, author = {Liu, Shuyu and Bunea, Florentina and Niles-Weed, Jonathan}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {3919--3940}, year = {2023}, editor = {Neu, Gergely and Rosasco, Lorenzo}, volume = {195}, series = {Proceedings of Machine Learning Research}, month = {12--15 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v195/liu23d/liu23d.pdf}, url = {https://proceedings.mlr.press/v195/liu23d.html}, 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 $\mathbb{R}^m$ 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.} }
Endnote
%0 Conference Paper %T Asymptotic confidence sets for random linear programs %A Shuyu Liu %A Florentina Bunea %A Jonathan Niles-Weed %B Proceedings of Thirty Sixth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Gergely Neu %E Lorenzo Rosasco %F pmlr-v195-liu23d %I PMLR %P 3919--3940 %U https://proceedings.mlr.press/v195/liu23d.html %V 195 %X 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 $\mathbb{R}^m$ 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.
APA
Liu, S., Bunea, F. & Niles-Weed, J.. (2023). Asymptotic confidence sets for random linear programs. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:3919-3940 Available from https://proceedings.mlr.press/v195/liu23d.html.

Related Material