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:
- Simple Averaged Tracking Algorithm: Executes $K$ random dual coordinate ascent steps on the current dataset upon the arrival of each new example.
- 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.
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).
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