← All setups

Kappa Free Sgd PLHessian — Window SGD under the PL Condition

Descriptions may be stale. Consult the linked Lean sources.

Window SGD under the PL Condition · Lean proof

Window SGD under the PL Condition

We consider minimizing a possibly nonconvex function f:E→R on a finite-dimensional real inner product space E. The objective has a Lipschitz gradient, a Lipschitz Hessian, and a global minimizer x⋆, and satisfies the Polyak–Łojasiewicz condition. A given starting point has bounded objective gap. At x∈E, the oracle returns g(x,ξ), an unbiased gradient estimate using a fresh independent sample ξ, with uniformly bounded second and fourth noise moments. Window SGD must produce a measurable output x¯∈E with integrable objective gap and E[f(x¯)−f(x⋆)]≤ε, where ε>0 and expectation includes sampling and algorithm randomness.

The optimization problem is minx∈Ef(x). Write ∥⋅∥ for the inner product norm and ∥⋅∥op for the induced operator norm. Fix a starting point x0∈E, a measurable sample space Ω, and parameters 0<μ≤L,ρ,σ,Δ≥0,K≥1,ε>0. The algorithm receives E, Ω, L, μ, ρ, σ, K, Δ, ε, and x0.

Our assumptions:

Assumption 1 (Gradient and Hessian regularity). The function f is Fréchet differentiable on E, and its gradient is Fréchet differentiable on E. For every 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 (Polyak–Łojasiewicz condition and initial gap). There exists x⋆∈E such that, for every x∈E, f(x⋆)≤f(x),2μ(f(x)−f(x⋆))≤∥∇f(x)∥2, and the given starting point satisfies f(x0)−f(x⋆)≤Δ.

Assumption 3 (Independent stochastic gradients and fourth moments). There is a probability measure ν on Ω and a jointly measurable map g:E×Ω→E. The measurable samples (ξk)k≥0 are mutually independent, each with law ν. At its kth call, the oracle returns g(x,ξk) for any query x∈E. For every fixed x∈E, g(x,ξ) is Bochner integrable under ξ∼ν, and Eξ∼ν[g(x,ξ)]=∇f(x). Writing e(x,ξ)=g(x,ξ)−∇f(x), both ∥e(x,ξ)∥2 and ∥e(x,ξ)∥4 are integrable, with Eξ∼ν[∥e(x,ξ)∥2]≤σ2,Eξ∼ν[∥e(x,ξ)∥4]≤Kσ4.

Our formulation is algorithm-specific: we analyze Window SGD. The algorithm chooses a constant step size η>0 and integers Ta,Tb≥0 from its inputs. Independently of the oracle samples, it draws τ uniformly from {0,…,Tb} and sets H=Ta+τ. Starting from the given x0, its recurrence for a budget of N≥0 oracle calls is gk=g(xk,ξk),xk+1={xk−ηgk,k<H,xk,k≥H,k=0,…,N−1. The output is x¯=xN. Calls continue to count after the iterate is frozen. Thus, when N≥Ta+Tb, the output is the SGD iterate at the uniformly selected index H; a smaller budget truncates the updates at N.

Let P be the joint law of τ and the oracle samples. The output must be measurable, its objective gap must be integrable under P, and the accuracy requirement is EP[f(x¯)−f(x⋆)]≤ε.

Proved result

⌈32⋅(16⋅L+14⋅L⋅Lμ+28311552⋅K⋅Lμ⋅L⋅σ2⋅ρ2μ4+64⋅σ2ε)μ⋅(log⁡(1+6⋅Lμ⋅Δε)+1)+512⋅σ2μ⋅ε⌉++1

OracleTemplate.Convergence LongTails.Setups.PLHessianLipschitzKurtosis.spec OracleTemplate.PLHessian.budget

Relevant previous results

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