Asymptotic linear convergence of fully-corrective generalized conditional gradient methods

Abstract

We propose a fully-corrective generalized conditional gradient method (FC-GCG) for the minimization of the sum of a smooth, convex loss function and a convex one-homogeneous regularizer over a Banach space. The algorithm relies on the mutual update of a finite set ${\mathcal{A}}_k$ of extremal points of the unit ball of the regularizer and of an iterate $u_k\in \mathrm{cone}({\mathcal{A}}_k)$. Each iteration requires the solution of one linear problem to update ${\mathcal{A}}_k$ and of one finite dimensional convex minimization problem to update the iterate. Under standard hypotheses on the minimization problem we show that the algorithm converges sublinearly to a solution. Subsequently, imposing additional assumptions on the associated dual variables, this is improved to a linear rate of convergence. The proof of both results relies on two key observations: First, we prove the equivalence of the considered problem to the minimization of a lifted functional over a particular space of Radon measures using Choquet's theorem. Second, the FC-GCG algorithm is connected to a Primal-Dual-Active-point Method (PDAP) on the lifted problem for which we finally derive the desired convergence rates.

arXiv comment50 pages, 3 figures

References in corpus (11)

• The Convex Geometry of Linear Inverse Problems
• The Sliding Frank-Wolfe Algorithm and its Application to Super-Resolution Microscopy
• Sparsity of solutions for variational inverse problems with finite-dimensional data
• On the linear convergence rates of exchange and continuous methods for total variation minimization
• Dynamic Cell Imaging in PET with Optimal Transport Regularization
• A generalized conditional gradient method for dynamic inverse problems with optimal transport regularization
• On the extremal points of the ball of the Benamou-Brenier energy
• An optimal transport approach for solving dynamic inverse problems in spaces of measures
• A superposition principle for the inhomogeneous continuity equation with Hellinger-Kantorovich-regular coefficients
• Extremal points and sparse optimization for generalized Kantorovich-Rubinstein norms
• Tensor-Free Proximal Methods for Lifted Bilinear/Quadratic Inverse Problems with Applications to Phase Retrieval

Cited by in corpus (4)

• Extremal points and sparse optimization for generalized Kantorovich-Rubinstein norms
• On extremal points for some vectorial total variation seminorms
• Sparsity for dynamic inverse problems on Wasserstein curves with bounded variation
• On extreme points and representer theorems for the Lipschitz unit ball on finite metric spaces