← All setups

Heavy-Tailed Nonconvex Strongly Concave Optimization

Descriptions may be stale. Consult the linked Lean sources.

Heavy-Tailed Nonconvex Strongly Concave Optimization

We consider infx∈Emaxy∈Ff(x,y) on finite-dimensional real inner product spaces E and F. The differentiable objective f:E×F→R has an L-Lipschitz joint gradient and is μ-strongly concave in y, with L≥μ>0, while it may be nonconvex in x. Given initial points, an initial value-gap bound, and an initial dual-gradient bound, the oracle returns unbiased gradient pairs from independent, identically distributed samples with bounded centered pth moment, 1<p≤2. The goal is a measurable output x¯ with ∥∇Φ(x¯)∥≤ε with probability at least 1−δ, where Φ(x)=maxyf(x,y), ε>0, and 0<δ<1/2.

Write the objective and optimization problem as Φ(x)=maxy∈Ff(x,y),infx∈EΦ(x). Equip E×F with the product norm ∥(u,v)∥=(∥u∥2+∥v∥2)1/2. The given points are x0∈E and y0∈F. The parameters satisfy 0<μ≤L,1<p≤2,σ,Δ,G≥0,ε>0,0<δ<12. The algorithm receives E,F, the measurable sample space Ω, all these parameters, and x0,y0; the objective and sampling law are accessed through the oracle.

Our assumptions:

Assumption 1 (Smoothness and strong concavity). Both partial gradients of f exist everywhere. For all z,z′∈E×F, ∥∇xf(z)−∇xf(z′)∥2+∥∇yf(z)−∇yf(z′)∥2≤L2∥z−z′∥2. For every x∈E and y,y′∈F, f(x,y′)≤f(x,y)+⟨∇yf(x,y),y′−y⟩−μ2∥y′−y∥2.

Assumption 2 (Initial bounds). For every x∈E and y∈F, there exists y′∈F such that f(x0,y)−f(x,y′)≤Δ. The initial dual gradient satisfies ∥∇yf(x0,y0)∥≤G.

Assumption 3 (Heavy-tailed stochastic gradients). Let ν be a probability measure on Ω. The oracle maps gx:(E×F)×Ω→E,gy:(E×F)×Ω→F are jointly measurable. At each fixed z∈E×F, both maps are Bochner integrable under ν and satisfy Eξ∼ν[gx(z,ξ)]=∇xf(z),Eξ∼ν[gy(z,ξ)]=∇yf(z). Define the paired error by e(z,ξ)=(gx(z,ξ)−∇xf(z),gy(z,ξ)−∇yf(z)). For every z, the random variable ∥e(z,ξ)∥p is integrable and Eξ∼ν[∥e(z,ξ)∥p]≤σp. The samples (ξk)k≥0 are measurable, mutually independent, and each has law ν under their joint law. At query zk∈E×F, call k returns the pair (gx(zk,ξk),gy(zk,ξk)), using the same sample for both components. Algorithm randomness is independent of the sample sequence.

Queries may be made anywhere in E×F. The output requirement includes the existence of a maximizing selection y⋆:E→F satisfying f(x,y)≤f(x,y⋆(x))for every x∈E, y∈F. For every such selection, the measurable output x¯∈E must satisfy P(‖∇[x↦f(x,y⋆(x))](x¯)‖>ε)≤δ, where P is the joint law of the samples and the independent algorithm randomness. Since every maximizing selection represents Φ, this is the high-probability stationarity requirement for the value function.

Results

Finite-dimensional real inner-product spaces; jointly L-Lipschitz gradient, μ-strong concavity in y, 0<μ≤L. Write Φ(x)=maxyf(x,y), with Φ(x0)−infΦ≤Δ and ∥∇yf(x0,y0)∥≤G. Jointly measurable IID unbiased joint-gradient oracle with central pth moment at most σp, 1<p≤2. Target: Pr(∥∇Φ(X)∥>ε)≤δ, ε>0, 0<δ<1/2.

Heavy-tailed NC–SC minimax optimization: HeavyTailedNcsc.
Result Oracle complexity Novelty Limitations
(1) HeavyTailedNcscAccelerated (Ours) (⋆⋆⋆) (review) O(Cpℓ2r+3[κ(1+A+Q)
+(Aκr/2+κr)(σ/ε)r]) joint-gradient calls.
(2) N2SGDA (Liu and Luo 2026), Thm. 4.2 O(logc⁡(⋅)[Aκ2+Aκr+1(σ/ε)r]) calls; logarithms suppressed, exponent unspecified. High-probability trajectory-average gradient norm. (1): noise coefficient κr+1→κr/2; deterministic κ2→κ. Extra noise term absorbed when A≥1/κ, up to logs. Certifies a selected point. (1): IID required; adds κQ, explicit ℓ2r+3 and enormous p-dependent prefactor.
(3) Stoc-TRGDAmax (Zhu et al. 2026), Thm. 4.3, (4.9); unregularized restriction O(Aκ1+r/2+Aκr+1(σ/ε)r) calls for expected random-iterate norm ≤ε, provided ε≥2L∥y0−y∗(x0)∥. (1): noise coefficient improves by κ1+r/2, deterministic by κ(r+1)/2, up to logs and initialization, when A≥1/κ. No compact-sublevel assumption; logarithmic confidence versus Markov conversion. (1): no composite regularizers or expected-norm guarantee; IID required. Markov conversion of (3) costs δ−(r+2) in its noise term, within its initialization regime.
(4) (Wu et al. 2026), Thm. 3.4; p=2 O(Λ10[κA+(Aκ+κ2)(σ/ε)2+κlog⁡(2+κ2G2/ε2+κ2A)]) calls; success 2/3. (1): extends to p<2, allowing infinite variance; tunable confidence. Matches polynomial rate at p=2. (1): IID instead of adaptive conditionally unbiased kernels; Cp and log exponent diverge as p↓1.

Abbr: κ=L/μ, r=p/(p−1), A=LΔ/ε2, Q=log⁡(2+κ3L(Δ+G2/μ)/ε2), ℓ=1+log⁡(2+κ+δ−1+A+(κσ/ε)r+Q), Cp=(280r)r+2; Λ=1+log⁡(2+κ)+log⁡(2+A)+log⁡(2+κ2σ2/ε2). logc⁡(⋅) denotes the suppressed polylogarithmic factors in (2).

Liu, Zhuanghua, and Luo Luo. 2026. Stochastic Bilevel Optimization with Heavy-Tailed Noise. https://doi.org/10.48550/arXiv.2509.14952.
Wu, Wendao, Haihan Zhang, Chenheng Zhang, et al. 2026. Sharp Fresh-Gradient Complexity of Nonconvex–Strongly-Concave Minimax Optimization. https://doi.org/10.48550/arXiv.2610.00229.
Zhu, Tianxi, Yi Xu, and Xiangyang Ji. 2026. The Role of Gradient Modification in Heavy-Tailed Nonconvex Stochastic Min-Max Optimization. https://doi.org/10.48550/arXiv.2609.06064.

Lean setup