Dynamic Screening with Approximate Dictionaries
Résumé
Various strategies to accelerate the Lasso optimization have been recently proposed. Among them, screening rules provide a way to safely eliminate inactive variables, thus reducing the problem’s dimensionality. Another line of work consists in replacing the dictionary matrix by a structured approximation of it, which is faster to manipulate. This paper proposes a method to conciliate both strategies. First, we show how to obtain safe screening rules for the exact problem while manipulating an approximate dictionary. We then adapt an existing screening rule to this new framework and define a general procedure to leverage the advantages of both strategies. Significant complexity reductions are obtained in comparison to screening rules alone.
Différentes stratégies pour accélérer la résolution du problème Lasso ont été proposées dernièrement. Notamment, les règles de screening, qui réduisent la dimensionalité du problème en permettent l’élimination de variables inutiles. Une autre technique consiste à approcher le dictionnaire par une matrice structurée plus rapide à manipuler. Cet article propose une façon de concilier ces deux stratégies. D’abord, on montre comment obtenir des règles de screening sûres vis-à-vis du problème exact en manipulant un dictionnaire approché. Ensuite, on adapte une règle de screening existante à ce nouveau cadre et on définit une procédure générale pour bien combiner les avantages des deux approches. Des réductions significatives de complexité ont été observées par rapport au screening isolé.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...