---
kind: concept
slug: heavy-tailed-noise
title: Heavy-tailed noise
summary: >-
  Stochastic gradient noise with only a finite p-th moment for some p in (1, 2], not finite variance, so rare very large samples are possible. Analyses that assume bounded variance do not carry over; one card gives a clipped, normalized bilevel method with complexity bounds, and no numeric recipe.
tags: [optimization, heavy-tailed-noise]
papers: ["2509.14952"]
related: [gradient-clipping, bilevel-optimization]
status: draft
updated_at: 2026-10-24
---

## 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) [arxiv: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 [arxiv: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](/concepts/gradient-clipping),
and by taking normalized (direction-only) steps in the outer loop
[arxiv: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 [arxiv:2509.14952 §3.1] [alg. 1]. Card:
[Stochastic Bilevel Optimization with Heavy-Tailed Noise](/papers/2509.14952).

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 [arxiv: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 [arxiv: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 [arxiv: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] [arxiv: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 [arxiv:2509.14952 tab. 2].

## When to use which

| Situation | Use | Why |
|---|---|---|
| Noise has finite variance (p = 2), bilevel problem | N2SBA, or the bounded-variance methods it is compared against | The authors report N2SBA matching the best bounded-variance bound [arxiv:2509.14952 tab. 1] |
| Noise may have infinite variance, only a p-th moment with p in (1, 2] | N2SBA | The only listed bound for this noise model; the paper lists no baseline for p < 2 [arxiv:2509.14952 tab. 1] |
| Minimax problem, nonconvex in x and strongly concave in y, heavy-tailed noise | N2SGDA | Stated bound for p in (1, 2] [arxiv:2509.14952 §4] |
| Lower level not strongly convex, or not smooth | Not covered | The analysis assumes a strongly convex lower level [arxiv:2509.14952 §1] |
| Need numeric step sizes, clip levels or lambda | Not covered | Theorems give orders only, with constants hidden [arxiv:2509.14952 §3.2] [§4] |
| Need evidence of practical speed | Weak evidence | Experiments are plots of SFO calls against a metric, with no reported final values [arxiv:2509.14952 §5] |

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
[arxiv: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.

```pseudocode
# 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
[arxiv: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](/papers/2509.14952):
  N2SBA for bilevel problems and N2SGDA for minimax problems under p-th-moment
  noise, with complexity bounds and small experiments.