← All setups

Sublevel Gradient Domination with Stochastic Gradients

Descriptions may be stale. Consult the linked Lean sources.

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

Results

On a finite-dimensional real inner-product space, f is differentiable, globally L-smooth and bounded below. With f⋆=infxf(x), assume f(x0)−f⋆≤Δ and f(x)−f⋆≤τ∥∇f(x)∥α whenever f(x)≤f(x0), where L,τ>0, 1≤α<2, σ,Δ≥0 and ε>0. The jointly measurable oracle uses IID samples from a probability measure p, with ∫g(x,z)dp(z)=∇f(x) and ∫∥g(x,z)−∇f(x)∥2dp(z)≤σ2; these integrals are integrable. The target is the unconditional last-iterate guarantee ∫[f(xK(ω))−f⋆]dP(ω)≤ε.

Sufficient oracle budgets for SublevelPLBoundedVariance.
Result Oracle complexity Novelty Limitations
(1) SublevelPLRobustBatchedGd (Ours) (⋆⋆) (review) O((1+cD)ℓ[1+ℓ(cσ2τ2/αε−2/α+σ2/(Lε))]) gradient samples, including every robust sub-batch; fixed budget.
(2) Derived bound: SGD under trajectory containment, (Fatkhullin et al. 2022; Masiha, Kiyavash, et al. 2026), Cor. 1 / Table 1 O(D+Lσ2τ4/αε−(4−α)/α) gradient samples, assuming the trajectory stays where α-PL holds; stated for ε≲min{Δ,Lα/(2−α)τ2/(2−α)}. The original global-α-PL formulation admits only constant globally smooth objectives here. (1): Scope: unconditional guarantee on nonconstant sublevel instances, without assumed containment; preserves the accuracy powers up to logarithms. (1): For D≥1, overhead cℓ in the deterministic term and c2ℓ2 in the noise term; Δ enters logarithms. Uses robust batches rather than SGD.
(3) SARAH, (Masiha, Salehkaleybar, et al. 2026), Thm. 3.2 O(ε−2/α) stochastic-gradient evaluations, including batches and paired evaluations; other constants depend on τ,σ,L~,s,R,δ. Requires a compact, isolated minimizer component, local smoothness, batch smoothness, x0∈U0 and ε≤s/2. Expected local gap is conditional on containment, whose probability is ≥1−δ. (1): Oracle: no mean-squared smoothness or paired samples. Unconditional global-gap expectation instead of conditional local-gap expectation; no prescribed minimizer neighbourhood. (1): Global smoothness required. Noise-dependent accuracy exponent (4−α)/α instead of 2/α. Setups and criteria differ; total rates are not comparable.
(4) Clipped SGD, (Sadiev et al. 2023), Thm. E.4; classical-PL special case O(1+Lhμlog(e+Lhμβ)+Lσ2μ2εalog2(e+Δεa)) gradient samples for gap ≤ε with probability 1−β. Assumes f−f⋆≤∥∇f∥2/(2μ) and smoothness on Q={x:dist(x,{f≤f⋆+2Δ})≤Δ/L/20}; displayed cost specializes to finite variance. (1): Scope: covers sublevel exponents 1≤α<2 beyond classical PL. Establishes unconditional expectation, which (4) does not imply without failure-event control.

(1): Global rather than Q-local smoothness; finite variance rather than heavier tails; expectation rather than high probability. On globally smooth PL instances with Δ>0, α=2−h−1 and

τ=Δ1−α/2(2μ)−α/2, cost becomes O((L/μ+Lσ2/(μ2ε))h2⋅log2(e+LΔ/(με))): extra polylogarithmic factors.

Abbr: c=α/(2−α), D=Lτ2/αε−(2−α)/α, ℓ=log⁡(e+(1+cD)Δ/ε); h=log⁡(e+Δ/ε), a=log⁡(e+Lσ2/(βμ2ε)), 0<β,δ<1, μ>0 is the classical PL parameter. L~ bounds mean-squared oracle smoothness: ∫∥g(x,z)−g(y,z)∥2dp(z)≤L~2∥x−y∥2. For (3), R is a minimizer-neighbourhood radius, s>0 its gap barrier, and U0={x:dist(x,M)<R/2, f(x)−l≤s/2}, with minimizer component M of level l. Logarithms are natural; ≲ hides universal factors.

Fatkhullin, Ilyas, Jalal Etesami, Niao He, and Negar Kiyavash. 2022. “Sharp Analysis of Stochastic Optimization Under Global Kurdyka–Łojasiewicz Inequality.” Advances in Neural Information Processing Systems 35: 15836–48. https://doi.org/10.52202/068431-1152.
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.
Masiha, Saeed, Saber Salehkaleybar, Niao He, Negar Kiyavash, and Patrick Thiran. 2026. Optimal Local Convergence Rates of Stochastic First-Order Methods Under Local α-PL. https://doi.org/10.48550/arXiv.2408.01839.
Sadiev, Abdurakhmon, Marina Danilova, Eduard Gorbunov, et al. 2023. “High-Probability Bounds for Stochastic Optimization and Variational Inequalities: The Case of Unbounded Variance.” Proceedings of the 40th International Conference on Machine Learning, Proceedings of machine learning research, vol. 202: 29563–648. https://doi.org/10.48550/arXiv.2302.00999.

Lean setup