Learning with Incremental Iterative Regularization
Within a statistical learning setting, we propose and study an iterative regularization algorithm for least squares defined by an incremental gradient method. In particular, we show that, if all other parameters are fixed a priori, the number of passes over the data (epochs) acts as a regularization parameter, and prove strong universal consistency, i.e. almost sure convergence of the risk, as well as sharp finite sample bounds for the iterates. Our results are a step towards understanding the effect of multiple epochs in stochastic gradient techniques in machine learning and rely on integrating statistical and optimization results.
AbstractThe paper considers the following scenario for leastsquares regression: - the covariate X is Hilbert space H valued - the considered function class is the set of bounded linear functionals over that Hilbert space H - the population least squares risk over H needs to be minimized. To solve this problem a method based on the empiricalrisk is considered that iteratively goes through the samples and performs a gradient step in the corresponding direction. The main theorems establish consistency (Theorem 1) andlearning rates (Theorems 2 and 3) under early stopping.These results are both in terms of excess risk andH-norm (if a minimizer exists). CommentsThe paper nicely describes the regularization effect of early stopping for this particular learning problem. In addition, the considered rather general setupincludes both linear regression and regression with RKHSs (for the latter it would have been nice though, toinclude a computational cost estimate). On the downside, the obtained rates for excess risk are far from beingoptimal. The proofs, which are mostly deferred to an appendix, use Hilbert space valued concentration inequalities, but the way the proof is set up, it seems that significantnew work is needed compared to the case of Thikonovregularization ("kernel least squares regression" or"least squares regression").Here some minor comments:pages 2. It should be better communicated why theHilbert space approach is taken (instead of an RKHS approach). Also, it should be better explained how the latter is recovered from your general setu.page 3, line following (4). I have no idea where an assumption like (3) and (4) can be found in [28]. This needs to be explained in detail.