Source-linked AI summary
Convergence Rate of Frank-Wolfe for Non-Convex Objectives
Simon Lacoste-Julien
TL;DR
The paper asks whether Frank-Wolfe has a convergence rate for potentially non-convex objectives. It analyzes adaptive-step Frank-Wolfe with the affine-invariant Frank-Wolfe gap and proves an O(1/√t) rate for the smallest gap encountered, with a local suboptimality interpretation on convex subsets.
Problem
Rates for the adaptive-step Frank-Wolfe algorithm were not known for potentially non-convex objectives, motivating an affine-invariant stationarity measure.
Method
The paper analyzes Frank-Wolfe with line search or an affine-invariant quadratic-upper-bound step size using the Frank-Wolfe gap as its stationarity measure.
Results
O(1/√t): the minimal Frank-Wolfe gap after t iterations is bounded by (max{2h_0,C})/(√t+1).
Takeaways & Limitations
The Frank-Wolfe gap is both affine invariant and a local suboptimality upper bound whenever the objective is convex on a subset of the domain.
Takeaways & Limitations
The rate assumes a finite curvature constant over a compact convex domain, and the related-work lower-bound example does not extend directly to compact constrained domains.
Abstract
from arXiv · showhide
We give a simple proof that the Frank-Wolfe algorithm obtains a stationary point at a rate of $O(1/\sqrt{t})$ on non-convex objectives with a Lipschitz continuous gradient. Our analysis is affine invariant and is the first, to the best of our knowledge, giving a similar rate to what was already proven for projected gradient methods (though on slightly different measures of stationarity).
1 Introduction
The paper analyzes Frank-Wolfe on potentially non-convex objectives over compact convex domains, using an affine-invariant stationarity measure and adaptive step sizes. It proves that the smallest Frank-Wolfe gap observed after t iterations decreases at an O(1/√t) rate and also bounds local suboptimality on convex subsets.
- Problem setting: Frank-Wolfe applies to continuously differentiable objectives over compact convex domains, even when the objective is potentially non-convex.The method requires access to a linear minimization oracle over the domain.
- Algorithm: Adaptive step sizes use either line search or an affine-invariant quadratic upper bound while keeping iterates feasible.Feasibility follows because the domain is convex and each update moves toward a point returned by the linear minimization oracle.
- Stationarity measure: The Frank-Wolfe gap is nonnegative, vanishes exactly at constrained stationary points, and is computed during the algorithm.It generalizes the unconstrained gradient-norm criterion while remaining affine invariant.
- Convergence result: On any convex subset M′ where f is convex, the Frank-Wolfe gap upper-bounds suboptimality relative to the constrained minimum on M′.Thus the stationarity measure also provides a local suboptimality certificate in regions where convexity holds.
2 Result
For non-convex objectives with finite curvature, the Frank-Wolfe algorithm reaches an approximate stationary point by controlling the smallest FW gap encountered over its iterates. The proof uses affine-invariant curvature-based descent and yields an O(1/√(t+1)) stationarity rate.
- Convergence result: Theorem 1 bounds the minimal FW gap ˜g_t = min_{0≤k≤t} g_k for non-convex f over a compact convex domain with finite curvature C_f.The result applies with line search using C := C_f or with a quadratic-upper-bound step size using any C ≥ C_f.
- Proof strategy: The objective decrease at each iteration cannot remain large indefinitely because it is bounded below by the global minimum over M, with initial suboptimality h_0 controlling the gap.This argument converts cumulative descent into a bound on the smallest gap encountered.
- Proof strategy: The proof derives affine-invariant descent from the curvature constant, then chooses a step size by line search or by minimizing a quadratic upper bound.Both choices produce progress controlled by the FW gap and the curvature parameter.
- Case analysis: When the minimal gap exceeds C in early iterations, it decreases at an O(1/t) rate with constant h_0; this case matters only when h_0 > C/2.If h_0 ≤ C/2, the analysis shows ˜g_t ≤ C for every t.
- Convergence result: O(1/√(t+1)) is the resulting simplified bound on the minimal FW gap after t iterations.The theorem statement is obtained by simplifying the case-dependent bounds under the conditions governing the first case.
3 Related work
Prior work establishes stationary-point rates for projected and unconstrained gradient methods, while non-convex Frank-Wolfe guarantees were slower or applied to different variants. The paper situates its O(1/√t) Frank-Wolfe rate alongside these results and notes an unresolved constrained lower-bound question.
- Frank-Wolfe methods: Earlier non-convex Frank-Wolfe work covered non-adaptive step sizes and obtained slower rates than O(1/√t).That work generalized the method to composite objectives with a non-smooth convex term, recovering standard Frank-Wolfe for a convex-set indicator.
- Frank-Wolfe methods: Bertsekas showed that limit points of standard Frank-Wolfe iterates are stationary under continuous differentiability, but provided no rates.The argument uses gradient-related directions and a stationary-point convergence proposition.
- Unconstrained and constrained gradient methods: O(1/√t) stationary-point rates are known for unconstrained gradient descent and projected gradient methods, using gradient norms or gradient mappings.The cited results include a gradient-descent bound involving h0 and L, and analogous projected-gradient rates.
- Open questions: The O(1/t) rate is known to be tight for unconstrained gradient descent, but adapting that lower-bound example to Frank-Wolfe on compact domains remains unclear.The cited example has its only stationarity point at +∞, so it does not directly apply to a compact domain.
- Comparison with gradient methods: The paper’s Frank-Wolfe stationarity rate is analogous to the projected-gradient and unconstrained gradient-descent rates, though the stationarity measures differ.Projected-gradient analyses use a local criticality measure or gradient mapping, whereas unconstrained gradient descent uses the gradient norm.
- Stationarity measures: Gradient-mapping stationarity specializes to the gradient norm in the unconstrained setting and is defined through a projected-gradient step in constrained optimization.For step size γ, the mapping is 1/γ times the difference between x and its projection after a gradient step.