Learning with incremental iterative regularization

Machine learning applications often require efficient statistical procedures to process potentially massive amount of high dimensional data. Motivated by such applications, the broad objective of our study is deriving learning procedures with optimal statistical properties, and, at the same time, computational complexities proportional to the generalization properties allowed by the data, rather than their raw amount [5]. In this paper, we focus on iterative regularization as a viable approach towards this goal. The key observation behind these techniques is that iterative optimization schemes applied to scattered, noisy data exhibit a self-regularizing property, in the sense that early termination (early-stop) of the iterative process has a regularizing effect [19, 22]. Indeed, iterative regularization algorithms are classical in inverse problems [14], and have been recently considered in machine learning [6, 32, 2, 4, 8, 24], where they have been proved to achieve optimal learning bounds, matching those of variational regularization schemes such as Tikhonov [7, 29]. 1 In this paper, we consider an iterative regularization algorithm for the square loss, based on a recursive procedure updating the solution after processing one training set point at each iteration. Methods of the latter form, often broadly referred to as online learning algorithms, have become standard in the processing of large data-sets, because of their often low iteration cost and good practical performance. Theoretical studies for this class of algorithms have been developed within different frameworks.