Linear Convergence of a Unified Primal--Dual Algorithm for Convex--Concave Saddle Point Problems with Quadratic Growth

基本信息

• 论文ID: 2510.11990
• 标题: Linear Convergence of a Unified Primal--Dual Algorithm for Convex--Concave Saddle Point Problems with Quadratic Growth
• 作者: Cody Melcher (University of Arizona), Afrooz Jalilzadeh (University of Arizona), Erfan Yazdandoost Hamedani (University of Arizona)
• 分类: math.OC (Optimization and Control)
• 发表时间: 2025年10月13日 (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}$对任意$y \in Y$关于$x$凸，对任意$x \in X$关于$y$凹，$X \subseteq \mathcal{X}$和$Y \subseteq \mathcal{Y}$是闭凸集。

研究动机

1. 传统方法的局限性：现有鞍点问题的线性收敛结果通常需要强凸-强凹条件，这在许多实际应用中过于严格。
2. 应用广泛性：鞍点问题在博弈论、分布鲁棒学习、生成对抗网络等领域有重要应用。
3. 理论空白：虽然在最小化问题中，二次增长条件(QFG和QGG)已被证明能保证线性收敛，但将这些条件扩展到鞍点问题是非平凡的挑战，且在很大程度上尚未被探索。
4. 方法统一性：现有的原对偶方法如APD、OGDA等缺乏统一的分析框架。

核心贡献

1. 提出双侧增长条件：首次将QFG和QGG条件扩展到鞍点问题，定义了双侧二次函数增长和双侧二次梯度增长条件。
2. 统一算法框架：提出了广义加速原对偶(GAPD)算法，统一了现有的APD和OGDA方法。
3. 线性收敛保证：证明了在双侧QFG或QGG条件下，GAPD算法实现线性收敛率。
4. Bregman距离扩展：将分析框架扩展到Bregman距离，增强了方法的灵活性和适用性。
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. Bregman距离：使用Bregman距离代替欧几里得距离，提供更大的灵活性。
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)：在C-C和SC-C设置下分别达到$O(1/ε)$和$O(1/ε^2)$

变分不等式

二次增长条件与单调算子的误差界分析和度量次正则性密切相关。

结论与讨论

主要结论

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篇相关文献，涵盖了鞍点优化、变分不等式、二次增长条件等多个相关领域的重要工作，为本研究提供了坚实的理论基础。