TL;DR
Kernel methods are powerful non-linear models, but when deployed in online learning, they suffer from the "curse of kernelization"—the number of support vectors grows linearly with stream size. The authors introduce the Approximation Vector Machine (AVM), an algorithm that partitions the input space into geometric cells of diameter $\delta$ and snaps incoming instances to nearby "core points." This automatically bounds the model size, delivers orders-of-magnitude faster training on multi-million-point streams, and preserves competitive predictive performance with rigorous theoretical convergence guarantees.
What Problem Does This Paper Address?
In online learning, models update incrementally as streaming data arrives. While linear models scale well, they struggle with complex, non-linear patterns. Kernel methods solve this by mapping inputs into high-dimensional feature spaces, but they encounter the curse of kernelization: every misclassified or margin-violating point becomes a new support vector. Over time, memory overflows and inference grinds to a halt.
Existing fixes have sharp drawbacks:
- Budgeted approaches cap model size at a fixed capacity $B$ using heuristics like removing, merging, or projecting vectors. However, choosing $B$ is tricky (risk of underfitting or slow merging updates that scale as $\mathcal{O}(B^2)$).
- Random Fourier features map data to an explicit randomized space, but approximating kernels accurately requires huge feature dimensions, ballooning compute costs.
Methods
AVM balances sparsity and accuracy by using the geometric concept of $\delta$-coverage:
- $\delta$-Coverage and Core Sets: The input space $\mathcal{X}$ is partitioned into overlapping cells (hyperspheres or hyperrectangles) of diameter $\le \delta$. Each cell has a representative core point $c_i$.
- Kernel Invariance: The authors prove (Theorem 4) that for any isotropic kernel (such as Gaussian RBF), a $\delta$-coverage in the input space guarantees an induced $\delta_\Phi$-coverage in the kernel feature space, where $\lim_{\delta \to 0} \delta_\Phi = 0$.
- Approximation via Online Core-Set Construction: When a new instance $(x_t, y_t)$ arrives:
- A Bernoulli variable $Z_t \in \{0, 1\}$ decides whether to approximate.
- If $x_t$ falls within an existing cell and $Z_t = 1$, its feature vector $\Phi(x_t)$ is approximated by the cell's core point $\Phi(c_{i_t})$ in the Stochastic Gradient Descent (SGD) update step.
- If $x_t$ falls outside all existing cells, a new cell is spawned on the fly with $x_t$ as its core point.
- General Loss Support: The paper establishes convergence bounds across six loss functions: Hinge, Logistic, and $\tau$-smooth Hinge (classification), as well as $\ell_1$, $\ell_2$, and $\varepsilon$-insensitive (regression). For $\ell_2$ regression, an origin hypersphere projection prevents weight explosion when the regularization parameter $\lambda \le 1$.
- Multiclass Extension: Adapts Crammer & Singer's multiclass formulation to the AVM update rule.
Incoming point (x_t, y_t)
│
▼
Does x_t lie in an
existing δ-cell?
├── YES ──► Approximate with core point c_it (if Z_t = 1)
└── NO ──► Create new δ-cell; register x_t as core point
Datasets
The authors evaluated AVM across 11 benchmark datasets (no new datasets were introduced):
- Classification: a9a, w8a, cod-rna, ijcnn1, covtype, poker, KDDCup99, and airlines (binary flight delay prediction). Five of these contain hundreds of thousands to over 5 million samples.
- Regression: casp, slice, year, and airlines (continuous flight departure delay in minutes).
- Sources: UCI Machine Learning Repository, LIBSVM, and the American Statistical Association (ASA).
Key Insights and Ideas
- Automatic, Data-Driven Model Bounds: Rather than enforcing an arbitrary manual budget $B$, AVM automatically infers its model size based on domain geometry and the resolution parameter $\delta$. If $\mathcal{X}$ is compact, the core set is guaranteed to remain finite regardless of data stream length or arrival order.
- Controlled Regret Gap: The theoretical regret bound naturally splits into the classical SGD rate $\mathcal{O}(\log(T)/T)$ (or $\mathcal{O}(1/T)$ for $\alpha$-suffix averaging) plus an approximation gap directly controlled by $\delta_\Phi$ and approximation frequency. Tuning $\delta$ lets practitioners directly trade off precision against model capacity.
- Aggressive Approximation Works Best: Experiments comparing random approximation schedules ($Z_t$) revealed that the naive "always approximate" setting ($\mathbb{P}(Z_t = 1) = 1$) achieved maximum sparsity with negligible loss in accuracy.
Key Results
- Massive Sparsity: On the 4.4M-instance KDDCup99 dataset, AVM capped model size at just 115 core vectors ($\delta = 3$). On the 5.3M-instance airlines dataset, it compressed the model down to 388 core vectors ($\delta = 1$).
- Speedups: On large datasets where standard batch kernel SVMs (LIBSVM) timed out (>2 hours), AVM completed online passes in hundreds of seconds (e.g., 540 seconds on KDDCup99 vs. 4,009 seconds for Nyström OGD).
- Predictive Performance:
- Online Classification: AVM achieved superior or competitive mistake rates compared to state-of-the-art budgeted baselines (e.g., 5.61% error on cod-rna vs. 7.15% for FOGD and 7.83% for NOGD; 19.28% on airlines vs. 25.56% for NOGD).
- Online Regression: AVM-
1and AVM-$\varepsilon$ achieved the lowest RMSE on year (0.1232 vs. 0.1375 for NOGD and 0.1881 for RBP) while reducing run time from over 600s down to ~47s.
Limitations and Future Work
- Curse of Dimensionality: Theoretical coverage size scales exponentially with input dimension $d$ (order of $(4D(\mathcal{X})/\delta)^d$). While empirical core set sizes remained very small, searching through core points requires $\mathcal{O}(d^2 M_t)$ nearest-cell lookups per iteration.
- Sensitivity to $\delta$: Performance relies on a sensible choice of cell diameter $\delta$, requiring heuristic tuning via sample pairwise distance distributions.
- Future Directions: The authors suggest applying the $\delta$-coverage framework to semi-supervised learning, anomaly detection, and support vector clustering.
Summary updated