Active set complexity of the away-step Frank-Wolfe algorithm
From MaRDI portal
Abstract: In this paper, we study active set identification results for the away-step Frank-Wolfe algorithm in different settings. We first prove a local identification property that we apply, in combination with a convergence hypothesis, to get an active set identification result. We then prove, in the nonconvex case, a novel convergence rate result and active set identification for different stepsizes (under suitable assumptions on the set of stationary points). By exploiting those results, we also give explicit active set complexity bounds for both strongly convex and nonconvex objectives. While we initially consider the probability simplex as feasible set, in the appendix we show how to adapt some of our results to generic polytopes.
Recommendations
- Some comments on Wolfe's ‘away step’
- An active-set algorithmic framework for non-convex optimization problems over the simplex
- First-order Methods for the Impatient: Support Identification in Finite Time with Convergent Frank--Wolfe Variants
- Avoiding bad steps in Frank-Wolfe variants
- Active-set identification with complexity guarantees of an almost cyclic 2-coordinate descent method with Armijo line search
Cites work
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 4029737 (Why is no real title available?)
- scientific article; zbMATH DE number 3526459 (Why is no real title available?)
- scientific article; zbMATH DE number 2155014 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- A New Active Set Algorithm for Box Constrained Optimization
- A Tight Upper Bound on the Rate of Convergence of Frank-Wolfe Algorithm
- An active set algorithm for nonlinear optimization with polyhedral constraints
- An active set feasible method for large-scale minimization problems with bound constraints
- An active-set algorithmic framework for non-convex optimization problems over the simplex
- Convex optimization algorithms
- Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm
- Exposing Constraints
- First-order Methods for the Impatient: Support Identification in Finite Time with Convergent Frank--Wolfe Variants
- From error bounds to the complexity of first-order descent methods for convex functions
- Gradient projection and conditional gradient methods for constrained nonconvex minimization
- Gradient-based methods for sparse recovery
- Growth transformations for functions on manifolds
- Identifiable Surfaces in Constrained Optimization
- Large-scale active-set box-constrained optimization method with spectral projected gradients
- Learning with submodular functions: a convex optimization perspective
- Lectures on convex optimization
- Linearly convergent away-step conditional gradient for non-strongly convex functions
- On the Identification of Active Constraints
- On the Identification of Active Constraints II: The Nonconvex Case
- On the convergence properties of the projected gradient method for convex optimization
- Polytope conditioning and linear convergence of the Frank-Wolfe algorithm
- Projected Newton Methods for Optimization Problems with Simple Constraints
- Some comments on Wolfe's ‘away step’
- ``Active-set complexity of proximal gradient: how long does it take to find the sparsity pattern?
Cited in
(13)- Two-stage stochastic standard quadratic optimization
- Active-set identification with complexity guarantees of an almost cyclic 2-coordinate descent method with Armijo line search
- Avoiding bad steps in Frank-Wolfe variants
- An active-set algorithmic framework for non-convex optimization problems over the simplex
- Frank--Wolfe Methods with an Unbounded Feasible Region and Applications to Structured Learning
- Some comments on Wolfe's ‘away step’
- Improved algorithms and novel applications of the FrankWolfe.jl library
- An augmented Lagrangian method exploiting an active-set strategy and second-order information
- Fast cluster detection in networks by first order optimization
- Minimization over the _1-ball using an active-set non-monotone projected gradient
- Frank-Wolfe and friends: a journey into projection-free first-order optimization methods
- Projection free methods on product domains
- On the von Neumann and Frank-Wolfe algorithms with away steps
This page was built for publication: Active set complexity of the away-step Frank-Wolfe algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5124005)
