Adaptive open-loop step-sizes for accelerated convergence rates of the Frank–Wolfe algorithm
Open Access
- 11 August 2026
- journal article
- research article
- Published by Springer Nature in Computational Optimization and Applications
- Vol. 95 (2) , 679-698
Abstract
Recent work has shown that, in several growth settings, the Frank–Wolfe algorithm () with fixed-parameter open-loop step-sizes $$\eta _t = \frac{\ell }{t+\ell }$$ for $$\ell \in \mathbb {N}_{\ge 2}$$ can converge faster than the classical $${\mathcal {O}}(t^{-1})$$ rate. In the strong-growth regime, increasing $$\ell $$ improves the asymptotic rate, so no single fixed choice of $$\ell $$ is uniformly preferable. We study the broader family of adaptive open-loop step-sizes $$\eta _t = \frac{g(t)}{t+g(t)}$$ and extend the affine-invariant analysis from the fixed-parameter case to non-decreasing functions g for which the resulting step-size sequence is non-increasing. For the log-adaptive choice $$g(t)=2+\log (t+1)$$ , this yields a schedule that matches the asymptotic rates of fixed-parameter rules up to polylogarithmic factors in the weak-growth settings considered here, while improving the asymptotic sublinear rate in strong-growth settings. We also report numerical experiments demonstrating the efficacy of the new proposed step-size rule.
Keywords
All Related Versions
Funding Information
- Deutsche Forschungsgemeinschaft
This publication has 29 references indexed in Scilit:
- Complexity of linear minimization and projection on some setsOperations Research Letters, 2021
- Conditional gradient type methods for composite nonlinear and stochastic optimizationMathematical Programming, 2018
- Complexity bounds for primal-dual methods minimizing the model of objective functionMathematical Programming, 2017
- Instance-Level Video Segmentation from Object Tracks2016
- Efficient Image and Video Co-localization with Frank-Wolfe Algorithm2014
- Robust Estimation of a Location Parameter1992
- Conditional gradient algorithms with open loop step size rulesJournal of Mathematical Analysis and Applications, 1978
- An extension of the frank and Wolfe method of feasible directionsMathematical Programming, 1974
- Constrained minimization methodsUSSR Computational Mathematics and Mathematical Physics, 1966
- An algorithm for quadratic programmingNaval Research Logistics Quarterly, 1956