Secant Line Search for Frank-Wolfe Algorithms
Deborah Hendrych, Sebastian Pokutta, Mathieu Besançon, David Martínez-Rubio
Abstract
We present a new step-size strategy based on the secant method for Frank-Wolfe algorithms. This strategy, which requires mild assumptions about the function under consideration, can be applied to any Frank-Wolfe algorithm. It is as effective as full line search and, in particular, allows for adapting to the local smoothness of the function, such as in Pedregosa et al. ( 2020), but comes with a significantly reduced computational cost, leading to higher effective rates of convergence. We provide theoretical guarantees and demonstrate the effectiveness of the strategy through numerical experiments.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
1 top-tier paper has cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
Cited by top-tier papers1
Builds on5
- Adaptive Gradient Descent without DescentYura Malitsky, Konstantin MishchenkoICML 2020 · 171 citations
- Adaptive Proximal Gradient Method for Convex OptimizationYura Malitsky, Konstantin MishchenkoNeurIPS 2024 · 80 citations
- Pairwise Conditional Gradients without Swap Steps and Sparser Kernel HerdingKazuma Tsuji, Ken'ichiro Tanaka, Sebastian PokuttaICML 2022 · 31 citations
- Simple steps are all you need: Frank-Wolfe and generalized self-concordant functionsAlejandro Carderera, Mathieu Besançon, Sebastian PokuttaNeurIPS 2021 · 22 citations
- Adaptive backtracking line searchJoao V. Cavalcanti, Laurent Lessard, Ashia C. WilsonICLR 2025
Related papers
- Beyond Short Steps in Frank-Wolfe AlgorithmsDavid Martínez-Rubio, Sebastian PokuttaICLR 2026 · 5 citations
- Fast Frank-Wolfe Algorithms with Adaptive Bregman Step-Size for Weakly Convex FunctionsShota Takahashi, Sebastian Pokutta, Akiko TakedaICLR 2026 · 10 citations
- Affine Invariant Analysis of Frank-Wolfe on Strongly Convex SetsThomas Kerdreux, Lewis Liu, Simon Lacoste-Julien, Damien ScieurICML 2021 · 20 citations
- Revisiting Frank-Wolfe for Polytopes: Strict Complementarity and SparsityDan GarberNeurIPS 2020 · 25 citations
- Self-Concordant Analysis of Frank-Wolfe AlgorithmsPavel E. Dvurechensky, Petr Ostroukhov, Kamil Safin, Shimrit Shtern et al.ICML 2020 · 25 citations
