This paper studies a simple data-driven approach to high-dimensional linear
programs (LPs). Given data of past $n$-dimensional LPs, we learn an $n\times k$
\textit{projection matrix} ($n > k$), which reduces the dimensionality from $n$
to $k$. Then, we address future LP instances by solving $k$-dimensional LPs and
recovering $n$-dimensional solutions by multiplying the projection matrix. This
idea is compatible with any user-preferred LP solvers, hence a versatile
approach to faster LP solving. One natural question is: how much data is
sufficient to ensure the recovered solutions' quality? We address this question
based on the idea of \textit{data-driven algorithm design}, which relates the
amount of data sufficient for generalization guarantees to the
\textit{pseudo-dimension} of performance metrics. We present an
$\tilde{\mathrm{O}}(nk^2)$ upper bound on the pseudo-dimension
($\tilde{\mathrm{O}}$ compresses logarithmic factors) and complement it by an
$\Omega(nk)$ lower bound, hence tight up to an $\tilde{\mathrm{O}}(k)$ factor.
On the practical side, we study two natural methods for learning projection
matrices: PCA- and gradient-based methods. While the former is simple and
efficient, the latter sometimes leads to better solution quality. Experiments
confirm that learned projection matrices are beneficial for reducing the time
for solving LPs while maintaining high solution quality.

该研究论文通过数据驱动方法，研究了高维线性规划问题，通过学习投影矩阵来降低维度，并探讨了数据量与解决方案质量之间的关系，同时研究了两种学习投影矩阵的方法及其在优化问题中的应用。