 |
Communication dans un congrès
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.
Littérature citée [37 références]
https://hal-enpc.archives-ouvertes.fr/hal-01502575
Contributeur : Marina Vinyes <>
Soumis le : dimanche 9 avril 2017 - 17:35:37
Dernière modification le : mardi 8 décembre 2020 - 09:51:09
Archivage à long terme le : : lundi 10 juillet 2017 - 12:25:14
Contributeur : Marina Vinyes <>
Soumis le : dimanche 9 avril 2017 - 17:35:37
Dernière modification le : mardi 8 décembre 2020 - 09:51:09
Archivage à long terme le : : lundi 10 juillet 2017 - 12:25:14