KrADagrad: Kronecker Approximation-Domination Gradient Preconditioned Stochastic Optimization
This work addresses a hardware constraint issue for deep learning practitioners by enabling efficient second-order optimization with lower precision, though it is incremental as it builds on existing Kronecker-factored preconditioners.
The authors tackled the problem of second-order stochastic optimizers requiring high memory and compute, particularly the need for 64-bit precision due to matrix inversions in methods like Shampoo, by proposing KrADagrad, a novel factorization that avoids inversion and uses 32-bit precision, showing improved performance in synthetic experiments and comparable or better generalization on real datasets.
Second order stochastic optimizers allow parameter update step size and direction to adapt to loss curvature, but have traditionally required too much memory and compute for deep learning. Recently, Shampoo [Gupta et al., 2018] introduced a Kronecker factored preconditioner to reduce these requirements: it is used for large deep models [Anil et al., 2020] and in production [Anil et al., 2022]. However, it takes inverse matrix roots of ill-conditioned matrices. This requires 64-bit precision, imposing strong hardware constraints. In this paper, we propose a novel factorization, Kronecker Approximation-Domination (KrAD). Using KrAD, we update a matrix that directly approximates the inverse empirical Fisher matrix (like full matrix AdaGrad), avoiding inversion and hence 64-bit precision. We then propose KrADagrad$^\star$, with similar computational costs to Shampoo and the same regret. Synthetic ill-conditioned experiments show improved performance over Shampoo for 32-bit precision, while for several real datasets we have comparable or better generalization.