We propose a conditional gradient framework for a composite convex minimization template with broad applications. Our approach combines the notions of smoothing and homotopy under the CGM framework, and provably achieves the optimal @math convergence rate. We demonstrate that the same rate holds if the linear subproblems are solved approximately with additive or multiplicative error. Specific applications of the framework include the non-smooth minimization, semidefinite programming, and minimization with linear inclusion constraints over a compact domain. We provide numerical evidence to demonstrate the benefits of the new framework.
The CGM for composite problems is considered recently by and . A similar but slightly different template, where @math and @math are assumed to be a closed convex cone and a norm respectively, is also studied by @cite_6 . However, these works are based on the resolvents of a modified oracle, which can be expensive, unless @math , or @math .
@cite_6
2003146967
Motivated by some applications in signal processing and machine learning, we consider two convex optimization problems where, given a cone @math K, a norm @math ?·? and a smooth convex function @math f, we want either (1) to minimize the norm over the intersection of the cone and a level set of @math f, or (2) to minimize over the cone the sum of @math f and a multiple of the norm. We focus on the case where (a) the dimension of the problem is too large to allow for interior point algorithms, (b) @math ?·? is "too complicated" to allow for computationally cheap Bregman projections required in the first-order proximal gradient algorithms. On the other hand, we assume that it is relatively easy to minimize linear forms over the intersection of @math K and the unit @math ?·?-ball. Motivating examples are given by the nuclear norm with @math K being the entire space of matrices, or the positive semidefinite cone in the space of symmetric matrices, and the Total Variation norm on the space of 2D images. We discuss versions of the Conditional Gradient algorithm capable to handle our problems of interest, provide the related theoretical efficiency estimates and outline some applications.