Asymptotic confidence sets for random linear programs

Shuyu Liu, Florentina Bunea, Jonathan Niles-Weed

Research output: Contribution to journalConference articlepeer-review

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 languageEnglish (US)
Pages (from-to)3919-3940
Number of pages22
JournalProceedings of Machine Learning Research
Volume195
StatePublished - 2023
Event36th Annual Conference on Learning Theory, COLT 2023 - Bangalore, India
Duration: Jul 12 2023Jul 15 2023

Keywords

  • Linear programming
  • confidence sets
  • distributional inference

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability

Fingerprint

Dive into the research topics of 'Asymptotic confidence sets for random linear programs'. Together they form a unique fingerprint.

Cite this