Deep learning has achieved impressive success in a variety of fields because
of its good generalization. However, it has been a challenging problem to
quickly train a neural network with a large number of layers. The existing
works utilize the locality-sensitive hashing technique or some data structures
on space partitioning to alleviate the training cost in each iteration. In this
work, we try accelerating the computations in each iteration from the
perspective of input data points. Specifically, for a two-layer fully connected
neural network, when the training data have some special properties, e.g.,
Kronecker structure, each iteration can be completed in sublinear time in the
data dimension.

该研究探讨了通过 Kronecker 结构加速训练数据输入的方法，从而在数据维度的次线性时间内完成每次迭代。

具有结构化数据的高效异步随机梯度算法

Efficient Asynchronize Stochastic Gradient Algorithm with Structured  Data

Given a graph $G$ that can be partitioned into $k$ disjoint expanders with
outer conductance upper bounded by $\epsilon\ll 1$, can we efficiently
construct a small space data structure that allows quickly classifying vertices
of $G$ according to the expander (cluster) they belong to? Formally, we would
like an efficient local computation algorithm that misclassifies at most an
$O(\epsilon)$ fraction of vertices in every expander. We refer to such a data
structure as a \textit{spectral clustering oracle}. Our main result is a
spectral clustering oracle with query time $O^*(n^{1/2+O(\epsilon)})$ and
preprocessing time $2^{O(\frac{1}{\epsilon} k^4 \log^2(k))}
n^{1/2+O(\epsilon)}$ that provides misclassification error $O(\epsilon \log k)$
per cluster for any $\epsilon \ll 1/\log k$. More generally, query time can be
reduced at the expense of increasing the preprocessing time appropriately (as
long as the product is about $n^{1+O(\epsilon)}$) -- this in particular gives a
nearly linear time spectral clustering primitive. The main technical
contribution is a sublinear time oracle that provides dot product access to the
spectral embedding of $G$ by estimating distributions of short random walks
from vertices in $G$. The distributions themselves provide a poor approximation
to the spectral embedding, but we show that an appropriate linear
transformation can be used to achieve high precision dot product access. We
then show that dot product access to the spectral embedding is sufficient to
design a clustering oracle. At a high level our approach amounts to hyperplane
partitioning in the spectral embedding of $G$, but crucially operates on a
nested sequence of carefully defined subspaces in the spectral embedding to
achieve per cluster recovery guarantees.

本研究的主要贡献是提出了一种使用子线性时间的谱聚类算法，该算法可以将图按照展开器分簇，并可以提高聚类的准确性，同时通过估计图中节点的随机游走的分布，实现对谱嵌入的点积访问，并使用谱嵌入进行超平面划分，从而实现聚类。

子线性时间下的谱聚类预测器

Spectral Clustering Oracles in Sublinear Time

Let $\mathbf{P}=\{ p_1, p_2, \ldots p_n \}$ and $\mathbf{Q} = \{ q_1, q_2
\ldots q_m \}$ be two point sets in an arbitrary metric space. Let $\mathbf{A}$
represent the $m\times n$ pairwise distance matrix with $\mathbf{A}_{i,j} =
d(p_i, q_j)$. Such distance matrices are commonly computed in software packages
and have applications to learning image manifolds, handwriting recognition, and
multi-dimensional unfolding, among other things. In an attempt to reduce their
description size, we study low rank approximation of such matrices. Our main
result is to show that for any underlying distance metric $d$, it is possible
to achieve an additive error low-rank approximation in sublinear time. We note
that it is provably impossible to achieve such a guarantee in sublinear time
for arbitrary matrices $\mathbf{A}$, and consequently our proof exploits
special properties of distance matrices. We develop a recursive algorithm based
on additive projection-cost preserving sampling. We then show that in general,
relative error approximation in sublinear time is impossible for distance
matrices, even if one allows for bicriteria solutions. Additionally, we show
that if $\mathbf{P} = \mathbf{Q}$ and $d$ is the squared Euclidean distance,
which is not a metric but rather the square of a metric, then a relative error
bicriteria solution can be found in sublinear time.

本文研究了距离矩阵的低秩近似，证明了在任何底层距离度量下，均可以在亚线性时间内实现加性误差的低秩近似，并发展了一种基于投影 - 成本保持抽样的递归算法。同时，在一般情况下，相对误差逼近是不可能的，即使允许二标准解决方案。此外，如果 P = Q 并且 d 是欧几里得平方距离，则可以在亚线性时间内找到相对误差的二标准解决方案。