Determinant Estimation under Memory Constraints and Neural Scaling Laws

Calculating or accurately estimating log-determinants of large positive semi-definite matrices is of fundamental importance in many machine learning tasks. While its cubic computational complexity can already be prohibitive, in modern applications even storing the matrices themselves can pose a memory bottleneck. To address this, we derive a novel hierarchical algorithm based on block-wise computation of the LDL decomposition for large-scale log-determinant calculation in memory-constrained settings. In extreme cases where matrices are highly ill-conditioned, accurately computing the full matrix itself may be infeasible. This is particularly relevant when considering kernel matrices at scale, including the empirical Neural Tangent Kernel (NTK) of neural networks trained on large datasets. Under the assumption of neural scaling laws in the test error, we show that the ratio of pseudo-determinants satisfies a power-law relationship, enabling the derivation of corresponding scaling laws. This allows for accurate estimation of NTK log-determinants from a tiny fraction of the full dataset; in our experiments, this results in a $\sim$100,000$\times$ speedup with improved accuracy to other state-of-the-art approaches. Using these techniques, we successfully estimate log-determinants for dense matrices of extreme sizes, which were previously deemed intractable and inaccessible due to their enormous scale and computational requirements.

Many machine-learning methods need to compute a summary (the “log-determinant”) from very large tables of numbers, but doing so can be extremely slow and even run out of computer memory. We created a way to compute this summary by breaking these huge data tables into smaller blocks, so the entire thing never needs to be loaded into the computer memory all at once. We also discovered a simple rule based on how neural networks behave as you add more data, that allows us to predict the needed number from just a tiny fraction of the full table. This can result in speedups of up to 100,000x in our experiments.