Towards Quantifying the Preconditioning Effect of Adam
This provides theoretical insights for machine learning practitioners on when Adam is beneficial, though it is incremental as it builds on existing optimization analysis.
The paper tackles the problem of characterizing Adam's preconditioning effect to mitigate ill-conditioning in optimization, showing that Adam can outperform gradient descent when dimension is less than a condition number threshold but may be worse for non-diagonal Hessians, with bounds like O(min(d, κ)) for diagonal cases.
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 $κ$, we show that the effective condition number-like quantity controlling the iteration complexity of Adam without momentum is $\mathcal{O}(\min(d, κ))$. For a diagonally dominant Hessian, we obtain a bound of $\mathcal{O}(\min(d \sqrt{d κ}, κ))$ for the corresponding quantity. Thus, when $d < \mathcal{O}(κ^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}(κ)$ 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}(κ^{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-Łojasiewicz condition.