Online regularized learning algorithm for functional data

Yuan Mao, Zheng-Chu GuoJ. Complex 2022 · OpenReview

Abstract

Functional linear models are increasingly vital for analyzing data represented as continuous curves. However, traditional batch learning methods struggle with the scalability requirements of modern streaming data. This paper investigates an online regularized learning algorithm for functional linear models within Reproducing Kernel Hilbert Spaces (RKHS). By introducing an explicit Tikhonov regularization term into a Stochastic Gradient Descent (SGD) framework, the authors establish convergence rates for both excess prediction error and estimation error. Notably, this approach overcomes the "saturation boundary" inherent in unregularized online learning, providing fast convergence rates even when the target function exhibits high smoothness.

Introduction

Functional Data Analysis (FDA) treats data points not as discrete vectors, but as continuous functions—such as daily temperature profiles, heart rate trajectories, or financial market fluctuations. The standard tool for relating a functional predictor $X(t)$ to a scalar response $Y$ is the functional linear regression model: $$Y = \int_{\mathcal{T}} \beta^*(t)X(t)dt + \epsilon$$ where $\beta^*(t)$ is the unknown slope function.

As datasets grow in size and velocity, "batch" methods—which require storing all data in memory—become computationally prohibitive. Online learning, specifically Stochastic Gradient Descent (SGD), offers a memory-efficient alternative by processing data sequentially. However, existing unregularized online algorithms for functional data face a theoretical "saturation boundary": they cannot capitalize on the smoothness of $\beta^*$ beyond a certain threshold. This paper by Mao and Guo addresses this gap by integrating explicit regularization into the online update rule.

The Online Regularized Learning Algorithm

The authors propose an algorithm that operates within a Reproducing Kernel Hilbert Space (RKHS). Unlike standard SGD, which minimizes the instantaneous squared loss, this algorithm incorporates a Tikhonov regularization term ($\lambda$) directly into the iterative update:

$$\beta_{k+1} = \beta_k - \gamma_k \left[ \left( \int_{\mathcal{T}} \beta_k(t)X_k(t)dt - Y_k \right) \int_{\mathcal{T}} K(s, \cdot)X_k(s)ds + \lambda \beta_k \right]$$

Here, $\gamma_k$ represents the step-size (learning rate) and $K(s, \cdot)$ is the kernel function associated with the RKHS. The inclusion of $\lambda > 0$ is the critical modification that allows the algorithm to handle complex regularity conditions.

Theoretical Framework and Convergence

The paper provides a rigorous convergence analysis under two distinct step-size regimes:

  1. Polynomially Decaying Step-Size: $\gamma_k \propto k^{-\mu}$, where the learning rate decreases over time.
  2. Constant Step-Size: $\gamma$ is fixed based on the total number of samples $n$.

Capacity-Dependent Analysis

To derive tighter error bounds, the authors employ a capacity-dependent analysis. This involves the effective dimension of the hypothesis space, often characterized by the decay rate of the eigenvalues of the covariance operator. By accounting for this "capacity," the authors achieve more refined convergence rates than previous capacity-independent studies.

Breaking the Saturation Boundary

A primary contribution of this work is "uplifting" the saturation boundary. In unregularized online learning, the convergence rate for the prediction error typically plateaus when the smoothness parameter $\theta$ of the target function exceeds $1/2$. By introducing explicit regularization, this algorithm allows the convergence rate to continue improving for $\theta > 1/2$, specifically achieving rates of $O(n^{-\frac{2\theta}{2\theta+1}})$.

Key Findings

  • Estimation Error Bounds: The paper establishes the first capacity-independent convergence rates for estimation error (the distance between the estimate $\beta_k$ and the true $\beta^*$) in the context of decaying step-sizes. This solves a lingering open problem in functional online learning.
  • Constant Step-Size Efficiency: The analysis reveals that constant step-sizes can be highly competitive. In many cases, they eliminate the logarithmic factors ($\log n$) often present in decaying step-size bounds, leading to faster convergence in finite-sample scenarios.
  • Unified Error Decomposition: The authors introduce a novel decomposition technique that separates the total error into "approximation error" (inherent to the model) and "sample error" (stemming from the stochastic nature of the data). This framework simplifies the analysis of complex functional operators.

Conclusion and Future Directions

This research provides a robust theoretical foundation for online functional linear regression. By demonstrating that explicit regularization can overcome the saturation limitations of standard SGD, the authors pave the way for more efficient processing of high-dimensional functional streams.

However, several challenges remain. The optimal selection of the regularization parameter $\lambda$ currently depends on the total sample size $n$, which may not be known in true "anytime" learning scenarios. Future work could explore time-varying regularization parameters $\{\lambda_k\}$. Additionally, while the saturation boundary has been moved, it still exists for extremely smooth functions ($\theta > 1$). Extending these results to high-probability bounds, rather than just expected values, would also enhance the practical reliability of these algorithms in sensitive applications.

Summary updated

Abstract

In recent years, functional linear models have attracted growing attention in statistics and machine learning for recovering the slope function or its functional predictor. This paper considers online regularized learning algorithm for functional linear models in a reproducing kernel Hilbert space. It provides convergence analysis of excess prediction error and estimation error with polynomially decaying step-size and constant step-size, respectively. Fast convergence rates can be derived via a capacity dependent analysis. Introducing an explicit regularization term extends the saturation boundary of unregularized online learning algorithms with polynomially decaying step-size and achieves fast convergence rates of estimation error without capacity assumption. In contrast, the latter remains an open problem for the unregularized online learning algorithm with decaying step-size. This paper also demonstrates competitive convergence rates of both prediction error and estimation error with constant step-size compared to existing literature.
BibTeX
@article{mao2022online,
  author = {Yuan Mao and Zheng-Chu Guo},
  title = {{Online regularized learning algorithm for functional data}},
  journal = {J. Complex.},
  year = {2022},
  url = {https://openreview.net/forum?id=Qe2gtkHf7J},
}
Figure