Линейная сходимость унифицированного алгоритма прямо-двойственного типа для выпукло-вогнутых задач седловой точки с квадратичным ростом

Основная информация

• ID статьи: 2510.11990
• Название: Linear Convergence of a Unified Primal--Dual Algorithm for Convex--Concave Saddle Point Problems with Quadratic Growth
• Авторы: Cody Melcher (Университет Аризоны), Afrooz Jalilzadeh (Университет Аризоны), Erfan Yazdandoost Hamedani (Университет Аризоны)
• Классификация: math.OC (Оптимизация и управление)
• Дата публикации: 13 октября 2025 г. (препринт arXiv)
• Ссылка на статью: https://arxiv.org/abs/2510.11990

Аннотация

В данной работе исследуются задачи седловой точки (SP), с особым акцентом на выпукло-вогнутые задачи оптимизации, удовлетворяющие условиям двусторонней квадратичной функциональной роста (QFG) или двусторонней квадратичной роста градиента (QGG). Эти условия являются новыми условиями, специально разработанными для задач седловой точки и представляют собой расширение условий квадратичного роста в задачах минимизации. Данные условия ослабляют традиционные требования сильной выпуклости-сильной вогнутости, охватывая, таким образом, более широкий класс задач. Авторы предлагают обобщённый ускоренный алгоритм прямо-двойственного типа (GAPD) для решения задач седловой точки с невилинейными целевыми функциями, унифицируя и расширяя существующие методы. Доказано, что данный метод достигает линейной скорости сходимости при указанных ослабленных условиях. Кроме того, приводятся примеры структурированных задач седловой точки, удовлетворяющих двусторонним условиям QFG или QGG, демонстрирующие практическую применимость и релевантность метода.

Исследовательский контекст и мотивация

Определение задачи

В работе исследуется следующая задача седловой точки: $\min_{x \in X} \max_{y \in Y} f(x,y)$ где $f: X \times Y \rightarrow \mathbb{R}$ выпукла по $x$ для любого $y \in Y$ и вогнута по $y$ для любого $x \in X$, а $X \subseteq \mathcal{X}$ и $Y \subseteq \mathcal{Y}$ — замкнутые выпуклые множества.

Мотивация исследования

1. Ограничения традиционных методов: Существующие результаты о линейной сходимости для задач седловой точки обычно требуют условий сильной выпуклости-сильной вогнутости, что является чрезмерно строгим ограничением для многих практических приложений.
2. Широкая применимость: Задачи седловой точки имеют важные приложения в теории игр, распределённо-робастном обучении, генеративных состязательных сетях и других областях.
3. Теоретический пробел: Хотя в задачах минимизации условия квадратичного роста (QFG и QGG) доказали свою эффективность для гарантирования линейной сходимости, расширение этих условий на задачи седловой точки представляет нетривиальную задачу и в значительной степени остаётся неисследованным.
4. Унификация методов: Существующие алгоритмы прямо-двойственного типа, такие как APD и OGDA, не имеют единой аналитической базы.

Основные вклады

1. Введение двусторонних условий роста: Впервые расширены условия QFG и QGG на задачи седловой точки с определением двусторонних условий квадратичного функционального роста и двусторонних условий квадратичного роста градиента.
2. Унифицированная схема алгоритма: Предложен обобщённый ускоренный алгоритм прямо-двойственного типа (GAPD), унифицирующий существующие методы APD и OGDA.
3. Гарантии линейной сходимости: Доказано, что алгоритм GAPD достигает линейной скорости сходимости при условиях двусторонней QFG или QGG.
4. Расширение на расстояния Брегмана: Аналитическая база расширена на расстояния Брегмана, повышая гибкость и применимость метода.
5. Классы структурированных задач: Приведены конкретные примеры структурированных задач седловой точки, удовлетворяющих двусторонним условиям роста.

Описание методологии

Определение задачи

Исследование выпукло-вогнутых задач оптимизации седловой точки, где целевая функция удовлетворяет условиям двусторонней квадратичной роста, а не традиционным условиям сильной выпуклости-сильной вогнутости.

Ключевые определения

Двусторонний квадратичный рост градиента (Two-Sided QGG)

