Budgeted Online Kernel Learning

38 concepts30 papers1 proposal

Online learning requires models to process data streams sequentially, updating their parameters in real time as new observations arrive. When paired with kernel methods, online learning becomes exceptionally powerful, enabling models to capture complex, non-linear decision boundaries by implicitly mapping data into high-dimensional feature spaces.

However, this power comes with a fundamental flaw known as the curse of kernelization. According to the classical Representer Theorem, a kernel model's prediction function is represented as a linear combination of kernel evaluations over historical data points:

$$f(x) = \sum_{i \in \mathcal{S}} \alpha_i k(x_i, x)$$

Every time the model encounters a challenging example or makes a mistake, that data point is added to the support set $\mathcal{S}$ as a new "support vector." In an infinite data stream, the size of $\mathcal{S}$ grows linearly over time ($|\mathcal{S}| \to \infty$). This causes a memory explosion and forces the computational cost of both inference and updates to scale linearly with time, eventually grinding real-time systems to a halt. As noted by Simon et al. in Introduction to the special issue on COLT 2006, online algorithms must modify traditional classifiers to balance adaptability to non-stationary targets with strict computational resource constraints.

To solve this, researchers introduce a strict, user-defined memory limit—a budget $B$—on the maximum number of support vectors the model can store. When the budget is full ($|\mathcal{S}| = B$), incorporating a new data point requires strategically modifying the active set to maintain constant memory and processing time. The field has converged on four core strategies to achieve this: deletion, projection, merging, and hypothesis sketching.


Deletion and Forgetting Mechanisms

The most straightforward way to maintain a fixed budget is to evict existing support vectors when new ones arrive. However, blindly discarding data can degrade accuracy. Effective deletion strategies must intelligently choose which vectors to forget to minimize predictive error.

Weight Shrinkage and Deterministic Eviction

In The Forgetron: A Kernel-Based Perceptron on a Fixed Budget, Dekel et al. introduced the Forgetron, the first kernel-based online learner with formal accuracy guarantees on a fixed budget. The Forgetron manages the budget by systematically "shrinking" the weights ($\alpha_i$) of older support vectors before eventually deleting the oldest one. This gradual decay ensures that the model smoothly discounts past information rather than introducing abrupt changes to the decision boundary.

In tracking and regression applications, pruning strategies often target the least significant support vectors. For instance, in the structured output tracking framework Struck (Struck: Structured output tracking with kernels), Hare et al. maintained real-time tracking speeds by identifying and removing support vectors that contribute least to the optimization objective. Similarly, Bounded Online Gradient Descent (BOGD), analyzed by Ren et al. in The application of Bounded Online Gradient Descent Algorithms for Kernel Based Online Learning in Tourist Number Forecasting, utilizes a fixed-size buffer and discards low-weight support vectors, demonstrating that the resulting predictive error remains minimal and bounded.

This pruning philosophy extends across diverse domains:

Randomized Replacement and Re-normalization

Rather than computing complex importance metrics, Cavallanti et al. proved a surprising theoretical result in Tracking the best hyperplane with a simple budget Perceptron: simply evicting a random historical support vector when the budget is full achieves a mistake bound that scales linearly with the total shift of the target sequence, matching the performance of algorithms with infinite memory. To maintain stability after such removals, modern variants like the POMDR algorithm by Li et al. (Improved Kernel Alignment Regret Bound for Online Kernel Learning) combine geometric budget-clearing strategies with hypothesis re-normalization to preserve predictive accuracy.


Projection and Redundancy Filtering

Simple deletion discards the geometric information contained within the evicted data point. Projection-based methods mitigate this loss by checking for redundancy and projecting new or discarded information onto the subspace spanned by the remaining support vectors.

Linear Independence Filtering

Before a point is even added to the budget, the model can check if it introduces genuinely new information. In On-line Independent Support Vector Machines for Cognitive Systems, Orabona et al. designed an Online Independent SVM (OISVM) that performs linear independence checks in the feature space. If a streaming data point can be represented as a linear combination of the currently stored support vectors, it is filtered out, ensuring that inference time remains strictly constant over long-term operation.

Subspace Projection (The Projectron Framework)

When a data point does contain new information but the budget is full, we can project it onto the existing support vector subspace. Orabona et al. formalized this in Bounded Kernel-Based Online Learning via the Projectron and Projectron++ algorithms.

Infinite Feature Space
       ▲
       │      ● New Data Point (x_t)
       │     /│
       │    / │ ◄─── Minimal Projection Error (δ)
       │   /  ▼
       │  / ┌───────────────────────────┐
       │ /  │ Subspace Spanned by      │
       │▼   │ Existing Support Vectors  │
       └────┴───────────────────────────┴──►

