We consider the problem of learning a latent $k$-vertex simplex
$K\subset\mathbb{R}^d$, given access to $A\in\mathbb{R}^{d\times n}$, which can
be viewed as a data matrix with $n$ points that are obtained by randomly
perturbing latent points in the simplex $K$ (potentially beyond $K$). A large
class of latent variable models, such as adversarial clustering, mixed
membership stochastic block models, and topic models can be cast as learning a
latent simplex. Bhattacharyya and Kannan (SODA, 2020) give an algorithm for
learning such a latent simplex in time roughly $O(k\cdot\textrm{nnz}(A))$,
where $\textrm{nnz}(A)$ is the number of non-zeros in $A$. We show that the
dependence on $k$ in the running time is unnecessary given a natural assumption
about the mass of the top $k$ singular values of $A$, which holds in many of
these applications. Further, we show this assumption is necessary, as otherwise
an algorithm for learning a latent simplex would imply an algorithmic
breakthrough for spectral low rank approximation.
At a high level, Bhattacharyya and Kannan provide an adaptive algorithm that
makes $k$ matrix-vector product queries to $A$ and each query is a function of
all queries preceding it. Since each matrix-vector product requires
$\textrm{nnz}(A)$ time, their overall running time appears unavoidable.
Instead, we obtain a low-rank approximation to $A$ in input-sparsity time and
show that the column space thus obtained has small $\sin\Theta$ (angular)
distance to the right top-$k$ singular space of $A$. Our algorithm then selects
$k$ points in the low-rank subspace with the largest inner product with $k$
carefully chosen random vectors. By working in the low-rank subspace, we avoid
reading the entire matrix in each iteration and thus circumvent the
$\Theta(k\cdot\textrm{nnz}(A))$ running time.

研究通过低秩逼近和选择落在小角度距离内的向量，从而避免了在每次迭代中读取整个矩阵的时间成本，从而实现了潜在的 $k$ 个顶点单纯形的简化学习问题。

在输入稀疏时间内学习一个潜在的单纯形

Learning a Latent Simplex in Input-Sparsity Time

This paper introduces the Metric-Free Natural Gradient (MFNG) algorithm for
training Boltzmann Machines. Similar in spirit to the Hessian-Free method of
Martens [8], our algorithm belongs to the family of truncated Newton methods
and exploits an efficient matrix-vector product to avoid explicitely storing
the natural gradient metric $L$. This metric is shown to be the expected second
derivative of the log-partition function (under the model distribution), or
equivalently, the variance of the vector of partial derivatives of the energy
function. We evaluate our method on the task of joint-training a 3-layer Deep
Boltzmann Machine and show that MFNG does indeed have faster per-epoch
convergence compared to Stochastic Maximum Likelihood with centering, though
wall-clock performance is currently not competitive.

本文介绍了度量自由自然梯度（MFNG）算法用于训练玻尔兹曼机，并通过联合训练三层深玻尔兹曼机的任务验证了 MFNG 的更快收敛速度。