  Second-order methods hold significant promise for enhancing the convergence
of deep neural network training; however, their large memory and computational
demands have limited their practicality. Thus there is a need for scalable
second-order methods that can efficiently train large models. In this paper, we
introduce the Sparsified Online Newton (SONew) method, a memory-efficient
second-order algorithm that yields a sparsified yet effective preconditioner.
The algorithm emerges from a novel use of the LogDet matrix divergence measure;
we combine it with sparsity constraints to minimize regret in the online convex
optimization framework. Empirically, we test our method on large scale
benchmarks of up to 1B parameters. We achieve up to 30% faster convergence,
3.4% relative improvement in validation performance, and 80% relative
improvement in training loss, in comparison to memory efficient optimizers
including first order methods. Powering the method is a surprising fact --
imposing structured sparsity patterns, like tridiagonal and banded structure,
requires little to no overhead, making it as efficient and parallelizable as
first-order methods. In wall-clock time, tridiagonal SONew is only about 3%
slower per step than first-order methods but gives overall gains due to much
faster convergence. In contrast, one of the state-of-the-art (SOTA)
memory-intensive second-order methods, Shampoo, is unable to scale to large
benchmarks. Additionally, while Shampoo necessitates significant engineering
efforts to scale to large benchmarks, SONew offers a more straightforward
implementation, increasing its practical appeal. SONew code is available at:
https://github.com/devvrit/SONew
