Descriptions may be stale. Consult the linked Lean sources.
Adam
with Heterogeneous Symmetric Noise
We consider minimizing a differentiable, possibly nonconvex function
on the Euclidean
space , where
are integers with . Its gradient is -Lipschitz, with , and the given starting point
has objective gap at most above the infimum. The oracle
returns unbiased stochastic gradients from independent, identically
distributed samples. Body-coordinate noise is symmetric with bounded
first moment and integrably Lipschitz sample paths; head-coordinate
noise has bounded second moment. We analyze heterogeneous Adam, seeking
a measurable output
satisfying for , where is the joint law of sampling and
algorithm randomness.
The optimization problem is Write
for the body and head blocks, with coordinate sets and . Throughout, denotes the Euclidean norm. The
parameters satisfy The algorithm receives , the measurable sample space , ,
and .
Our assumptions:
Assumption 1 (Smoothness and initial gap). The
function is differentiable
everywhere, and for all ,
Assumption 2 (Unbiased heterogeneous noise). There
exist a probability measure on
and a jointly measurable map
. For every
, is Bochner integrable under
, and Define the noise . For every
, The head squared-noise sum is integrable under
. Each body coordinate has a
symmetric noise distribution:
Assumption 3 (Samplewise body-noise regularity).
There exists a measurable, integrable function with . For
-almost every , and, simultaneously for all
and ,
At call , a query returns . The sample variables are measurable, mutually
independent, and each has law ;
they are independent of the algorithm’s randomness.
Our result is algorithm-specific: we analyze heterogeneous Adam,
using bias-corrected Adam updates on the body and cumulative
squared-gradient normalization on the head. The algorithm chooses a
nonnegative integer , a scalar
, and deterministic
positive step sequences and from the available
inputs. The momentum coefficients and denominator offset are fixed as
Initialize the iterates at the given , with For , the body coordinates
obey, for , The head coordinates obey, for , Independently of the samples, draw uniformly from . After oracle calls, the output rule is
Thus, when , the output is uniformly selected from . The required output is
measurable, its gradient norm is integrable under , and the accuracy criterion is