Zeroth-Order primal-dual Alternating Projection Gradient Algorithms for Nonconvex Minimax Problems with Coupled linear Constraints

This paper proposes two novel single-loop zeroth-order primal-dual algorithms, ZO-PDAPG and ZO-RMPDPG, that achieve state-of-the-art iteration complexity guarantees for solving nonconvex-(strongly) concave minimax problems with coupled linear constraints under both deterministic and stochastic settings.

The Gist

Here is an explanation of the paper, translated from complex mathematical jargon into a story about a high-stakes game of chess played in the dark.

The Big Picture: A Game of Cat and Mouse in the Dark

Imagine you are trying to solve a very difficult puzzle. This puzzle isn't just about finding the best solution; it's a battle. On one side, you have a "Minimizer" (let's call him Bob) who wants to make a cost as low as possible. On the other side, you have a "Maximizer" (let's call her Alice) who wants to make that cost as high as possible. They are playing a game of Minimax.

Usually, in math, players have a map. They can see the terrain, calculate the slope of the hill, and know exactly which way to step to win. This is called having "First-Order" information (gradients).

But in this paper, the players are blindfolded.

This is a Zeroth-Order problem. Bob and Alice cannot see the map, and they cannot feel the slope. They can only ask one question: "If I take a tiny step here, what is the final score?" They have to guess the best direction based purely on trial and error.

The Twist: The Tangled Rope

To make things even harder, Bob and Alice are tied together by a tangled rope (the "Coupled Linear Constraints").

• Bob can't just move anywhere; his move is limited by what Alice does, and vice versa.
• If Bob moves left, the rope pulls Alice. If Alice moves up, the rope restricts Bob.
• They have to find a winning strategy while constantly adjusting to keep the rope from snapping (violating the constraints).

The Problem: Why This Matters

This isn't just a theoretical game. This happens in the real world:

1. Cybersecurity: A hacker (Alice) tries to poison a database to break a security system (Bob), while the system tries to stay secure.
2. Network Traffic: A jammer tries to clog a network, while the network tries to route traffic efficiently.
3. AI Training: Training an AI to be robust against attacks.

The problem is that these systems are often non-convex. Imagine the terrain isn't a smooth bowl; it's a jagged mountain range with deep valleys and high peaks. It's easy to get stuck in a small valley thinking it's the bottom, when the real bottom is far away.

The Solution: Two New "Blindfolded" Strategies

The authors of this paper invented two new algorithms (strategies) for Bob and Alice to play this game without seeing the map, while respecting the tangled rope.

1. The "Steady Step" Strategy (ZO-PDAPG)

• How it works: This is a methodical, step-by-step approach.
  • Alice takes a blind step to maximize the score.
  • Bob takes a blind step to minimize it.
  • They check the rope. If they pulled too hard, they gently pull back to stay within the rules.
  • They repeat this, alternating turns.
• The Analogy: Imagine two people trying to find the center of a dark room while holding a bungee cord. They take small, careful steps, feeling the tension in the cord to know if they are drifting too far apart.
• The Result: For the "smooth" version of the game (Strongly Concave), they proved this method finds a solution very quickly. For the "jagged" version (Concave), it takes longer, but it still works.

2. The "Momentum" Strategy (ZO-RMPDPG)

• How it works: This is the "Steady Step" strategy but with momentum and memory.
  • Instead of just looking at the current step, this algorithm remembers the last few steps.
  • If the score was getting better in a certain direction, it builds up speed (momentum) in that direction, like a skier going downhill.
  • It also uses a "variance reduction" trick. Since they are blindfolded, their guesses are noisy (like trying to hear a whisper in a storm). This strategy filters out the noise by averaging many small guesses (mini-batches) to get a clearer signal.
• The Analogy: Imagine a skier in a blizzard. Instead of stopping after every turn to check the map, they trust their momentum, use their memory of the last few turns to smooth out the bumps, and rely on a team of friends shouting directions from behind to filter out the wind noise.
• The Result: This is the champion. It is the fastest known method for these specific "blindfolded" games. It beats all previous methods, especially in the noisy, random (stochastic) environments found in real-world machine learning.

