AISTATS 2017poster16 citations
Fast column generation for atomic norm regularization
Marina Vinyes, Guillaume Obozinski
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 that generalizes the min-norm point algorithm.
BibTeX
@InProceedings{pmlr-v54-vinyes17a,
title = {{Fast column generation for atomic norm regularization}},
author = {Vinyes, Marina and Obozinski, Guillaume},
booktitle = {Proceedings of the 20th International Conference on Artificial Intelligence and Statistics},
pages = {547--556},
year = {2017},
editor = {Singh, Aarti and Zhu, Jerry},
volume = {54},
series = {Proceedings of Machine Learning Research},
month = {20--22 Apr},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v54/vinyes17a/vinyes17a.pdf},
url = {https://proceedings.mlr.press/v54/vinyes17a.html},
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 that generalizes the min-norm point algorithm.}
}