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

Non-contrastive methods of self-supervised learning (such as BYOL and
SimSiam) learn representations by minimizing the distance between two views of
the same image. These approaches have achieved remarkable performance in
practice, but the theoretical understanding lags behind. Tian et al. 2021
explained why the representation does not collapse to zero, however, how the
feature is learned still remains mysterious. In our work, we prove in a linear
network, non-contrastive methods learn a desirable projection matrix and also
reduce the sample complexity on downstream tasks. Our analysis suggests that
weight decay acts as an implicit threshold that discards the features with high
variance under data augmentations, and keeps the features with low variance.
Inspired by our theory, we design a simpler and more computationally efficient
algorithm DirectCopy by removing the eigen-decomposition step in the original
DirectPred algorithm in Tian et al. 2021. Our experiments show that DirectCopy
rivals or even outperforms DirectPred on STL-10, CIFAR-10, CIFAR-100, and
ImageNet.

我们的研究表明，非对比自监督学习方法可以通过学习理想的投影矩阵来降低下游任务的样本复杂度，并且我们还设计了一个更简单、更高效的算法 DirectCopy，其可以成功地应用于 STL-10、CIFAR-10、CIFAR-100 和 ImageNet 数据集，表现良好。

通过非对比自我监督实现对表征学习的揭秘

Towards Demystifying Representation Learning with Non-contrastive  Self-supervision

This paper shows how to solve linear programs of the form $\min_{Ax=b,x\geq0}
c^\top x$ with $n$ variables in time
$$O^*((n^{\omega}+n^{2.5-\alpha/2}+n^{2+1/6}) \log(n/\delta))$$ where $\omega$
is the exponent of matrix multiplication, $\alpha$ is the dual exponent of
matrix multiplication, and $\delta$ is the relative accuracy. For the current
value of $\omega\sim2.37$ and $\alpha\sim0.31$, our algorithm takes
$O^*(n^{\omega} \log(n/\delta))$ time. When $\omega = 2$, our algorithm takes
$O^*(n^{2+1/6} \log(n/\delta))$ time.
Our algorithm utilizes several new concepts that we believe may be of
independent interest:
$\bullet$ We define a stochastic central path method.
$\bullet$ We show how to maintain a projection matrix
$\sqrt{W}A^{\top}(AWA^{\top})^{-1}A\sqrt{W}$ in sub-quadratic time under
$\ell_{2}$ multiplicative changes in the diagonal matrix $W$.

本文介绍了一种解决线性规划问题的算法，旨在在对矩阵乘法进行研究后，以次二次时间复杂度解决规模为 n 的问题，同时提出了新的概念，如随机中心路径法和投影矩阵等。