Non-parametric Stochastic Approximation with Large Step sizes

Aymeric Dieuleveut (1, 2, 3) , Francis Bach (1, 2)

1 SIERRA - Statistical Machine Learning and Parsimony
2 LIENS - Laboratoire d'informatique de l'école normale supérieure
3 CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique

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), 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}$.

Mots clés: Reproducing kernel Hilbert space; Stochastic approximation

Domaines: Statistiques [math.ST]; Théorie [stat.TH]

Aymeric Dieuleveut, Francis Bach. Non-parametric Stochastic Approximation with Large Step sizes. The Annals of Statistics, 2015, 44 (4), ⟨10.1214/15-AOS1391⟩. ⟨hal-01053831v2⟩