Adaptive Variant of the Frank-Wolfe Algorithm for Convex Optimization Problems

G. V. Aivazian; Айвазян Г. В.; F. S. Stonyakin; Стонякин Ф. С.; D. A. Pasechnyk; Пасечнюк Д. А.; M. S. Alkousa; Алкуса М. С.; A. M. Raigorodsky; Райгородский А. М.; I. V. Baran; Баран И. В.

doi:10.31857/S0132347423060031

Адаптивный вариант алгоритма Франк–Вульфа для задач выпуклой оптимизации

Авторы: Айвазян Г.В.¹, Стонякин Ф.С.¹^,2, Пасечнюк Д.А.¹^,3, Алкуса М.С.¹^,4, Райгородский А.М.¹^,5^,6, Баран И.В.²
Учреждения:
1. Московский физико-технический институт
2. Крымский федеральный университет им. В.И. Вернадского
3. Исследовательский центр доверенного искусственного интеллекта ИСП РАН
4. Национальный исследовательский университет “Высшая школа экономики”
5. Московский государственный университет им. М.В. Ломоносова, механико-математический факультет
6. Кавказский математический центр Адыгейского государственного университета
Выпуск: № 6 (2023)
Страницы: 14-26
Раздел: АНАЛИЗ ДАННЫХ
URL: https://journals.rcsi.science/0132-3474/article/view/148116
DOI: https://doi.org/10.31857/S0132347423060031
EDN: https://elibrary.ru/GGFHZJ
ID: 148116

Цитировать

Полный текст

Открытый доступ
Доступ закрыт

Доступ предоставлен
Доступ закрыт

Только для подписчиков

Аннотация

В данной работе исследовался вариант метода Франк–Вульфа для задач выпуклой оптимизации с адаптивным подбором параметра шага, соответствующего информации о гладкости целевой функции (константа Липшица градиента). Получены теоретические оценки качества выдаваемого методом приближенного решения с использованием адаптивно подобранных параметров L_k. На классе задач на выпуклом допустимом множестве с выпуклой целевой функцией гарантируемая скорость сходимости предложенного метода сублинейна. Рассмотрено сужение этого класса задач (целевая функция с условием градиентного доминирования) и получена оценка скорости сходимости с использованием адаптивно подбираемых параметров L_k. Важной особенностью полученного результата является проработка ситуации, при которой можно гарантировать после завершения итерации уменьшение невязки функции не менее чем в 2 раза. В то же время использование адаптивно подобранных параметров в теоретических оценках позволяет применять метод как для гладких, так и для негладких задач при условии выполнения критерия выхода из итерации. Для гладких задач можно доказать, что теоретические оценки метода гарантированно оптимальны с точностью до умножения на постоянный множитель. Выполнены вычислительные эксперименты, и проведено сравнение с двумя другими алгоритмами, в ходе чего была продемонстрирована эффективность алгоритма для ряда как гладких, так и негладких задач.

Список литературы

Canon M.D., Cullum C.D. A tight upper bound on the rate of convergence of Frank–Wolfe algorithm // SIAM Journal on Control. 1968. V. 6 (2.4). P. 509–516.
Bomze I.M., Rinaldi F., Zeffiro D. Frank–Wolfe and friends: a journey into projection-free first-order optimization methods // 4OR-Q J Oper Res. 2021. V. 19. P. 313–345.
Braun G., Carderera A., Combettes C.W., Hassani H., Karbasi A., Mokhtari A., Pokutta S. Conditional Gradient Methods. https://arxiv.org/pdf/2211.14103.pdf
Nesterov Y. Complexity bounds for primal-dual methods minimizing the model of objective function // Math. Program. 2018. V. 171 (1-2). P. 311–330.
Nesterov Y. Universal gradient methods for convex optimization problems // Math. Program. A 2015. V. 152. P. 381–404.
Pedregosa F., Negiar G., Askari A., Jaggi M. Linearly convergent Frank–Wolfe with backtracking line-search. In: International Conference on Artificial Intelligence and Statistics. Proceedings of Machine Learning Research. 2020. P. 1–10.
Polyak B.T. Gradient methods for minimizing functionals (in Russian) // Zh. Vychisl. Mat. Mat. Fiz. 1963. P. 643–653.
Łojasiewicz S. A topological property of real analytic subsets (in French) // Coll. du CNRS, Les équations aux dérivos partielles. 1963. P. 87–89.
Karimi H., Nutini J., Schmidt M. Linear convergence of gradient and proximal-gradient methods under the Polyak–Łojasiewicz condition // Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19–23, 2016, Proceedings, Part I 16. Springer International Publishing, 2016. P. 795–811.
Freund R.M., Grigas P., Mazumder R. An extended Frank–Wolfe method within face directions, and its application to low-rank matrix completion // SIAM Journal on Optimization. 2017. V. 27 (2.1). P. 319–346.
,000 ratings and 3,600 tag applications applied to 9,000 movies by 600 users. Last updated 9/2018. https://grouplens.org/datasets/movielens/
Vapnik V. The Nature of Statistical Learning Theory. Springer. 2013.
Clarkson K.L. Coresets, sparse greedy approximation, and the Frank–Wolfe algorithm // ACM Transactions on Algorithms. 2010. V. 6 (2.4). P. 1–30.
Pima Indians Diabetes Database. https://www.kaggle.com/datasets/uciml/pima-indians-diabetes-database
Ivanov V.K., Vasin V.V., Tanana V.P. Theory of linear ill-posed problems and its applications. Walter de Gruyter. 2013.
LIBSVM Data: Classification (Binary Class). https://www.csie.ntu.edu.tw/cjlin/libsvmtools/datasets/binary.html
Левитин Е.С., Поляк Б.Т. Методы минимизации при наличии ограничений // Журнал вычислит. матем. и матем. физ. 1966. Т. 6. № 5. С. 787–823.
Candes E.J., Recht B. Exact matrix completion via convex optimization // Foundations of Computational Mathematics. 2009. V. 9 (2.6). P. 717–772.
Combettes C.W., Pokutta S. Complexity of Linear Minimization and Projection on Some Sets // Operations Research Letters. 2021. V. 49 (2.4). P. 565–571.
Frank M., Wolfe P. An algorithm for quadratic programming // Naval Research Logistics Quarterly. 1956. V. 3 (1–2). P. 95–110.