When a new point arrives, the algorithm computes its projection error $\delta$ relative to the stored budget vectors. If $\delta$ is below a certain threshold, the algorithm updates the weights of the existing support vectors to approximate the new point, consuming zero additional budget.

To scale this to continuous streams, Stump et al. developed POLK (Parsimonious Online Learning with Kernels) in Parsimonious Online Learning with Kernels via sparse projections in function space. By pairing functional stochastic gradient descent with error-bounded greedy pruning, they proved that the number of support vectors remains strictly bounded under a constant step-size regime. This greedy subspace projection mechanism was further adapted by Koppel et al. in Decentralized Online Learning with Kernels to prevent memory explosion across distributed networks of agents, while Chen et al. combined sparse projections with dual buffering strategies in Online Semi-Supervised Learning With Multiple Regularization Terms.

Alternatively, the non-parametric problem can be converted into a parametric one entirely. In Adaptation and learning over networks for nonlinear system modeling, Scardapane et al. demonstrated that sharing a fixed dictionary of representative basis points across network nodes stabilizes communication and memory requirements indefinitely.


Merging Support Vectors

Instead of deleting a vector or projecting a new point away, we can compress the existing budget by merging two support vectors into a single, synthetic vector.

This approach was pioneered by Wang et al. in Online Passive-Aggressive Algorithms on a Budget and Multi-Class Pegasos on a Budget. When the budget is exceeded, the algorithm identifies the two closest or most redundant support vectors in the active set and solves a joint optimization problem:

$$\min_{z, \beta} \| f_{\text{original}} - f_{\text{merged}} \|^2$$

The two vectors are replaced by a single synthetic vector $z$ with an adjusted weight $\beta$, chosen specifically to minimize the distortion of the decision boundary.

Budget Exceeded (B + 1)            Optimized Merging (Strict Budget B)

   ● α_i (x_i)                         
                                       ● β (z)  ◄─── Synthetic Vector
   ● α_j (x_j)                                       (Boundary Preserved)

   ● Stored Vector                     ● Stored Vector
   ● Stored Vector                     ● Stored Vector

By treating budget maintenance as a parameter optimization step rather than a destructive deletion step, merging retains a significantly richer representation of the decision boundary within the same memory footprint.


Hypothesis Sketching and Feature Approximation

A more recent paradigm shifts away from managing discrete support vectors, focusing instead on compressing the entire hypothesis space via randomized sketching.

In Incremental Randomized Sketching for Online Kernel Learning, Zhang et al. introduced SkeGD (Sketched Online Gradient Descent). SkeGD employs a hybrid training procedure: it performs exact kernelized gradient descent until the user-defined memory budget is reached. At that exact boundary, it computes a randomized sketch of the accumulated kernel matrix and transitions seamlessly to updates within a fixed, approximate feature space.

The authors extended this framework to continuous kernel spaces (such as learning across an infinite family of Gaussian kernel widths) in Hypothesis Sketching for Online Kernel Selection in Continuous Kernel Space. By maintaining a fixed-size "hypothesis sketch" that tracks a constant number of basis functions, their algorithm achieves the optimal sublinear regret bound of $O(\sqrt{T})$ while keeping per-round time and memory complexity strictly constant. This addresses long-standing challenges in streaming multi-kernel environments, an open problem highlighted by Orabona et al. in OM-2: An online multi-class Multi-Kernel Learning algorithm Luo Jie.


Summary of Budgeting Strategies

Strategy Representative Work Core Mechanism Primary Advantage
Deletion Dekel et al. (Forgetron)<br>Cavallanti et al. Gradually shrinks weights or randomly evicts old/low-weight vectors. Extremely low computational overhead per update.
Projection Orabona et al. (Projectron)<br>Stump et al. (POLK) Projects new points onto the subspace of existing support vectors. Minimizes information loss in the Reproducing Kernel Hilbert Space (RKHS).
Merging Wang et al. Combines two redundant vectors into a single optimized synthetic vector. Excellent preservation of the local decision boundary geometry.
Sketching Zhang et al. (SkeGD) Transitions from exact kernel space to a fixed, sketched feature space. Provides optimal $O(\sqrt{T})$ regret bounds for infinite data streams.

Key Foundational Work

The Forgetron: A Kernel-Based Perceptron on a Fixed Budget (2005) — contributed 2 concept elements to this direction.
Online novelty detection on temporal sequences (2003) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 27 papers
  2. Version 1 · 2026-10-04 · 28 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_budgeted_online_learning_f243f334,
  title = {budgeted online learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/budgeted-online-learning/rdr_f243f33446d046b1981d513821ea5996},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_budgeted_online_learning_f243f334_v2,
  title = {budgeted online learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/budgeted-online-learning/rdr_f243f33446d046b1981d513821ea5996/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake