Fast column generation for atomic norm regularization

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
The 20th International Conference on Artificial Intelligence and Statistics, Apr 2017, Fort Lauderdale, United States. 2017, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics
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 : jeudi 11 janvier 2018 - 06:20:23
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. 2017, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics. 〈hal-01502575〉

Partager

Métriques

Consultations de la notice

76

Téléchargements de fichiers

37