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

Basic Information

• Paper ID: 2510.11990
• Title: Linear Convergence of a Unified Primal--Dual Algorithm for Convex--Concave Saddle Point Problems with Quadratic Growth
• Authors: Cody Melcher (University of Arizona), Afrooz Jalilzadeh (University of Arizona), Erfan Yazdandoost Hamedani (University of Arizona)
• Classification: math.OC (Optimization and Control)
• Publication Date: October 13, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.11990

Abstract

This paper investigates saddle point (SP) problems, with particular focus on convex-concave optimization problems satisfying two-sided quadratic function growth (QFG) or two-sided quadratic gradient growth (QGG) conditions. These conditions are newly tailored for saddle point problems and extend the quadratic growth conditions from minimization problems. These conditions relax traditional strong convexity-strong concavity requirements, thereby encompassing a broader class of problems. The authors propose a generalized accelerated primal-dual (GAPD) algorithm to solve saddle point problems with non-bilinear objective functions, unifying and extending existing methods. Linear convergence rates are established under these relaxed conditions. Furthermore, concrete examples of structured saddle point problems satisfying two-sided QFG or QGG are provided, demonstrating the practical applicability and relevance of the proposed approach.

Research Background and Motivation

Problem Definition

This paper studies the following saddle point problem: $\min_{x \in X} \max_{y \in Y} f(x,y)$ where $f: X \times Y \rightarrow \mathbb{R}$ is convex in $x$ for any $y \in Y$ and concave in $y$ for any $x \in X$, with $X \subseteq \mathcal{X}$ and $Y \subseteq \mathcal{Y}$ being closed convex sets.

Research Motivation

1. Limitations of Traditional Methods: Existing linear convergence results for saddle point problems typically require strong convexity-strong concavity conditions, which are overly restrictive in many practical applications.
2. Broad Applicability: Saddle point problems have important applications in game theory, distributionally robust learning, generative adversarial networks, and other fields.
3. Theoretical Gap: While quadratic growth conditions (QFG and QGG) have been proven to guarantee linear convergence in minimization problems, extending these conditions to saddle point problems is a non-trivial challenge and remains largely unexplored.
4. Method Unification: Existing primal-dual methods such as APD and OGDA lack a unified analytical framework.

Core Contributions

1. Two-Sided Growth Conditions: First extends QFG and QGG conditions to saddle point problems, defining two-sided quadratic function growth and two-sided quadratic gradient growth conditions.
2. Unified Algorithm Framework: Proposes a generalized accelerated primal-dual (GAPD) algorithm that unifies existing APD and OGDA methods.
3. Linear Convergence Guarantee: Establishes linear convergence rates for the GAPD algorithm under two-sided QFG or QGG conditions.
4. Bregman Distance Extension: Extends the analytical framework to Bregman distances, enhancing method flexibility and applicability.
5. Structured Problem Classes: Provides concrete examples of structured saddle point problems satisfying two-sided growth conditions.

Method Details

Task Definition

Study convex-concave saddle point optimization problems where the objective function satisfies two-sided quadratic growth conditions rather than traditional strong convexity-strong concavity conditions.

Core Definitions

Two-Sided Quadratic Gradient Growth (Two-Sided QGG)

For a saddle point problem, if there exist constants $(μ_x, μ_y) \in \mathbb{R}_{++}^2$ such that for any $x \in X$ and $y \in Y$: $\langle F(z) - F(\bar{z}), z - \bar{z} \rangle \geq 2D_Z^M(z, \bar{z})$ where $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 Quadratic Function Growth (Two-Sided QFG)

If there exist constants $(μ_x, μ_y) \in \mathbb{R}_{++}^2$ such that: $f(x, \bar{y}) - f(\bar{x}, y) \geq D_Z^M(z, \bar{z})$

GAPD Algorithm Architecture

The core update rules of the GAPD algorithm are:

1. Momentum Term Computation:
   • $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. Dual Variable Update: $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. Aggregated Gradient Construction: $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. Primal Variable Update: $x_{k+1} = \arg\min_{x \in X} \left\{ \langle s_k, x \rangle + \frac{1}{τ_k} D_X(x, x_k) \right\}$

Technical Innovations

1. Unification: Unifies existing methods through parameter $θ_k$:
   • $θ_k = 0$: Reduces to OGDA
   • $θ_k = 1, β_k = 0$: Reduces to APD
2. Bregman Distance: Uses Bregman distance instead of Euclidean distance, providing greater flexibility.
3. Two-Sided Conditions: First extends one-sided growth conditions to two-sided versions for saddle point problems.

Theoretical Analysis

