Descriptions may be stale. Consult the linked Lean sources.
Adam with
Heavy-Tailed Gradients
We consider stationarity for a differentiable, possibly nonconvex
function , where is an integer. Its gradient is
-Lipschitz, with , and a given starting point satisfies , with . The oracle returns unbiased
stochastic gradients with independent, identically distributed samples
and coordinatewise noise moments of order whose sum is bounded by
, where . We analyze Adam with a
randomly selected iterate ;
the goal is , where and expectation includes
sampling and iterate selection.
The underlying optimization problem is and denotes the Euclidean norm. The
algorithm receives , the
measurable sample space ,
, , , , , and .
Our assumptions:
Assumption 1 (Smoothness and initial gap). The
function is differentiable
everywhere, and for every ,
Assumption 2 (Heavy-tailed stochastic gradients).
Let be a probability measure on
. The oracle is a jointly
measurable map .
For each , the map
is Bochner integrable,
and the scalar random variable is integrable for . They satisfy At call , a
query receives
. The measurable sample
variables are
mutually independent with common law under their joint law , and are independent of the algorithm’s
randomness.
Our result is algorithm-specific: we analyze Adam with constant
parameters and without bias correction. The algorithm chooses using
the available inputs. Starting from the given and , it queries at and performs the coordinatewise
updates Independently of the samples, it draws uniformly from . Its saved output is
initialized to and replaced by
the pre-update iterate when
call is made. Thus, after oracle calls, its output is In particular, with calls the output is the uniformly
selected iterate from ; the final call and update
are included in this budget.
Let be the joint law of the
samples and the independent index . The required output is measurable, is integrable under
, and the accuracy requirement is