Search papers, labs, and topics across Lattice.
This paper investigates the superior empirical performance of Adam over SGD by focusing on Adam's second-moment normalization. Through a novel stopping-time/martingale analysis under the bounded variance model, the authors establish a theoretical separation in high-probability convergence rates. Specifically, they prove that Adam achieves a $δ^{-1/2}$ dependence on the confidence parameter $δ$, while SGD exhibits at least a $δ^{-1}$ dependence, providing a theoretical explanation for Adam's faster convergence.
Adam's faster convergence isn't just empirical luck: its second-moment normalization provably yields sharper tails in high-probability convergence guarantees compared to SGD.
Despite Adam demonstrating faster empirical convergence than SGD in many applications, much of the existing theory yields guarantees essentially comparable to those of SGD, leaving the empirical performance gap insufficiently explained. In this paper, we uncover a key second-moment normalization in Adam and develop a stopping-time/martingale analysis that provably distinguishes Adam from SGD under the classical bounded variance model (a second moment assumption). In particular, we establish the first theoretical separation between the high-probability convergence behaviors of the two methods: Adam achieves a $δ^{-1/2}$ dependence on the confidence parameter $δ$, whereas corresponding high-probability guarantee for SGD necessarily incurs at least a $δ^{-1}$ dependence.
