Expected Generalized Smooth Adam — Adam under Generalized Smoothness
Descriptions may be stale. Consult the linked Lean sources.
Adam under Generalized Smoothness · Lean proof
Adam under Generalized Smoothness
We consider minimizing a differentiable, possibly nonconvex function
The optimization problem is
Our assumptions:
Assumption 1 (Generalized smoothness). The function
Assumption 2 (Initial objective gap). For every
Assumption 3 (Stochastic gradient oracle). Let
Our result is algorithm-specific: we analyze Adam with the following
recurrence. The algorithm chooses constants
The required output is measurable, its squared gradient norm is
integrable, and it satisfies
Proved result
OracleTemplate.Convergence LongTails.Setups.GeneralizedSmoothAdam.spec
OracleTemplate.ExpectedGeneralizedSmoothAdam.budgetRelevant previous results
- Shen-Yi Zhao, Yin-Peng Xie, Wu-Jun Li. On the
convergence and improvement of stochastic normalized gradient
descent. 2021. Complexity:
stochastic-gradient oracle calls, including minibatches, for SNGD to achieve ; and , with universal . - Amirhossein Reisizadeh, Haochuan Li, Subhro Das, Ali Jadbabaie. Variance-reduced Clipping for
Non-convex Optimization. 2023 preprint, v2; published ICASSP 2025.
Complexity:
stochastic-gradient oracle calls, including minibatches, for ClippedSGD to achieve ; and , with universal and no such restriction when .