Main Convergence Theorem

Theorem 4.4: Let $\{(x_k, y_k)\}_{k≥0}$ be the sequence generated by Algorithm 1. Assume Assumptions 2.1-4.3 hold. Then for any $K ≥ 1$ and $Γ \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)$

Linear Convergence Rate

Corollary 4.5: Under appropriate parameter choices, the iterative sequence converges to the optimal solution set at a linear rate: $D_Z(\bar{z}_K, z_K) ≤ D_Z^{R_K}(\bar{z}_0, z_0)$ where $R_K = \frac{α^{K+1}}{(1-α)c_M}$, and the convergence rate depends on parameter $ς > 0$ (with $ς = θ$ for QFG and $ς = 2(1-θ)$ for QGG).

Structured Problem Classes

Problem Class

Consider the following structured convex-concave saddle point problem: $\min_{x \in X} \max_{y \in Y} h(C_1 x) + \langle Ax, y \rangle - g(C_2 y)$ where $h: \mathbb{R}^p \rightarrow \mathbb{R}$ and $g: \mathbb{R}^q \rightarrow \mathbb{R}$ are strongly convex functions.

Sufficient Conditions for Satisfying the Conditions

Proposition 5.1: If there exist constants $ξ_1, ξ_2, ξ_3, ξ_4 > 0$ such that:

• $ξ_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$

then this problem class satisfies two-sided QGG and QFG conditions.

Numerical Experiments

Experimental Setup

Consider randomly generated saddle point problems: $\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$

Experimental Results

1. Dimension Testing: Tests conducted on three different dimensions $(n,m,p,q) \in \{(75,60,60,50), (150,120,120,100), (300,240,240,200)\}$.
2. Performance Comparison: GAPD outperforms standard GDA methods across different values of $θ$.
3. Parameter Impact: $θ = 0.99$ achieves the best performance, slightly outperforming the case $θ = 1$.

Related Work

Minimization Problems

• QFG and QGG conditions are important in both deterministic and stochastic optimization settings
• Existing work primarily focuses on linear convergence in convex optimization problems

Saddle Point Problems

• Arrow-Hurwicz method (GDA): $O(κ^2 \log(1/ε))$ complexity
• Extragradient method (EG): $O(κ \log(1/ε))$ complexity
• Optimistic gradient method (OGDA): $O(κ \log(1/ε))$ complexity
• Accelerated primal-dual method (APD): Achieves $O(1/ε)$ and $O(1/ε^2)$ complexity in C-C and SC-C settings respectively

Variational Inequalities

Quadratic growth conditions are closely related to error bound analysis and metric subregularity for monotone operators.

Conclusions and Discussion

Main Conclusions

1. Successfully extends quadratic growth conditions to saddle point problems, proposing two-sided QFG and QGG conditions
2. GAPD algorithm achieves linear convergence under relaxed conditions, unifying existing methods
3. Provides structured problem classes satisfying the new growth conditions

Limitations

1. Condition Verification: Verifying two-sided growth conditions in practical applications may be challenging
2. Parameter Selection: Optimal parameter choice for $θ$ requires problem-specific knowledge
3. Constraint Handling: Primarily focuses on simple constraint sets with limited treatment of complex constraints

Future Directions

1. Investigate convergence behavior under one-sided quadratic growth conditions
2. Explore applications in distributed optimization
3. Extend to more complex constrained optimization problems

In-Depth Evaluation

Strengths

1. Theoretical Innovation: First systematically extends quadratic growth conditions to saddle point problems, filling an important theoretical gap
2. Unified Framework: GAPD algorithm elegantly unifies multiple existing methods
3. Practical Value: Relaxed conditions make the method applicable to a broader class of problems
4. Rigorous Analysis: Provides complete convergence analysis and explicit convergence rates

Weaknesses

1. Limited Experiments: Numerical experiments are relatively simple, lacking validation on practical application scenarios
2. Condition Relationships: Analysis of relationships between two-sided QFG and QGG conditions could be deeper
3. Computational Complexity: Computational complexity per iteration is not analyzed in detail

Impact

1. Academic Contribution: Provides important theoretical tools for saddle point optimization theory
2. Practical Value: Method unification and flexibility make it promising for multiple application domains
3. Extensibility: Provides a solid theoretical foundation for subsequent research

Applicable Scenarios

1. Adversarial training in machine learning
2. Distributionally robust optimization
3. Game-theoretic applications
4. Convex optimization problems with special structure

References

The paper cites 46 relevant references covering multiple related fields including saddle point optimization, variational inequalities, and quadratic growth conditions, providing a solid theoretical foundation for this research.