Fast column generation for atomic norm regularization

Marina Vinyes 1, 2, 3 Guillaume Obozinski 1, 2, 3
3 IMAGINE [Marne-la-Vallée]
LIGM - Laboratoire d'Informatique Gaspard-Monge, ENPC - École des Ponts ParisTech
Abstract : We consider optimization problems that consist in minimizing a quadratic function under an atomic norm regularization or constraint. In the line of work on conditional gradient algorithms, we show that the fully corrective Frank-Wolfe (FCFW) algorithm — which is most naturally reformulated as a column generation algorithm in the regularized case — can be made particularly efficient for difficult problems in this family by solving the simplicial or conical subproblems produced by FCFW using a special instance of a classical active set algorithm for quadratic programming (Nocedal and Wright, 2006) that generalizes the min-norm point algorithm (Wolfe, 1976). Our experiments show that the algorithm takes advantages of warm-starts and of the sparsity induced by the norm, displays fast linear convergence, and clearly outperforms the state-of-the-art, for both complex and classical norms, including the standard group Lasso.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

Littérature citée [37 références]  Voir  Masquer  Télécharger

https://hal-enpc.archives-ouvertes.fr/hal-01502575
Contributeur : Marina Vinyes <>
Soumis le : dimanche 9 avril 2017 - 17:35:37
Dernière modification le : mercredi 4 juillet 2018 - 16:38:09
Document(s) archivé(s) le : lundi 10 juillet 2017 - 12:25:14

Identifiants

  • HAL Id : hal-01502575, version 1

Citation

Marina Vinyes, Guillaume Obozinski. Fast column generation for atomic norm regularization. The 20th International Conference on Artificial Intelligence and Statistics, Apr 2017, Fort Lauderdale, United States. ⟨hal-01502575⟩

Partager

Métriques

Consultations de la notice

181

Téléchargements de fichiers

112