Capacity dependent analysis for functional online learning algorithms

Xin Guo, Zheng-Chu Guo, Lei ShiarXiv 2022 · OpenReview

Abstract

This article provides convergence analysis of online stochastic gradient descent algorithms for functional linear models. Adopting the characterizations of the slope function regularity, the kernel space capacity, and the capacity of the sampling process covariance operator, significant improvement on the convergence rates is achieved. Both prediction problems and estimation problems are studied, where we show that capacity assumption can alleviate the saturation of the convergence rate as the regularity of the target function increases. We show that with properly selected kernel, capacity assumptions can fully compensate for the regularity assumptions for prediction problems (but not for estimation problems). This demonstrates the significant difference between the prediction problems and the estimation problems in functional data analysis.

Introduction

In Functional Data Analysis (FDA), the Functional Linear Model aims to relate a scalar response $Y$ to a random input function $X(u)$. This task is inherently challenging because functions reside in infinite-dimensional spaces. Researchers typically employ Stochastic Gradient Descent (SGD) to learn the "slope function" $\beta^*$ that defines this relationship.

However, existing theoretical analyses often encounter a "saturation" point—a speed limit where the algorithm’s convergence rate ceases to improve even if the true slope function is extremely smooth (high regularity). This paper addresses this limitation by considering not only the smoothness of the target but also the "capacity" of the space it occupies, which characterizes how quickly the eigenvalues of the data's dimensions decay.

Methodology

The authors utilize a kernel-based SGD approach within a Reproducing Kernel Hilbert Space (RKHS). They analyze two primary learning scenarios:

  1. The Online Setting: An infinite stream of data where the model is updated iteratively with a decreasing step-size.
  2. The Finite-Horizon Setting: A fixed dataset of size $T$ where the algorithm uses a constant step-size optimized for that specific sample size.

The technical core is the Capacity Dependent Analysis. By using a condition based on the trace of the integral operator ($\text{Tr}(\mathcal{L}_K^s) < \infty$), the authors characterize the eigenvalue decay of the kernel and covariance operators. This allows for a more nuanced error decomposition that tracks the propagation of noise and approximation errors through iterations.

Key Insights: Prediction vs. Estimation

A fundamental contribution of this work is highlighting the divide between prediction and estimation in functional learning:

  • Prediction (estimating $Y$ for a new $X$) is relatively "easier" due to the smoothing effect of the integration process. The authors demonstrate that capacity assumptions can fully compensate for a lack of regularity in prediction tasks.
  • Estimation (identifying the exact $\beta^*$) is more difficult. While capacity helps, it cannot entirely replace the requirement for target function smoothness.

Furthermore, the paper provides a mathematical bridge between different capacity measures (trace conditions, effective dimension, and eigenvalue decay), showing their equivalence under specific conditions.

Key Results

The analysis yields optimal rates for prediction. In the online setting, the convergence rate is $O(t^{-\theta})$, where $\theta$ is a complex index derived from both regularity ($r$) and capacity ($s$). For the finite-horizon setting, the rate can approach $O(T^{-1})$ for highly smooth functions.

Convergence rate index $\theta$ as a function of regularity $r$ and capacity $s$.

As shown in the figure above, the convergence rate $\theta$ is determined by the interplay between regularity $r$ and capacity $s$. The capacity assumptions alleviate the saturation of convergence rates found in previous "capacity-independent" analyses. A smaller capacity (faster eigenvalue decay) allows the rate to continue improving as regularity increases.

The paper also provides non-trivial convergence rates for estimation error in the strong RKHS metric, moving beyond the weak convergence (prediction error) typically studied. Additionally, assuming a specific capacity ($s < 1$) removes logarithmic factors from the convergence bounds, resulting in cleaner theoretical rates.

Limitations and Future Work

Despite these advancements, some challenges remain:

  • The $s=1$ Gap: The online estimation analysis does not yet cover the capacity-independent setting ($s=1$), which remains an open theoretical problem.
  • Known Operators: The analysis assumes certain properties of the covariance operator are fixed. In practice, estimating covariance from data introduces additional noise.
  • Practical Implementation: The work is primarily theoretical and does not provide a direct guide for estimating parameters $s$ or $r$ from real-world data to choose optimal step-sizes. Future research could focus on adaptive algorithms that automatically sense these parameters.

Summary updated

Abstract

This article provides convergence analysis of online stochastic gradient descent algorithms for functional linear models. Adopting the characterizations of the slope function regularity, the kernel space capacity, and the capacity of the sampling process covariance operator, significant improvement on the convergence rates is achieved. Both prediction problems and estimation problems are studied, where we show that capacity assumption can alleviate the saturation of the convergence rate as the regularity of the target function increases. We show that with properly selected kernel, capacity assumptions can fully compensate for the regularity assumptions for prediction problems (but not for estimation problems). This demonstrates the significant difference between the prediction problems and the estimation problems in functional data analysis.
BibTeX
@misc{guo2022capacity,
  author = {Xin Guo and Zheng-Chu Guo and Lei Shi},
  title = {{Capacity dependent analysis for functional online learning algorithms}},
  year = {2022},
  eprint = {2209.12198},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2209.12198},
}
Figure