Active set algorithms for the LASSO

Le LASSO est une méthode de régression ajoutant à la méthode des moindres-carrés une contrainte ou une pénalisation sur la norme l1 du coefficient linéaire. Cette contrainte a un effet de sélection de variable et de régularisation sur l'estimateur. Un estimateur LASSO est défini comme étant la solution d'un problème pouvant être vu comme un programme quadratique. Cette thèse se base sur deux algorithmes dédiés à la résolution du LASSO publiés en 2000 par M. Osbourne et alii. L'un, une méthode par homotopie, a été reformulé en 2004 par J. Friedman et alii sous le nom de LAR-LASSO (ou LARS), s'imposant alors comme la méthode standard. Le second, présenté comme une méthode d'ensemble actif, fût largement ignoré, semble-t-il pour deux raisons: une application apparemment limitée à la formulation "contrainte", et une compréhension plus difficile de l'algorithme. Nous reformulons donc le principe général du second, que nous baptisons "Descente sur Ensemble Actif" (DEA) et sa dérivation sur le LASSO, ainsi que la méthode par homotopie que nous mettons en évidence comme directement dérivée de la DEA. La formulation simplifiée des deux méthodes permet d'en améliorer la compréhension, mais aussi l'efficacité en temps de calcul. Elle met en outre en évidence l'applicabilité de la DEA sur la formulation "pénalisée" du LASSO, donnant un algorithme plus simple encore. Enfin, elle conduit à une analyse et un traitement de cas limites dans lesquels ces algorithmes peuvent échouer. Nous proposons ensuite une application directe du LASSO sur un nombre infini de variables formant un espace multidimensionel, et étudions l'adaptation des algorithmes d'ensemble actifs dans ce cadre.The LASSO is a regression method that adds a constraint or penalization of the l1 norm of the coefficient to the least-squares methodThe LASSO is a regression method that adds a constraint or penalization of the l1 norm of the coefficient to the least-squares method. This constraint has variable-selection and a regularization effects over the estimator. The LASSO estimator is defined as a solution to a minimization problem that can be seen as a quadratic program. This thesis is based on two algorithms designed for solving the LASSO, that were published in 2000 by Osbourne et alii. One, an homotopy method, was re-formulated and popularized in 2004 by J. Friedman et alii under the name of LAR-LASSO (or LARS). The second, presented as an active set method, was largely ignored, for two main reasons: its apparent limitation to the constrained formulation, and a more difficult understanding of the algorithm. We re-formulate its general principle, under the name of "Active Set Descent", and its derivation for the LASSO problem, as well as the homotopy method, that appears as a direct extension of ASD. The simplified formulation of both methods yields a better understanding, and also a lower complexity, in terms of computation time. It also shows the direct appliability of ASD to the penalized formulation of the LASSO, in a even simpler algorithm than for the constrained one. Finally, it facilitates the analysis and workarounds of degenerate situations in which the algorithms may fail. We then propose a direct application of the LASSO on an infinite number of variables forming a multidimensional space, and study the adaptation of active set algorithms on this framework