Calculus of Variations and Geometric Measure Theory

K. Bredies - M. Carioni - S. Fanzon - D. Walter

Linear convergence of accelerated generalized conditional gradient methods

created by fanzon on 15 Oct 2021
modified by carioni on 04 Apr 2022

[BibTeX]

Submitted Paper

Inserted: 15 oct 2021
Last Updated: 4 apr 2022

Year: 2021

ArXiv: 2110.06756 PDF

Abstract:

We propose an accelerated generalized conditional gradient method (AGCG) 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 extreme points of the unit ball of the regularizer and an iterate $u_k \in \operatorname{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 AGCG algorithm is connected to a Primal-Dual-Active-point Method (PDAP) on the lifted problem for which we finally derive the desired convergence rates.


Download: