PaperlayerView exact revision on arXiv

Source-linked AI summary

Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods

Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D. Lee, Meisam Razaviyayn

arXiv:1902.08297v3math.OCcs.LGstat.ML

TL;DR

Non-convex min-max games make equilibrium computation difficult, so this paper targets first-order stationary points under conditions enabling one player's objective to be optimized globally. It proposes multi-step gradient descent-ascent methods and obtains near-optimal O(ε^-2 log(ε^-1)) complexity for PL-games and O(ε^-3.5 log(ε^-1)) for non-convex concave games.

  • Problem

    The paper addresses finding first-order equilibria in non-convex min-max games, where even local Nash equilibria are NP-hard to compute and may not exist.

  • Method

    The paper proposes multi-step gradient descent-ascent methods that approximately solve inner maximization problems to obtain descent directions for PL-games and non-convex concave games.

  • Results

    O(ε^-2 log(ε^-1)) overall complexity is achieved for PL-games, while O(ε^-3.5 log(ε^-1)) is achieved for non-convex concave games.

  • Takeaways & Limitations

    The framework extends iterative first-order equilibrium computation beyond convex-concave games under PL or concavity assumptions.

  • Takeaways & Limitations

    The guarantees rely on smoothness assumptions and, depending on the setting, an unconstrained max-player satisfying the PL condition or a concave max-player.

Abstract

from arXiv · show

Recent applications that arise in machine learning have surged significant interest in solving min-max saddle point games. This problem has been extensively studied in the convex-concave regime for which a global equilibrium solution can be computed efficiently. In this paper, we study the problem in the non-convex regime and show that an \varepsilon--first order stationary point of the game can be computed when one of the player's objective can be optimized to global optimality efficiently. In particular, we first consider the case where the objective of one of the players satisfies the Polyak-Łojasiewicz (PL) condition. For such a game, we show that a simple multi-step gradient descent-ascent algorithm finds an \varepsilon--first order stationary point of the problem in \widetilde{\mathcal{O}}(\varepsilon^{-2}) iterations. Then we show that our framework can also be applied to the case where the objective of the "max-player" is concave. In this case, we propose a multi-step gradient descent-ascent algorithm that finds an \varepsilon--first order stationary point of the game in \widetilde{\cal O}(\varepsilon^{-3.5}) iterations, which is the best known rate in the literature. We applied our algorithm to a fair classification problem of Fashion-MNIST dataset and observed that the proposed algorithm results in smoother training and better generalization.

1 Introduction

Min-max saddle-point games underpin many machine-learning and robust-optimization applications, but general non-convex non-concave settings lack reliable practical solution methods. The introduction motivates first-order stationarity as a tractable target by contrasting these challenges with classical convex-concave results and existing partial guarantees.

  • Motivation: Min-max saddle-point formulations arise in GANs, reinforcement learning, adversarial learning, fair statistical inference, and other machine-learning applications.These problems model competing objectives between minimizing and maximizing players.
  • Existing methods: Gradient descent-ascent alternates descent and ascent updates but fails to converge even for simple bilinear zero-sum games.Negative momentum and primal-dual methods were proposed to address this failure.
  • Classical setting: Convex-concave games yield monotone variational inequalities, enabling extensive study of algorithms for finding Nash equilibria.More general algorithms have also covered monotone and pseudomonotone variational problems.
  • Problem setting: Non-convex machine-learning games, including GANs, motivate moving beyond classical settings, while general non-convex non-concave games may lack a local Nash equilibrium.The introduction uses competing neural networks in GANs as a representative non-convex zero-sum formulation.
  • Research gap: Prior methods provide partial first-order stationarity guarantees under strong assumptions, including strongly concave objectives, Max-oracles, or Minty variational inequality solutions.The Minty-based conditions are described as strong and difficult to check, motivating more practical guarantees.

2 Two-player Min-Max Games and First-Order Nash Equilibrium

The section defines Nash and first-order Nash equilibria for two-player min-max games, emphasizing that non-convex non-concave games can make Nash equilibria computationally intractable or nonexistent. It then motivates approximate FNE computation under smoothness assumptions.

  • Nash Equilibrium: In non-convex non-concave games, computing even local Nash equilibria is NP-hard, and local Nash equilibria may not exist.This contrasts with convex-concave games, where Nash equilibria exist and algorithms can find them.
  • First-Order Nash Equilibrium: First-order Nash equilibrium imposes each player’s first-order optimality conditions, reducing without constraints to ∇θf(θ∗, α∗) = 0 and ∇αf(θ∗, α∗) = 0.For constrained sets, the conditions are expressed through directional inequalities over each player’s feasible set.
  • Approximate FNE: First-order Nash equilibrium points exist even when local Nash equilibria may not, motivating the approximate ε-FNE notion for iterative computation.The paper’s stated goal is to compute an ε-FNE using iterative methods.
  • Approximate FNE: Without constraints, ε-FNE requires both players’ gradient norms to be at most ε.Specifically, ∥∇θf(θ∗, α∗)∥ ≤ ε and ∥∇αf(θ∗, α∗)∥ ≤ ε.
  • Smoothness Assumptions: The analysis assumes continuous differentiability and Lipschitz gradient bounds with constants L11, L22, and L12 across players’ variables.These bounds control within-player and cross-player gradient variation.

