← All setups

Strong Growth Restarted Agd — Stationarity Under Strong Growth

Descriptions may be stale. Consult the linked Lean sources.

Stationarity Under Strong Growth · Lean proof

Stationarity Under Strong Growth

We consider minimizing a possibly nonconvex, twice continuously differentiable function f:E→R on a finite-dimensional real inner product space E. Its gradient and Hessian are Lipschitz with constants L>0 and ρ>0, and a given point x0∈E satisfies f(x0)−infx∈Ef(x)≤Δ, where Δ≥0. The oracle returns unbiased stochastic gradients with independent, identically distributed samples and mean squared error at most (κ−1)∥∇f(x)∥2, where κ≥1. The goal is a measurable output x¯∈E with E∥∇f(x¯)∥≤ε, where ε>0 satisfies 48ρε≤L2.

The optimization problem is infx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, and ∥⋅∥op denotes the induced operator norm. The algorithm receives E, the measurable sample space Ω, L, ρ, κ, Δ, ε, and x0.

Our assumptions:

Assumption 1 (Gradient and Hessian regularity). The function f belongs to C2(E;R), and, for all x,y∈E, ∥∇f(x)−∇f(y)∥≤L∥x−y∥,∥∇2f(x)−∇2f(y)∥op≤ρ∥x−y∥. Here ∇2f(x):E→E is the derivative of the gradient.

Assumption 2 (Initial objective gap). The given point x0 satisfies f(x0)−f(x)≤Δ,x∈E.

Assumption 3 (Strong-growth stochastic oracle). There is a probability measure ν on Ω and a jointly measurable map g:E×Ω→E. For every x∈E, the random vector g(x,ξ) is Bochner integrable and ∥g(x,ξ)−∇f(x)∥2 is integrable for ξ∼ν, with Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[∥g(x,ξ)−∇f(x)∥2]≤(κ−1)∥∇f(x)∥2. The samples (ξk)k≥0 are measurable, mutually independent, and each has law ν under a joint probability law Q on ΩN. At the kth query x∈E, the oracle returns g(x,ξk). Algorithm randomness is independent of this sample sequence.

Queries may be made at any point of E. After the allotted oracle calls, the output x¯ must be measurable, its gradient norm must be integrable, and it must satisfy EP[∥∇f(x¯)∥]≤ε, where P is the joint law of the algorithm’s randomness and the oracle samples.

Proved result

(⌈log⁡(1+8⋅2⋅L⋅Δε)⌉++1)⋅(⌈268435456⋅Δ⋅ρε⋅ε⌉++1)⋅(⌈Lρ⋅ε⌉++1+(8+⌈2⋅log⁡(1+8⋅(log⁡(1+8⋅2⋅L⋅Δε)+2)⋅(268435456⋅Δ⋅ρε⋅ε+2)⋅(8⋅L⋅Δ+L⋅ε⋅ερ+ε2+L⋅ερ)ε)⌉+))⋅⌈800⋅κ⌉+

OracleTemplate.Convergence LongTails.Setups.StrongGrowthHessianLipschitz.spec
  OracleTemplate.StrongGrowthRestartedAgd.budget

Relevant previous results

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