Для задачи седловой точки, если существуют константы $(μ_x, μ_y) \in \mathbb{R}_{++}^2$ такие, что для любых $x \in X$ и $y \in Y$ выполняется: $\langle F(z) - F(\bar{z}), z - \bar{z} \rangle \geq 2D_Z^M(z, \bar{z})$ где $z = [x^T, y^T]^T$, $\bar{z} = P_{Z^*}(z)$, $F(z) = [\nabla_x f(x,y)^T, -\nabla_y f(x,y)^T]^T$, $M = \text{diag}(\{μ_x I_n, μ_y I_m\})$.

Двусторонний квадратичный функциональный рост (Two-Sided QFG)

Если существуют константы $(μ_x, μ_y) \in \mathbb{R}_{++}^2$ такие, что: $f(x, \bar{y}) - f(\bar{x}, y) \geq D_Z^M(z, \bar{z})$

Архитектура алгоритма GAPD

Основные правила обновления алгоритма GAPD:

1. Вычисление членов импульса:
   • $q_k^y = \nabla_y f(x_k, y_k) - \nabla_y f(x_{k-1}, y_{k-1})$
   • $q_k^x = \nabla_x f(x_k, y_k) - \nabla_x f(x_{k-1}, y_{k-1})$
2. Обновление двойственной переменной: $y_{k+1} = \arg\min_{y \in Y} \left\{-\langle \nabla_y f(x_k, y_k) + α_k q_k^y, y \rangle + \frac{1}{σ_k} D_Y(y, y_k) \right\}$
3. Конструирование агрегированного градиента: $s_k = θ_k \nabla_x f(x_k, y_{k+1}) + (1-θ_k) \nabla_x f(x_k, y_k) + β_k q_k^x$
4. Обновление прямой переменной: $x_{k+1} = \arg\min_{x \in X} \left\{ \langle s_k, x \rangle + \frac{1}{τ_k} D_X(x, x_k) \right\}$

Технические инновации

1. Унификация: Через параметр $θ_k$ унифицируются существующие методы:
   • $θ_k = 0$: вырождается в OGDA
   • $θ_k = 1, β_k = 0$: вырождается в APD
2. Расстояния Брегмана: Использование расстояний Брегмана вместо евклидова расстояния обеспечивает большую гибкость.
3. Двусторонние условия: Впервые односторонние условия роста расширены на двусторонние версии для задач седловой точки.

Теоретический анализ

Основная теорема сходимости

Теорема 4.4: Пусть $\{(x_k, y_k)\}_{k≥0}$ — последовательность, генерируемая алгоритмом 1. Предположим, что выполнены предположения 2.1-4.3, тогда для любых $K ≥ 1$ и $Γ \succ 0$: $D_Z^{A_K - Γ B_K}(\bar{z}_K, z_K) ≤ \frac{t_0}{t_K} D_Z^{A_0}(\bar{z}_0, z_0)$

Линейная скорость сходимости

Следствие 4.5: При надлежащем выборе параметров итерационная последовательность сходится к множеству оптимальных решений с линейной скоростью: $D_Z(\bar{z}_K, z_K) ≤ D_Z^{R_K}(\bar{z}_0, z_0)$ где $R_K = \frac{α^{K+1}}{(1-α)c_M}$, скорость сходимости зависит от параметра $ς > 0$ (при QFG $ς = θ$, при QGG $ς = 2(1-θ)$).

Классы структурированных задач

Класс задач

Рассматривается следующий класс структурированных выпукло-вогнутых задач седловой точки: $\min_{x \in X} \max_{y \in Y} h(C_1 x) + \langle Ax, y \rangle - g(C_2 y)$ где $h: \mathbb{R}^p \rightarrow \mathbb{R}$ и $g: \mathbb{R}^q \rightarrow \mathbb{R}$ — сильно выпуклые функции.

Достаточные условия для выполнения требований

Предложение 5.1: Если существуют константы $ξ_1, ξ_2, ξ_3, ξ_4 > 0$ такие, что:

• $ξ_1 C_1^T C_1 \succeq A^T A$, $ξ_2 C_1^T C_1 \succeq \|λ^*\|^2 G^T G$
• $ξ_3 C_2^T C_2 \succeq AA^T$, $ξ_4 C_2^T C_2 \succeq \|ν^*\|^2 F^T F$

