改进弗兰克-沃尔夫算法，用更优步长提升收敛速度和实用性。
Beyond Short Steps in Frank-Wolfe Algorithms
- 引入乐观框架设计新算法，结合原对偶保证
- 新策略使原对偶间隙可计算，收敛更快
- 适用于梯度下降等其他算法，适合优化研究者
我们提出新方法，通过利用函数光滑性超越传统短步长限制，改进弗兰克-沃尔夫算法。研究聚焦于具备原对偶保证的步长策略，提供实用的停止准则。提出一种基于乐观框架的新弗兰克-沃尔夫算法，并给出原对偶收敛证明。此外，设计了一种广义短步长策略，以优化可计算的原对偶间隙。有趣的是，该策略还可推广至弗兰克-沃尔夫之外的梯度下降算法。作为副产品，本文重新审视并精炼了原对偶分析技术，实现了更紧的原对偶收敛率。实验表明，新算法在实际中优于现有方法，展现出显著优势。
原文摘要 · Abstract (English)
We introduce novel techniques to enhance Frank-Wolfe algorithms by leveraging function smoothness beyond traditional short steps. Our study focuses on Frank-Wolfe algorithms with step sizes that incorporate primal-dual guarantees, offering practical stopping criteria. We present a new Frank-Wolfe algorithm utilizing an optimistic framework and provide a primal-dual convergence proof. Additionally, we propose a generalized short-step strategy aimed at optimizing a computable primal-dual gap. Interestingly, this new generalized short-step strategy is also applicable to gradient descent algorithms beyond Frank-Wolfe methods. As a byproduct, our work revisits and refines primal-dual techniques for analyzing Frank-Wolfe algorithms, achieving tighter primal-dual convergence rates. Empirical results demonstrate that our optimistic algorithm outperforms existing methods, highlighting its practical advantages.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。