Sublevel PLRobust Batched Gd — Sublevel Gradient Domination with Stochastic Gradients
Descriptions may be stale. Consult the linked Lean sources.
Sublevel Gradient Domination with Stochastic Gradients · Lean proof
Sublevel
Gradient Domination with Stochastic Gradients
We consider minimizing a possibly nonconvex differentiable function
on a
finite-dimensional real inner product space . Its gradient is -Lipschitz, with , and is finite.
Given , assume whenever , where
and . The oracle
returns an unbiased stochastic gradient with variance at most , where , using independent,
identically distributed samples. For , the goal is an output
with integrable
objective gap and ,
where is the joint law of
algorithm and oracle randomness.
The optimization problem is The norm is induced by the inner product
on . The algorithm receives , , , , , an initial-gap bound , the tolerance , and the given point .
Our assumptions:
Assumption 1 (Smoothness). The function is Fréchet differentiable everywhere on
, and
Assumption 2 (Sublevel gradient domination). The
function is bounded below, and
its initial sublevel set satisfies
Assumption 3 (Unbiased gradients with bounded
variance). Let be a
measurable sample space and a
probability measure on .
There is a jointly measurable map such that, for every
fixed , is Bochner integrable and
is
integrable under , with The samples have a joint probability
law on . Each coordinate is
measurable, the coordinates are mutually independent, and each has
distribution . At query , the oracle returns . The algorithm’s randomness
is independent of this sample sequence.
Queries may be made at any point of . After the allotted oracle calls, the
output must have an integrable objective gap under and satisfy
Proved result
OracleTemplate.Convergence LongTails.Setups.SublevelPLBoundedVariance.spec
OracleTemplate.SublevelRobustGradient.SublevelPLRobustBatchedGd.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.