Opposite Online Learning via Sequentially Integrated Stochastic Gradient Descent Estimators

Wenhai Cui, Xiaoting Ji, Linglong Kong, Xiaodong YanAAAI 2023 · DOI

Abstract

In the era of big data, performing hypothesis testing on continuous data streams is a significant challenge due to memory constraints and the limitations of traditional offline methods. This paper introduces "Opposite Online Learning," a novel framework that utilizes Stochastic Gradient Descent (SGD) to construct powerful online test statistics. By framing the integration of estimators as a "two-armed bandit" process, the authors develop a testing procedure that is both scalable and more powerful than existing methods. The resulting test statistics follow a newly identified distribution family, $\mathcal{B}(\kappa)$, which enhances the ability to correctly reject false null hypotheses.

Introduction

The rise of streaming data from financial markets, clinical sensors, and social media has necessitated the development of online statistical tools. While Stochastic Gradient Descent (SGD) is widely used for parameter estimation in these settings, statistical inference—specifically hypothesis testing—has lagged behind. Existing online testing methods often lack the "power" of their offline counterparts. This paper addresses this gap by proposing a framework that strategically integrates SGD estimators to perform robust and efficient hypothesis testing.

Methods

The proposed framework, Opposite Online Learning via Sequentially Integrated SGD Estimators, relies on several key innovations:

  1. Bootstrap-based SGD: A recursive bootstrap approach generates a set of estimators, capturing their distribution and providing robustness against local minima or saddle points.
  2. Two-Armed Bandit (TAB) Strategy: The construction of the test statistic is treated as a game where the algorithm chooses between a batch-specific estimator ($M_t$) and its negative counterpart ($-M_t$).
  3. Opposite Learning: The algorithm selects an "arm" based on the previous step's test statistic, integrating evidence over time.
  4. The $\mathcal{B}(\kappa)$ Distribution: The authors identify that their test statistic converges to a novel family of distributions, $\mathcal{B}(\kappa)$, which is sharper than a standard normal distribution under the null hypothesis.
Density functions of the $\mathcal{B}(\kappa)$ distribution family for various values of $\kappa$, showing the "sharpness" compared to standard distributions.

Results

The framework was validated using simulated datasets, including toy mean models and high-dimensional linear regression. Theoretical results show that the test statistic converges to the $\mathcal{B}(\kappa)$ distribution. In empirical tests, the "Opposite" test demonstrated significantly higher power. For a toy model with a minimal effect size ($\theta_0 = 0.02$), the test achieved a power of 0.9943, correctly identifying the effect nearly 100% of the time.

Comparison of test statistic densities under null (blue) and alternative (red) hypotheses. Under the alternative, the distribution "slips" toward the extremes, increasing test power.

Discussion and Conclusion

Opposite Online Learning offers a scalable solution for streaming inference with a constant memory footprint. By strategically flipping the sign of evidence based on a bandit strategy, the method ensures that the test statistic remains informative and sensitive. While currently focused on linear models, the framework's theoretical generality suggests potential for broader applications. Future research will explore its performance in non-convex landscapes, such as deep neural networks, and refine hyperparameter tuning for real-world scenarios.

Summary updated

BibTeX
@inproceedings{cui2023opposite,
  author = {Wenhai Cui and Xiaoting Ji and Linglong Kong and Xiaodong Yan},
  title = {{Opposite Online Learning via Sequentially Integrated Stochastic Gradient Descent Estimators}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i6.25886},
}
Figure