Abstract
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, allowing us to derive corresponding scaling laws. This enables accurate estimation of NTK log-determinants from a tiny fraction of the full dataset; in our experiments, this results in a ~100,000x speedup with improved accuracy over competing approximations. 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 demands.
Introduction
In modern machine learning, calculating the log-determinant of large, dense, positive-definite matrices is a critical yet computationally expensive task. Applications range from Gaussian Process (GP) marginal likelihood estimation to model selection and information-theoretic analysis. However, two major hurdles persist: the $O(n^3)$ computational complexity and the "memory wall." For instance, the Neural Tangent Kernel (NTK) for a dataset like ImageNet-1k would require over 13 exabytes of storage, making standard in-memory algorithms impossible. Furthermore, standard stochastic approximations often struggle with the ill-conditioned nature of NTK matrices, where small eigenvalues lead to significant numerical instability.
MEMDET: Exact Computation via Hierarchical LDL
To overcome memory limitations, we introduce MEMDET, a memory-constrained hierarchical algorithm. MEMDET utilizes a block-wise LDL (or LU) decomposition strategy. Instead of loading the entire matrix into RAM, it partitions the matrix into smaller blocks and manages intermediate computations on a disk-based "scratchpad."
The algorithm employs a specific processing order designed to minimize data transfer between the disk and main memory. By optimizing the movement of blocks, MEMDET enables exact log-determinant computation on standard hardware for matrices that are terabytes in size, effectively bypassing the RAM bottleneck.
FLODANCE: Approximation via Neural Scaling Laws
While MEMDET provides exact results, the $O(n^3)$ complexity remains a factor for extremely large $n$. We propose FLODANCE (Factorial-based Log-Determinant Analysis and Numerical Curve Estimation), which leverages the observation that determinant ratios follow predictable scaling laws. We demonstrate that for a broad class of kernels, the ratio of successive determinants $\det(\mathbf{K}_n)/\det(\mathbf{K}_{n-1})$ follows a power-law relationship with respect to the dataset size $n$. This relationship is intrinsically linked to the neural scaling laws observed in test error curves.
The FLODANCE workflow involves computing log-determinants for a small subset of the data using MEMDET, fitting a linear regression model to these values based on the derived power law, and extrapolating to predict the log-determinant for the full-scale dataset.
Experimental Results
We evaluated our methods on datasets including CIFAR-10 and MNIST using various architectures (ResNet, MobileNet). A key achievement was the exact computation of a dense $500,000 \times 500,000$ NTK matrix for ResNet50 on CIFAR-10, requiring 2 TB of storage. FLODANCE achieved a staggering 100,000x speedup, estimating the log-determinant of the 500k-dimension matrix in just 1 minute on a CPU, compared to 13.8 days for the exact MEMDET algorithm on a high-end GPU. Remarkably, FLODANCE maintained a relative error of only 0.02%, outperforming traditional methods like Stochastic Lanczos Quadrature (SLQ), which showed errors up to 55%.
Conclusion
By combining exact out-of-core computation (MEMDET) with scaling-law-based approximation (FLODANCE), we provide a robust framework for handling massive matrices. Our findings suggest that the internal geometry of kernel matrices is highly predictable, allowing for accurate estimation from minimal data. These algorithms are implemented in the high-performance Python package detkit.
Summary updated