3 Non-Convex PL-Game

This section defines non-convex PL-games and presents a multi-step gradient descent-ascent method for finding ε-FNEs. Under the stated assumptions, the method achieves near-optimal iteration complexity while approximating the inner maximization gradient despite possible non-unique optima.

  • 3 Non-Convex PL-Game: PL-games allow the max-player objective transformation h_θ(α) = −f(θ, α) to satisfy the PL condition even when the game is non-convex.The max player is unconstrained, and the PL condition is imposed for every θ.
  • Algorithm: The algorithm performs multiple projected gradient ascent steps on α, then uses the approximate inner solution to descend on θ through the value-function gradient.This approach addresses the possibility that the inner maximization has multiple optimal solutions, so Danskin’s theorem does not directly apply.
  • Main result: O(ε−2) θ-gradient evaluations and O(ε−2 log(ε−1)) α-gradient evaluations suffice to find an ε-FNE under the section’s assumptions.When both gradient oracles have the same complexity, the overall complexity is O(ε−2 log(ε−1)).
  • Main result: The iteration complexity order O(ε−2 log(ε−1)) is tight up to logarithmic factors for general non-convex optimization.The section also presents generative adversarial imitation learning of linear quadratic regulators as a practical PL-game example.
  • Main result: The computed pair (θ_t, α_K(θ_t)) is an ε-FNE, while θ_t is concurrently an ε-first order stationary solution of the inner maximization value problem.The inner variable α_K(θ_t) is only an approximate solution of the maximization problem.

4 Non-Convex Concave Games

Section 4 studies non-convex concave games, where concavity and compactness in the max-player variable enable regularization-based optimization despite a potentially non-differentiable value function. The resulting multi-step framework converges to an ε-first-order stationary solution with overall complexity O(ε^-3.5 log(ε^-1)) when the two gradient oracles have equal complexity.

  • Assumptions: The game assumes f(θ, α) is concave in α, with a convex compact feasible set A contained in a radius-R ball.These conditions constitute Assumption 4.1.
  • Challenge: Concavity in α does not ensure differentiability of g(θ) = max_{α∈A} f(θ, α), as the example g(θ) = |θ| shows.This non-smoothness distinguishes the setting from PL-games.
  • Regularization: A small quadratic regularization makes f_λ strongly concave in α and g_λ smooth with Lipschitz gradient, enabling gradient estimation through approximate maximization.The method uses multiple Nesterov accelerated projected gradient ascent steps to estimate the maximizer and a descent direction for θ.
  • Algorithm 2: Algorithm 2 alternates K accelerated projected gradient ascent steps for α, periodically restarted every N iterations, with a Frank-Wolfe or projected-gradient update for θ.The approximate maximizer αt+1 supplies first-order information for updating θ.
  • Convergence: O(ε^-3) gradient evaluations with respect to θ and O(ε^-0.5 log(ε^-1)) with respect to α yield an ε-first-order stationary solution.When both oracles have the same complexity, the overall complexity is O(ε^-3.5 log(ε^-1)).

5 Numerical Results

The section evaluates Algorithm 2 through two Fashion-MNIST experiments, including a non-convex CNN classification setting motivated by bias across clothing categories.

  • Algorithm 2 is evaluated in two applications.
  • Experimental Setup: The Fashion-MNIST dataset contains 60,000 training images and 10,000 testing images of 28 × 28 grayscale clothing images across 10 categories.
  • Experimental Setup: The experiments replace logistic regression with a more complex non-convex CNN to address classification bias across selected clothing categories.

W max {L1(W), L2(W), L3(W)}, (12) · A Proofs for results in Section 3 · A.1 Danskin-type Lemma for PL Functions

