Research map / Probabilistic and scientific modeling / Bayesian optimization
Stabilizing Linear Passive-Aggressive Online Learning with Weighted Reservoir Sampling
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes WRS-Augmented Training (WAT), which keeps a size-K weighted reservoir of intermediate passive-aggressive weight vectors (weighted by their survival times) and averages them to stabilize online learning test accuracy, applied to PAC and FSOL.
Problem
Online passive-aggressive linear classifiers over-correct on noisy stream points, so test accuracy can drop sharply between timesteps and the final solution may be poor, without hold-out sets or extra passes.
Approach
Use the number of subsequent passive steps (survival time) of each intermediate weight vector as a proxy for its quality, and maintain a weighted reservoir sample of K such vectors during one pass; the ensemble (simple or weighted average) of reservoir members is the output.
Key results
- FSOL-WRS with standard weights and simple averaging (K=64) reduces ROP relative to base FSOL on all 16 datasets, per the paper's count.
- PAC-WRS with exponential weights and simple averaging stabilizes test accuracy in 14 of 16 datasets versus base PAC.
- Wilcoxon tests show statistically significant ROP reductions for PAC-WRS and FSOL-WRS with standard weights (p < 0.0386), while only FSOL-WRS yields a significant final test accuracy gain.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add standard-weight WRS with simple averaging | FSOL · 16 benchmark datasets | ROP: 16 of 16 datasets | Helped |
| Add standard-weight WRS | PAC and FSOL · 16 benchmark datasets | ROP: p < 0.0386 in each case | Helped |
| Add standard-weight WRS | FSOL · 16 benchmark datasets | final test accuracy | Helped |
| Add WRS | PAC · 16 benchmark datasets | final test accuracy | No clear effect |
| Use exponential rather than standard WRS weights (ablation) | PAC-WRS and FSOL-WRS · 16 benchmark datasets | ROP: PAC: 14 vs. 13; FSOL: 13 vs. 16 | Hurt |
| Use weighted averaging rather than simple averaging (ablation) | PAC-WRS and FSOL-WRS · 16 benchmark datasets | ROP: PAC standard: 13 vs. 13; PAC exponential: 11 vs. 14; FSOL standard: 16 vs. 16; FSOL exponential: 11 vs. 13 | Mixed |
| Increase reservoir size K (ablation) | PAC-WRS · benchmark datasets | ROP | Helped |
| Enable voting-based zeroing (ablation) | FSOL-WRS · benchmark datasets | final sparsity | Helped |
| Enable voting-based zeroing (ablation) | FSOL-WRS · benchmark datasets | final test accuracy | No clear effect |
| Replace probabilistic WRS selection with deterministic top-64 selection (ablation) | PAC and FSOL · 16 benchmark datasets | ROP: PAC simple: 10 vs. 13; PAC weighted: 12 vs. 13; FSOL simple: 15 vs. 16; FSOL weighted: 15 vs. 16 | Hurt |
| Use moving average of recent weight vectors instead of WRS (ablation) | PAC and FSOL · benchmark datasets | ROP | Mixed |
| Use exponential average instead of WRS (ablation) | PAC and FSOL · benchmark datasets | ROP | Hurt |
Surprising findings
- PAC-WRS does not yield a statistically significant improvement in final test accuracy over base PAC, despite stabilizing ROP.
- Exponential weights were less effective than standard weights, attributed to over-greedy selection that retains lucky poor candidates.
Limitations
- Assumes training and test data come from fixed, stationary distributions; non-IID drift is not handled.
- Final test accuracy gain is not statistically significant for PAC, and experiments use only 5 trials.
Experimental setup
Datasets: Avazu (App) Avazu (Site) Criteo Dexter Dorothea KDD2010 (Algebra) MNIST8 (4+9) News20 Newsgroups (Binary, CS) PCMAC RCV1 Real-Sim
Benchmarks: Avazu (App) Avazu (Site) Criteo Dexter Dorothea KDD2010 (Algebra) MNIST8 (4+9) News20 Newsgroups (Binary, CS) PCMAC RCV1 Real-Sim
Metrics: relative oracle performance final test accuracy final sparsity Wilcoxon signed-rank p-value
Baselines: PAC FSOL moving average exponential average top-K averaging
Builds on: Passive-Aggressive Classifier First-Order Sparse Online Learning Weighted reservoir sampling (Efraimidis and Spirakis) Online-to-batch conversion
Closest papers by meaning
- Adaptive Passive-Aggressive Framework for Online Regression with Side Information (NeurIPS 2024 · similarity 0.88)
- Online Linear Classification with Massart Noise (ICML 2025 · similarity 0.85)
- Bandit and Delayed Feedback in Online Structured Prediction (NeurIPS 2025 · similarity 0.84)
- Efficient Non-stationary Online Learning by Wavelets with Applications to Online Distribution Shift Adaptation (ICML 2024 · similarity 0.83)
- Diffusion Models are Certifiably Robust Classifiers (NeurIPS 2024 · similarity 0.83)
- On the Convergence of Loss and Uncertainty-based Active Learning Algorithms (NeurIPS 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.