← All setups

Heavy Tailed Ncsc Accelerated — Heavy-Tailed Nonconvex Strongly Concave Optimization

Descriptions may be stale. Consult the linked Lean sources.

Heavy-Tailed Nonconvex Strongly Concave Optimization · Lean proof

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.

Proved result

⌈(280⋅pp−1)pp−1+2⋅(1+log⁡(2+Lμ+1δ+L⋅Δε2+(Lμ⋅σε)pp−1+log⁡(2+(Lμ)3⋅L⋅(Δ+G2μ)ε2)))2⋅pp−1+3⋅(Lμ⋅(1+L⋅Δε2+log⁡(2+(Lμ)3⋅L⋅(Δ+G2μ)ε2))+(L⋅Δε2⋅(Lμ)pp−12+(Lμ)pp−1)⋅(σε)pp−1)⌉+

OracleTemplate.Convergence LongTails.Setups.HeavyTailedNcsc.spec OracleTemplate.HeavyTailedNcscAccelerated.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.