We consider the problem of training a multi-layer over-parametrized neural
networks to minimize the empirical risk induced by a loss function. In the
typical setting of over-parametrization, the network width $m$ is much larger
than the data dimension $d$ and number of training samples $n$
($m=\mathrm{poly}(n,d)$), which induces a prohibitive large weight matrix $W\in
\mathbb{R}^{m\times m}$ per layer. Naively, one has to pay $O(m^2)$ time to
read the weight matrix and evaluate the neural network function in both forward
and backward computation. In this work, we show how to reduce the training cost
per iteration, specifically, we propose a framework that uses $m^2$ cost only
in the initialization phase and achieves a truly subquadratic cost per
iteration in terms of $m$, i.e., $m^{2-\Omega(1)}$ per iteration.
To obtain this result, we make use of various techniques, including a shifted
ReLU-based sparsifier, a lazy low rank maintenance data structure, fast
rectangular matrix multiplication, tensor-based sketching techniques and
preconditioning.

本文提出了一种降低神经网络训练成本的框架，其中使用各种技术，包括基于 ReLU 的稀疏化器、低秩数据结构、矩形矩阵乘法、张量草图技术和预处理，实现每次迭代的真正次二次成本。

在亚二次时间内训练多层过参数化神经网络

Training Multi-Layer Over-Parametrized Neural Network in Subquadratic  Time

We study algorithmic and structural aspects of connectivity in hypergraphs.
Given a hypergraph $H=(V,E)$ with $n = |V|$, $m = |E|$ and $p = \sum_{e \in E}
|e|$ the best known algorithm to compute a global minimum cut in $H$ runs in
time $O(np)$ for the uncapacitated case and in $O(np + n^2 \log n)$ time for
the capacitated case. We show the following new results.
1. Given an uncapacitated hypergraph $H$ and an integer $k$ we describe an
algorithm that runs in $O(p)$ time to find a subhypergraph $H'$ with sum of
degrees $O(kn)$ that preserves all edge-connectivities up to $k$ (a
$k$-sparsifier). This generalizes the corresponding result of Nagamochi and
Ibaraki from graphs to hypergraphs. Using this sparsification we obtain an $O(p
+ \lambda n^2)$ time algorithm for computing a global minimum cut of $H$ where
$\lambda$ is the minimum cut value.
2. We generalize Matula's argument for graphs to hypergraphs and obtain a
$(2+\epsilon)$-approximation to the global minimum cut in a capacitated
hypergraph in $O(\frac{1}{\epsilon} (p \log n + n \log^2 n))$ time.
3. We show that a hypercactus representation of all the global minimum cuts
of a capacitated hypergraph can be computed in $O(np + n^2 \log n)$ time and
$O(p)$ space.
We utilize vertex ordering based ideas to obtain our results. Unlike graphs
we observe that there are several different orderings for hypergraphs which
yield different insights.

该研究论文研究超图的连通性的算法和结构方面，主要贡献是通过顶点排序的思想，提出了求解最小割、超图稀疏子图和超图全局最小割的高效算法，并且还提出了对所有全局最小割的超环图表示方法。