Компьютерные исследования и моделирование
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Компьютерные исследования и моделирование:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Компьютерные исследования и моделирование, 2022, том 14, выпуск 2, страницы 257–275
DOI: https://doi.org/10.20537/2076-7633-2022-14-2-257-275
(Mi crm967)
 

МАТЕМАТИЧЕСКИЕ ОСНОВЫ И ЧИСЛЕННЫЕ МЕТОДЫ МОДЕЛИРОВАНИЯ

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. Таким образом, мы используем структуру задачи для достижения быстрой сходимости. В исследовании получены отдельные оценки сложности для градиентов различных компонент относительно различных переменных. Предложенный подход накладывает слабые предположения о целевой функции. В частности, не требуется ни сильной выпуклости, ни гладкости относительно низкоразмерной группы переменных. Количество шагов предложенного алгоритма, а также арифметическая сложность каждого шага явно зависят от размерности внешней переменной, отсюда предположение, что она относительно мала.
Ключевые слова: седловые задачи, методы первого порядка, методы секущей плоскости, редукция дисперсии.
Финансовая поддержка Номер гранта
Deutsche Forschungsgemeinschaft 390685689
Министерство науки и высшего образования Российской Федерации 0714-2020-0005
Работа Е. Л. Гладина финансирована Deutsche Forschungsgemeinschaft (DFG, Немецкий исследовательский фонд) в рамках Excellence Strategy Германии --- Берлинский математический исследовательский центр MATH+ (EXC-2046/1, project ID: 390685689). Работа Е. Бородич выполнена при поддержке Министерства науки и высшего образования Российской Федерации (госзадание), № 075-00337-20-03, проект № 0714-2020-0005.
Поступила в редакцию: 13.02.2022
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.8
Язык публикации: английский
Образец цитирования: 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
Цитирование в формате AMSBIB
\RBibitem{GlaBor22}
\by E.~L.~Gladin, E.~D.~Borodich
\paper Variance reduction for minimax problems with a small dimension of one of the variables
\jour Компьютерные исследования и моделирование
\yr 2022
\vol 14
\issue 2
\pages 257--275
\mathnet{http://mi.mathnet.ru/crm967}
\crossref{https://doi.org/10.20537/2076-7633-2022-14-2-257-275}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4216031}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/crm967
  • https://www.mathnet.ru/rus/crm/v14/i2/p257
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Компьютерные исследования и моделирование
    Статистика просмотров:
    Страница аннотации:109
    PDF полного текста:37
    Список литературы:24
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024