Scholarlink

<p>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 <i>star-convex functions</i>, which retain essential geometric properties despite the lack of convexity. We establish iteration-complexity bounds of <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\mathcal {O}(1/k)\)</EquationSource> </InlineEquation> 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Frank–wolfe algorithm for star-convex functions

  • 期刊论文

  • 发表日期：

    2026年5月19日

查看全文
  • R. Díaz Millán,
  • O. P. Ferreira,
  • J. Ugon

摘要

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 \(\mathcal {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.