Avoiding bad steps in Frank Wolfe variants
Preprint
Abstract
The analysis of Frank Wolfe (FW) variants is often complicated by the presence of different kinds of "good" and "bad" steps. In this article we aim to simplify the convergence analysis of some of these variants by getting rid of such a distinction between steps, and to improve existing rates by ensuring a sizable decrease of the objective at each iteration. In order to do this, we define the Short Step Chain (SSC) procedure, which skips gradient computations in consecutive short steps until proper stopping conditions are satisfied. This technique allows us to give a unified analysis and converge rates in the general smooth non convex setting, as well as a linear convergence rate under a Kurdyka-Lojasiewicz (KL) property. While this setting has been widely studied for proximal gradient type methods, to our knowledge, it has not been analyzed before for the Frank Wolfe variants under study. An angle condition, ensuring that the directions selected by the methods have the steepest slope possible up to a constant, is used to carry out our analysis. We prove that this condition is satisfied on polytopes by the away step Frank-Wolfe (AFW), the pairwise Frank-Wolfe (PFW), and the Frank-Wolfe method with in face directions (FDFW).Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- An active-set algorithmic framework for non-convex optimization problems over the simplexComputational Optimization and Applications, 2020
- “Active-set complexity” of proximal gradient: How long does it take to find the sparsity pattern?Optimization Letters, 2018
- Global Convergence of ADMM in Nonconvex Nonsmooth OptimizationJournal of Scientific Computing, 2018
- From error bounds to the complexity of first-order descent methods for convex functionsMathematical Programming, 2016
- Linearly convergent away-step conditional gradient for non-strongly convex functionsMathematical Programming, 2016
- Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methodsMathematical Programming, 2011
- Error bounds and convergence analysis of feasible descent methods: a general approachAnnals of Operations Research, 1993
- Estimates for the minimal width of polytopes inscribed in convex bodiesDiscrete & Computational Geometry, 1989
- Some comments on Wolfe's ‘away step’Mathematical Programming, 1986
- The width and diameter of a simplexGeometriae Dedicata, 1977