Towards Quantifying the Preconditioning Effect of Adam
Rudrajit Das Naman Agarwal Sujay Sanghavi Inderjit S. Dhillon
There is a notable dearth of results characterizing the preconditioning
effect of Adam and showing how it may alleviate the curse of ill-conditioning
-- an issue plaguing gradient descent (GD). In this work, we perform a detailed
analysis of Adam's preconditioning effect for quadratic functions and quantify
to what extent Adam can mitigate the dependence on the condition number of the
Hessian. Our key finding is that Adam can suffer less from the condition number
but at the expense of suffering a dimension-dependent quantity. Specifically,
for a $d$-dimensional quadratic with a diagonal Hessian having condition number
$\kappa$, we show that the effective condition number-like quantity controlling
the iteration complexity of Adam without momentum is $\mathcal{O}(\min(d,
\kappa))$. For a diagonally dominant Hessian, we obtain a bound of
$\mathcal{O}(\min(d \sqrt{d \kappa}, \kappa))$ for the corresponding quantity.
Thus, when $d < \mathcal{O}(\kappa^p)$ where $p = 1$ for a diagonal Hessian and
$p = 1/3$ for a diagonally dominant Hessian, Adam can outperform GD (which has
an $\mathcal{O}(\kappa)$ dependence). On the negative side, our results suggest
that Adam can be worse than GD for a sufficiently non-diagonal Hessian even if
$d \ll \mathcal{O}(\kappa^{1/3})$; we corroborate this with empirical evidence.
Finally, we extend our analysis to functions satisfying per-coordinate
Lipschitz smoothness and a modified version of the Polyak-\L ojasiewicz
condition.