Asymptotic linear convergence of fully-corrective generalized conditional gradient methods
From MaRDI portal
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 of extremal points of the unit ball of the regularizer and of an iterate . Each iteration requires the solution of one linear problem to update 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.
Recommendations
- Linear convergence of accelerated conditional gradient algorithms in spaces of measures
- Affine Invariant Convergence Rates of the Conditional Gradient Method
- Adaptive conditional gradient method
- scientific article; zbMATH DE number 1873287
- A conditional gradient method with linear rate of convergence for solving convex linear systems
Cites work
- scientific article; zbMATH DE number 5764998 (Why is no real title available?)
- scientific article; zbMATH DE number 3576139 (Why is no real title available?)
- scientific article; zbMATH DE number 2152346 (Why is no real title available?)
- scientific article; zbMATH DE number 1448982 (Why is no real title available?)
- scientific article; zbMATH DE number 7632135 (Why is no real title available?)
- scientific article; zbMATH DE number 3274229 (Why is no real title available?)
- scientific article; zbMATH DE number 3345848 (Why is no real title available?)
- A GENERAL ATOMIC DECOMPOSITION THEOREM AND BANACH'S CLOSED RANGE THEOREM
- A Tight Upper Bound on the Rate of Convergence of Frank-Wolfe Algorithm
- A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem
- A generalized conditional gradient method and its connection to an iterative shrinkage method
- A generalized conditional gradient method for dynamic inverse problems with optimal transport regularization
- A minimum effort optimal control problem for elliptic PDEs
- A superposition principle for the inhomogeneous continuity equation with Hellinger–Kantorovich-regular coefficients
- An extension of the frank and Wolfe method of feasible directions
- An iterative thresholding algorithm for linear inverse problems with a sparsity constraint
- An optimal transport approach for solving dynamic inverse problems in spaces of measures
- Conditional gradient algorithms with open loop step size rules
- Convergence Rates for Conditional Gradient Sequences Generated by Implicit Step Length Rules
- Generalized conditional gradient for sparse estimation
- Infinite dimensional analysis. A hitchhiker's guide.
- Inverse problems in spaces of measures
- Iterated Hard Shrinkage for Minimization Problems with Sparsity Constraints
- Lectures on Choquet's theorem
- Linear convergence of Frank-Wolfe for rank-one matrix recovery without strong convexity
- Linear convergence of accelerated conditional gradient algorithms in spaces of measures
- Mathematical image processing. Translated from the German
- Metric subregularity of the convex subdifferential in Banach spaces
- Minimal effort problems and their treatment by semismooth Newton methods
- New analysis and results for the Frank-Wolfe method
- Numerical analysis of sparse initial data identification for parabolic problems
- On representer theorems and convex regularization
- On the extremal points of the ball of the Benamou-Brenier energy
- On the linear convergence rates of exchange and continuous methods for total variation minimization
- Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
- Optimal transport for particle image velocimetry: real data and postprocessing algorithms
- Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
- Rates of Convergence for Conditional Gradient Algorithms Near Singular and Nonsingular Extremals
- Restricted simplicial decomposition for convex constrained problems
- Simplicial decomposition in nonlinear programming algorithms
- Some comments on Wolfe's ‘away step’
- Sparse initial data identification for parabolic PDE and its finite element approximations
- Sparsity of solutions for variational inverse problems with finite-dimensional data
- Sufficient second-order conditions for bang-bang control problems
- Tensor-free proximal methods for lifted bilinear/quadratic inverse problems with applications to phase retrieval
- The alternating descent conditional gradient method for sparse inverse problems
- The convex geometry of linear inverse problems
- Trading accuracy for sparsity in optimization problems with sparsity constraints
- \(W^{1,p}\)-quasiconvexity and variational problems for multiple integrals
Cited in
(8)- Extremal points and sparse optimization for generalized Kantorovich-Rubinstein norms
- A sparse optimization approach to infinite infimal convolution regularization
- Convergence analysis of the discretization of continuous-domain inverse problems
- A -convergence result and an off-the-grid charge algorithm for curve reconstruction in inverse problems
- Conditional gradients for total variation regularization with PDE constraints: a graph cuts approach
- On extremal points for some vectorial total variation seminorms
- Nonlocal perimeters and variations: extremality and decomposability for finite and infinite horizons
- Sparsity for dynamic inverse problems on Wasserstein curves with bounded variation
This page was built for publication: Asymptotic linear convergence of fully-corrective generalized conditional gradient methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6126647)
