Generalized Conditional Gradient for Sparse Estimation
  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.
