Nonnegative Sample Stationarity Lower Bound — Stationarity for Nonnegative Smooth Sample Losses
Descriptions may be stale. Consult the linked Lean sources.
Stationarity for Nonnegative Smooth Sample Losses · Lean proof
Stationarity for
Nonnegative Smooth Sample Losses
We seek a stationary point of a possibly nonconvex objective on a finite-dimensional
Euclidean space . The objective is
the expectation of nonnegative sample losses with -Lipschitz gradients, where , and for a given . Each oracle call returns the
gradients of one fresh, independently sampled loss at both queried
points. For a tolerance , the goal is a
measurable output
satisfying , with expectation over the oracle
samples and the algorithm’s independent randomness.
The parameters satisfy . For
a nonnegative integer specifying
the extra width, set The optimization problem is where carries the
Euclidean norm , with the Frobenius norm. The algorithm receives , the sample space , the starting point
, and the parameters .
Our assumptions:
Assumption 1 (Sample loss regularity). For each
, the loss is
differentiable. Writing , we
require for every and
that The map is jointly
measurable.
Assumption 2 (Population objective and initial
value). There is a probability distribution on such that is -integrable for every , and
On call , the algorithm may
query any pair
and receives . The samples
are independent
random variables with common law , and the sample sequence is
independent of the algorithm’s randomness. After the allotted calls, the
output must be measurable,
its gradient norm must be integrable, and
Proved result
OracleTemplate.NonConvergence LongTails.Setups.NonnegativeSmoothSampleLossEuclidean.spec
LongTails.Theorems.NonnegativeSampleStationarityLowerBound.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.