In online learning, data arrives in a continuous, sequential stream. For non-parametric models—such as kernel methods—and replay-based continual learning systems, this streaming setup creates a fundamental bottleneck: memory consumption scales with the number of observed data points. As noted by Christophe P. Bernard et al. in Wavelet interpolation networks, retaining every data point leads to a linear growth in memory and a corresponding slowdown in processing speed.
To prevent this "memory explosion," systems must enforce a strict, fixed memory budget. However, introducing a hard cap creates a new challenge: budget-induced information loss. When a memory buffer fills up, how do we decide what to discard without destroying the historical knowledge the model has acquired?
The Pitfalls of Naive Eviction
The simplest way to maintain a fixed budget is to evict data points using basic heuristics, such as discarding the oldest data (First-In-First-Out), deleting points at random, or wiping the buffer entirely when it reaches capacity. For instance, Giovanni Cavallanti et al. in Tracking the best hyperplane with a simple budget Perceptron analyze a randomized budget Perceptron that discards old data points to track shifting targets.
While computationally cheap, these heuristic pruning strategies often result in substantial information loss. Discarding observations based on arbitrary criteria like age distorts the learned decision boundaries and increases predictive uncertainty, as argued by Marcin Detyniecki et al. in Memory management for data streams subject to concept drift.
Furthermore, Junfan Li et al. in Learnability in Online Kernel Selection with Memory Constraint via Data-dependent Regret Analysis demonstrate that drastic measures, such as clearing the entire buffer upon reaching capacity, introduce severe instability into the learning process. When critical or rare support vectors are permanently deleted, the model's long-term accuracy degrades. The authors of Kernelized Online Imbalanced Learning with Fixed Budgets (Junjie Hu et al.) note that this degradation prevents models from maintaining long-term accuracy as the data stream evolves.
Geometric Projection and Optimization-Based Maintenance
To minimize information loss, advanced budgeted learning algorithms shift from deleting data to compressing or projecting it. The core intuition is geometric: if a new data point cannot be stored explicitly due to budget constraints, its influence can be projected onto the mathematical space spanned by the existing stored points.
Naive Deletion:
[Existing Support Vectors] + [New Point] ---> Budget Full ---> [Drop Oldest/Random Point] (Information Lost)
Projection-Based:
[Existing Support Vectors] + [New Point] ---> Budget Full ---> [Project New Point onto Existing Space] (Information Retained)
This insight led to the development of the Projectron framework by Francesco Orabona et al. in The projectron: a bounded kernel-based Perceptron. Instead of simply discarding a new sample or an old support vector, the algorithm projects the new information onto the existing support set. By doing so, the authors show in Bounded Kernel-Based Online Learning that the model can maintain a strictly bounded memory footprint while preserving hypothesis integrity and achieving higher accuracy than heuristic pruning.
Alternatively, budget maintenance can be framed as a joint optimization problem. In Online Passive-Aggressive Algorithms on a Budget, Zhuang Wang et al. propose a budgeted framework where support vector removal is optimized to minimize the distortion of the decision boundary. Rather than a simple deletion, the weights of the remaining support vectors are adjusted to compensate for the lost point.
More recently, Yun Liao et al. in Ahpatron: A New Budgeted Online Kernel Learning Machine with Tighter Mistake Bound introduce a "halve-and-project" strategy that aggressively updates the model but systematically projects removed data points to retain their predictive influence, yielding tighter theoretical mistake bounds.
Sketching and Functional Approximation
Rather than managing an explicit budget of individual data points, another branch of research seeks to transform the hypothesis space itself so that the memory footprint remains inherently constant.
One approach is hypothesis sketching. As explored by Xiao Zhang et al. in Hypothesis Sketching for Online Kernel Selection in Continuous Kernel Space, instead of keeping a buffer of past instances, the algorithm maintains a fixed-size mathematical "sketch" of the continuous kernel space. This preserves the cumulative influence of all observed data within a fixed set of parameters, bypassing the need for instance-level pruning entirely.
A parallel strategy relies on functional approximation. Steven HOI et al. argue in Large Scale Online Kernel Classification that instead of managing a budget of support vectors via deletion, merging, or projection, models can map incoming data into a low-dimensional, fixed feature space using methods like Random Fourier Features or Nyström approximations. This shifts the online learning process from a non-parametric setting (where memory grows) to a parametric setting with a strictly fixed size, scaling linearly with data size without sacrificing accuracy.
Application to Deep Replay Buffers
The challenge of fixed-budget information loss extends far beyond classical kernel methods; it is a central hurdle in deep reinforcement learning (RL) and online continual learning (OCL). In these domains, neural networks use a fixed-capacity experience replay buffer to prevent catastrophic forgetting.
As Steven Hansen et al. observe in Fast deep reinforcement learning using online adjustments from the past, finite replay buffers often delete valuable or rare experiences before the deep parametric model has had enough time to fully integrate the information via gradient descent. When these samples are permanently erased, the model loses historical knowledge.
To combat this, the authors of Sample Condensation in Online Continual Learning (Antonio Carta et al.) propose sample condensation techniques to compress the information density of the buffer before eviction occurs. Similarly, in the context of large language models, Yanhui Guo et al. demonstrate in Q-Tuning: Queue-based Prompt Tuning for Lifelong Few-shot Language Learning that standard FIFO queues for task-specific prompts risk losing critical knowledge, advocating instead for information-theoretic regularization and PCA-based eviction to maximize the utility of the fixed budget.
Whether through geometric projection, functional approximation, or sample condensation, the core principle remains identical: when operating under a strict memory budget, an algorithm must treat memory maintenance not as an administrative deletion task, but as an information-preserving optimization problem.
Key Foundational Work
Tracking the best hyperplane with a simple budget Perceptron (2007) — contributed 1 concept elements to this direction.
Wavelet interpolation networks (1998) — contributed 1 concept elements to this direction.