Active set strategy for high-dimensional non-convex sparse optimization problems

Description

The use of non-convex sparse regularization has attracted much interest when estimating a very sparse model on high dimensional data. In this work we express the optimality conditions of the optimization problem for a large class of non-convex regularizers. From those conditions, we derive an efficient active set strategy that avoids the computing of unnecessary gradients. Numerical experiments on both generated and real life datasets show a clear gain in computational cost w.r.t. the state of the art when using our method to obtain very sparse solutions.

Abstract (French)

L'utilisation de régularisations non-convexes a attiré beaucoup d'attention pour l'estimation de modèles parcimonieux en grandes dimensions. Dans ce travail, nous exprimons les conditions d'optimalité du problème d'optimisation correspondant pour une large classe de régularisations non convexes. Nous développons un stratégie de type "ensemble actif" efficace à partir de ces conditions, évitant ainsi des calculs de gradients inutiles. Une étude numérique sur données générées et sur données réelles montrent clairement l'apport en temps de calcul de notre méthode par rapport à celles de l'état de l'art pour obtenir des solutions très parcimonieuses.

Abstract

International audience

Additional details