то данный класс задач удовлетворяет условиям двусторонней QGG и QFG.

Численные эксперименты

Установка экспериментов

Рассматривается случайно сгенерированная задача седловой точки: $\min_{x \in \mathbb{R}^n} \max_{y \in \mathbb{R}^m} \frac{1}{2}\|C_1 x - b_1\|_2^2 + \langle Ax, y \rangle - \frac{1}{2}\|C_2 y - b_2\|_2^2$

Результаты экспериментов

1. Тестирование размерности: Тестирование проводилось при трёх различных размерностях $(n,m,p,q) \in \{(75,60,60,50), (150,120,120,100), (300,240,240,200)\}$.
2. Сравнение производительности: Алгоритм GAPD превосходит стандартный метод GDA при различных значениях $θ$.
3. Влияние параметров: Значение $θ = 0.99$ показывает наилучшую производительность, незначительно превосходя случай $θ = 1$.

Связанные работы

Задачи минимизации

• Условия QFG и QGG имеют важное значение как в детерминированных, так и в стохастических параметрах оптимизации
• Существующие работы в основном сосредоточены на линейной сходимости в выпуклых задачах оптимизации

Задачи седловой точки

• Метод Arrow-Hurwicz (GDA): сложность $O(κ^2 \log(1/ε))$
• Метод внешнего градиента (EG): сложность $O(κ \log(1/ε))$
• Оптимистичный метод градиента (OGDA): сложность $O(κ \log(1/ε))$
• Ускоренный алгоритм прямо-двойственного типа (APD): достигает $O(1/ε)$ и $O(1/ε^2)$ в параметрах C-C и SC-C соответственно

Вариационные неравенства

Условия квадратичного роста тесно связаны с анализом границ ошибок для монотонных операторов и метрической субрегулярностью.

Заключение и обсуждение

Основные выводы

1. Успешно расширены условия квадратичного роста на задачи седловой точки с введением двусторонних условий QFG и QGG
2. Алгоритм GAPD достигает линейной сходимости при ослабленных условиях, унифицируя существующие методы
3. Предоставлены классы структурированных задач, удовлетворяющих новым условиям роста

Ограничения

1. Проверка условий: Проверка двусторонних условий роста в практических приложениях может быть сложной задачей
2. Выбор параметров: Выбор оптимального параметра $θ$ требует знания, специфичного для конкретной задачи
3. Обработка ограничений: Основное внимание уделяется простым множествам ограничений, обработка сложных ограничений ограничена

Направления будущих исследований

1. Исследование поведения сходимости при односторонних условиях квадратичного роста
2. Изучение приложений в распределённой оптимизации
3. Расширение на более сложные задачи оптимизации с ограничениями

Глубокая оценка

Преимущества

1. Теоретическая инновация: Впервые систематически расширены условия квадратичного роста на задачи седловой точки, заполняя важный теоретический пробел
2. Унифицированная база: Алгоритм GAPD элегантно унифицирует несколько существующих методов
3. Практическая ценность: Ослабленные условия делают метод применимым к более широкому классу задач
4. Строгий анализ: Предоставлен полный анализ сходимости и конкретные скорости сходимости

Недостатки

1. Ограниченные эксперименты: Численные эксперименты относительно просты, отсутствует проверка на практических сценариях приложений
2. Анализ соотношений условий: Анализ соотношения между двусторонними условиями QFG и QGG может быть более глубоким
3. Вычислительная сложность: Вычислительная сложность каждой итерации не проанализирована подробно

Влияние

1. Академический вклад: Предоставляет важные теоретические инструменты для теории оптимизации седловой точки
2. Практическая ценность: Унификация и гибкость метода открывают потенциал для применения в нескольких областях
3. Масштабируемость: Обеспечивает прочную теоретическую базу для последующих исследований

Сценарии применения

1. Состязательное обучение в машинном обучении
2. Распределённо-робастная оптимизация
3. Приложения в теории игр
4. Выпуклые задачи оптимизации со специальной структурой

Библиография

Статья цитирует 46 связанных работ, охватывающих оптимизацию седловой точки, вариационные неравенства, условия квадратичного роста и другие смежные области, обеспечивая прочную теоретическую базу для данного исследования.