Scholarlink

<p>We prove that the block-coordinate Frank-Wolfe (BCFW) algorithm converges with state-of-the-art rates in both convex and nonconvex settings under a very mild “block-iterative” assumption. This appears to be the first result on BCFW addressing the setting of nonconvex objective functions with Lipschitz-continuous gradients and no additional assumptions. This analysis newly allows for (I) progress without activating the most-expensive linear minimization oracle(s), LMO(s), at every iteration, (II) parallelized updates that do not require all LMOs, and therefore (III) deterministic parallel update strategies that take into account the numerical cost of the problem’s LMOs. Our results apply for short-step BCFW as well as an adaptive method for convex functions. New relationships between updated coordinates and primal progress are proven, and a favorable speedup is demonstrated using <Emphasis FontCategory="NonProportional">FrankWolfe.jl</Emphasis>.</p>

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

Flexible Block-Iterative Analysis for the Frank-Wolfe Algorithm

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年7月31日

查看全文
  • Gábor Braun,
  • Jannis Halbey,
  • Sebastian Pokutta,
  • Zev Woodstock

摘要

We prove that the block-coordinate Frank-Wolfe (BCFW) algorithm converges with state-of-the-art rates in both convex and nonconvex settings under a very mild “block-iterative” assumption. This appears to be the first result on BCFW addressing the setting of nonconvex objective functions with Lipschitz-continuous gradients and no additional assumptions. This analysis newly allows for (I) progress without activating the most-expensive linear minimization oracle(s), LMO(s), at every iteration, (II) parallelized updates that do not require all LMOs, and therefore (III) deterministic parallel update strategies that take into account the numerical cost of the problem’s LMOs. Our results apply for short-step BCFW as well as an adaptive method for convex functions. New relationships between updated coordinates and primal progress are proven, and a favorable speedup is demonstrated using FrankWolfe.jl.