A Simple Convergence Proof of Adam and Adagrad
This provides theoretical guarantees for widely used optimizers in machine learning, though it is incremental as it refines existing convergence bounds.
The paper tackles the convergence analysis of Adam and Adagrad optimization algorithms for smooth non-convex functions, showing that with proper hyperparameters, Adam converges at a rate of O(d ln(N)/√N) and improves the dependency on momentum decay rate from O((1-β1)^{-3}) to O((1-β1)^{-1}).
We provide a simple proof of convergence covering both the Adam and Adagrad adaptive optimization algorithms when applied to smooth (possibly non-convex) objective functions with bounded gradients. We show that in expectation, the squared norm of the objective gradient averaged over the trajectory has an upper-bound which is explicit in the constants of the problem, parameters of the optimizer, the dimension $d$, and the total number of iterations $N$. This bound can be made arbitrarily small, and with the right hyper-parameters, Adam can be shown to converge with the same rate of convergence $O(d\ln(N)/\sqrt{N})$. When used with the default parameters, Adam doesn't converge, however, and just like constant step-size SGD, it moves away from the initialization point faster than Adagrad, which might explain its practical success. Finally, we obtain the tightest dependency on the heavy ball momentum decay rate $β_1$ among all previous convergence bounds for non-convex Adam and Adagrad, improving from $O((1-β_1)^{-3})$ to $O((1-β_1)^{-1})$.