Online Learning as Stochastic Approximation of Regularization Paths: Optimality and Almost-Sure Convergence

By Pierre Tarres, Yuan Yao. 2011

99 citations recorded by the source corpus.

In this paper, an online learning algorithm is proposed as sequential stochastic approximation of a regularization path converging to the regression function in reproducing kernel Hilbert spaces (RKHSs). We show that it is possible to produce the best known strong (RKHS norm) convergence rate of batch learning, through a careful choice of the gain or step size sequences, depending on regularity assumptions on the regression function. The corresponding weak (mean square distance) convergence rate is optimal in the sense that it reaches the minimax and individual lower rates in this paper. In both cases, we deduce almost sure convergence, using Bernstein-type inequalities for martingales in Hilbert spaces. To achieve this, we develop a bias-variance decomposition similar to the batch learning setting; the bias consists in the approximation and drift errors along the regularization path, which display the same rates of convergence, and the variance arises from the sample error analyzed as a (reverse) martingale difference sequence. The rates above are obtained by an optimal tradeoff between the bias and the variance.

Subfields: Computational Mechanics, Control and Systems Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Control and Systems Engineering

Citations in the corpus

Non-parametric Stochastic Approximation with Large Step sizes (2014, methodology): “In the next section, we illustrate on such a toy model our main results and compare our learning algorithm to Ying and Pontil’s [16], Tarrès and Yao’s [17] and Zhang’s [42] algorithms.”
Optimal Statistical Rates for Decentralised Non-Parametric Regression with Linear Speed-Up (2019, methodology): “We will need the following lemma, taken from [26, Lemma 15], which itself follows [55, 48].”
Stochastic Gradient Descent for Nonconvex Learning Without Bounded Gradient Assumptions (2019, background): “ log− β 1+α (T+2). This together with (6) then shows the stated result. This proves the Part (b). C. Proof of Theorem 4 We shall need the following elementary inequality which was essentially used in [21, 25]. Lemma 6. Let {ηt}t∈N be a sequence of non-negative numbers such that lim t→∞ η =0and P∞ t=”
Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learning (2014, methodology): “Another important difference is that we can use any smooth and Lipschitz loss, useful for example to generate sparse solutions, while the optimal results in [29, 33] are specific for the square loss.”