The paper applies its non-convex min-max framework to category-balanced Fashion-MNIST training and robust neural-network training, while proving the PL-based lemmas underpinning its Section 3 results. The experiments show balanced category accuracies and competitive adversarial robustness, and the appendix establishes stability and gradient identities for PL inner problems.

  • W max {L1(W), L2(W), L3(W), (12): W represents CNN parameters, while L1, L2, and L3 are losses for T-shirt/top, Coat, and Shirt samples in the max objective.The formulation maximizes among the three category-specific losses.
  • W max {L1(W), L2(W), L3(W), (12): The inner maximization is concave, enabling the theory to be applied to the category-based objective.The authors implement regularized and unregularized versions of Algorithm 2.
  • W max {L1(W), L2(W), L3(W), (12): The inner variable t can be optimized using KKT conditions with sorting or bisection, followed by a gradient descent step on W.The optimization with respect to t is described as an almost closed-form update.
  • W max {L1(W), L2(W), L3(W), (12): 5500 epochs compare regularized MinMax, unregularized MinMax, and gradient descent on the average category loss using test accuracy across categories.The comparison evaluates whether regularization sacrifices empirical performance.
  • W max {L1(W), L2(W), L3(W), (12): Across 50 runs, MinMax and regularized MinMax produce more balanced category accuracies than normal training, with regularization yielding a slightly better worst-case result.Each run evaluates 1000 testing samples per category.
  • 5.2 Robust Neural Network Training: For robust training, the paper replaces the difficult non-convex non-concave problem with a concave probability-simplex inner problem, enabling multi-step gradient descent-ascent.The resulting formulation has comparable performance to [38] [57] under FGSM and PGD, sometimes exceeding them by ≈15% accuracy.
  • A Proofs for results in Section 3: A PL function with constant µ satisfies quadratic growth with constant γ = 4µ, and PL inner objectives provide stability of the arg max with respect to the outer variable.These lemmas are introduced as prerequisites for proving the main results in Section 3.
  • A.1 Danskin-type Lemma for PL Functions: The PL Danskin-type lemma shows that ∇g(θ) = ∇θf(θ, α∗) for any maximizing α∗, so the outer gradient is independent of the maximizing solution chosen.The result follows by analyzing directional derivatives and the stability lemma.

A.2 Proof of Theorem 3.4 … B.3 Smoothness of function gλ(·)

The appendices establish that the inner loop approximates the gradient of the outer objective closely enough for Algorithm 1 to reach an ε-first-order stationary point. They also detail accelerated ascent and Frank–Wolfe alternatives, and prove smoothness of the regularized value function gλ.

  • A.2 Proof of Theorem 3.4: Algorithm 1’s inner loop computes an approximate gradient, so its updates behave similarly to vanilla gradient descent on the outer problem.The approximation is expressed as ∇θf(θt, αt+1) ≈ ∇g(θt).
  • A.2 Proof of Theorem 3.4: ε and ∥∇αf(θbt, αbt+1)∥ ≤ ε hold for at least one index bt, completing the theorem’s stationarity guarantee.The result also states Xbt ≤ ε.
  • B.1 Accelerated Projected Gradient Ascent Subroutine Used in Algorithm 2: Algorithm 3 implements accelerated projected gradient ascent with restart using constants αt, θt, η, K, and N, returning xN.The routine performs nested loops over restarted blocks and N inner iterations.
  • B.2 Frank–Wolfe update rule for Step 3 in Algorithm 2: Step 3 of Algorithm 2 can use one Frank–Wolfe step, whose direction is bst = −∇θfλ(θt, αt+1) in the unconstrained case.In that case, the Frank–Wolfe direction coincides with the gradient descent step.
  • B.3 Smoothness of function gλ(·): gλ is L-Lipschitz smooth under Assumptions 2.5 and 4.1, with differentiability following directly from Danskin’s Theorem.The proof derives smoothness using the regularized inner maximization and Lipschitzness assumptions.
  • B.3 Smoothness of function gλ(·): Algorithm 2 solves its inner maximization with accelerated projected gradient descent applied to strongly convex functions, using step-size 1/L and restart parameter N.Lemma B.2 assumes λ-strong convexity and L-smoothness and establishes the corresponding accelerated projected-gradient guarantee.

B.4 Proof of Theorem 4.2

The proof shows that Algorithm 2’s inner loop produces an approximate gradient for the smoothed objective g_λ, enabling the outer method to find an ε-first-order stationary solution. It establishes this result for both Frank-Wolfe and projected-gradient-descent updates under the theorem’s assumptions.

  • Approximate-gradient guarantee: The inner loop computes an approximate gradient, with ∇_θf_λ(θ_t, α_{t+1}) approximating ∇g_λ(θ_t).The proof bounds the error between the gradient evaluated at the inner-loop iterate and the gradient of the smoothed objective.
  • Approximate-gradient guarantee: Compactness of Θ provides a uniform bound Δ such that g(θ_t) − f(θ_t, α_0(θ_t)) ≤ Δ for every iteration.The argument uses the bound on differences between consecutive inner-loop optimal solutions and compactness of Θ.
  • Theorem conclusion: The theorem’s outer updates use the approximate gradient for sufficiently small λ and yield an ε-first-order stationary solution of problem (2).The proof explicitly connects the approximate-gradient implementation to an ε-FNE through Frank-Wolfe or projected descent applied to g_λ.
  • Frank-Wolfe steps: The Frank-Wolfe proof sums descent inequalities over iterations and uses Lemma B.3 to identify an iterate satisfying the required stationarity bound.The argument relies on the descent lemma, bounded update directions, Cauchy-Schwarz, and the selected λ and K.
  • Projected gradient descent: The projected-gradient-descent proof applies projection properties and Taylor expansion, then uses Lemma B.3 and choices of K and T to identify a stationary iterate.The final stationarity argument also uses the theorem’s λ choice and the assumption ∥α^K(θ_{t}) − ᾱ∥ ≤ 2R.

C Numerical Results on Fashion MNIST with SGD

This section summarizes Fashion-MNIST results using mini-batch SGD, including experiments with batch-size = 3000 and batch-size = 600 because SGD requires more tuning.

  • SGD Results: The SGD results are summarized in Table 4 and Table 5.The experiments use the mini-batch SGD optimizer.
  • SGD Results: SGD requires more tuning than the reported baseline setup, motivating inclusion of batch-size = 3000 results.The passage explicitly attributes the additional batch-size experiment to SGD's tuning requirements.
  • SGD Results: Table 4 reports mini-batch SGD results with λ = 0.05 and batch-size = 3000.The table reports the mean and standard deviation of correctly classified samples.
  • SGD Results: Table 5 reports mini-batch SGD results with λ = 0.0005 and batch-size = 600.The table reports the mean and standard deviation of correctly classified samples.

D Numerical Results on Fashion MNIST with Logistic Rgression Model

Table 6 evaluates the proposed formulation with gradient-descent training on the Fashion-MNIST logistic regression model. It reports improved accuracy for Shirts and more balanced accuracies across three categories, while noting early termination affects the standard derivations.

  • Results: The proposed formulation improves accuracy in the worst category, Shirts, while producing more balanced accuracies across three categories.Table 6 reports results for a model trained by gradient descent.
  • Results: The standard derivations not equal to 0 are attributed to early termination of the simulation.This qualification accompanies the gradient-descent results.
  • Results: λ = 0.1 is the training setting reported for Table 6’s mean and standard deviation of correctly classified samples.The table summarizes gradient-descent training results.

E Numerical Results on Robust Neural Network Training

The paper reformulates robust neural-network training as a non-convex, concave-inner min-max problem solvable by Algorithm 2, demonstrating the practicality of this approach despite theory–experiment mismatches. The MNIST experiment evaluates test accuracy under FGSM and PGD attacks.

  • Robust objective reformulation: The robust-training objective is approximated by a finite maximum over targeted adversarial examples, then replaced with a probability-simplex optimization that is non-convex in w but concave in t.This reformulation enables application of Algorithm 2 to the resulting optimization problem.
  • Adversarial-example construction: Targeted adversarial examples are generated separately for each of the 10 classification labels using projected gradient ascent within an infinity ball.The procedure starts from the original sample and uses the corresponding network logit, step-size α, and projection operator.
  • MNIST experiment: The reformulated problem is tested on MNIST using a convolutional neural network, with results reported as test accuracies under FGSM and PGD attacks.Training uses K = 10, PGD generation uses step-size 0.01, and adversarial images are quantized to 256 levels.
  • Theory–experiment mismatch: The numerical experiment does not satisfy the theory’s smoothness assumption because ReLU activations and the projection operator make the objective non-smooth.The experiment also omits the strongly concave regularizer because its optimal value was very small and almost zero.
  • Practical implication: The experiment’s main takeaway is that challenging non-convex min-max problems may be approximated by one-sided problems solvable in one player’s variable, yielding computational tractability and possibly no performance loss.This conclusion is presented as evidence for the practicality of the paper’s reformulation idea.

F Experimental Setup of Fair Classifier

This section specifies the Fashion-MNIST model architecture and reports training parameters for gradient descent, Adam, and SGD.

  • Model Architecture: The Fashion-MNIST experimental setup includes a defined model architecture.The architecture is documented in Table 9.
  • Training Parameters: Training parameters are provided for gradient descent on Fashion-MNIST.These settings are documented in Table 10.
  • Training Parameters: Training parameters are provided separately for Adam on Fashion-MNIST.These settings are documented in Table 11.
  • Training Parameters: Training parameters are provided separately for SGD on Fashion-MNIST.These settings are documented in Table 12.
Loading 1902.08297v3…