Revisiting Projection-Free Optimization for Strongly Convex Constraint Sets

By Jarrid Rector-Brooks, Jun-Kun Wang, Barzan Mozafari. 2018

9 citations recorded by the source corpus.

We revisit the Frank-Wolfe (FW) optimization under strongly convex constraint sets. We provide a faster convergence rate for FW without line search, showing that a previously overlooked variant of FW is indeed faster than the standard variant. With line search, we show that FW can converge to the global optimum, even for smooth functions that are not convex, but are quasi-convex and locally-Lipschitz. We also show that, for the general case of (smooth) non-convex functions, FW with line search converges with high probability to a stationary point at a rate of O(1/t), as long as the constraint set is strongly convex—one of the fastest convergence rates in non-convex optimization.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Numerical Analysis

In Optimization & Training

Citations in the corpus

Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets (2020, background): “, 2021b;a)) is one of such structural assumptions which lead to various accelerated convergence rates, like linear convergence rates when the unconstrained optimum is outside the constraint set (Levitin & Polyak, 1966; Demyanov & Rubinov, 1970; Dunn, 1979; Rector-Brooks et al., 2019) or sublinear ra”