Nonparametric stochastic approximation with large step-sizes

Aymeric Dieuleveut, Francis BachThe Annals of Statistics 2016 · DOI · arXiv

Abstract

We consider the random-design least-squares regression problem within the reproducing kernel Hilbert space (RKHS) framework. Given a stream of independent and identically distributed input/output data, we aim to learn a regression function within an RKHS $\mathcal{H}$, even if the optimal predictor (the conditional expectation) is not in $\mathcal{H}$. In a stochastic approximation framework where the estimator is updated after each observation, we show that the averaged unregularized least-mean-square (LMS) algorithm—a form of stochastic gradient descent—attains minimax optimal rates of convergence when paired with sufficiently large step-sizes. Our results apply to various regimes of smoothness for both the optimal prediction function and the functions in $\mathcal{H}$, and they extend to the finite-dimensional setting of parametric least-squares regression, demonstrating the estimator's adaptivity to the spectral decay of the covariate covariance matrix.

Introduction

In nonparametric regression, the goal is to learn the relationship between inputs and outputs without assuming a rigid functional form. Kernel methods, such as Kernel Ridge Regression (KRR), have long been the standard for this task. However, KRR typically requires solving large linear systems with $O(n^3)$ complexity and necessitates the careful tuning of a regularization parameter ($\lambda$).

Stochastic Approximation, or Stochastic Gradient Descent (SGD), provides a more efficient "online" alternative, updating the model one observation at a time. Traditionally, SGD employs "short" step-sizes that decrease at a rate of $1/n$. While stable, these small steps often lead to slow convergence in high-dimensional or infinite-dimensional settings. This paper addresses a critical gap in the literature: whether a single-pass, unregularized algorithm can achieve the same minimax optimal theoretical performance as batch-regularized methods by utilizing "large" step-sizes.

The Averaged Unregularized LMS Algorithm

The authors focus on the Averaged Unregularized Least-Mean-Square (LMS) algorithm. The process is defined by two primary components:

  1. The Update Rule: For each new observation $(x_n, y_n)$, the function $g$ is updated as follows: $$g_n = g_{n-1} - \gamma_n(g_{n-1}(x_n) - y_n)K_{x_n}$$ where $K_{x_n}$ represents the kernel function at $x_n$ and $\gamma_n$ is the step-size.

  2. Iterate Averaging: Rather than using the final iterate $g_n$, the algorithm outputs the average of all previous iterates: $\bar{g}_n = \frac{1}{n+1} \sum_{k=0}^n g_k$.

  3. Large Step-Sizes: In contrast to the $1/n$ decay used in traditional SGD, the authors employ constant step-sizes (for a fixed $n$) or slowly decreasing step-sizes (e.g., $n^{-1/2}$).

The theoretical analysis centers on the covariance operator of the RKHS and its spectral decay. By assuming the eigenvalues $\mu_i$ of the operator drop off according to $\mu_i \approx i^{-\alpha}$, the authors can characterize the convergence behavior in relation to the complexity of the space.

Key Insights and Theoretical Contributions

Implicit Regularization

A significant finding of this work is that explicit regularization (such as a penalty term like $\|g\|^2$) is unnecessary. Instead, the combination of a large step-size and the specific number of iterations acts as an implicit regularizer. This phenomenon functions as a built-in form of "early stopping" within the stochastic recursion.

Noise Cancellation through Averaging

In standard SGD, large step-sizes typically create a "noise floor" where iterates oscillate around the optimal solution. The authors demonstrate that averaging these iterates effectively cancels out this noise. This allows the algorithm to reap the benefits of the faster progress enabled by large steps without suffering the usual stability penalties.

Adaptivity and Misspecification

The method is naturally adaptive to the spectral decay of the kernel. It achieves the minimax optimal rate of $O(n^{-2\alpha r / (2\alpha r + 1)})$ by selecting a step-size based on the decay rate ($\alpha$) and the smoothness of the target function ($r$). Notably, these results hold even in "misspecified" cases—where the true regression function is either smoother or rougher than the functions contained within the chosen RKHS.

Empirical Validation

The theoretical results were validated using synthetic datasets, specifically Splines on the Circle. This toy model, where the RKHS consists of periodic Sobolev functions, allows for precise control over the smoothness of the target function using Bernoulli polynomials. In simulations, the measured "effective" convergence rates for the averaged LMS algorithm matched the predicted theoretical rates almost perfectly, outperforming other stochastic kernel algorithms that rely on smaller step-sizes.

Conclusion and Limitations

This research proves that simple, unregularized SGD with iterate averaging and large step-sizes is a theoretically optimal approach for nonparametric regression. It demonstrates that the traditional $1/n$ step-size is often sub-optimal for these problems.

However, some practical challenges remain. While the algorithm is "online," the basic implementation requires $O(n^2)$ time and space because each update adds a new support vector. Future work may involve integrating "reduced-set methods" to achieve $O(n)$ complexity. Additionally, the current analysis is limited to squared loss; extending these benefits to other loss functions, such as logistic regression, would likely require an "online Newton" approach. Finally, while the current bounds are provided in expectation, deriving high-probability bounds remains an open area for future research.

Summary updated

Abstract

We consider the random-design least-squares regression problem within the reproducing kernel Hilbert space (RKHS) framework. Given a stream of independent and identically distributed input/output data, we aim to learn a regression function within an RKHS $\mathcal{H}$, even if the optimal predictor (i.e., the conditional expectation) is not in $\mathcal{H}$. In a stochastic approximation framework where the estimator is updated after each observation, we show that the averaged unregularized least-mean-square algorithm (a form of stochastic gradient descent), given a sufficient large step-size, attains optimal rates of convergence for a variety of regimes for the smoothnesses of the optimal prediction function and the functions in $\mathcal{H}$. Our results apply as well in the usual finite-dimensional setting of parametric least-squares regression, showing adaptivity of our estimator to the spectral decay of the covariance matrix of the covariates.
BibTeX
@article{dieuleveut2016nonparametric,
  author = {Aymeric Dieuleveut and Francis Bach},
  title = {{Nonparametric stochastic approximation with large step-sizes}},
  journal = {The Annals of Statistics},
  year = {2016},
  doi = {10.1214/15-aos1391},
}
Figure