Beyond Short Steps in Frank-Wolfe Algorithms
This work addresses optimization challenges in machine learning and related fields, offering incremental improvements to Frank-Wolfe algorithms with practical applications.
The paper tackles the problem of improving Frank-Wolfe algorithms by developing novel techniques that leverage function smoothness beyond traditional short steps, resulting in an optimistic algorithm that empirically outperforms existing methods with tighter primal-dual convergence rates.
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.