Fast column generation for atomic norm regularization

Marina Vinyes (1, 2, 3) , Guillaume Obozinski (1, 2, 3)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 ENPC - École des Ponts ParisTech
3 imagine [Marne-la-Vallée]

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.

Mots clés: active set; conditional gradient; convex optimization; structured sparsity; atomic norm

Domaines: Machine Learning [stat.ML]

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⟩