Generalized Conditional Gradient for Sparse Estimation
This provides a more efficient computational method for researchers and practitioners working with structured sparsity in data analysis applications.
The paper tackles the challenge of efficient algorithm design for structured sparse optimization problems by enhancing the generalized conditional gradient (GCG) algorithm, showing it can significantly reduce training costs compared to state-of-the-art alternatives in experiments on matrix completion, multi-class classification, multi-view dictionary learning, and overlapping group lasso.
Structured sparsity is an important modeling tool that expands the applicability of convex formulations for data analysis, however it also creates significant challenges for efficient algorithm design. In this paper we investigate the generalized conditional gradient (GCG) algorithm for solving structured sparse optimization problems---demonstrating that, with some enhancements, it can provide a more efficient alternative to current state of the art approaches. After providing a comprehensive overview of the convergence properties of GCG, we develop efficient methods for evaluating polar operators, a subroutine that is required in each GCG iteration. In particular, we show how the polar operator can be efficiently evaluated in two important scenarios: dictionary learning and structured sparse estimation. A further improvement is achieved by interleaving GCG with fixed-rank local subspace optimization. A series of experiments on matrix completion, multi-class classification, multi-view dictionary learning and overlapping group lasso shows that the proposed method can significantly reduce the training cost of current alternatives.