← All setups

Sublevel PLRobust Batched Gd — Sublevel Gradient Domination with Stochastic Gradients

Descriptions may be stale. Consult the linked Lean sources.

Sublevel Gradient Domination with Stochastic Gradients · Lean proof

Sublevel Gradient Domination with Stochastic Gradients

We consider minimizing a possibly nonconvex differentiable function f:E→R on a finite-dimensional real inner product space E. Its gradient is L-Lipschitz, with L>0, and f⋆=infx∈Ef(x) is finite. Given x0∈E, assume f(x)−f⋆≤τ∥∇f(x)∥α whenever f(x)≤f(x0), where τ>0 and 1≤α<2. The oracle returns an unbiased stochastic gradient with variance at most σ2, where σ≥0, using independent, identically distributed samples. For ε>0, the goal is an output x¯∈E with integrable objective gap and EP[f(x¯)−f⋆]≤ε, where P is the joint law of algorithm and oracle randomness.

The optimization problem is infx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E. The algorithm receives E, L, τ, α, σ, an initial-gap bound Δ≥0, the tolerance ε, and the given point x0.

Our assumptions:

Assumption 1 (Smoothness). The function f is Fréchet differentiable everywhere on E, and ∥∇f(x)−∇f(y)∥≤L∥x−y∥,x,y∈E.

Assumption 2 (Sublevel gradient domination). The function f is bounded below, and its initial sublevel set satisfies f(x)−f⋆≤τ∥∇f(x)∥αwhenever f(x)≤f(x0),f(x0)−f⋆≤Δ.

Assumption 3 (Unbiased gradients with bounded variance). Let Ω be a measurable sample space and ν a probability measure on Ω. There is a jointly measurable map g:E×Ω→E such that, for every fixed x∈E, g(x,⋅) is Bochner integrable and ∥g(x,⋅)−∇f(x)∥2 is integrable under ν, with Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[∥g(x,ξ)−∇f(x)∥2]≤σ2. The samples (ξk)k≥0 have a joint probability law Q on ΩN. Each coordinate is measurable, the coordinates are mutually independent, and each has distribution ν. At query xk∈E, the oracle returns g(xk,ξk). The algorithm’s randomness is independent of this sample sequence.

Queries may be made at any point of E. After the allotted oracle calls, the output must have an integrable objective gap under P and satisfy EP[f(x¯)−f⋆]≤ε.

Proved result

(⌈32⋅α7⋅(2−α)⋅L⋅τ2α⋅(ε4)α−2α⌉++1)⋅((6+⌈log2⁡(32⋅(32⋅α7⋅(2−α)⋅L⋅τ2α⋅(ε4)α−2α+2)⋅Δε)⌉+)⋅(1+⌈(1152+16⋅(6+⌈log2⁡(32⋅(32⋅α7⋅(2−α)⋅L⋅τ2α⋅(ε4)α−2α+2)⋅Δε)⌉+))⋅(19⋅α2−α⋅τ2α⋅σ2⋅ε−2α+2⋅σ2L⋅ε)⌉+))

OracleTemplate.Convergence LongTails.Setups.SublevelPLBoundedVariance.spec
  OracleTemplate.SublevelRobustGradient.SublevelPLRobustBatchedGd.budget

Relevant previous results

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