|
МАТЕМАТИЧЕСКИЕ ОСНОВЫ И ЧИСЛЕННЫЕ МЕТОДЫ МОДЕЛИРОВАНИЯ
On accelerated methods for saddle-point problems with composite structure
[Об ускоренных методах для седловых задач с композитной структурой]
Ya. D. Tominina, V. D. Tominina, E. D. Borodicha, D. A. Kovalevb, P. E. Dvurechenskiicd, A. V. Gasnikova, S. V. Chukanove a Moscow Institute of Physics and Technology,
9 Institutskiy per., Dolgoprudny, Moscow region, 141701, Russia
b King Abdullah University of Science and Technology,
Thuwal, 23955 Thuwal, Makkah province, Saudi Arabia
c Weierstrass Institute for Applied Analysis and Stochastics,
39 Mohren st., Berlin, 10117, Germany
d IITP RAS,
19/1 Bolshoy Karetny per., Moscow, 127051, Russia
e Research Center “Computer Science and Control” of Russian Academy of Sciences,
44/2 Vavilova st., Moscow, 119333, Russia
Аннотация:
В данной работе рассматриваются сильно-выпукло сильно-вогнутые не билинейные седловые задачи с разными числами обусловленности по прямым и двойственным переменным. Во-первых, мы рассматриваем задачи с гладкими композитами, один из которых имеет структуру с конечной суммой. Для этой задачи мы предлагаем алгоритм уменьшения дисперсии с оценками сложности, превосходящими существующие ограничения в литературе. Во-вторых, мы рассматриваем седловые задачи конечной суммы с композитами и предлагаем несколько алгоритмов в зависимости от свойств составных членов. Когда составные члены являются гладкими, мы получаем лучшие оценки сложности, чем в литературе, включая оценки недавно предложенных почти оптимальных алгоритмов, которые не учитывают составную структуру задачи. Кроме того, наши алгоритмы позволяют разделить сложность, т. е. оценить для каждой функции в задаче количество вызовов оракула, достаточное для достижения заданной точности. Это важно, так как разные функции могут иметь разную арифметическую сложность оракула, а дорогие оракулы желательно вызывать реже, чем дешевые. Ключевым моментом во всех этих результатах является наша общая схема для седловых задач, которая может представлять самостоятельный интерес. Эта структура, в свою очередь, основана на предложенном нами ускоренном мета-алгоритме для композитной оптимизации с вероятностными неточными оракулами и вероятностной неточностью в проксимальном отображении, которые также могут представлять самостоятельный интерес.
Ключевые слова:
седловая задача, минимаксная оптимизация, композитная оптимизация, ускоренные алгоритмы.
Поступила в редакцию: 22.02.2023 Принята в печать: 23.02.2023
Образец цитирования:
Ya. D. Tominin, V. D. Tominin, E. D. Borodich, D. A. Kovalev, P. E. Dvurechenskii, A. V. Gasnikov, S. V. Chukanov, “On accelerated methods for saddle-point problems with composite structure”, Компьютерные исследования и моделирование, 15:2 (2023), 433–467
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/crm1069 https://www.mathnet.ru/rus/crm/v15/i2/p433
|
Статистика просмотров: |
Страница аннотации: | 83 | PDF полного текста: | 45 | Список литературы: | 19 |
|