Minimax optimization

Overview

A minimax problem has an outer variable that is minimized and an inner variable that is maximized. The inner maximization is the hard part: an approximate inner solve is what the outer step sees, so how accurate that solve is matters. Two cards cover this slug with different settings.

In the stochastic setting, the outer variable x is minimized and the inner variable y is maximized. The paper's minimax setting is nonconvex in x and strongly concave in y, and its stationarity measure is the gradient norm of an outer function Phi(x) 2509.14952 §4 fig. 1. The paper treats minimax as a special case of its bilevel method: with the lower-level objective negated and the penalty set to zero, the nested solve reduces to a single inner ascent loop and a normalized outer step 2509.14952 §4 alg. 2. The stochastic gradients are assumed to have heavy-tailed noise, with a finite p-th central moment for p in (1, 2] 2509.14952 §2.

In adversarial training, the inner maximization searches for a perturbed input inside an epsilon-ball that maximizes the loss, and the outer minimization fits the model parameters on those inputs 2112.08304 eq. 1 §1. The assumptions are local: the inner problem is assumed to be locally strongly concave inside the ball, and the outer analysis assumes bounded gradient variance 2112.08304 §4.2.

Variants

Normalized gradient descent-ascent with clipped inner ascent (N2SGDA)

Each outer step runs K clipped stochastic ascent steps on y, which carry over to the next outer step. The outer variable then takes one step of fixed length in the direction of a mini-batch x-gradient at the current y 2509.14952 alg. 2. The stated SFO complexity is tilde-O(kappa^3 sigma^2 eps^-4) at p = 2, and tilde-O(kappa^((2p-1)/(p-1)) sigma^(p/(p-1)) eps^(-(3p-2)/(p-1))) for p in (1, 2] 2509.14952 tab. 2 2509.14952 §4. Card: Stochastic Bilevel Optimization with Heavy-Tailed Noise, the minimax part of the paper.

Adversarial min-max with a stationarity-controlled inner attack (dynamic adversarial training)

The outer step is ordinary SGD on adversarial examples; the variant changes only how the inner maximization is stopped. The paper defines FOSC, a first-order stationarity score for an inner point, as the maximum over the epsilon-ball of the inner product of the displacement with the input gradient 2112.08304 eq. 4 §3.1. It has a closed form in terms of the L1 norm of the gradient and the displacement from the start point §3.1. Each PGD example is attacked only while its FOSC is above a threshold, and the threshold falls linearly over training to zero at epoch T′ 2112.08304 §4.1 alg. 1. Author-reported white-box PGD-10 accuracy on CIFAR-10 with an 8-layer CNN is 48.06% for this variant against 44.39% for standard PGD training 2112.08304 tab. 1. Card: On the Convergence and Robustness of Adversarial Training.

When to use which

Implementation sketch

The sketch below restates the outer loop of N2SGDA in pseudocode. The paper's bilevel method adds penalty-weighted inner loops for the lower-level problem, covered on bilevel-optimization. A second sketch shows the FOSC-controlled inner attack of the adversarial variant.

# clip(v, c): rescale v so its norm is at most c  [arxiv:2509.14952 §3]
def clip(vector, level):
    size = norm(vector)
    if size == 0:
        return zeros_like(vector)
    return min(1.0, level / size) * vector

# One outer step of N2SGDA  [arxiv:2509.14952 alg. 2]
def n2sgda_outer_step(x, y, eta_x, eta_y, clip_levels, K, M):
    # K clipped stochastic ascent steps on y  [alg. 2, l. 675-677]
    for k in range(K):
        grad_y = grad_y_F(x, y, sample_f())
        y = y + eta_y * clip(grad_y, clip_levels[k])
    # Mini-batch x-gradient at (x, y), averaged over M samples  [alg. 2, l. 680-681]
    grad_x = average([grad_x_F(x, y, sample_f()) for _ in range(M)])
    # Normalized descent: fixed length, direction only  [alg. 2, l. 682]
    # The caller must guard against norm(grad_x) == 0.
    x = x - eta_x * grad_x / norm(grad_x)
    return x, y

# FOSC-controlled inner attack  [arxiv:2112.08304 alg. 1] [§3.1] [§4.1]
# Stop attacking an example once its FOSC is at or below the threshold c_t.
def fosc_controlled_pgd(model, x0, y_label, c_t, eps, alpha, K):
    x = x0
    active = ones_like(y_label)           # 1 = still being attacked
    for _ in range(K):
        grad = input_gradient(model, x, y_label)
        x = x + active * alpha * sign(grad)
        x = clip(x, x0 - eps, x0 + eps)   # project onto the eps-ball
        # FOSC closed form: eps * L1(grad) - <x - x0, grad>  [§3.1]
        fosc = eps * l1(grad) - inner(x - x0, grad)
        active = fosc > c_t
        if not any(active):
            break
    return x

Contradictions

Within the adversarial card, the printed indicator in alg. 1 reads the opposite way to its own comment: the formula marks an example as active where FOSC is at most c_t, but the comment says the element becomes zero where FOSC is smaller than c_t 2112.08304 alg. 1. The paper's text on the FOSC threshold §4.1 matches the comment, so the sketch above follows the text and the comment. An implementation that copies the printed formula would attack the wrong examples.

Within the stochastic card, the expectation and high-probability theorems for minimax use different step sizes and constants for the inner loop and the initial distance R_y 2509.14952 §4 thm. 4.1, 4.2. They give different guarantees, so pick the one that matches the guarantee you need.

The two cards solve different problems (stochastic heavy-tailed gradients and adversarial training with a locally strongly concave inner problem). Their reported numbers are not comparable, and neither card reports results on the other's setting.

Papers

• On the Convergence and Robustness of Adversarial Training: FOSC-controlled inner attack and dynamic threshold schedule for adversarial min-max training (§3 to §4).
• Stochastic Bilevel Optimization with Heavy-Tailed Noise: N2SGDA for minimax problems (§4), alongside the bilevel method N2SBA.