Heavy-tailed noise

Overview

Heavy-tailed noise is a gradient noise model in which the variance may be infinite. The paper assumes instead that the noise has a finite p-th central moment for some p in (1, 2] (the p-BCM assumption) 2509.14952 §2. At p = 2 this reduces to the usual bounded-variance case. For p below 2, the authors argue that standard SGD-based analyses, which need bounded variance, do not apply 2509.14952 §3.1.

The practical consequence is that occasional samples can produce gradients far larger than typical ones. The only card so far handles this by capping the norm of inner-loop gradients, which is gradient-clipping, and by taking normalized (direction-only) steps in the outer loop 2509.14952 §3.1 alg. 1.

Variants

N2SBA, nested bilevel method

Targets smooth bilevel problems with a strongly convex lower level. Inner subproblems use clipped SGD with warm starts. The outer update normalizes the gradient estimate of a penalized surrogate, so each outer step has the same length 2509.14952 §3.1 alg. 1. Card: Stochastic Bilevel Optimization with Heavy-Tailed Noise.

Its stated SFO complexity for an approximate stationary point is tilde-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. At p = 2 this is tilde-O(kappa^11 sigma^2 eps^-6), which the authors state matches the best bounded-variance bound for this setting 2509.14952 tab. 1.

N2SGDA, nested minimax method

The same scheme with the lower level removed (G = -F and lambda = 0). It runs clipped gradient ascent on y and a normalized step on x for nonconvex-strongly-concave minimax problems 2509.14952 §4 alg. 2.

Its stated complexity is tilde-O(kappa^((2p-1)/(p-1)) sigma^(p/(p-1)) eps^(-(3p-2)/(p-1))) for p in (1, 2] 2509.14952 §4. At p = 2 the paper reports tilde-O(kappa^3 sigma^2 eps^-4), the same as the SGDmax and SGDA baselines it compares against 2509.14952 tab. 2.

When to use which

The paper's lower bound for quadratic lower levels has a different kappa exponent from the upper bound, so the complexity in the gap is open 2509.14952 §3.3.

Implementation sketch

Core of N2SBA alg. 1: a clipped stochastic step for the inner variables and a normalized step for the outer variable.

# Cap a stochastic gradient's norm before the step  [alg. 1] [§3]
def clip(vector, level):
    size = norm(vector)
    if size == 0:
        return zeros_like(vector)
    return min(1.0, level / size) * vector

# Inner step: clipped SGD on a strongly convex subproblem  [alg. 1]
def inner_step(param, grad, step, level):
    return param - step * clip(grad, level)

# Outer step: use only the direction of the averaged gradient  [alg. 1]
def outer_step(x, grad_x, step):
    # The algorithm leaves grad_x = 0 undefined; guard it in code  [§3.1]
    if norm(grad_x) == 0:
        return x
    return x - step * grad_x / norm(grad_x)

The clip levels decay in the inner index k and differ between the y and z loops 2509.14952 alg. 1 §3.2. The paper gives only their order, tilde-Theta(exp(-eta lambda mu k) R / eta), so they are not set here.

Contradictions

None known. Only one card covers this slug.

Papers

• Stochastic Bilevel Optimization with Heavy-Tailed Noise: N2SBA for bilevel problems and N2SGDA for minimax problems under p-th-moment noise, with complexity bounds and small experiments.