Adaptive Gradient Methods Converge Faster with Over-Parameterization (but you should do a line-search)

Understand

Adaptive gradient methods are typically used for training over-parameterized models.

• To better understand their behaviour, we study a simplistic setting -- smooth, convex losses with models over-parameterized enough to interpolate the data.
• In this setting, we prove that AMSGrad with constant step-size and momentum converges to the minimizer at a faster $O(1/T)$ rate.
• When interpolation is only approximately satisfied, constant step-size AMSGrad converges to a neighbourhood of the solution at the same rate, while AdaGrad is robust to the violation of interpolation.