Learning with incremental iterative regularization

SILVIA VILLAAbstract. We study the learning algorithm corresponding to the incremental gradient descent defined by theempirical risk over an infinite dimensional hypotheses space. We consider a statistical learning setting and showthat, provided with a universal step-size and a suitable early stopping rule, the learning algorithm thus obtained isuniversally consistent and derive finite sample bounds. Our results provide a theoretical foundation for consideringearly stopping in online learning algorithms and shed light on the effect of allowing for multiple passes over the data.Key words. Online learning, incremental gradient descent, consistency