Skip to main content

Research Repository

Advanced Search

Asymptotic linear convergence of fully-corrective generalized conditional gradient methods

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


Kristian Bredies

Marcello Carioni

Daniel Walter


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.


Bredies, K., Carioni, M., Fanzon, S., & Walter, D. (2023). Asymptotic linear convergence of fully-corrective generalized conditional gradient methods. Mathematical Programming,

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
Keywords Non-smooth optimization; Conditional gradient method; Sparsity; Choquet’s theorem
Public URL


Published article (1.1 Mb)

Publisher Licence URL

Copyright Statement
© The Author(s) 2023.
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit

You might also like

Downloadable Citations