Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming

Gregory Dexter, Petros Drineas, David Woodruff, Taisuke Yasuda

Abstract

Sparse Dictionary Learning (SDL) and $k$-means clustering are foundational techniques in unsupervised learning. While approximation schemes for $k$-means are well-established, similar guarantees for SDL have remained elusive. Furthermore, maintaining cluster or dictionary assignments in the challenging turnstile streaming model—where data can be both added and deleted—presents significant space complexity hurdles. This paper presents the first Polynomial Time Approximation Scheme (PTAS) for SDL and establishes near-optimal space bounds for the assignment problem in turnstile streams.

Introduction

In $k$-means clustering, the goal is to partition $n$ data points into $k$ clusters, minimizing the sum of squared distances to the nearest center. Sparse Dictionary Learning (SDL) generalizes this by representing each data point as a linear combination of at most $r$ dictionary atoms from a set of $k$ atoms. Despite their ubiquity, two significant gaps persist in the literature: the lack of a PTAS for SDL and the high memory cost of the "assignment problem" in streaming environments.

The assignment problem involves not just finding the optimal centers or dictionary, but also determining which atoms or clusters correspond to each specific data point. In "turnstile" streams, where entries can be updated arbitrarily, this task becomes particularly difficult. This work addresses these gaps by leveraging a unified toolkit of sketching and coresets.

A PTAS for Sparse Dictionary Learning

The primary theoretical contribution is the first PTAS for SDL. For fixed $k, r,$ and $\epsilon$, the algorithm provides a $(1+\epsilon)$ approximation in polynomial time.

SDL as Projective Clustering

A key insight of this work is that $r$-sparse dictionary learning can be framed as a specific instance of $(l, m)$-projective clustering. In projective clustering, the goal is to find a collection of low-dimensional subspaces that best fit the data. By establishing this connection, the authors adapt advanced coreset techniques originally developed for geometric clustering to the SDL problem.

Coreset Construction

To handle the massive scale of potential data, the algorithm reduces the dataset of $n$ points into a representative "coreset" of size $O(\log n)$. This reduction preserves the objective function's value within a $(1+\epsilon)$ factor for any candidate dictionary. The small size of the coreset allows the use of sophisticated polynomial system solvers, such as Renegar’s algorithm, to find the optimal dictionary atoms in time polynomial in $n$.

The Assignment Problem in Turnstile Streams

In many real-world applications, identifying the dictionary atoms or cluster centers is insufficient; one must also recover the assignments for each data point.

Space Complexity and Lower Bounds

The paper demonstrates that outputting assignments is fundamentally more memory-intensive than simply identifying centers. In a turnstile stream, any algorithm that outputs assignments for $k$-means requires at least $\Omega(n/\epsilon)$ bits of space. This lower bound is derived using reductions from the "Set Disjointness" problem in communication complexity, proving that the $n$ dependency is unavoidable.

Upper Bounds via Sketching

To match these lower bounds, the authors propose a "guess-the-sketch" framework. By maintaining small linear sketches (such as Johnson-Lindenstrauss transforms), the algorithm can verify and refine assignments at the end of the stream. The resulting space complexities are:

  • SDL: $O(nr/\epsilon^2 + dk/\epsilon)$
  • $k$-means: $O(n/\epsilon^2 + dk/\epsilon)$

These results show that the proposed algorithms are nearly tight with respect to the number of points $n$.

Sensitivity and Random Order Streams

The authors further explore how data distribution affects complexity. In "random-order" streams—where the rows of the data matrix arrive in a uniformly random sequence—the space requirements can be relaxed if the data has "bounded sensitivity" (meaning no single point disproportionately affects the total clustering cost). Under these conditions, the $1/\epsilon^2$ penalty in the space complexity can be reduced, achieving $\tilde{O}(n + dk/\epsilon)$ space.

Conclusion

This work provides a robust theoretical framework for SDL and streaming clustering. By bridging the gap between projective clustering and dictionary learning, the authors deliver the first PTAS for SDL. Additionally, the exploration of the assignment problem in turnstile streams establishes fundamental limits on space complexity while providing near-optimal algorithms for practical use. Future research may focus on removing assumptions regarding bit complexity and closing the remaining $\epsilon$ gap in streaming bounds.

Summary updated

Abstract

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.
BibTeX
@inproceedings{dexter2023sketching,
  author = {Gregory Dexter and Petros Drineas and David Woodruff and Taisuke Yasuda},
  title = {{Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=qHzEFxtheD},
}
Figure