Tracking the best hyperplane with a simple budget Perceptron

Giovanni Cavallanti, Nicolò Cesa-Bianchi, Claudio GentileMachine Learning 2007 · DOI · OpenReview

Abstract

This paper addresses the challenge of kernel-based online learning in non-stationary environments where the target concept evolves over time. We present the Randomized Budget Perceptron (RBP), a simple yet effective algorithm that maintains a fixed memory budget by randomly discarding support vectors. We provide a theoretical analysis showing that RBP achieves optimal mistake bounds for tracking shifting targets, comparable to algorithms with unlimited memory. Empirical evaluations on the Reuters Corpus Volume 1 (RCV1) demonstrate that RBP's randomized eviction strategy provides a robust forgetting mechanism, allowing it to adapt to concept shifts more effectively than deterministic counterparts while maintaining high computational efficiency.

Introduction

In traditional online learning, the objective is typically to identify a single, fixed best-performing classifier from a sequence of data. However, real-world data streams—such as news feeds, financial markets, or user preferences—are often non-stationary. In these scenarios, the target concept shifts, requiring the learner to "track" a moving target rather than converge on a static one. This is known as the shifting or tracking problem.

Kernel-based learners, such as the Kernel Perceptron, are powerful tools for these tasks due to their ability to handle non-linearities. However, they suffer from a significant drawback: the "linear growth" problem. Every time the algorithm makes a mistake, it must store the corresponding data point as a support vector. In a long-running stream, the memory requirements grow indefinitely, eventually leading to prohibitive computational costs. To address this, we must implement a budget—a fixed limit on the number of support vectors stored.

The Randomized Budget Perceptron (RBP)

We propose the Randomized Budget Perceptron (RBP) as a solution to both the memory constraint and the tracking problem. The algorithm maintains a budget of $B$ support vectors. When a new mistake occurs and the budget is full, the algorithm must evict an existing vector to make room for the new one.

While many strategies for eviction exist (such as discarding the oldest or the least significant vector), RBP employs a surprisingly simple approach: it selects a support vector to discard at random.

This randomized eviction serves as a natural "forgetting" mechanism. By discarding old information, the algorithm prevents itself from being anchored to obsolete patterns, allowing it to adapt to new trends in the data stream. Unlike deterministic rules, random eviction is robust against adversarial patterns and ensures that, on average, the influence of older data decays at an appropriate rate for non-stationary environments.

Theoretical Guarantees

Through a potential-based analysis, we demonstrate that RBP is not just a heuristic but is theoretically grounded. We prove that RBP strikes an optimal trade-off between the budget size $B$ and the complexity of the target sequence (measured by the norm $U$). Specifically, we show the relationship $U = \Theta(\sqrt{B})$, which improves upon previous, more complex budget management algorithms.

Furthermore, we derive mistake bounds for RBP that scale linearly with the "total shift" of the target sequence. This indicates that RBP can track a moving target with a performance penalty that is proportional to how much the target actually moves, matching the theoretical efficiency of algorithms that have access to unlimited memory.

Experimental Evaluation

To validate our approach, we conducted experiments using the Reuters Corpus Volume 1 (RCV1) dataset. The stories were preprocessed using standard TF-IDF bag-of-words encoding and normalized into vectors.

Synthetic Shifts

To simulate a tracking environment, we created synthetic shifts within the RCV1 stream. We defined a "target category" (e.g., Corporate news vs. Economics) that changed at specific intervals across a sequence of 20,000 examples. We tested scenarios with 0, 1, 3, and 7 shifts to observe how quickly the learners could "unlearn" the old category and adapt to the new one.

Results

The experiments yielded several key insights:

  • Robust Convergence: RBP showed a smooth and consistent convergence toward the error rates of non-budgeted versions of the Perceptron.
  • Forgetting as a Feature: In high-shift environments, the limited budget was actually an advantage. Because RBP was forced to discard old data, it adapted to new categories faster than a standard Perceptron with infinite memory, which remained weighted down by obsolete support vectors.
  • Efficiency: RBP is highly efficient for high-speed streams, achieving $O(1)$ update time and $O(B)$ evaluation time.

Conclusion

The Randomized Budget Perceptron demonstrates that simplicity can be a powerful asset in online learning. By using random eviction to manage a fixed memory budget, the algorithm provides a robust and theoretically optimal solution for tracking moving targets in large-scale data streams. Future work may involve extending these randomized strategies to second-order methods and exploring even tighter bounds for smooth, continuous concept shifts.

Summary updated

Abstract

Shifting bounds for on-line classification algorithms ensure good performance on any sequence of examples that is well predicted by a sequence of changing classifiers. When proving shifting bounds for kernel-based classifiers, one also faces the problem of storing a number of support vectors that can grow unboundedly, unless an eviction policy is used to keep this number under control. In this paper, we show that shifting and on-line learning on a budget can be combined surprisingly well. First, we introduce and analyze a shifting Perceptron algorithm achieving the best known shifting bounds while using an unlimited budget. Second, we show that by applying to the Perceptron algorithm the simplest possible eviction policy, which discards a random support vector each time a new one comes in, we achieve a shifting bound close to the one we obtained with no budget restrictions. More importantly, we show that our randomized algorithm strikes the optimal trade-off $$U = \Theta(\sqrt{B})$$ between budget B and norm U of the largest classifier in the comparison sequence. Experiments are presented comparing several linear-threshold algorithms on chronologically-ordered textual datasets. These experiments support our theoretical findings in that they show to what extent randomized budget algorithms are more robust than deterministic ones when learning shifting target data streams.
BibTeX
@article{cavallanti2007tracking,
  author = {Giovanni Cavallanti and Nicolò Cesa-Bianchi and Claudio Gentile},
  title = {{Tracking the best hyperplane with a simple budget Perceptron}},
  journal = {Machine Learning},
  year = {2007},
  doi = {10.1007/s10994-007-5003-0},
}
Figure