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
The optimization problem is
Our assumptions:
Assumption 1 (Smoothness). The function
Assumption 2 (Sublevel gradient domination). The
function
Assumption 3 (Unbiased gradients with bounded
variance). Let
Queries may be made at any point of
Results
On a finite-dimensional real inner-product space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) SublevelPLRobustBatchedGd
(Ours) |
|||
| (2) Derived bound: SGD under trajectory containment, (Fatkhullin et al. 2022; Masiha, Kiyavash, et al. 2026), Cor. 1 / Table 1 | (1): Scope: unconditional guarantee on nonconstant sublevel instances, without assumed containment; preserves the accuracy powers up to logarithms. | (1): For |
|
| (3) SARAH, (Masiha, Salehkaleybar, et al. 2026), Thm. 3.2 | (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) Clipped SGD, (Sadiev et al. 2023), Thm. E.4; classical-PL special case | (1): Scope: covers
sublevel exponents |
(1): Global rather
than |
Abbr: