Online Regularized Statistical Learning in Reproducing Kernel Hilbert Space With Non-Stationary Data

Xiwei Zhang, Tao Li, Li, TaoarXiv 2024 · DOI · arXiv

Abstract

We study recursive regularized learning algorithms in the reproducing kernel Hilbert space (RKHS) with non-stationary online data streams. We introduce the concept of a random Tikhonov regularization path and decompose the tracking error of the algorithm's output for the regularization path into random difference equations in RKHS. We show that the tracking error vanishes in mean square if the regularization path is slowly time-varying. Then, leveraging the monotonicity of inverse operators and the spectral decomposition of compact operators, and introducing the RKHS persistence of excitation condition, we develop a dominated convergence method to prove the mean square consistency between the regularization path and the unknown function to be learned. Especially, for independent and non-identically distributed data streams, the mean square consistency between the algorithm's output and the unknown function is achieved if the input data's marginal probability measures are slowly time-varying and the average measure over each fixed-length time period has a uniformly strictly positive lower bound.

Introduction

Most theoretical guarantees for online learning assume that data is independent and identically distributed (i.i.d.). However, real-world data—such as speech signals, financial tickers, or sensor readings from a manufacturing plant—is rarely so well-behaved. It is often non-stationary, meaning the underlying distribution changes over time, and dependent, meaning current data points are correlated with past ones.

While some researchers have tackled non-i.i.d. data in finite-dimensional settings, doing so in a Reproducing Kernel Hilbert Space (RKHS)—an infinite-dimensional space of smooth functions—is significantly more complex. The primary challenge is that standard tools like mixing coefficients or ergodicity are difficult to apply when the target function is effectively moving or when the data does not "cover" the space evenly. This paper provides the first rigorous theoretical framework for online regularized learning in RKHS using non-stationary and dependent data streams.

Methodology

The authors propose a recursive regularized learning algorithm and analyze its convergence using several novel theoretical constructs:

1. Random Tikhonov Regularization Path

Instead of attempting to jump directly to the unknown function $f^*$, the authors define an intermediate "ideal" target that changes at every time step based on the current data distribution. They then prove the algorithm successfully tracks this moving target. This "moving target" strategy is a core insight: by analyzing the distance to a regularization path that itself converges to the true function, the authors can establish convergence even when the data distribution shifts.

2. RKHS Persistence of Excitation (PE)

In traditional control theory, "Persistence of Excitation" ensures that a system receives enough varied input to identify its parameters. The authors generalize this to infinite-dimensional Hilbert spaces. In finite dimensions, PE usually means the smallest eigenvalue of the covariance matrix is bounded away from zero. In an RKHS, eigenvalues always decay to zero. The authors solve this by requiring the operator itself to be bounded below by a strictly positive compact operator over a fixed time window.

3. Structural Error Decomposition

The total error is decomposed into four manageable components:

  • Previous tracking error: The residual error from the prior step.
  • Multiplicative noise: Error resulting from random inputs.
  • Sampling error: Discretization effects.
  • Drift error: The rate at which the "ideal" target (the regularization path) moves.

4. Dominated Convergence Method

This mathematical technique is used to show that as the regularization parameter vanishes, the random path eventually converges to the true unknown function $f^*$.

Experimental Validation

While primarily a theoretical work, the authors validate their findings using a synthetic non-stationary dataset. The input $x_k$ consists of independent random variables following a uniform distribution on a time-varying interval $I_k$ that shifts across the range $[-1, 5]$. The target function is a Gaussian-shaped function $f^*(x) = e^{-(x-2)^2}$, and the noise $v_k$ is standard Gaussian $N(0, 0.1)$.

The proposed algorithm was compared against standard online kernel methods: Kernel Least Mean Square (KLMS) and NORMA (Naive Online Regularized Method). In simulations with shifting data distributions, the proposed algorithm successfully converged to the true function. In contrast, KLMS and NORMA hit an "error floor" and failed to converge because they could not account for the non-stationarity of the data stream.

Key Insights and Results

  • Mean Square Consistency: The authors prove that the algorithm's output converges to the true unknown function in mean square ($E[\|f_k - f^*\|^2] \to 0$) under non-stationary conditions.
  • Slow-Varying Distributions: For data that is not identically distributed, the paper shows that as long as the marginal probability measures change "slowly" (quantified using Hölder space norms), the algorithm can still achieve mean square consistency.
  • Theoretical Generalization: The work demonstrates that existing i.i.d. online learning theories are special, simplified cases of this broader framework.

Limitations and Future Work

The paper assumes the underlying function $f^*$ is fixed, even if the data distributions used to find it are changing. In some applications, $f^*$ itself might change over time. Additionally, while the paper proves convergence, it does not provide a universal "optimal rate" for all non-stationary settings, which remains a complex open problem. Future research may explore integrating acceleration techniques, such as Nesterov’s accelerated gradient or "heavy-ball" methods, into this non-stationary RKHS framework to enhance practical learning speeds.

Summary updated

Abstract

We study recursive regularized learning algorithms in the reproducing kernel Hilbert space (RKHS) with non-stationary online data streams. We introduce the concept of random Tikhonov regularization path and decompose the tracking error of the algorithm's output for the regularization path into random difference equations in RKHS. We show that the tracking error vanishes in mean square if the regularization path is slowly time-varying. Then, leveraging the monotonicity of inverse operators and the spectral decomposition of compact operators, and introducing the RKHS persistence of excitation condition, we develop a dominated convergence method to prove the mean square consistency between the regularization path and the unknown function to be learned. Especially, for independent and non-identically distributed data streams, the mean square consistency between the algorithm's output and the unknown function is achieved if the input data's marginal probability measures are slowly time-varying and the average measure over each fixed-length time period has a uniformly strictly positive lower bound.
BibTeX
@misc{zhang2024online,
  author = {Xiwei Zhang and Tao Li and Li, Tao},
  title = {{Online Regularized Statistical Learning in Reproducing Kernel Hilbert Space With Non-Stationary Data}},
  year = {2024},
  eprint = {2404.03211},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2404.03211},
}
Figure