Beating SGD: Learning SVMs in Sublinear Time

Elad Hazan, Tomer Koren, Nati SrebroNeurIPS 2011 · OpenReview

Stochastic Gradient Descent (SGD) has long been considered the gold standard for training Support Vector Machines (SVMs) in a single pass. However, as datasets grow increasingly massive, even a single pass over the data can be prohibitively expensive. In this paper, Hazan, Koren, and Srebro introduce SIMBA (Sublinear IMportance-sampling Bi-stochastic Algorithm), an optimization approach that learns in sublinear time. By sampling individual features rather than entire data vectors, SIMBA achieves optimal generalization error while reading significantly less data than the total size of the training set.

The Bottleneck of Standard SGD

In large-scale machine learning, SGD and its variants (such as Pegasos) are the go-to tools for linear SVMs. Their runtime is typically $O(n \cdot d)$, where $n$ is the number of examples and $d$ is the dimensionality. This is often deemed "optimal" because it takes exactly one pass over the data to reach the desired generalization goal.

However, when datasets feature millions of examples and dimensions, processing full vectors at every iteration becomes a severe bottleneck. The authors pose a radical question: Can we learn a model without even reading all the data? Specifically, they target the $O(d)$ cost of processing a full vector at every iteration, seeking a method that scales with the number of feature accesses rather than the total number of entries in the data matrix.

The SIMBA Approach

The core innovation of SIMBA is a bi-stochastic primal-dual approach that minimizes feature accesses:

  1. Primal Step (Weight Update): Instead of standard SGD, SIMBA uses an importance-weighted version. It samples an instance $i$ based on a dynamically updated distribution $p$ and updates the model weights $w$.
  2. Dual Step (Weighting the Data): The algorithm maintains a distribution $p$ over the training examples, essentially "learning" which examples are the most informative (e.g., those near the SVM margin) and focusing computational effort there.
  3. Feature-Level Sparsity: Unlike standard online methods that process a whole vector $x_i$ at each step, SIMBA only accesses randomly sampled coordinates (features) of the vectors.
  4. Hybrid Framework: The algorithm combines the stochastic primal-dual CHW framework with the deterministic PST framework for linear programs. This combination handles slack variables and bias terms efficiently, avoiding the slow convergence usually associated with applying these frameworks naively to SVMs.

To make this efficient in practice, the authors utilize a tree-based data structure to perform sampling in $O(\log n)$ or $O(\log d)$ time.

Key Insights

  • Breaking the $O(d)$ Barrier: The critical realization is that we do not need to see every feature of an example to get a useful gradient estimate. By treating feature access as the primary computational cost, the algorithm can effectively "skip" irrelevant data.
  • Sublinear Learning is Possible: The paper proves that in high-dimensional regimes with relatively low noise, the runtime required for generalization is actually less than the size of the minimal training set. You can learn the underlying pattern before you have finished reading the data.
  • Importance Sampling as a Dual Update: Instead of treating all examples equally, SIMBA uses the dual update to focus resources on the "hard" examples that define the SVM margin.

Empirical Results

The authors evaluated SIMBA on large-scale, high-dimensional datasets, including the news20 text classification dataset (~1.35 million features, ~20,000 examples) and a real vs. simulated dataset (~21,000 features, ~72,000 examples).

Theoretically, SIMBA is guaranteed to reach an $\epsilon$-approximate solution in $O(\epsilon^{-2}(n + d))$ time, a massive improvement over the $O(n \cdot d)$ required to simply read the data.

Empirically, these theoretical gains translate into dramatic speedups. In head-to-head tests against Pegasos (a state-of-the-art SGD variant), SIMBA achieved the same test error while using approximately 100 times fewer feature accesses.

SIMBA vs Pegasos test error

This efficiency is particularly potent for sparse data, where the method can be implemented to scale with the overall data sparsity ratio.

Limitations and Future Work

While SIMBA offers groundbreaking theoretical and empirical speedups, it comes with specific constraints:

  • Random Access Requirement: The algorithm assumes "random access" to specific coordinates of specific vectors. This is trivial in RAM but can be challenging for data stored in sequential formats or streamed over a network.
  • Regime Specificity: The sublinear advantage is most pronounced in high-dimensional settings with low noise. In low-dimensional or extremely noisy settings, the overhead of the dual updates might diminish the performance gains.

The authors suggest several promising extensions for this bi-stochastic approach, including adapting it for multiclass and structured SVMs, latent SVMs, kernel methods (via linearization), and $\ell_1$-regularized problems.

Summary updated

Abstract

We present an optimization approach for linear SVMs based on a stochastic primal-dual approach, where the primal step is akin to an importance-weighted SGD, and the dual step is a stochastic update on the importance weights. This yields an optimization method with a sublinear dependence on the training set size, and the first method for learning linear SVMs with runtime less then the size of the training set required for learning!
BibTeX
@inproceedings{hazan2011beating,
  author = {Elad Hazan and Tomer Koren and Nati Srebro},
  title = {{Beating SGD: Learning SVMs in Sublinear Time}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2011},
  url = {https://openreview.net/forum?id=Sk-UCvWu-S},
}
Figure