- Оптимизация седловой точки с приближенной минимизацией Oracle(arXiv)
Автор: Юхей Акимото
Аннотация: Основным подходом к оптимизации седловой точки minxmaxyf(x,y) является подход, основанный на градиенте, популяризированный генеративно-состязательными сетями (GAN). Напротив, мы анализируем альтернативный подход, полагающийся только на оракул, который приблизительно решает задачу минимизации. Наш подход находит приблизительные решения x′ и y′ для minx′f(x′,y) и maxy′f(x,y′) в заданной точке (x,y) и обновляет (x,y) до этих приблизительных решений (x′,y′) со скоростью обучения η. На локально сильных выпукло-вогнутых гладких функциях мы выводим условия на η, чтобы показать линейную сходимость к локальной седловой точке, что выявляет возможный недостаток недавно разработанных надежных алгоритмов обучения с подкреплением состязательности. Мы разрабатываем эвристический подход для адаптации η без производных и реализуем алгоритмы минимизации нулевого и первого порядка. Численные эксперименты проводятся, чтобы показать точность теоретических результатов, а также полезность механизма адаптации η.
2. Эффективные алгоритмы для федеративной седловой оптимизации (arXiv)
Автор: Чарли Хоу, Киран К. Текумпарампил, Джулия Фанти, Севун О.
Аннотация: Мы рассматриваем сильно выпукло-вогнутые минимаксные задачи в федеративной среде, где основным узким местом является коммуникационное ограничение. Когда клиенты произвольно разнородны, простой Minibatch Mirror-prox обеспечивает наилучшую производительность. По мере того, как клиенты становятся более однородными, использование множественных локальных градиентных обновлений на клиентах значительно улучшает Minibatch Mirror-prox за счет менее частого обмена данными. Наша цель — разработать алгоритм, который может использовать преимущество сходства клиентов при восстановлении производительности Minibatch Mirror-prox при произвольной неоднородности (вплоть до логарифмических коэффициентов). Мы даем первый объединенный алгоритм минимаксной оптимизации, который достигает этой цели. Основная идея состоит в том, чтобы объединить (i) SCAFFOLD (алгоритм, который выполняет уменьшение дисперсии между клиентами для выпуклой оптимизации), чтобы устранить наихудшую зависимость от неоднородности, и (ii) Catalyst (структуру для ускорения, основанную на изменении цели) для ускорения конвергенции без усиления отклонения клиентов. Мы доказываем, что этот алгоритм достигает нашей цели, и включаем эксперименты для проверки теории.
