← All setups

Window SGD under the PL Condition

Descriptions may be stale. Consult the linked Lean sources.

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⋆)]≤ε.

Results

On a finite-dimensional real inner-product space, f has an attained minimum f⋆=f(x⋆), an L-Lipschitz gradient, and a differentiable gradient with ρ-Lipschitz Hessian. Globally, 2μ(f−f⋆)≤∥∇f∥2, with 0<μ≤L and f(x0)−f⋆≤Δ. The jointly measurable oracle uses IID samples of law p0: ∫g(x,ω)dp0=∇f(x) and, for e=g−∇f, ∫∥e∥2dp0≤σ2, ∫∥e∥4dp0≤Kσ4. Here ρ,σ,Δ≥0, K≥1. The setup requires constant-step SGD with a uniformly sampled final-window iterate x^; the target is ∫(f(x^)−f⋆)dP≤ε, ε>0, under its execution probability law P.

Stochastic optimization under PLHessianLipschitzKurtosis.
Result Oracle complexity Novelty Limitations
(1) KappaFreeSgdPLHessian (Ours) (⋆⋆⋆) (review) O([κ5/4+Kκ3/2σ2ρ2μ4+σ2με]ℓ)
(2) SGD (Khaled and Richtárik 2020, Thm. 3, Cor. 2) O(κ[1+log⁡(1+Δ/ε)]+κσ2με) (1): statistical factor κ→ℓ; total gain κ/ℓ when ℓ≪κ and ε≪ℓ−1min{σ2μ3/4L1/4,μ7/2KL1/2ρ2}. For μ=σ=ρ=Δ=1, K=3, ε=κ−2: O(κ3)→O(κ2log⁡κ). (1) adds Hessian regularity and kurtosis; κ5/4ℓ initialization and a ρ-term. Random window replaces last iterate. Noise term worsens when ℓ≫κ.
(3) Weighted SGD (Stich 2019, Thm. 5); strongly convex restriction O(κ[1+log⁡(1+κΔ/ε)]+σ2με) (1): scope extends from strong convexity to PL, allowing non-isolated minimizers. (1) on the strongly convex overlap: extra κ1/4 initialization factor, ρ-term and statistical logarithm; needs ρ,K.
(4) Ruppert–Polyak averaging (Gadat and Panloup 2017, Thm. 2); isolated-minimizer restriction Derived bound: O(1+trΣ⋆δ+(Cδ)4/5) for E∥x¯−x⋆∥2≤δ, steps γn−3/4. Requires coercivity, unique critical point, ∇2f(x⋆)≻0, Lipschitz noise covariance and L4 consistency. C is non-explicit. (1) allows non-isolated minimizers and gives explicit parameter dependence. Rates are not comparable: squared-distance accuracy and covariance/consistency assumptions differ.
(5) Lower bound (Masiha et al. 2026, Thm. 4.3, Rem. 4.6); broader smooth PL class Ω(κσ2με) for 0<ε≤Δ/10, σ>0; all randomized first-order methods with bounded-variance gradient access. (1) improves the statistical dependence on a narrower subclass. The hard instances lack Lipschitz Hessians; this is not an improvement on the full smooth PL class.

Abbr: κ=L/μ; ℓ=1+log⁡(1+κΔ/ε). Costs count individual stochastic-gradient calls, including the initial window burn-in. δ is squared-distance tolerance; x¯ is an averaged iterate; Σ⋆=[∇2f(x⋆)]−1S(x⋆)[∇2f(x⋆)]−1, with S the noise covariance; C is the remainder constant. L4 consistency means E∥xn−x⋆∥4=O(γn2); γ>0 is the stepsize scale.

Gadat, Sébastien, and Fabien Panloup. 2017. Optimal Non-Asymptotic Bound of the Ruppert–Polyak Averaging Without Strong Convexity. https://doi.org/10.48550/arXiv.1709.03342.
Khaled, Ahmed, and Peter Richtárik. 2020. Better Theory for SGD in the Nonconvex World. https://doi.org/10.48550/arXiv.2002.03329.
Masiha, Saeed, Negar Kiyavash, and Patrick Thiran. 2026. Sharp First-Order Lower Bounds Under α-Polyak–Lojasiewicz Conditions. https://doi.org/10.48550/arXiv.2606.28278.
Stich, Sebastian U. 2019. Unified Optimal Analysis of the (Stochastic) Gradient Method. https://doi.org/10.48550/arXiv.1907.04232.

Lean setup