Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets
arXiv:2011.03351
Abstract
It is known that the Frank-Wolfe (FW) algorithm, which is affine-covariant, enjoys accelerated convergence rates when the constraint set is strongly convex. However, these results rely on norm-dependent assumptions, usually incurring non-affine invariant bounds, in contradiction with FW's affine-covariant property. In this work, we introduce new structural assumptions on the problem (such as the directional smoothness) and derive an affine invariant, norm-independent analysis of Frank-Wolfe. Based on our analysis, we propose an affine invariant backtracking line-search. Interestingly, we show that typical backtracking line-searches using smoothness of the objective function surprisingly converge to an affine invariant step size, despite using affine-dependent norms in the step size's computation. This indicates that we do not necessarily need to know the set's structure in advance to enjoy the affine-invariant accelerated rate.
References in corpus (14)
- Generalized power method for sparse principal component analysis
- Learning a Text-Video Embedding from Incomplete and Heterogeneous Data
- Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets
- Weakly Supervised Action Labeling in Videos Under Ordering Constraints
- An Affine Invariant Linear Convergence Analysis for Frank-Wolfe Algorithms
- Blended Conditional Gradients: the unconditioning of conditional gradients
- Projection-Free Optimization on Uniformly Convex Sets
- Curvature of Feasible Sets in Offline and Online Optimization
- Frank-Wolfe Method is Automatically Adaptive to Error Bound Condition
- Boosting Frank-Wolfe by Chasing Gradients
- Projection-Free Adaptive Gradients for Large-Scale Optimization
- Lazifying Conditional Gradient Algorithms
- A unifying framework for the analysis of projection-free first-order methods under a sufficient slope condition
- Generalized conditional subgradient and generalized mirror descent: duality, convergence, and symmetry