TL;DR
This paper introduces two breakthroughs for computing the log-determinants of massive, dense matrices like Neural Tangent Kernels (NTKs): MEMDET, an exact out-of-core block decomposition algorithm that bypasses memory limits by streaming data from disk, and FLODANCE, an approximation method that leverages neural scaling laws to extrapolate log-determinants from tiny data subsets, achieving up to a $\sim100,000\times$ speedup with exceptional accuracy.
What Problem Does This Paper Address?
Log-determinants of large, dense, positive definite matrices are foundational to many machine learning tasks, including training Gaussian processes, evaluating determinantal point processes, and performing model selection. However, computing them exactly carries a prohibitive cubic time complexity ($O(m^3)$) and quadratic memory complexity ($O(m^2)$).
In modern deep learning, analyzing the empirical Neural Tangent Kernel (NTK)—a matrix capturing how network outputs change relative to parameters—hits a massive "memory wall." For instance, storing the NTK matrix for the modest MNIST dataset requires 2.9 TB of RAM, while ImageNet-1k would demand an impossible 13.1 exabytes. Because these matrices are often highly ill-conditioned, standard randomized or low-precision approximations fail catastrophically, as small eigenvalue errors are heavily magnified on a log scale.
Methods
The authors tackle this problem on two fronts, providing both an exact baseline tool and an ultra-fast approximation framework:
- MEMDET (Memory-Constrained Determinant Calculation): This is an exact algorithm that computes LU, LDL, or Cholesky decompositions by partitioning a massive matrix into small $b \times b$ blocks. Instead of loading the whole matrix into RAM, MEMDET keeps only 3 or 4 blocks in memory at any given time, reading and writing intermediate results to disk (out-of-core processing). The authors design an optimized block-processing sequence using Hamiltonian paths on line graphs to minimize disk I/O overhead.
- FLODANCE (Factorial-based Log-Determinant Analysis and Numerical Curve Estimation): This novel approximation technique relies on a deep theoretical insight: the ratio of successive determinants of a kernel matrix can be bounded by the mean-squared error of an associated Gaussian process. Since learning curves in machine learning follow power-law "neural scaling laws," the authors prove that the determinant ratios do too. FLODANCE runs MEMDET on a tiny fraction of the dataset, fits a linear regression to the scaling curve using a Laurent series correction, and accurately extrapolates the log-determinant for the full dataset.
Datasets
The methods were evaluated using the following datasets and architectures:
- CIFAR-10: Paired with ResNet9, ResNet18, and ResNet50 models to generate large-scale empirical NTK matrices.
- MNIST: Paired with a MobileNet architecture.
- Synthetic Spatial Data: Used to test FLODANCE's generality on non-neural kernels via a multi-output Matérn kernel Gaussian Process.
Key Insights and Ideas
- The Determinant-GP Error Connection: The paper’s core theoretical contribution bridges pure linear algebra and statistical learning theory. Showing that successive determinant ratios mirror the prediction error of a Gaussian process allows researchers to exploit well-studied neural scaling laws for matrix computations.
- Bypassing the Memory Wall Exactly: MEMDET proves that exactness does not have to be sacrificed due to hardware limitations. By carefully scheduling block updates, disk storage can seamlessly substitute for RAM without increasing the total FLOP count.
- Global Scaling Beats Local Approximation: Standard approaches like Stochastic Lanczos Quadrature (SLQ) try to approximate the full matrix spectrum locally, which fails when matrices are ill-conditioned. FLODANCE succeeds because it models the global scaling behavior of the determinant as data size grows.
Key Results
- Unprecedented Scale: The authors computed the first-ever exact log-determinant of a full empirical NTK matrix at scale (a dense $500,000 \times 500,000$ matrix for ResNet50 on CIFAR-10). This required 2 TB of storage and ran for 244 hours on an NVIDIA Grace Hopper GH200 GPU using MEMDET to establish a ground-truth baseline.
- Massive Speedups with FLODANCE: For the same ResNet50 matrix, FLODANCE reduced the wall-clock time from 13.8 days (exact MEMDET) to just 1.5 hours—a massive speedup—while achieving an incredibly low relative error of 0.02%.
- Failure of Existing Approximations: Traditional state-of-the-art methods like SLQ exhibited a massive 55% relative error on the large-scale NTK matrix, proving highly inaccurate for these types of ill-conditioned matrices.
Limitations and Future Work
- Burn-in Period Requirement: The power-law scaling relationship requires a short "burn-in" phase (typically discarding the first <500 terms) before stabilizing. This is caused by the sudden appearance of very small eigenvalues early in the data sequence, which can skew initial regression fits if not accounted for via cross-validation.
- Block Pivoting Constraints: While LU block decomposition worked well without block pivoting on the empirical NTKs studied, highly unstable or non-symmetric matrices might require block pivoting, which would complicate MEMDET's deterministic disk-scheduling order.
- Future Directions: The authors plan to extend these principles to extract more refined spectral information from sub-blocks and apply blockwise decompositions directly to large-scale Jacobian matrices, eliminating the need to explicitly form the $JJ^\top$ product entirely.
Summary updated