Closing the Gap Between the Upper Bound and the Lower Bound of Adam's Iteration Complexity
This work provides a tight theoretical guarantee for Adam's convergence, addressing a fundamental problem in optimization theory for machine learning practitioners and researchers.
The paper tackles the gap between the known lower bound and existing upper bounds for Adam's iteration complexity under smoothness and noise assumptions, and closes it by deriving a new convergence guarantee that meets the lower bound with proper hyperparameters.
Recently, Arjevani et al. [1] established a lower bound of iteration complexity for the first-order optimization under an $L$-smooth condition and a bounded noise variance assumption. However, a thorough review of existing literature on Adam's convergence reveals a noticeable gap: none of them meet the above lower bound. In this paper, we close the gap by deriving a new convergence guarantee of Adam, with only an $L$-smooth condition and a bounded noise variance assumption. Our results remain valid across a broad spectrum of hyperparameters. Especially with properly chosen hyperparameters, we derive an upper bound of the iteration complexity of Adam and show that it meets the lower bound for first-order optimizers. To the best of our knowledge, this is the first to establish such a tight upper bound for Adam's convergence. Our proof utilizes novel techniques to handle the entanglement between momentum and adaptive learning rate and to convert the first-order term in the Descent Lemma to the gradient norm, which may be of independent interest.