- Негладкая композитная невыпукло-вогнутая минимаксная оптимизация(arXiv)
Автор:Цзяджин Ли, Линлинчжи Чжу, Энтони Ман-Чо Со
Аннотация . Невыпукло-вогнутая минимаксная оптимизация вызвала большой интерес в машинном обучении, включая обучение с устойчивостью к распределению данных, обучение с неразложимыми потерями, состязательное обучение и многие другие. Тем не менее, большинство существующих работ сосредоточено на вариантах градиент-спуск-подъем (GDA), которые можно применять только в гладких условиях. В данной работе рассматривается семейство минимаксных задач, целевая функция которых имеет негладкую составную структуру по переменной минимизации и вогнутую по переменной максимизации. Полностью используя составную структуру, мы предлагаем алгоритм сглаженного проксимального линейного спуска (\textit{smoothed} PLDA) и далее устанавливаем его сложность итерации O(ε−4), которая соответствует сложности сглаженного GDA~\cite{zhang2020single} при плавные настройки. Более того, при мягком предположении, что целевая функция удовлетворяет одностороннему условию Курдыки-Лоясевича с показателем степени θ∈(0,1), мы можем дополнительно повысить сложность итерации до O(ε−2max{2θ,1}). Насколько нам известно, это первый доказуемо эффективный алгоритм для негладких невыпукло-вогнутых задач, который может достичь оптимальной сложности итерации O (ε−2), если θ∈(0,1/2]. В качестве побочного продукта мы обсуждаем различных концепций стационарности и количественно прояснить их взаимосвязь, что может представлять самостоятельный интерес.Эмпирически мы иллюстрируем эффективность предложенного сглаженного PLDA в вариационных регуляризованных задачах устойчивой к распределению Вассерштейна оптимизации.△
2.Близкие к оптимальным алгоритмы уменьшения градиента в стохастической минимаксной оптимизации(arXiv)
Аннотация: мы изучаем задачу поиска почти стационарной точки для гладкой минимаксной оптимизации. Недавно предложенные методы дополнительного закрепленного градиента (EAG) обеспечивают оптимальную скорость сходимости для выпукло-вогнутой минимаксной задачи в детерминированной постановке. Однако прямое расширение EAG для стохастической оптимизации неэффективно. В этой статье мы разрабатываем новый стохастический алгоритм, называемый рекурсивной привязанной итерацией (RAIN). Мы показываем, что RAIN достигает почти оптимальной сложности стохастического оракула первого порядка (SFO) для стохастической минимаксной оптимизации как в выпукло-вогнутом, так и в сильно выпукло-сильно вогнутом случаях. Кроме того, мы расширили идею RAIN для решения структурированной невыпукло-невогнутой минимаксной задачи, а также достигли почти оптимальной сложности SFO.
