Designing and analysing new early stopping rules for saving computational resources

Ce travail développe et analyse des stratégies pour construire des instances de ce que l’on appelle les règles d’arrêt prématurés appliquées à certains algorithmes d’apprentissage itératif pour estimer la fonction de régression. Ces quantités sont des règles "data-driven" indiquant quand arrêter le processus d’apprentissage itératif pour parvenir à un compromis entre les coûts de calcul et la précision statistique. Contrairement à une grande partie de la littérature existante sur l’arrêt prématuré, où ces règles ne dépendent que des données de manière "faible", nous fournissons des solutions data-driven pour le problème susmentionné sans utiliser les données de validation. L’idée cruciale exploitée ici est celle du principe d’écart minimal (MDP), qui montre où arrêter un algorithme d’apprentissage itératif. À notre connaissance, cette idée remonte aux travaux de Vladimir A. Morozov dans les années 1960-1970 qui a étudié des problèmes linéaires mal posés et leur régularisation, principalement inspirés par des problèmes de physique mathématique. Parmi les différentes applications de cette ligne de travail, les soi-disant estimateurs de filtre spectral tels que le "spectral cut-off", les itérations de Landweber, et la régularisation de Tikhonov (ridge) ont reçu beaucoup d’attention (par exemple, dans des problèmes statistiques inverses). Il est à noter que le principe d’écart minimal consiste à contrôler les résidus d’un estimateur (qui sont minimisés de manière itérative) et à leur fixer correctement un seuil tel que l’on puisse atteindre une certaine optimalité (minimax). La première partie de cette thèse est consacrée aux garanties théoriques des règles d’arrêt basées sur le principe d’écart minimal et appliquées à la descente de gradient, et à la régression de Tikhonov (ridge) dans le cadre de l’espace de Hilbert à noyau reproduisant (RKHS). Là, nous montrons que ce principe fournit un estimateur fonctionnel optimal minimax de la fonction de régression lorsque le rang du noyau est fini. Cependant, quand nous traitons des noyaux reproduisants de rang infini, l’estimateur résultant sera seulement sous-optimal. En recherchant une solution, nous avons trouvé l’existence de la stratégie dite de lissage polynomial des résidus. Cette stratégie (combinée avec le MDP) s’est avérée optimale pour l’estimateur "spectral cut-off" dans le modèle de séquence gaussienne linéaire. Nous empruntons cette stratégie, modifions la règle d’arrêt en conséquence, et prouvons que le principe d’écart minimal lissé produira un estimateur fonctionnel optimal minimax sur une gamme d’espaces de fonctions, qui comprend la classe de fonctions Sobolev bien connue. Notre deuxième contribution consiste à explorer des propriétés théoriques de la règle d’arrêt d’écart minimal appliquée à la famille plus générale des estimateurs linéaires. La principale difficulté de cette approche est que, contrairement aux estimateurs de filtre spectral considérés précédemment, les estimateurs linéaires ne conduisent plus à des quantités monotones (les biais et variance). Mentionnons que c’est également le cas des algorithmes célèbres tels que la descente de gradient stochastique. Motivés par d’autres applications pratiques, nous travaillons avec l’estimateur de régression des k plus proches voisins largement utilisé, comme premier exemple fiable. Nous montrons que la règle d’arrêt susmentionnée conduit à un estimateur fonctionnel optimal minimax, en particulier sur la classe des fonctions de Lipschitz sur un domaine borné. La troisième contribution consiste à illustrer au moyen de simulations empiriques que, pour le choix du paramètre dans un estimateur linéaire (la méthode des k plus proches voisins, la régression de Nadaraya-Watson, et l’estimateur de sélection de variables), la règle d’arrêt prématuré basée sur le MDP se comporte comparativement bien par rapport à d’autres critères de sélection de modèles, largement utilisés et connus.This work develops and analyzes strategies for constructing instances of the so-called early stopping rules applied to some iterative learning algorithms for estimating the regression function. Such quantities are data-driven rules indicating when to stop the iterative learning process to reach a trade-off between computational costs and the statistical precision. Unlike a large part of the existing literature on early stopping, where these rules only depend on the data in a "weak manner", we provide data-driven solutions for the aforementioned problem without utilizing validation data. The crucial idea exploited here is that of the minimum discrepancy principle (MDP), which shows when to stop an iterative learning algorithm. To the best of our knowledge, this idea dates back to the work of Vladimir A. Morozov in the 1960s-1970s who studied linear ill-posed problems and their regularization, mostly inspired by mathematical physics problems. Among different applications of this line of work, the so-called spectral filter estimators such as spectral cut-off, Landweber iterations, and Tikhonov (ridge) regularization have received quite a lot of attention (e.g., in statistical inverse problems). It is worth mentioning that the minimum discrepancy principle consists in controlling the residuals of an estimator (which are iteratively minimized) and properly setting a threshold for them such that one can achieve some (minimax) optimality. The first part of this thesis is dedicated to theoretical guarantees of stopping rules based on the minimum discrepancy principle and applied to gradient descent, and Tikhonov (ridge) regression in the framework of reproducing kernel Hilbert space (RKHS). There, we show that this principle provides a minimax optimal functional estimator of the regression function when the rank of the kernel is finite. However, when one deals with infinite-rank reproducing kernels, the resulting estimator will be only suboptimal. While looking for a solution, we found the existence of the so-called residuals polynomial smoothing strategy. This strategy (combined with MDP) has been proved to be optimal for the spectral cut-off estimator in the linear Gaussian sequence model. We borrow this strategy, modify the stopping rule accordingly, and prove that the smoothed minimum discrepancy principle yields a minimax optimal functional estimator over a range of function spaces, which includes the well-known Sobolev function class. Our second contribution consists in exploring the theoretical properties of the minimum discrepancy stopping rule applied to the more general family of linear estimators. The main difficulty of this approach is that, unlike the spectral filter estimators considered earlier, linear estimators do no longer lead to monotonic quantities (the bias and variance terms). Let us mention that this is also the case for famous algorithms such as Stochastic Gradient Descent. Motivated by further practical applications, we work with the widely used k-NN regression estimator as a reliable first example. We prove that the aforementioned stopping rule leads to a minimax optimal functional estimator, in particular, over the class of Lipschitz functions on a bounded domain.The third contribution consists in illustrating through empirical experiments that for choosing the tuning parameter in a linear estimator (the k-NN regression, Nadaraya-Watson, and variable selection estimators), the MDP-based early stopping rule performs comparably well with respect to other widely used and known model selection criteria