Hybrid Conditional Gradient - Smoothing Algorithms with Applications to Sparse and Low Rank Regularization
This work provides an incremental improvement for researchers in optimization and machine learning dealing with large-scale problems involving sparse and low-rank regularization.
The authors tackled the problem of solving composite convex optimization problems with multiple nonsmooth terms by developing a hybrid conditional gradient-smoothing algorithm (HCGS), which demonstrated computational advantages over proximal methods on large-scale matrix optimization problems including sparse PCA.
We study a hybrid conditional gradient - smoothing algorithm (HCGS) for solving composite convex optimization problems which contain several terms over a bounded set. Examples of these include regularization problems with several norms as penalties and a norm constraint. HCGS extends conditional gradient methods to cases with multiple nonsmooth terms, in which standard conditional gradient methods may be difficult to apply. The HCGS algorithm borrows techniques from smoothing proximal methods and requires first-order computations (subgradients and proximity operations). Unlike proximal methods, HCGS benefits from the advantages of conditional gradient methods, which render it more efficient on certain large scale optimization problems. We demonstrate these advantages with simulations on two matrix optimization problems: regularization of matrices with combined $\ell_1$ and trace norm penalties; and a convex relaxation of sparse PCA.