Descriptions may be stale. Consult the linked Lean sources.
Adam
with Affine Heavy-Tailed Noise
We consider minimizing a differentiable, possibly nonconvex function
, where
is an integer. The function
is -smooth in the -to- sense, with and . A given starting point
satisfies , where . The oracle returns unbiased
stochastic gradients from independent, identically distributed samples,
with coordinatewise noise moments of order bounded affinely in the
corresponding gradient magnitudes to power . We analyze minibatch Adam with bias
correction. For ,
its output must satisfy
, where expectation includes
sampling and algorithm randomness and .
The optimization problem is The
ambient space has its Euclidean inner product, which defines . Write ,
with both norms equal to zero when . Let be a measurable sample space, and
let
and be nonnegative noise
parameters. The algorithm receives , , , , , , , , , and .
Our assumptions:
Assumption 1 (Generalized smoothness). The function
is Fréchet differentiable
everywhere. For all satisfying ,
Assumption 2 (Initial objective gap). The given
starting point satisfies
Assumption 3 (Affine heavy-tailed oracle). There
exist a probability measure on
and a jointly measurable map
.
For every , the map is Bochner integrable and
For every and
coordinate , the random variable
is
integrable and satisfies At call , a query receives . Under their joint law , the measurable samples are mutually independent
and each has distribution .
Algorithm randomness is independent of this sample sequence.
Our formulation is algorithm-specific: we analyze minibatch Adam with
bias correction and a constant step size. Its tuning parameters satisfy
These parameters may depend on the supplied
inputs. Initialize the moments at and the iterate at the given
. At iteration , take consecutive oracle samples at and form
For each coordinate , the update
is Each completed iteration uses oracle calls. For an allotted budget
, let be the number of
completed iterations. Any remaining calls are made at and do not produce another
update.
Independently of the samples, draw uniformly from . The output rule saves the
selected iterate immediately before its update; explicitly, In particular, when , this is a uniform selection
from . Let be the joint law of and the oracle samples. The output must
be measurable, must be integrable under , and the required accuracy is