Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programming

How to solve high-dimensional linear programs (LPs) efficiently is a fundamental question.Recently, there has been a surge of interest in reducing LP sizes using *random projections*, which can accelerate solving LPs independently of improving LP solvers. This paper explores a new direction of *data-driven projections*, which use projection matrices learned from data instead of random projection matrices.Given training data of n -dimensional LPs, we learn an n\times k projection matrix with n k . When addressing a future LP instance, we reduce its dimensionality from n to k via the learned projection matrix, solve the resulting LP to obtain a k -dimensional solution, and apply the learned matrix to it to recover an n -dimensional solution.On the theoretical side, a natural question is: how much data is sufficient to ensure the quality of recovered solutions? We address this question based on the framework of *data-driven algorithm design*, which connects the amount of data sufficient for establishing generalization bounds to the *pseudo-dimension* of performance metrics. We also provide an \Omega(nk) lower bound, implying our result is tight up to an \tilde{\mathrm{O}}(k) factor.