Grimoire
Sheet
pathtraining/optimisers
difficultyadvanced
timeO(d^1.5)
described2018
revised5w ago

Second-Order Preconditioning

Update rules that precondition by a factored second-moment matrix rather than a diagonal, and the cheaper orthogonalisation approximations that have displaced them in practice.

Status

This entry is a stub. The maths has not been rederived by hand, or the implementation has not been run on real tensors, so it is recorded here as an open question rather than an answer.

Read what follows as a pointer to the sources, not as a settled account.

Notes

Adam preconditions by a diagonal — one scalar per parameter, no knowledge of how parameters interact. Shampoo instead maintains a Kronecker-factored approximation to the full second-moment matrix, one factor per tensor axis, and the orthogonalised-update family approximates the resulting inverse root with a few Newton–Schulz iterations rather than an eigendecomposition.

The maths here has not been rederived by hand, and in particular the relationship between the Newton–Schulz coefficient choice and the conditioning of the update is recorded from the sources rather than checked. Treat this entry as a pointer.

Related
References
[1]Gupta et al. — Shampoo: Preconditioned Stochastic Tensor Optimization (2018)arXiv:1802.09568