Abstract: We present AROW, a new online learning algorithm that combines several properties of successful methods: large margin training, confidence weighting, and the capacity to handle non-separable data. AROW performs adaptive regularization of the prediction function upon seeing each new instance, allowing it to perform especially well in the presence of label noise. We derive a mistake bound, similar in form to the second order perceptron bound, which does not assume separability. We also relate our algorithm to recent confidence-weighted online learning techniques and empirically show that AROW achieves state-of-the-art performance and notable robustness in the case of non-separable data.
Introduction
Online learning algorithms are essential for processing large-scale data streams efficiently by updating models incrementally. A significant recent development, Confidence Weighted (CW) learning, tracks the uncertainty of feature weights using a Gaussian distribution. While highly effective on separable data, CW is sensitive to label noise due to its aggressive update rules that force the model to satisfy classification constraints for every new instance. We introduce AROW (Adaptive Regularization of Weight Vectors), a novel algorithm that combines the benefits of confidence weighting with the robustness of large-margin classifiers.
Methods: Adaptive Regularization
AROW shifts the focus from hard classification constraints to a soft optimization problem. For each new instance, the algorithm minimizes an objective function that balances three criteria:
- Conservatism: Minimizing the KL divergence between the new and old weight distributions to prevent drastic parameter swings.
- Correctness: Minimizing the squared-hinge loss on the current example to ensure accurate predictions.
- Confidence: Adaptively reducing weight variance based on the observed features to refine the model's certainty.
This formulation results in closed-form, decoupled updates for the mean and covariance of the weight vector. This ensures computational efficiency comparable to simpler online methods while providing a more stable learning process.
Experimental Results
The authors evaluated AROW against several state-of-the-art baselines, including Passive-Aggressive (PA), Second Order Perceptron (SOP), and CW, using synthetic, text, and OCR datasets.
As illustrated in Figure 3, AROW demonstrates superior performance on both synthetic data with 10% noise and the MNIST digit recognition task. Unlike CW, which can overfit to noisy labels by aggressively adjusting parameters, AROW's regularized updates allow it to maintain a stable and accurate prediction function even in "messy" environments.
Robustness to Label Noise
A key strength of AROW is its performance in non-separable settings. In experiments where labels were intentionally flipped (up to 30% noise), AROW maintained its accuracy while CW's performance degraded significantly.
Figure 6 highlights AROW's consistent advantage over CW in optical character recognition tasks. By treating constraints as regularizers, AROW effectively "dampens" the impact of outliers and mislabeled instances. This behavior acts as a per-feature learning rate: if the model is already confident about a feature, it resists making large changes based on a single noisy example, leading to better generalization on real-world data.
Conclusion
AROW successfully bridges the gap between high-performance confidence-weighted learning and robust large-margin classification. Its ability to handle non-separable data with theoretical guarantees—specifically a mistake bound that does not assume separability—makes it a powerful and reliable tool for modern online learning applications.
Summary updated