Frank-Wolfe algorithm for star-convex functions

2025/07/23 by Millan, R. Diaz, Ferreira, Orizon Pereira, Ugon, Julien · 3 citations
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2507.17272

Abstract

We study the Frank-Wolfe algorithm for minimizing a differentiable function with Lipschitz continuous gradient over a compact convex set. To extend classical complexity bounds to certain non-convex functions, we focus on the class of star-convex functions, which retain essential geometric properties despite the lack of convexity. We establish iteration-complexity bounds of O(1/k) for both the objective values and the duality gap under star-convexity, using diminishing, Armijo-type, and Lipschitz-based stepsize rules. Notably, the diminishing and Armijo strategies do not require prior knowledge of Lipschitz or curvature constants. These results demonstrate that the Frank-Wolfe method preserves optimal complexity guarantees beyond the convex setting.

Citations

• Simplified Versions of the Conditional Gradient Method
• Convergence Rate of Frank-Wolfe for Non-Convex Objectives
• Conditional gradient type methods for composite nonlinear and stochastic optimization
• An Extended Frank-Wolfe Method with "In-Face" Directions, and its Application to Low-Rank Matrix Completion
• The Alternating Descent Conditional Gradient Method for Sparse Inverse\n Problems
• The Cyclic Block Conditional Gradient Method for Convex Optimization Problems
• Conditional Gradient Algorithms for Norm-Regularized Smooth Convex Optimization
• Conditional Gradient Algorithms for Rank-One Matrix Approximations with a Sparsity Constraint

Cited by

• Conditional gradient methods on unbounded feasible regions
• Adaptive Conditional Gradient Descent
• Smooth Quasar-Convex Optimization with Constraints

Related

• The Iterates of the Frank-Wolfe Algorithm May Not Converge
• Optimizing Star-Convex Functions
• The Frank-Wolfe algorithm: a short introduction
• The Frank-Wolfe Algorithm: A Short Introduction
• Convergence Rate of Frank-Wolfe for Non-Convex Objectives