Email this article 
AN ADAPTIVE VARIANT OF THE FRANK–WOLFE METHOD FOR RELATIVE SMOOTH CONVEX OPTIMIZATION PROBLEMS
- Authors: Vyguzov A.A.1,2, Stonyakina F.S.1,2,3
-
Affiliations:
- Moscow Institute of Physics and Technology
- Innopolis University
- V.I. Vernadsky Crimean Federal University, Republic of Crimea
- Issue: Vol 65, No 3 (2025)
- Pages: 364-375
- Section: Optimal control
- URL: https://ogarev-online.ru/0044-4669/article/view/293545
- DOI: https://doi.org/10.31857/S0044466925030105
- EDN: https://elibrary.ru/HSRUGM
- ID: 293545
Cite item
Open Access
Access granted
Subscription Access
Abstract
This paper proposes a new variant of the adaptive Frank–Wolfe algorithm for relatively smooth convex minimization problems. It suggests using a divergence different from half of the squared Euclidean norm in the step size adjustment formula. Convergence rate estimates for this algorithm are proven for minimization problems involving relatively smooth convex functions with the triangle scaling property. We also conducted computational experiments for the Poisson linear inverse problem and SVM models. The paper also identifies the conditions under which the proposed algorithm shows a clear advantage over the adaptive proximal gradient Bregman method and its accelerated variants.
About the authors
A. A. Vyguzov
Moscow Institute of Physics and Technology; Innopolis University
Email: al.vyguzov@yandex.ru
Dolgoprudny, 141701 Russia; Innopolis, 420500 Russia
F. S. Stonyakina
Moscow Institute of Physics and Technology; Innopolis University; V.I. Vernadsky Crimean Federal University, Republic of Crimea
Email: fedyor@mail.ru
Dolgoprudny, 141701 Russia; Innopolis, 420500 Russia; Simferopol, 295007 Russia
References
- Bauschke H. H., Bolte J., and Teboulle M. A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications // Mathematics of Operations Research. 2017. V. 42. P. 330–48.
- Lu H., Freund R. M., and Nesterov Y. Relatively smooth convex optimization by first-order methods, and applications // SIAM Journal on Optimization 2018. V. 28. P. 333–54.
- Hendrikx H., Xiao L., Bubeck S., Bach F., and Massoulie L. Statistically preconditioned accelerated gradient method for distributed optimization // In: International conference on machine learning. PMLR. 2020:4203–27.
- Lu H. “Relative continuity” for non-Lipschitz nonsmooth convex optimization using stochastic (or deterministic) mirror descent // INFORMS Journal on Optimization 2019. V. 1. P. 288–303.
- Nesterov Y. Implementable tensor methods in unconstrained convex optimization // Mathematical Programming. 2021. V. 186 P. 157–83.
- Stonyakin F., Titov A., Alkousa M., Savchuk O., and Gasnikov A. Adaptive Algorithms for Relatively Lipschitz Continuous Convex Optimization Problems // Pure and Applied Functional Analysis. 2023. V. 8. P. 1505–26.
- Dragomir R. A., Taylor A. B., d’Aspremont A, and Bolte J. Optimal complexity and certification of Bregman first-order methods // Mathematical Programming 2022:1–43.
- Hanzely F., Richtarik P., and Xiao L. Accelerated Bregman Proximal Gradient Methods for Relatively Smooth Convex Optimization // Comput Optim Appl. 2021. V. 79. P. 405–440.
- Dragomir R. A. Bregman gradient methods for relatively-smooth optimization // PhD thesis. UT1 Capitole, 2021.
- Combettes C. W. and Pokutta S. Complexity of linear minimization and projection on some sets // Operations Research Letters. 2021. V. 49. P. 565–71.
- Bomze I. M., Rinaldi F., and Zeffiro D. Frank–Wolfe and friends: a journey into projection-free first order optimization methods // 4OR-Q J Oper Res. 2021. V. 14. P. 313–345.
- Frank M., Wolfe P., et al. An algorithm for quadratic programming // Naval research logistics quarterly. 1956. V. 3. P. 95–110.
- Aivazian G., Stonyakin F. S., Pasechnyk D., Alkousa M. S., Raigorodsky A., and Baran I. Adaptive variant of the Frank– Wolfe algorithm for convex optimization problems // Programming and Computer Software 2023. V. 49. P. 493–504.
- Polyak B. Introduction to Optimization. 2020.
- Braun G., Carderera A., Combettes C. W., et al. Conditional gradient methods // arXiv preprint arXiv:2211.14103 2022.
Supplementary files
