Une perspective unifiée sur la sparsité structurée convexe : Normes hiérarchiques, symétriques, submodulaires et au-delà.

Résumé Dans cet article, nous proposons une théorie unifiée pour les normes convexes structurées induisant la sparsité sur des vecteurs associés à des fonctions de pénalité combinatoires. Plus précisément, nous considérons la situation d'un modèle simultanément (a) pénalisé par une fonction d'ensemble définie sur le support du vecteur paramètre inconnu qui représente la connaissance préalable sur les supports, et (b) régularisé en p-norme. Nous montrons que chacun des problèmes d'optimisation combinatoire obtenus admet une relaxation naturelle en tant que problème d'optimisation régularisé par une norme correspondante induisant la sparsité. Pour caractériser l'étanchéité de la relaxation, nous introduisons une notion d'enveloppe combinatoire inférieure d'une fonction-ensemble. Symétriquement, une notion d'enveloppe combinatoire supérieure produit l'expression de norme la plus concise. Nous montrons que ces relaxations prennent la forme de Lassos de groupes latents combinatoires associés à des pénalités à couverture minimale, également connues sous le nom de schémas de codage par blocs. Pour les fonctions de pénalité submodulaires, la norme associée, la norme duale et l'opérateur proximal correspondant peuvent être calculés efficacement à l'aide d'un algorithme générique de type diviser pour régner. Notre cadre obtient des dérivations constructives pour le Lasso, le Lasso de groupe, le Lasso exclusif, les pénalités OWL, OSCAR et SLOPE, la norme k-support, plusieurs pénalités hiérarchiques considérées dans la littérature pour les chaînes et les structures arborescentes, et produit également de nouvelles normes. Elle conduit à des algorithmes généraux efficaces pour toutes ces normes, récupérant comme cas particuliers plusieurs algorithmes proposés dans la littérature et produisant des procédures améliorées pour certains cas. Pour les normes associées à des pénalités submodulaires, y compris un grand nombre de normes non-décomposables, nous généralisons les résultats classiques de récupération de support et de convergence rapide basés respectivement sur la généralisation de la condition d'irreprésentabilité et de la condition de valeur propre restreinte.