Linear and Kernel Classification in the Streaming Model: Improved Bounds for Heavy Hitters

Arvind V. Mahankali, David WoodruffNeurIPS 2021 · OpenReview

In the era of massive datasets, machine learning models frequently encounter feature spaces ($d$) so vast that storing even a single weight vector becomes computationally prohibitive. Consider natural language processing tasks utilizing $n$-gram features, where the dimensionality can easily scale into the millions or billions. How can we effectively train a classifier when the memory budget is restricted to kilobytes rather than gigabytes?

This paper presents a significant advancement in solving the "heavy hitter" problem for linear and kernel classification in the streaming model, offering robust algorithms that operate in sublinear space.

The Challenge: Memory-Constrained Online Learning

The core problem lies in memory-constrained online learning. In a streaming model, data points $(x_t, y_t)$ arrive sequentially. If $x_t \in \mathbb{R}^d$ and $d$ is massive, storing the optimal weight vector $w_*$ is impossible.

Previous approaches, notably by Tai et al. (2018), estimated individual weights (point queries) using sublinear space but suffered from three major limitations:

  1. Weak Error Guarantees: They only provided $\ell_1$ error guarantees, which are significantly weaker than $\ell_2$ bounds in high dimensions.
  2. Strict Data Ordering: They required the data stream to arrive in a uniformly random order to guarantee convergence.
  3. Limited Scope: The techniques were restricted to simple linear classifiers.

This research overcomes these hurdles, aiming to identify the "Heavy Hitters"—the specific features contributing most to the classification—using minimal memory, even when data arrives in an adversarial order.

Methodology: Sketch-and-Solve and Online Gradient Descent

The authors develop a "sketch-and-solve" framework integrated with Online Gradient Descent (OGD):

  • Sketched OGD: Instead of maintaining the full weight vector $w_t \in \mathbb{R}^d$, the algorithm maintains a compressed representation $z_t \in \mathbb{R}^k$ using a Johnson-Lindenstrauss (JL) matrix.
  • Decoupling Sketches: A pivotal innovation is decoupling the JL matrix (which preserves the geometry of the loss function) from the specific "point query" sketch (used to recover the weights). For $\ell_2$ heavy hitters, the authors reduce the problem to the well-studied turnstile streaming model, enabling the use of established tools like CountSketch or Expander Sketches.
  • Deterministic $\ell_1$ Queries: By introducing $\epsilon$-incoherent matrices, the authors create a deterministic algorithm for $\ell_1$ point queries, improving the space complexity over prior randomized methods.
  • Tensor Sketching for Kernels: To handle complex kernels (such as the Gaussian kernel), the weights are treated as high-order tensors. Utilizing "Recursive Tensor Sketches" allows the algorithm to find heavy hitters in the kernel space without explicitly expanding the features into an astronomical or infinite dimension.

Key Insights and Empirical Results

The algorithms were evaluated on standard high-dimensional benchmarks, including RCV1 (text categorization), KDD Cup 2010 Algebra (student performance prediction), and a Malicious URL Dataset.

Theoretical and Practical Breakthroughs

  • Adversarial Robustness: By leveraging regret bounds from OGD theory rather than relying on the statistical properties of the data stream, the authors prove their algorithms remain effective even if an adversary dictates the order of incoming data points.
  • The Power of $\ell_2$ Guarantees: Transitioning from $\ell_1$ to $\ell_2$ guarantees is a major theoretical leap. In high-dimensional spaces, the $\ell_1$ norm can be $\sqrt{d}$ times larger than the $\ell_2$ norm. An $\ell_2$ guarantee ensures that the error is tightly controlled relative to the actual "energy" of the weight vector.
  • Kernel Interpretability: Kernel methods are traditionally viewed as "black boxes." By identifying heavy hitters in the polynomial expansion of a kernel, this method allows researchers to interpret which specific combinations of features are most predictive.

Performance Highlights

  • Accuracy vs. Memory: On the RCV1 dataset, restricted to a tiny 16KB memory budget, the proposed combined JL/point query sketch demonstrated a 15% improvement in weight recovery error over the previous state-of-the-art (WM-Sketch).
  • Efficiency: The kernel algorithms achieve space and time complexity polynomial in the degree of the kernel ($p$) and $\log d$. This makes high-degree polynomial kernels computationally feasible in streaming environments for the first time.

Limitations and Future Directions

While the space complexity is sublinear in $d$, the algorithms require a large number of samples ($T$) to converge. The error terms generally scale with $T^{-1/4}$, meaning a very long data stream is necessary to achieve high precision.

Furthermore, for kernel classification, the current method of "ignoring permutations" (e.g., treating the feature combination $x_1x_2$ identically to $x_2x_1$) is effective but leaves room for optimization in space complexity. The authors highlight a promising open question: whether this can be achieved in $\text{poly}(\epsilon^{-1} p \log d)$ space regardless of the Hamming distance of the indices.

Summary updated

Abstract

We study linear and kernel classification in the streaming model. For linear classification, we improve upon the algorithm of (Tai, et al. 2018), which solves the $\ell_1$ point query problem on the optimal weight vector $w_* \in \mathbb{R}^d$ in sublinear space. We first give an algorithm solving the more difficult $\ell_2$ point query problem on $w_*$, also in sublinear space. We also give an algorithm which solves the $\ell_2$ heavy hitter problem on $w_*$, in sublinear space and running time. Finally, we give an algorithm which can $\textit{deterministically}$ solve the $\ell_1$ point query problem on $w_*$, with sublinear space improving upon that of (Tai, et al. 2018). For kernel classification, if $w_* \in \mathbb{R}^{d^p}$ is the optimal weight vector classifying points in the stream according to their $p^{th}$-degree polynomial kernel, then we give an algorithm solving the $\ell_2$ point query problem on $w_*$ in $\text{poly}(\frac{p \log d}{\varepsilon})$ space, and an algorithm solving the $\ell_2$ heavy hitter problem in $\text{poly}(\frac{p \log d}{\varepsilon})$ space and running time. Note that our space and running time are polynomial in $p$, making our algorithms well-suited to high-degree polynomial kernels and the Gaussian kernel (approximated by the polynomial kernel of degree $p = \Theta(\log T)$).
BibTeX
@inproceedings{mahankali2021linear,
  author = {Arvind V. Mahankali and David Woodruff},
  title = {{Linear and Kernel Classification in the Streaming Model: Improved Bounds for Heavy Hitters}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=_pmQOVi3gHx},
}
Figure