Asymptotic linear convergence of fully-corrective generalized conditional gradient methods

Bredies, Kristian; Carioni, Marcello; Fanzon, Silvio; Walter, Daniel

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 Ak of extremal points of the unit ball of the regularizer and of an iterate uk∈ cone (Ak) . Each iteration requires the solution of one linear problem to update Ak 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 on the lifted problem for which we finally derive the desired convergence rates.

Citation

Bredies, K., Carioni, M., Fanzon, S., & Walter, D. (2023). Asymptotic linear convergence of fully-corrective generalized conditional gradient methods. Mathematical Programming, https://doi.org/10.1007/s10107-023-01975-z

• Journal Article Type: Article
• Acceptance Date: Apr 28, 2023
• Online Publication Date: Jul 13, 2023
• Publication Date: Jul 13, 2023
• Deposit Date: Jul 13, 2023
• Publicly Available Date: Jul 14, 2023
• Journal: Mathematical Programming
• Print ISSN: 0025-5610
• Electronic ISSN: 1436-4646
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• DOI: https://doi.org/10.1007/s10107-023-01975-z
• Keywords: Non-smooth optimization; Conditional gradient method; Sparsity; Choquet’s theorem
• Public URL: https://hull-repository.worktribe.com/output/4332169