Отправить статью по E-mail Решение сильно выпукло-вогнутых композитных седловых задач с небольшой размерностью одной из групп переменных
- Авторы: Алкуса М.С.1, Гасников А.В.1,2,3,4, Гладин Е.Л.5, Курузов И.А.1, Пасечнюк Д.А.1, Стонякин Ф.С.1,6
-
Учреждения:
- Московский физико-технический институт (национальный исследовательский университет)
- Институт системного программирования им. В.П. Иванникова РАН
- Институт проблем передачи информации им. А.А. Харкевича Российской академии наук
- Кавказский математический центр, Адыгейский государственный университет
- Humboldt University
- Крымский федеральный университет имени В. И. Вернадского
- Выпуск: Том 214, № 3 (2023)
- Страницы: 3-53
- Раздел: Статьи
- URL: https://bakhtiniada.ru/0368-8666/article/view/133505
- DOI: https://doi.org/10.4213/sm9700
- ID: 133505
Цитировать
Открытый доступ
Доступ предоставлен
Только для подписчиков
Аннотация
Разработаны алгоритмические методы, гарантирующие эффективные оценки сложности для сильно выпукло-вогнутых седловых задач в случае, когда одна из групп переменных имеет большую размерность, а другая – достаточно малую (до сотни). Предлагаемая методика основана на сведении задач такого типа к задаче минимизации выпуклого (максимизации вогнутого) функционала по одной из переменных, для которого можно найти приближенное значение градиента в произвольной точке с необходимой точностью с помощью вспомогательной оптимизационной подзадачи по другой переменной. При этом для маломерных задач предлагается использовать методы эллипсоидов и Вайды, а для многомерных – ускоренные градиентные методы с неточной информацией о градиенте или субградиенте. Для случая очень малой размерности задачи одной из групп переменных (до 5) на гиперкубе достаточно эффективным будет иной предлагаемый подход к сильно выпукло-вогнутым седловым задачам на базе нового варианта многомерного аналога метода Ю. Е. Нестерова на квадрате (метод многомерной дихотомии) с возможностью использования неточных значений градиента целевого функционала.Библиография: 28 названий.
Ключевые слова
Об авторах
Мохаммад Соуд Алкуса
Московский физико-технический институт (национальный исследовательский университет)
Email: mohammad.alkousa@phystech.edu
Александр Владимирович Гасников
Московский физико-технический институт (национальный исследовательский университет); Институт системного программирования им. В.П. Иванникова РАН; Институт проблем передачи информации им. А.А. Харкевича Российской академии наук; Кавказский математический центр, Адыгейский государственный университет
Email: gasnikov@yandex.ru
доктор физико-математических наук, доцент
Егор Леонидович Гладин
Humboldt University
Email: mohammad.alkousa@phystech.edu
Илья Алексеевич Курузов
Московский физико-технический институт (национальный исследовательский университет)
Email: mohammad.alkousa@phystech.edu
Дмитрий Аркадьевич Пасечнюк
Московский физико-технический институт (национальный исследовательский университет)
Email: pasechniuk.da@phystech.edu
без ученой степени, без звания
Федор Сергеевич Стонякин
Московский физико-технический институт (национальный исследовательский университет); Крымский федеральный университет имени В. И. Вернадского
Автор, ответственный за переписку.
Email: fedyor@mail.ru
кандидат физико-математических наук, доцент
Список литературы
- М. С. Алкуса, А. В. Гасников, Д. М. Двинских, Д. А. Ковалев, Ф. С. Стонякин, “Ускоренные методы для седловых задач”, Ж. вычисл. матем. и матем. физ., 60:11 (2020), 1843–1866
- W. Azizian, I. Mitliagkas, S. Lacoste-Julien, G. Gidel, “A tight and unified analysis of gradient-based methods for a whole spectrum of differentiable games”, Proceedings of the twenty third international conference on artificial intelligence and statistics, Proceedings of Machine Learning Research (PMLR), 108, 2020, 2863–2873
- А. В. Гасников, П. Е. Двуреченский, Ю. Е. Нестеров, “Стохастические градиентные методы с неточным оракулом”, Труды МФТИ, 8:1 (2016), 41–91
- А. В. Гасников, Д. М. Двинских, П. Е. Двуреченский, Д. И. Камзолов, В. В. Матюхин, Д. А. Пасечнюк, Н. К. Тупица, А. В. Чернов, “Ускоренный метаалгоритм для задач выпуклой оптимизации”, Ж. вычисл. матем. и матем. физ., 61:1 (2021), 20–31
- Le Thi Khanh Hien, Renbo Zhao, W. B. Haskell, An inexact primal-dual framework for large-scale non-bilinear saddle point problem
- Guanghui Lan, First-order and stochastic optimization methods for machine learning, Springer Ser. Data Sci., Springer, Cham, 2020, xiii+582 pp.
- Tianyi Lin, Chi Jin, M. I. Jordan, “Near-optimal algorithms for minimax optimization”, Proceedings of thirty third conference on learning theory, Proceedings of Machine Learning Research (PMLR), 125, 2020, 2738–2779
- I. Usmanova, M. Kamgarpour, A. Krause, K. Levy, “Fast projection onto convex smooth constraints”, Proceedings of the 38th international conference on machine learning, Proceedings of Machine Learning Research (PMLR), 139, 2021, 10476–10486
- А. В. Гасников, Современные численные методы оптимизации. Метод универсального градиентного спуска, 2-е испр. изд., МЦНМО, М., 2021, 272 с.
- B. Cox, A. Juditsky, A. Nemirovski, “Decomposition techniques for bilinear saddle point problems and variational inequalities with affine monotone operators”, J. Optim. Theory Appl., 172:2 (2017), 402–435
- Yu. Nesterov, “Excessive gap technique in nonsmooth convex minimization”, SIAM J. Optim., 16:1 (2005), 235–249
- Junyu Zhang, Mingyi Hong, Shuzhong Zhang, “On lower iteration complexity bounds for the convex concave saddle point problems”, Math. Program., 194:1-2, Ser. A (2022), 901–935
- Yuanhao Wang, Jian Li, “Improved algorithms for convex-concave minimax optimization”, NIPS 2020, Adv. Neural Inf. Process. Syst., 33, MIT Press, Cambridge, MA, 2020, 11 pp.
- A. Nemirovski, S. Onn, U. G. Rothblum, “Accuracy certificates for computational problems with convex structure”, Math. Oper. Res., 35:1 (2010), 52–78
- A. Nemirovski, Information-based complexity of convex programming, Lecture notes, 1995, 268 pp.
- Д. А. Пасечнюк, Ф. С. Стонякин, “Об одном методе минимизации выпуклой липшицевой функции двух переменных на квадрате”, Компьютерные исследования и моделирование, 11:3 (2019), 379–395
- Б. Т. Поляк, Введение в оптимизацию, Наука, М., 1983, 384 с.
- O. Devolder, F. Glineur, Yu. Nesterov, “First-order methods of smooth convex optimization with inexact oracle”, Math. Program., 146:1-2, Ser. A (2014), 37–75
- P. M. Vaidya, “A new algorithm for minimizing convex functions over convex sets”, Math. Program., 73:3, Ser. A (1996), 291–341
- S. Bubeck, “Convex optimization: algorithms and complexity”, Found. Trends Mach. Learn., 8:3-4 (2015), 231–357
- E. Gladin, A. Sadiev, A. Gasnikov, P. Dvurechensky, A. Beznosikov, M. Alkousa, “Solving smooth min-min and min-max problems by mixed oracle algorithms”, MOTOR 2021: Mathematical optimization theory and operations research–recent trends, Commun. Comput. Inf. Sci., 1476, Springer, Cham, 2021, 19–40
- А. В. Гасников, Ю. Е. Нестеров, “Универсальный метод для задач стохастической композитной оптимизации”, Ж. вычисл. матем. и матем. физ., 58:1 (2018), 52–69
- J. M. Danskin, “The theory of Max-Min, with applications”, SIAM J. Appl. Math., 14:4 (1966), 641–664
- O. Devolder, Exactness, inexactness and stochasticity in first-order methods for large-scale convex optimization, PhD thesis, UCL, CORE, Louvain-la-Neuve, 2013, vii+309 pp.
- O. Devolder, F. Glineur, Yu. Nesterov, First-order methods with inexact oracle: the strongly convex case, CORE Discussion Papers, no. 2013/16, 2013, 35 pp.
- Н. З. Шор, Методы минимизации недифференцируемых функций и их приложения, Наукова думка, Киев, 1979, 199 с.
- Исходный код экспериментов на GitHub
- P. Bernhard, A. Rapaport, “On a theorem of Danskin with an application to a theorem of von Neumann–Sion”, Nonlinear Anal., 24:8 (1995), 1163–1181
Дополнительные файлы
