Research map / Optimization / Nonconvex and smooth optimization

Frank-Wolfe Beyond 1/t Convergence

NeurIPS 2026 · Optimization › Nonconvex and smooth optimization · approach: Nonconvex minimax and constrained methods · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces Local Dual Sharpness (LDS), a condition on the feasible region and its LMO around a reference set, showing vanilla Frank-Wolfe attains o(1/t) primal gap on fixed smooth convex instances, with explicit polynomial rates under a local Hölder error bound.

Problem

Vanilla Frank-Wolfe has a worst-case Omega(1/t) primal-gap barrier for smooth convex minimization over compact convex sets, and faster rates usually need strong convexity, Hölder error bounds, or lower-bounded gradients.

Approach

Impose a local power-type dual sharpness inequality on the LMO support map around the minimizer set; under this condition, short steps, exact line search, and open-loop steps give o(1/t) on each fixed instance without objective growth assumptions, and uniformly convex sets satisfy it globally.

Key results

• Under LDS around the minimizer set, vanilla Frank-Wolfe with short steps, exact line search, or open-loop 2/(t+2) satisfies f(x_t)-f* = o(1/t) on the fixed instance.
• Uniformly convex compact sets satisfy LDS globally, so the o(1/t) conclusion applies to every smooth convex objective on such sets.
• Combining LDS(q) with a local Hölder error bound of order r gives tail rate O(t^{-rq/(rq-2)}); a logarithmic example gives primal gap ~ L/(t(log t)^4).

Surprising findings

• An instance satisfying global LDS and having no local Hölder error bound of any finite order still has primal gap ~1/(t(log t)^4), so o(1/t) rates need not be polynomially faster than 1/t.
• Compact strict convexity alone does not imply LDS, since a superflat boundary can violate every power-type inequality.

Limitations

• Results are fixed-instance asymptotic (o(1/t)) and not uniform minimax rates; burn-in is instance-dependent and possibly arbitrarily long.
• Verifying LDS requires knowing the minimizer set location, and LDS depends on the fixed LMO tie-breaking rule.
• Quantitative polynomial rates require an additional local Hölder error bound assumption on f.

Experimental setup

Metrics: primal gap f(x_t)-f* t*F_t asymptotics

Baselines: vanilla Frank-Wolfe with short steps exact line search open-loop step-size 2/(t+2) strongly convex sets analysis

Builds on: Frank-Wolfe algorithm uniform convexity of sets Hölderian error bound Wolfe's proper-face analysis

Closest papers by meaning

• Lower Bounds for Frank-Wolfe on Strongly Convex Sets (ICML 2026 · similarity 0.92)
• Fast Frank–Wolfe Algorithms with Adaptive Bregman Step-Size for Weakly Convex Functions (ICLR 2026 · similarity 0.91)
• Revisiting Projection-Free Optimization for Strongly Convex Constraint Sets (AAAI 2019 · similarity 0.91)
• Revisiting Frank-Wolfe for Structured Nonconvex Optimization (NeurIPS 2025 · similarity 0.88)
• Last-Iterate Convergence for Generalized Frank-Wolfe in Monotone Variational Inequalities (NeurIPS 2024 · similarity 0.88)
• Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features (ICML 2024 · similarity 0.87)