Sketching algorithms have recently proven to be a powerful approach both for
designing low-space streaming algorithms as well as fast polynomial time
approximation schemes (PTAS). In this work, we develop new techniques to extend
the applicability of sketching-based approaches to the sparse dictionary
learning and the Euclidean $k$-means clustering problems. In particular, we
initiate the study of the challenging setting where the dictionary/clustering
assignment for each of the $n$ input points must be output, which has
surprisingly received little attention in prior work. On the fast algorithms
front, we obtain a new approach for designing PTAS's for the $k$-means
clustering problem, which generalizes to the first PTAS for the sparse
dictionary learning problem. On the streaming algorithms front, we obtain new
upper bounds and lower bounds for dictionary learning and $k$-means clustering.
In particular, given a design matrix $\mathbf A\in\mathbb R^{n\times d}$ in a
turnstile stream, we show an $\tilde O(nr/\epsilon^2 + dk/\epsilon)$ space
upper bound for $r$-sparse dictionary learning of size $k$, an $\tilde
O(n/\epsilon^2 + dk/\epsilon)$ space upper bound for $k$-means clustering, as
well as an $\tilde O(n)$ space upper bound for $k$-means clustering on random
order row insertion streams with a natural "bounded sensitivity" assumption. On
the lower bounds side, we obtain a general $\tilde\Omega(n/\epsilon +
dk/\epsilon)$ lower bound for $k$-means clustering, as well as an
$\tilde\Omega(n/\epsilon^2)$ lower bound for algorithms which can estimate the
cost of a single fixed set of candidate centers.

通过新技术扩展基于草图的方法，开展了稀疏字典学习和欧氏 k-means 聚类问题的研究，在快速算法方面获得了对 $k$-means 聚类问题的新方法，并推广到稀疏字典学习问题。在流算法方面，得到了字典学习和 $k$-means 聚类的新上界和下界。

稀疏字典学习的素描算法：PTAS 和转轴流式处理

Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile  Streaming

We consider sketching algorithms which first compress data by multiplication
with a random sketch matrix, and then apply the sketch to quickly solve an
optimization problem, e.g., low-rank approximation and regression. In the
learning-based sketching paradigm proposed by~\cite{indyk2019learning}, the
sketch matrix is found by choosing a random sparse matrix, e.g., CountSketch,
and then the values of its non-zero entries are updated by running gradient
descent on a training data set. Despite the growing body of work on this
paradigm, a noticeable omission is that the locations of the non-zero entries
of previous algorithms were fixed, and only their values were learned. In this
work, we propose the first learning-based algorithms that also optimize the
locations of the non-zero entries. Our first proposed algorithm is based on a
greedy algorithm. However, one drawback of the greedy algorithm is its slower
training time. We fix this issue and propose approaches for learning a
sketching matrix for both low-rank approximation and Hessian approximation for
second order optimization. The latter is helpful for a range of constrained
optimization problems, such as LASSO and matrix estimation with a nuclear norm
constraint. Both approaches achieve good accuracy with a fast running time.
Moreover, our experiments suggest that our algorithm can still reduce the error
significantly even if we only have a very limited number of training matrices.

本文提出了优化稀疏矩阵的学习算法，通过优化矩阵中非零项的位置和值来实现低秩逼近、回归和二阶优化。

学习 CountSketch 中的位置

Learning the Positions in CountSketch

Matrix trace estimation is ubiquitous in machine learning applications and
has traditionally relied on Hutchinson's method, which requires
$O(\log(1/\delta)/\epsilon^2)$ matrix-vector product queries to achieve a $(1
\pm \epsilon)$-multiplicative approximation to $\text{tr}(A)$ with failure
probability $\delta$ on positive-semidefinite input matrices $A$. Recently, the
Hutch++ algorithm was proposed, which reduces the number of matrix-vector
queries from $O(1/\epsilon^2)$ to the optimal $O(1/\epsilon)$, and the
algorithm succeeds with constant probability. However, in the high probability
setting, the non-adaptive Hutch++ algorithm suffers an extra
$O(\sqrt{\log(1/\delta)})$ multiplicative factor in its query complexity.
Non-adaptive methods are important, as they correspond to sketching algorithms,
which are mergeable, highly parallelizable, and provide low-memory streaming
algorithms as well as low-communication distributed protocols. In this work, we
close the gap between non-adaptive and adaptive algorithms, showing that even
non-adaptive algorithms can achieve $O(\sqrt{\log(1/\delta)}/\epsilon +
\log(1/\delta))$ matrix-vector products. In addition, we prove matching lower
bounds demonstrating that, up to a $\log \log(1/\delta)$ factor, no further
improvement in the dependence on $\delta$ or $\epsilon$ is possible by any
non-adaptive algorithm. Finally, our experiments demonstrate the superior
performance of our sketch over the adaptive Hutch++ algorithm, which is less
parallelizable, as well as over the non-adaptive Hutchinson's method.

本文研究了矩阵迹估计的算法，提出了 Hutch++ 以及一种新的非自适应算法，通过实验证明了该算法的优越性。