← All setups

Stationarity Under Strong Growth

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

On a finite-dimensional real inner-product space, f∈C2 has L-Lipschitz gradient, ρ-Lipschitz Hessian, and f(x0)−f(x)≤Δ for every x. The jointly measurable IID oracle is unbiased with integrable gradients and squared errors satisfying E∥g(x)−∇f(x)∥2≤(κ−1)∥∇f(x)∥2. Here L,ρ,ε>0, κ≥1, Δ≥0, and 48ρε≤L2. Target: ∫∥∇f(out(ξ))∥dP(ξ)≤ε, for the constructed restarted AGD’s validated candidate; the setup imposes no algorithm restriction.

Strong-growth stochastic stationarity under Lipschitz Hessians: StrongGrowthHessianLipschitz.
Result Oracle complexity Novelty Limitations
(1) StrongGrowthRestartedAgd (Ours) (⋆⋆⋆) (review) O(κℓ(1+Δρε3/2)[(L2ρε)1/4+ℓ]) stochastic gradient calls, including batching and validation.

Abbr: ℓ=log⁡(2+LΔ/ε2+L2/(ρε)); P is the IID sample-sequence law; out is the validated candidate; ∇2f denotes the Hessian.

Lean setup