Bilevel optimization

Overview

A bilevel problem minimizes an outer objective phi(x) = f(x, y*(x)), where y*(x) is the minimizer of an inner objective g(x, .) 2509.14952 §1. The outer variable might be a regularization strength or a per-source data weight, and every outer candidate needs an inner solve. Only stochastic gradients of f and g are available 2509.14952 eq. 2.

The shared core is a penalized surrogate. For a penalty lambda > 0, the surrogate is the minimum over y of f(x, y) + lambda (g(x, y) - min_z g(x, z)) 2509.14952 §3.1. Its gradient needs first-order information at two inner points, y*_lambda(x) and y*(x), so the method does not need Hessian-vector products 2509.14952 §3.1.

Variants

Heavy-tailed-noise nested loop (N2SBA)

Inner clipped SGD on two strongly convex subproblems, then a normalized outer step that uses only the direction of the outer gradient estimate 2509.14952 §3.1 alg. 1. Its noise assumption is a finite p-th central moment with p in (1, 2], instead of finite variance 2509.14952 §2. Card: Stochastic Bilevel Optimization with Heavy-Tailed Noise.

Its stated SFO complexity to reach an approximate stationary point is O~(kappa^((7p-3)/(p-1)) sigma^(p/(p-1)) eps^(-(4p-2)/(p-1))), in expectation and with high probability 2509.14952 §3.2 tab. 1. Here kappa is the condition number and sigma the noise scale. At p = 2 this becomes O~(kappa^11 sigma^2 eps^-6) 2509.14952 tab. 1.

Bounded-variance case (p = 2)

The same method at p = 2 matches the bound the authors give for F2BSA (Chen et al. 2025), after the authors' tightening from kappa^12 to kappa^11 2509.14952 tab. 1 2509.14952 app. E. F2BSA is named here only; its content is not used. The authors state that their bounds match the best known results in the bounded-variance case 2509.14952 §3.2.

Minimax special case (N2SGDA)

Setting G = -F and lambda = 0 turns the method into nested gradient descent ascent: clipped ascent on y, normalized descent on x 2509.14952 §4 alg. 2. Its stated complexity is O~(kappa^((2p-1)/(p-1)) sigma^(p/(p-1)) eps^(-(3p-2)/(p-1))) for p in (1, 2] 2509.14952 tab. 2 §4. At p = 2 it gives O~(kappa^3 sigma^2 eps^-4), the same order as the SGDmax and SGDA bounds the authors cite 2509.14952 tab. 2.

When to use which

Practical limits: the bounds are given up to hidden constants, so the step sizes, clip levels, lambda, K and M must be chosen by the implementer 2509.14952 tab. 1. The inner steps shrink as lambda grows and lambda grows as eps shrinks 2509.14952 §3.2. The paper's experiments are small and reported only as plots 2509.14952 §5.

Implementation sketch

Outer loop with normalized steps, inner loops with clipped steps and a warm start. Condensed from 2509.14952 alg. 1; the sample-draw details are omitted.

# clip(g, tau): rescale g so its norm is at most tau  [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

# Outer loop with inner warm starts  [arxiv:2509.14952 alg. 1]
def n2sba(x, y, lam, eta_x, eta_y, eta_z, clip_y, clip_z, T, K, M):
    z = y
    iterates = []
    for t in range(T):
        # Inner loops: clipped SGD on f + lam*g (for y) and lam*g (for z)
        # [arxiv:2509.14952 §3.1] [eq. 4]
        for k in range(K):
            grad_y = grad_y_F(x, y, sample_f()) + lam * grad_y_G(x, y, sample_g())
            y = y - eta_y[t] * clip(grad_y, clip_y[t][k])
            grad_z = lam * grad_y_G(x, z, sample_g())
            z = z - eta_z[t] * clip(grad_z, clip_z[t][k])
        # Mini-batch estimate of the penalized outer gradient
        # [arxiv:2509.14952 §3.1]
        grad_x = mean_over_batch(M, x, y, z)
        # Normalized outer step: only the direction is used
        # [arxiv:2509.14952 alg. 1]
        x = x - eta_x * grad_x / norm(grad_x)
        iterates.append(x)
    return uniform_choice(iterates)

Guard the division by norm(grad_x) when the gradient is zero, since the algorithm leaves that case undefined 2509.14952 §3.1.

Contradictions

None known. Only one card covers this concept. The paper leaves an open gap between its upper bound's kappa exponent and its lower bound's 2509.14952 §3.3.

Papers

• Stochastic Bilevel Optimization with Heavy-Tailed Noise: N2SBA for bilevel problems with heavy-tailed gradient noise and its minimax variant N2SGDA, with complexity bounds and a lower bound for quadratic lower levels.