Parameter Free Heavy Tailed Nsgdm — Parameter-Free Heavy-Tailed Stationarity
Descriptions may be stale. Consult the linked Lean sources.
Parameter-Free Heavy-Tailed Stationarity · Lean proof
Parameter-Free
Heavy-Tailed Stationarity
We consider a differentiable, possibly nonconvex function on a separable real
Hilbert space , with hidden
gradient Lipschitz constant .
A given point satisfies
for a global
lower bound and
. The oracle returns an
unbiased stochastic gradient at , using independent samples with common law , with centered th moment at most , where and . For , the goal is for an output , averaging over sampling and
algorithm randomness.
The underlying optimization problem is The norm is induced by the inner product
on , and carries its Borel sigma-algebra. The
algorithm receives only and ; the parameters , , , , and may enter the oracle-call
budget but are not algorithm inputs.
Our assumptions:
Assumption 1 (Smoothness and initial gap). The
function is Fréchet
differentiable everywhere, and There exists such that
Assumption 2 (Heavy-tailed stochastic gradients).
Let be a measurable sample
space and a probability measure
on . The map is jointly
measurable. For every , is Bochner integrable, the
random variable is integrable for , and
At call , a query receives . The sample variables are measurable and
mutually independent with common law under their joint probability law.
Any algorithm randomness is independent of this sample sequence. Queries
may be made at any point of .
After the allotted oracle calls, the output must be measurable, must be integrable,
and where is the joint law of the algorithm
randomness and the sample sequence.
Proved result
OracleTemplate.Convergence LongTails.Setups.ParameterFreeHeavyTailedSmooth.spec
LongTails.Theorems.ParameterFreeHeavyTailedNsgdm.budget
Relevant previous results
- Florian Hübler, Ilyas Fatkhullin, and Niao He. From Gradient
Clipping to Normalization for Heavy Tailed SGD. 2025 (preprint 2024;
analysis checked in arXiv v3). Complexity:
stochastic-gradient calls, including minibatches, for
using tuned minibatch normalized SGD.