Approximation Vector Machines for Large-scale Online Learning

Trung Le, Tu Dinh Nguyen, Vu Nguyen, Dinh Q. Phung

Abstract

One of the most challenging problems in kernel online learning is to bound the model size and to promote the model sparsity. Sparse models not only improve computation and memory usage, but also enhance the generalization capacity, a principle that concurs with the law of parsimony. However, inappropriate sparsity modeling may also significantly degrade the performance. In this paper, we propose Approximation Vector Machine (AVM), a model that can simultaneously encourage the sparsity and safeguard its risk in compromising the performance. When an incoming instance arrives, we approximate this instance by one of its neighbors whose distance to it is less than a predefined threshold. Our key intuition is that since the newly seen instance is expressed by its nearby neighbor the optimal performance can be analytically formulated and maintained. We develop theoretical foundations to support this intuition and further establish an analysis to characterize the gap between the approximation and optimal solutions. This gap crucially depends on the frequency of approximation and the predefined threshold. We perform the convergence analysis for a wide spectrum of loss functions including Hinge, smooth Hinge, and Logistic for classification task, and $l_1$, $l_2$, and $\epsilon$-insensitive for regression task. We conducted extensive experiments for classification task in batch and online modes, and regression task in online mode over several benchmark datasets. The results show that our proposed AVM achieved a comparable predictive performance with current state-of-the-art methods while simultaneously achieving significant computational speed-up due to the ability of the proposed AVM in maintaining the model size.

The Curse of Kernelization

In the domain of online learning, data arrives in a continuous stream, requiring algorithms that can update incrementally. Kernel methods are a popular choice because they allow linear algorithms to solve complex non-linear problems by mapping data into high-dimensional feature spaces. However, they suffer from a fundamental flaw known as the curse of kernelization.

In standard kernel Stochastic Gradient Descent (SGD), every time the model makes a mistake or encounters a point within the margin, that point is added to the model as a "support vector." For large-scale streaming data involving millions of points, the model size grows linearly with the number of updates. This eventually exhausts memory and makes real-time prediction impossible. While existing "budgeted" methods attempt to fix this by deleting or merging vectors, these operations are often computationally expensive or lead to significant accuracy loss.

The Approximation Vector Machine (AVM)

To address these limitations, we introduce the Approximation Vector Machine (AVM). The core of AVM is a nonparametric approach based on the concept of $\delta$-coverage.

$\delta$-Coverage and Core Points

The input space is partitioned into overlapping cells (hyperspheres or hyperrectangles) with a maximum diameter of $\delta$. Each cell is represented by a single "core point." When a new data point arrives, the AVM checks if it falls within an existing cell. If it does, the algorithm approximates that point using the cell's core point. If it falls outside all current cells, a new cell and core point are created.

Visualization of $\delta$-coverage where data points are approximated by core points within hyperspheres.

The Algorithm

The AVM uses a Bernoulli random variable to decide when to perform this approximation. By using core points instead of every unique data instance, the model size is naturally limited by the number of cells needed to cover the data distribution. This "Automatic Budgeting" means the model size is inferred from the geometry of the data and the chosen $\delta$, rather than being a fixed, arbitrary number.

Theoretical Foundations

Unlike many heuristic approaches to sparsity, AVM is built on rigorous theoretical foundations. We provide a convergence analysis for a wide spectrum of loss functions:

  • Classification: Hinge, smooth Hinge, and Logistic loss.
  • Regression: $l_1$, $l_2$, and $\epsilon$-insensitive loss.

Our analysis proves that the "gap" between the AVM's approximation and the optimal solution is bounded and controllable via the parameter $\delta$. This allows the $\delta$ parameter to act as a "knob" for engineers to precisely tune the trade-off between hardware constraints (speed/memory) and predictive accuracy.

Experimental Evaluation

We evaluated AVM against 11 diverse benchmark datasets across classification and regression tasks, including a9a, w8a, cod-rna, ijcnn1, covtype, poker, KDDCup99, airlines, casp, slice, and year. These datasets range from tens of thousands to over 5 million instances, specifically chosen to test scalability.

Key Results

  • Extreme Sparsity: On the KDDCup99 dataset (4.4 million instances), AVM maintained a model size of just 115 core points while achieving 99.82% accuracy.
  • Massive Speedups: In online classification, AVM was often orders of magnitude faster than baselines. On the airlines dataset, AVM-Hinge trained in approximately 587 seconds, whereas the state-of-the-art BSGD-M (merging) could not complete the task within a two-hour limit.
  • Competitive Accuracy: Despite aggressive approximation, AVM consistently matched or outperformed other budgeted online methods like FOGD (Fourier Online Gradient Descent) and NOGD (Nystrom Online Gradient Descent).

Conclusion

Approximation Vector Machines offer a robust solution to the curse of kernelization by leveraging spatial partitioning to bound model size. By approximating incoming instances with nearby core points, AVM achieves significant computational speed-ups and extreme sparsity without sacrificing the theoretical guarantees or predictive performance required for large-scale online learning. Future work will explore extending this framework to semi-supervised learning, anomaly detection, and support vector clustering.

Summary updated

Abstract

One of the most challenging problems in kernel online learning is to bound the model size and to promote the model sparsity. Sparse models not only improve computation and memory usage, but also enhance the generalization capacity, a principle that concurs with the law of parsimony. However, inappropriate sparsity modeling may also significantly degrade the performance. In this paper, we propose Approximation Vector Machine (AVM), a model that can simultaneously encourage the sparsity and safeguard its risk in compromising the performance. When an incoming instance arrives, we approximate this instance by one of its neighbors whose distance to it is less than a predefined threshold. Our key intuition is that since the newly seen instance is expressed by its nearby neighbor the optimal performance can be analytically formulated and maintained. We develop theoretical foundations to support this intuition and further establish an analysis to characterize the gap between the approximation and optimal solutions. This gap crucially depends on the frequency of approximation and the predefined threshold. We perform the convergence analysis for a wide spectrum of loss functions including Hinge, smooth Hinge, and Logistic for classification task, and $l_1$, $l_2$, and $\epsilon$-insensitive for regression task. We conducted extensive experiments for classification task in batch and online modes, and regression task in online mode over several benchmark datasets. The results show that our proposed AVM achieved a comparable predictive performance with current state-of-the-art methods while simultaneously achieving significant computational speed-up due to the ability of the proposed AVM in maintaining the model size.
BibTeX
@article{le2017approximation,
  author = {Trung Le and Tu Dinh Nguyen and Vu Nguyen and Dinh Q. Phung},
  title = {{Approximation Vector Machines for Large-scale Online Learning}},
  journal = {J. Mach. Learn. Res.},
  year = {2017},
  url = {https://openreview.net/forum?id=vY1JkEogXuR},
}
Figure