Generalization Properties of Doubly Online Learning Algorithms

Junhong Lin, Lorenzo RosascoarXiv 2017 · DOI · OpenReview

Abstract: Doubly stochastic learning algorithms are scalable kernel methods that perform very well in practice. However, their generalization properties are not well understood and their analysis is challenging since the corresponding learning sequence may not be in the hypothesis space induced by the kernel. In this paper, we provide an in-depth theoretical analysis for different variants of doubly stochastic learning algorithms within the setting of nonparametric regression in a reproducing kernel Hilbert space and considering the square loss. Particularly, we derive convergence results on the generalization error for the studied algorithms either with or without an explicit penalty term. To the best of our knowledge, the derived results for the unregularized variants are the first of this kind, while the results for the regularized variants improve those in the literature. The novelties in our proof are a sample error bound that requires controlling the trace norm of a cumulative operator, and a refined analysis of bounding initial error.

Introduction

Kernel methods are a cornerstone of nonparametric machine learning, offering powerful tools for capturing complex patterns in data. However, traditional kernel methods suffer from a significant "curse of dimensionality" regarding computational resources: standard implementations require $O(T^2)$ time and space complexity for $T$ samples. This quadratic scaling makes them impractical for the massive datasets common in modern applications.

To address this, researchers developed doubly stochastic learning algorithms. These methods achieve scalability by employing two levels of approximation:

  1. Data Sampling: Utilizing stochastic gradient descent (SGD) to process one sample at a time.
  2. Feature Approximation: Approximating the kernel function using a finite set of random features (based on Bochner’s Theorem), which avoids the need to store the entire kernel matrix.

While these algorithms have demonstrated strong empirical performance, their theoretical foundations remained incomplete. This paper provides the first rigorous analysis of their generalization properties, particularly focusing on how these methods converge even when the learned functions drift outside the original hypothesis space.

The Challenge of "Out-of-Space" Iterates

The primary difficulty in analyzing doubly stochastic algorithms lies in the nature of the approximation. Because the algorithm uses a finite set of random features to approximate the kernel, the functions it produces ($f_t$) do not actually reside within the original Reproducing Kernel Hilbert Space (RKHS) $\mathcal{H}$.

Standard generalization proofs typically rely on the assumption that the iterates remain within $\mathcal{H}$. When the iterates leave this space, traditional bounds fail. Previous attempts to bridge this gap often required restrictive assumptions, such as bounded gradient estimates, which resulted in slower, sub-optimal convergence rates. This paper overcomes these hurdles by introducing a new error decomposition strategy that accounts for this "out-of-space" drift.

Methodological Framework

The authors analyze the algorithm within the context of nonparametric regression using the square loss function. They investigate three primary algorithmic variants:

  • Unregularized with a fixed step-size: Where the total number of iterations $T$ acts as the primary control for model complexity.
  • Unregularized with a decaying step-size: A standard SGD approach where the learning rate diminishes over time.
  • Regularized: Where an explicit penalty term (similar to Ridge Regression) is incorporated into the update rule.

The technical core of the analysis involves breaking the total error into "initial error" (the distance between the starting point and the ground truth) and "sample error" (noise introduced by the stochastic sampling of both data and features). To bound the sample error, the authors employ sophisticated functional analysis tools, specifically controlling the trace norm of a cumulative operator. This allows for a refined bound on the noise even as the iterates move outside the RKHS.

Key Theoretical Insights

Implicit Regularization and Early Stopping

A significant finding of this research is that explicit regularization is not strictly necessary for optimal performance. By carefully selecting the step-size or the total number of iterations, the algorithm naturally avoids overfitting. This phenomenon, known as "early stopping," allows the unregularized doubly stochastic algorithm to achieve the same optimal convergence rates as its regularized counterparts.

Optimal Convergence Rates

The authors derive convergence rates for the excess risk (generalization error). For a target function with regularity $\zeta$ and a kernel with capacity $\gamma$, they establish the following rate:

$$\mathbb{E}[\|f_{T+1} - f_\rho\|_\rho^2] \leq O\left(T^{-\frac{2\zeta}{2\zeta+\gamma+1}} \ln T\right)$$

These rates are essentially optimal for nonparametric regression in this setting. Notably, these results improve upon prior literature (e.g., Dai et al., 2014) and provide the first-ever theoretical guarantees for the unregularized version of the doubly stochastic algorithm.

Relaxed Assumptions

Unlike previous frameworks, this analysis does not require bounded gradient estimates. This relaxation makes the theory more applicable to real-world scenarios where data may contain outliers or follow heavy-tailed distributions, ensuring the mathematical guarantees hold under more realistic conditions.

Limitations and Future Directions

While this paper establishes a robust theoretical foundation, several avenues for future work remain:

  • High Probability Bounds: The current results are "in expectation." Future research is needed to derive high-confidence bounds that guarantee performance for a single execution of the algorithm.
  • Alternative Loss Functions: The current analysis is specific to the square loss. Extending these proofs to other convex losses, such as the Hinge loss for classification, would broaden the utility of the theory.
  • Iterate Refinement: The study focuses on the "last iterate" of the SGD process. Exploring iterate averaging or mini-batching could potentially yield even more stable convergence in practice.
  • Multi-pass Analysis: This theory covers the "online" (single-pass) setting. Analyzing the dynamics of multi-pass stochastic methods within the doubly stochastic framework remains an open challenge.

Summary updated

Abstract

Doubly stochastic learning algorithms are scalable kernel methods that perform very well in practice. However, their generalization properties are not well understood and their analysis is challenging since the corresponding learning sequence may not be in the hypothesis space induced by the kernel. In this paper, we provide an in-depth theoretical analysis for different variants of doubly stochastic learning algorithms within the setting of nonparametric regression in a reproducing kernel Hilbert space and considering the square loss. Particularly, we derive convergence results on the generalization error for the studied algorithms either with or without an explicit penalty term. To the best of our knowledge, the derived results for the unregularized variants are the first of this kind, while the results for the regularized variants improve those in the literature. The novelties in our proof are a sample error bound that requires controlling the trace norm of a cumulative operator, and a refined analysis of bounding initial error.
BibTeX
@misc{lin2017generalization,
  author = {Junhong Lin and Lorenzo Rosasco},
  title = {{Generalization Properties of Doubly Online Learning Algorithms}},
  year = {2017},
  eprint = {1707.00577},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1707.00577},
}
Figure