Guarantees for Approximate Incremental SVMs

Nicolas Usunier, Antoine Bordes, Léon Bottou

Abstract

This paper provides theoretical guarantees for approximate incremental Support Vector Machines (SVMs), proving that a constant number of optimization steps per new example is sufficient to track the optimal classifier over time. By introducing a novel "duality lemma," the authors show these online algorithms achieve an averaged accuracy comparable to batch solvers but with significantly lower computational costs, making them highly effective for active learning.

Introduction

In large-scale machine learning, training models on massive datasets using traditional batch methods is often computationally prohibitive. Incremental (or online) learning addresses this by updating the model sequentially as new data arrives. This approach is particularly vital in active learning or curriculum learning scenarios, where a "teacher" selects the most informative examples based on the learner's current state. For such systems to be effective, the learner must maintain a classifier that remains close to the optimal solution for all data seen thus far. While empirical successes like LASVM demonstrated the potential of fast online SVMs, they lacked theoretical guarantees for tracking a moving sequence of optima. This paper bridges this gap by providing a formal analysis of approximate incremental SVMs.

Methods

The authors analyze dual coordinate ascent algorithms for SVMs that perform a fixed, constant number of iterations ($K$) per new example rather than optimizing to full convergence. The core of their theoretical contribution is a Duality Lemma, which establishes a mathematical connection between the duality gap—the distance from the optimal solution—and the expected improvement from a single random coordinate ascent step.

Two primary algorithms are proposed:

  1. Simple Averaged Tracking Algorithm: Executes $K$ random dual coordinate ascent steps on the current dataset upon the arrival of each new example.
  2. Averaged Tracking Algorithm with PROCESS/REPROCESS: An extension inspired by LASVM that includes a specific optimization step for the new example's coefficient before performing the $K$ random updates.

Results

The algorithms were evaluated on standard benchmarks, including the ADULT census dataset and a subset of MNIST (8 vs All), using RBF kernels.

Stable Tracking and Efficiency

Empirical results confirm that the normalized duality gap remains stable over time, demonstrating that the algorithms successfully track the moving optimum without divergence. Notably, performing as few as $K=10$ or $K=20$ iterations per example allows the incremental solver to perform nearly as well as a fully converged batch algorithm.

Normalized duality gap over time for Algorithms 1 and 2 with varying K.

Synergy with Active Learning

The low computational cost of incremental updates makes these algorithms ideal for active learning. The learner can update its decision boundary rapidly, enabling the teacher to immediately identify the next most informative example (typically those closest to the boundary).

Comparison of normalized duality gap between random and active selection strategies.

As shown in the figures, active selection combined with incremental updates leads to a significantly faster reduction in the duality gap and better generalization compared to random selection.

Discussion

A key insight of this work is that "constant effort is enough"—full convergence at each step is unnecessary for effective tracking. Furthermore, the theoretical bounds are "teacher-agnostic," meaning they hold regardless of the example presentation order, ensuring stability even in biased or adversarial active learning setups.

While the theory requires outputting an average of parameter vectors over time, which can compromise the natural sparsity of SVMs, the authors observe that using the latest parameters in practice maintains sparsity without sacrificing performance. Future work may involve refining caching strategies for gradient computations to further enhance real-world implementation speed.

Summary updated

Abstract

Assume a teacher provides examples one by one. An approximate incremental SVM computes a sequence of classi ers that are close to the true SVM solutions computed on the successive incremental training sets. We show that simple algorithms can satisfy an averaged accuracy criterion with a computational cost that scales as well as the best SVM algorithms with the number of examples. Finally, we exhibit some experiments highlighting the bene ts of joining fast incremental optimization and curriculum and active learning (Schohn & Cohn, 2000; Bordes et al., 2005; Bengio et al., 2009). 1
BibTeX
@inproceedings{usunier2010guarantees,
  author = {Nicolas Usunier and Antoine Bordes and Léon Bottou},
  title = {{Guarantees for Approximate Incremental SVMs}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2010},
  url = {https://openreview.net/forum?id=mXOoWRACvn-},
}
Figure