Unveiling Statistical Significance of Online Regression Over Multiple Datasets

Mohammad Abu-Shaira, Weishi Shi

TL;DR

This paper addresses the often-overlooked challenge of rigorously comparing multiple online learning algorithms across diverse datasets. By applying non-parametric statistical frameworks—specifically the Friedman and Nemenyi tests—the authors demonstrate how to move beyond simple average performance metrics to determine if one online regression model truly outperforms another with statistical certainty.

What Problem Does This Paper Address?

In traditional "batch" machine learning, we often compare two models on a static dataset using standard t-tests. However, the world of Online Learning is different: data arrives in continuous streams, models update incrementally, and "concept drift" (changes in data patterns over time) is a constant threat.

Most research in this sub-field focuses on a single algorithm's performance on a single dataset. The authors argue that this is insufficient. To claim a model is "state-of-the-art," researchers need a robust way to compare multiple algorithms across many different datasets simultaneously. Because streaming data often violates the assumptions of standard parametric tests (like ANOVA)—such as normality and equal variance—a more flexible, non-parametric approach is required to validate which models are actually superior.

Methods

The authors evaluate eight different online linear regression models using a two-step statistical framework:

  1. The Friedman Test: A non-parametric equivalent of the repeated-measures ANOVA. It ranks the performance of each model on every dataset (1 for the best, $k$ for the worst) and calculates whether the measured differences in average ranks are statistically significant or just due to random noise.
  2. Nemenyi Post-hoc Test: If the Friedman test finds a significant difference, the Nemenyi test is used to perform "pairwise" comparisons. it calculates a Critical Difference (CD); if the gap between two models' average ranks is larger than the CD, the difference is considered statistically significant.

Algorithms Compared: * SGD & MBGD: Stochastic and Mini-Batch Gradient Descent. * LMS: Least Mean Squares (Widrow-Hoff). * ORR & OLR: Online Ridge and Lasso Regression. * RLS: Recursive Least Squares. * PA: Passive Aggressive algorithm. * OLR-WA: Online Regression with Weighted Average (the authors' focus).

Datasets

The study utilizes a mix of eight datasets to ensure a comprehensive evaluation:

  • Synthetic (DS1–DS4): Four generated datasets ranging from low (3) to high (500) dimensionality and varying noise levels.
  • Real-World:
    • MCPD: Medical Cost Personal Datasets.
  • 1KC: 1,000 Companies Profit dataset.
  • KCHSD: King County House Sale Data.
  • CCPP: Combined Cycle Power Plant datasets.

All evaluations used 5-fold cross-validation with seed averaging to ensure the results weren't a fluke of data partitioning.

Key Insights and Ideas

  • Ranks Matter More Than Raw MSE: In online learning, models often converge to similar Mean Squared Error (MSE) levels eventually. The "aha moment" here is that statistical significance should be measured during the initial convergence phase (the first 10 iterations), where the speed of adaptation is most visible.
  • The ANOVA Trap: The authors highlight that traditional ANOVA is often a "bad fit" for ML benchmarking because real-world datasets have wildly different noise levels (heteroscedasticity), which breaks ANOVA's core assumptions.
  • Rank vs. Significance: A model can have the best (lowest) average rank without being "significantly" better than its closest competitors. For example, while OLR-WA had the best rank (1.25), the Nemenyi test showed it wasn't significantly different from LMS or PA at the $\alpha=0.05$ level.

Key Results

  • Friedman Test Success: The calculated $F_F$ statistic was 7.63, significantly higher than the critical value of 3.047. This allowed the authors to reject the null hypothesis and confirm that there are indeed real performance differences between the models.
  • Top Performer: OLR-WA achieved the lowest average rank (1.250), followed by PA and RLS (both at 3.875).
  • Statistical Gaps: The Nemenyi test confirmed that OLR-WA significantly outperforms SGD, MBGD, and Online Ridge Regression (ORR). However, the performance gap between OLR-WA and LMS (Least Mean Squares) was 3.125—less than the Critical Difference of 3.712—meaning we cannot statistically claim OLR-WA is better than LMS in this specific context.

Limitations and Future Work

The authors acknowledge that while their tests confirmed the performance of many baselines, there is still "room for improvement" in state-of-the-art methods.

  • Scope of Evaluation: The study focused heavily on the first 10 iterations to measure convergence. Future work could extend this to long-term stability under extreme concept drift.
  • Model Complexity: The paper focuses on linear models. Applying this rigorous statistical framework to non-linear online models (like online deep learning) remains a promising next step.
  • Parameter Sensitivity: The performance of many of these models (like PA) is highly dependent on hyperparameter tuning; the paper suggests that future adaptive models should handle this tuning automatically to perform well across diverse datasets.

Summary updated

BibTeX
@inproceedings{abushaira2024unveiling,
  author = {Mohammad Abu-Shaira and Weishi Shi},
  title = {{Unveiling Statistical Significance of Online Regression Over Multiple Datasets}},
  booktitle = {MIPR},
  year = {2024},
  doi = {10.1109/mipr62202.2024.00051},
}
Figure