Why Is This a Big Deal?

Before this paper, if you wanted to solve these "blindfolded, rope-tied" games, you either:

1. Had to use a very slow method that took forever.
2. Had to assume you could see the map (which you can't in black-box AI attacks).
3. Had no guarantee that the method would actually work.

The authors proved mathematically that their new methods will definitely find a solution, and they calculated exactly how many steps it will take.

• The "Steady Step" (ZO-PDAPG) is the first to guarantee a solution for the deterministic (no noise) version of these coupled problems.
• The "Momentum" (ZO-RMPDPG) is the first to guarantee a solution for the noisy (stochastic) version, and it does it faster than anyone else has ever done before.

The Bottom Line

The authors took a very hard problem—optimizing a battle between two opponents who are blindfolded and tied together—and gave them two new, mathematically proven strategies to win.

• For the real world: This means we can now better train AI to resist attacks, secure networks against hackers, and optimize complex systems without needing to know the internal "secret sauce" (gradients) of the models.
• The takeaway: Even when you can't see the path and you're tied down, you can still find the best route if you have the right strategy and enough patience.

Technical Summary

Here is a detailed technical summary of the paper "Zeroth-Order Primal-Dual Alternating Projection Gradient Algorithms for Nonconvex Minimax Problems with Coupled Linear Constraints."

1. Problem Statement

The paper addresses nonconvex minimax optimization problems subject to coupled linear constraints under both deterministic and stochastic settings. The general form of the problem is:

$$\min_{x \in X} \max_{y \in Y} \{ f(x, y) \mid Ax + By \preceq c \}$$

Where:

• $x \in X \subseteq \mathbb{R}^{d_x}$ and $y \in Y \subseteq \mathbb{R}^{d_y}$ are decision variables in convex compact sets.
• $f(x, y)$ is smooth, nonconvex in $x$, and (strongly) concave in $y$.
• $Ax + By \preceq c$ represents coupled linear constraints (where $\preceq$ denotes either $\leq$ or $=$).
• Stochastic Setting (P-S): The objective is an expectation $g(x, y) = \mathbb{E}_{\zeta}[G(x, y, \zeta)]$, common in machine learning applications like adversarial attacks and data poisoning.

Significance: These problems arise in critical applications such as adversarial attacks on resource allocation, network flow optimization, and robust training of deep neural networks. The "zeroth-order" aspect is crucial because, in many modern black-box scenarios (e.g., attacking a proprietary model or tuning hyperparameters), gradient information is unavailable, and only function evaluations are possible.

2. Methodology

The authors propose two novel single-loop zeroth-order algorithms that utilize primal-dual frameworks and alternating projection steps. They approximate gradients using finite differences (zeroth-order estimators) rather than exact gradients.

A. ZO-PDAPG (Deterministic Setting)

• Algorithm: Zeroth-Order Primal-Dual Alternating Projected Gradient.
• Mechanism:
  • Uses a Lagrangian formulation to handle coupled constraints via a dual variable $\lambda$.
  • At each iteration $k$, it updates $y$ (maximization step), $x$ (minimization step), and $\lambda$ (dual ascent step) sequentially.
  • Gradients are approximated using coordinate-wise finite differences: $\hat{\nabla} f(x, y) \approx \frac{f(x+\theta u, y) - f(x, y)}{\theta} u$.
  • Updates involve projection onto the feasible sets $X, Y$ and the dual cone $\Lambda$.
• Key Feature: It constructs a new potential function to handle the non-compactness of the dual variable set $\Lambda$, a major difficulty in analyzing constrained minimax problems.

B. ZO-RMPDPG (Stochastic Setting)

• Algorithm: Zeroth-Order Regularized Momentum Primal-Dual Projected Gradient.
• Mechanism:
  • Designed for the stochastic setting where the objective is an expectation.
  • Incorporates variance reduction techniques (using mini-batches and recursive gradient estimators $v_k, w_k$) to stabilize the stochastic noise.
  • Includes a momentum step to accelerate convergence.
  • Uses a regularization term ($\rho_k \|y\|^2$) that decreases over time to handle the non-strongly concave case.
• Key Feature: It combines variance reduction, momentum, and regularization within a single loop, distinguishing it from existing multi-loop or non-momentum zeroth-order methods.

3. Key Contributions

1. First Zeroth-Order Algorithms with Coupled Constraints: To the authors' knowledge, these are the first zeroth-order algorithms with theoretical iteration complexity guarantees for solving nonconvex-(strongly) concave minimax problems with coupled linear constraints in both deterministic and stochastic settings.
2. Novel Complexity Bounds: The paper establishes rigorous iteration complexity results for finding an $\epsilon$-stationary point:
   • Deterministic Nonconvex-Strongly Concave: $O(\epsilon^{-2})$ for ZO-PDAPG.
   • Deterministic Nonconvex-Concave: $O(\epsilon^{-4})$ for ZO-PDAPG.
   • Stochastic Nonconvex-Strongly Concave: $\tilde{O}(\epsilon^{-3})$ for ZO-RMPDPG.
   • Stochastic Nonconvex-Concave: $\tilde{O}(\epsilon^{-6.5})$ for ZO-RMPDPG.
   • Note: The $\tilde{O}$ notation hides logarithmic factors and condition numbers.
3. State-of-the-Art Performance:
   • When specialized to stochastic nonconvex-concave problems without coupled constraints (i.e., $A=B=c=0$), the ZO-RMPDPG algorithm achieves a complexity of $\tilde{O}(\epsilon^{-6.5})$, which is significantly better than the existing $O(\epsilon^{-8})$ bound of the ZO-GDEGA algorithm.
4. Theoretical Innovation: The authors developed new potential functions and convergence analysis techniques to overcome the challenge of the non-compact dual set $\Lambda$ in the presence of coupled constraints, which previous zeroth-order methods could not handle.

4. Results

Theoretical Results

• Convergence: The algorithms are proven to converge to an $\epsilon$-stationary point (satisfying KKT conditions approximately) within the stated iteration bounds.
• Constraint Satisfaction: The analysis guarantees that at the stopping time, the constraint violation $\max\{0, [Ax+By-c]_i\}$ is also bounded by $\epsilon$.
• Function Queries: The total number of function value queries is proportional to the dimension of the variables ($d_x + d_y$) multiplied by the iteration complexity.

Numerical Experiments

The authors tested the algorithms on two real-world applications:

1. Adversarial Attacks in Network Flow: Simulating an adversary injecting traffic to maximize network congestion costs.
   • Result: ZO-PDAPG achieved a "relative cost increase" comparable to state-of-the-art first-order algorithms (PDAPG, MGD, PGmsAD), demonstrating that zeroth-order methods are effective even without gradient access.
2. Data Poisoning against Logistic Regression: An attacker manipulates the training data to degrade model performance.
   • Result: Both ZO-PDAPG and ZO-RMPDPG achieved stationary gaps and test accuracy comparable to first-order methods, validating their practical efficiency in stochastic, black-box settings.

5. Significance

This work bridges a critical gap in optimization theory and machine learning:

• Black-Box Optimization: It provides a rigorous theoretical foundation for solving complex constrained minimax problems when gradients are inaccessible, a common scenario in security (adversarial attacks) and hyperparameter tuning.
• Handling Constraints: Unlike many existing zeroth-order minimax methods that only handle unconstrained or simple box-constrained problems, this paper tackles coupled linear constraints, which are essential for modeling resource allocation and network flow.
• Efficiency: By achieving better complexity bounds than existing methods (especially in the stochastic nonconvex-concave case), the proposed algorithms set a new state-of-the-art, making them highly relevant for large-scale machine learning applications where computational efficiency is paramount.

In summary, the paper successfully extends zeroth-order optimization to a broader and more challenging class of constrained minimax problems, offering both theoretical guarantees and practical algorithms that perform competitively with first-order methods.