Abstract:The boosted Frank-Wolfe algorithm accelerates the classical Frank-Wolfe algorithm by better aligning the update direction with the negative gradient. Its analysis, however, has been limited to deterministic convex problems, with step sizes that require either line search or knowledge of the Lipschitz constant of the gradient. We develop a novel step size strategy that does not depend on the Lipschitz constant of the gradient, which allows us to extend the boosted Frank-Wolfe algorithm to the stochastic setting. We prove that boosting with this step size strategy can be combined with many modern gradient estimators, including SAGA, L-SVRG, SAG, Heavy Ball momentum, and zeroth-order estimators, among others, while retaining the worst-case convergence rates of ordinary stochastic Frank-Wolfe. Our analysis also yields the first convergence rates for boosted Frank-Wolfe on nonconvex and quasar-convex objectives, results which are new even for deterministic problems. Experiments on sparse logistic regression and quantum process tomography show that stochastic boosted Frank-Wolfe achieves faster convergence per gradient oracle call (and on wall-clock) compared to the non-boosted baseline.
| Subjects: | Optimization and Control (math.OC); Machine Learning (stat.ML) |
| MSC classes: | 90C26, 90C15, 65K05, 90C25 |
| Cite as: | arXiv:2605.25255 [math.OC] |
| (or arXiv:2605.25255v1 [math.OC] for this version) | |
| https://doi.org/10.48550/arXiv.2605.25255 arXiv-issued DOI via DataCite (pending registration) |
From: Antonio Silveti-Falls [view email]
[v1]
Sun, 24 May 2026 21:04:26 UTC (6,131 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。