|
МАТЕМАТИЧЕСКИЕ ОСНОВЫ И ЧИСЛЕННЫЕ МЕТОДЫ МОДЕЛИРОВАНИЯ
Variance reduction for minimax problems with a small dimension of one of the variables
[Редукция дисперсии для минимаксных задач с небольшой размерностью одной из переменных]
E. L. Gladinabc, E. D. Borodichb a Humboldt University of Berlin,
6 Unter den Linden, Berlin, 10117, Germany
b Moscow Institute of Physics and Technology,
9 Institutskiy per., Dolgoprudny, 141701, Russia
c Institute for Information Transmission Problems RAS,
19/1 Bolshoy Karetny per., Moscow, 127051, Russia
Аннотация:
Статья посвящена выпукло-вогнутым седловым задачам, в которых целевая функция является суммой большого числа слагаемых. Такие задачи привлекают значительное внимание математического сообщества в связи с множеством приложений в машинном обучении, включая adversarial learning, adversarial attacks и robust reinforcement learning, и это лишь некоторые из них. Отдельные функции в сумме обычно представляют собой ошибку, связанную с объектом из выборки. Кроме того, формулировка допускает (возможно, негладкий) композитный член. Такие слагаемые часто отражают регуляризацию в задачах машинного обучения. Предполагается, что размерность одной из групп переменных относительно мала (около сотни или меньше), а другой — велика. Такой случай возникает, например, при рассмотрении двойственной формулировки задачи минимизации с умеренным числом ограничений. Предлагаемый подход основан на использовании метода секущей плоскости Вайды для минимизации относительно внешнего блока переменных. Этот алгоритм оптимизации особенно эффективен, когда размерность задачи не очень велика. Неточный оракул для метода Вайды вычисляется через приближенное решение внутренней задачи максимизации, которая решается ускоренным алгоритмом с редукцией дисперсии Katyusha. Таким образом, мы используем структуру задачи для достижения быстрой сходимости. В исследовании получены отдельные оценки сложности для градиентов различных компонент относительно различных переменных. Предложенный подход накладывает слабые предположения о целевой функции. В частности, не требуется ни сильной выпуклости, ни гладкости относительно низкоразмерной группы переменных. Количество шагов предложенного алгоритма, а также арифметическая сложность каждого шага явно зависят от размерности внешней переменной, отсюда предположение, что она относительно мала.
Ключевые слова:
седловые задачи, методы первого порядка, методы секущей плоскости, редукция дисперсии.
Поступила в редакцию: 13.02.2022
Образец цитирования:
E. L. Gladin, E. D. Borodich, “Variance reduction for minimax problems with a small dimension of one of the variables”, Компьютерные исследования и моделирование, 14:2 (2022), 257–275
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/crm967 https://www.mathnet.ru/rus/crm/v14/i2/p257
|
Статистика просмотров: |
Страница аннотации: | 109 | PDF полного текста: | 37 | Список литературы: | 24 |
|