Regularization by Early Stopping for Online Learning Algorithms
SILVIA VILLAAbstract. We study the learning algorithm corresponding to the incremental gradient descent deﬁned by theempirical risk over an inﬁnite 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 ﬁnite 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