Fast column generation for atomic norm regularization


Marina Vinyes, Guillaume Obozinski ;
Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:547-556, 2017.


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 that generalizes the min-norm point algorithm.

Related Material