Адаптивный вариант алгоритма Франк–Вульфа для задач выпуклой оптимизации
- Авторы: Айвазян Г.В.1, Стонякин Ф.С.1,2, Пасечнюк Д.А.1,3, Алкуса М.С.1,4, Райгородский А.М.1,5,6, Баран И.В.2
-
Учреждения:
- Московский физико-технический институт
- Крымский федеральный университет им. В.И. Вернадского
- Исследовательский центр доверенного искусственного интеллекта ИСП РАН
- Национальный исследовательский университет “Высшая школа экономики”
- Московский государственный университет им. М.В. Ломоносова, механико-математический факультет
- Кавказский математический центр Адыгейского государственного университета
- Выпуск: № 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
Цитировать
Аннотация
В данной работе исследовался вариант метода Франк–Вульфа для задач выпуклой оптимизации с адаптивным подбором параметра шага, соответствующего информации о гладкости целевой функции (константа Липшица градиента). Получены теоретические оценки качества выдаваемого методом приближенного решения с использованием адаптивно подобранных параметров Lk. На классе задач на выпуклом допустимом множестве с выпуклой целевой функцией гарантируемая скорость сходимости предложенного метода сублинейна. Рассмотрено сужение этого класса задач (целевая функция с условием градиентного доминирования) и получена оценка скорости сходимости с использованием адаптивно подбираемых параметров Lk. Важной особенностью полученного результата является проработка ситуации, при которой можно гарантировать после завершения итерации уменьшение невязки функции не менее чем в 2 раза. В то же время использование адаптивно подобранных параметров в теоретических оценках позволяет применять метод как для гладких, так и для негладких задач при условии выполнения критерия выхода из итерации. Для гладких задач можно доказать, что теоретические оценки метода гарантированно оптимальны с точностью до умножения на постоянный множитель. Выполнены вычислительные эксперименты, и проведено сравнение с двумя другими алгоритмами, в ходе чего была продемонстрирована эффективность алгоритма для ряда как гладких, так и негладких задач.
Об авторах
Г. В. Айвазян
Московский физико-технический институт
Автор, ответственный за переписку.
Email: aivazian.grigory25@yandex.ru
Россия, 141701, г. Долгопрудный, Институтский пер., 9
Ф. С. Стонякин
Московский физико-технический институт; Крымский федеральный университет им. В.И. Вернадского
Автор, ответственный за переписку.
Email: fedyor@mail.ru
Россия, 141701, г. Долгопрудный, Институтский пер., 9; Россия, 295007, г. Симферополь, проспект академика Вернадского, 4
Д. А. Пасечнюк
Московский физико-технический институт; Исследовательский центр доверенного искусственного интеллекта ИСП РАН
Автор, ответственный за переписку.
Email: dmivilensky1@gmail.com
Россия, 141701, г. Долгопрудный, Институтский пер., 9; Россия, 109004, г. Москва, ул. Александра Солженицына, 25
М. С. Алкуса
Московский физико-технический институт; Национальный исследовательский университет “Высшая школа экономики”
Автор, ответственный за переписку.
Email: mohammad.alkousa@phystech.edu
Россия, 141701, г. Долгопрудный, Институтский пер., 9; Россия, 101000, г. Москва, ул. Мясницкая, д. 20
А. М. Райгородский
Московский физико-технический институт; Московский государственный университет им. М.В. Ломоносова, механико-математический факультет; Кавказский математический центр Адыгейского государственного университета
Автор, ответственный за переписку.
Email: raigorodsky@yandex-team.ru
Россия, 141701, г. Долгопрудный, Институтский пер., 9; Россия, 119991, г. Москва,, Ленинские горы, д. 1; Россия, 385000, г. Майкоп, ул. Первомайская, 208
И. В. Баран
Крымский федеральный университет им. В.И. Вернадского
Автор, ответственный за переписку.
Email: matemain@mail.ru
Россия, 295007, г. Симферополь, проспект академика Вернадского, 4
Список литературы
- 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.