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.

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

线性规划降维的数据驱动投影：广义界限和学习方法

Data-Driven Projection for Reducing Dimensionality of Linear Programs:  Generalization Bound and Learning Methods

This paper addresses the problem of nearly optimal Vapnik--Chervonenkis
dimension (VC-dimension) and pseudo-dimension estimations of the derivative
functions of deep neural networks (DNNs). Two important applications of these
estimations include: 1) Establishing a nearly tight approximation result of
DNNs in the Sobolev space; 2) Characterizing the generalization error of
machine learning methods with loss functions involving function derivatives.
This theoretical investigation fills the gap of learning error estimations for
a wide range of physics-informed machine learning models and applications
including generative models, solving partial differential equations, operator
learning, network compression, distillation, regularization, etc.

本研究解决了深度神经网络导函数的最优 Vapnik-Chervonenkis 维度（VC-dimension）和伪维度估计的问题，并将其应用于机器学习方法中涉及函数导数的损失函数的学习误差估计，从而填补了包括物理为基础的机器学习模型和应用程序（例如生成模型、解决偏微分方程、操作学习、网络压缩、提取、正则化等）的学习误差估计的空白。

深度神经网络导数的近似最优 VC 维度和伪维度上界

Nearly Optimal VC-Dimension and Pseudo-Dimension Bounds for Deep Neural  Network Derivatives

We characterize the expressive power of quantum circuits with the
pseudo-dimension, a measure of complexity for probabilistic concept classes. We
prove pseudo-dimension bounds on the output probability distributions of
quantum circuits; the upper bounds are polynomial in circuit depth and number
of gates. Using these bounds, we exhibit a class of circuit output states out
of which at least one has exponential state complexity, and moreover
demonstrate that quantum circuits of known polynomial size and depth are
PAC-learnable.

本文采用伪维度来表征量子电路的表达能力，并证明了量子电路输出概率分布的伪维度上界多项式上界，由此证明了已知多项式尺寸和深度的量子电路是可 PAC 学习的一个电路输出状态类中至少有一个状态具有指数级状态复杂度。