Determinant Estimation under Memory Constraints and Neural Scaling Laws

Siavash Ameli, Chris van der Heide, Liam Hodgkinson, Fred Roosta, Michael W. Mahoney

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:

  1. 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.
Figure 1: Schematic diagram of MEMDET illustrating the efficient block processing order for LU decompo- sition (Algorithm D.1, left panel) and LDL/Cholesky decompositions (Algorithm D.2, Algorithm D.3, right panel). The detailed ordering strategy is described in Appendix D.1.
  1. 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.
Figure 2: Demonstration of a scaling law for the ratios of successive determinants det(Kn)/ det(Kn−1) (Assumption 1) for the empirical neural tangent kernel Gram matrix of a trained ResNet50 network on CIFAR-10 with n = 50,000 datapoints.

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

Abstract

Calculating or accurately estimating log-determinants of large positive 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 $\sim$100,000$\times$ 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.
BibTeX
@inproceedings{ameli2025determinant,
  author = {Siavash Ameli and Chris van der Heide and Liam Hodgkinson and Fred Roosta and Michael W. Mahoney},
  title = {{Determinant Estimation under Memory Constraints and Neural Scaling Laws}},
  booktitle = {International Conference on Machine Learning},
  year = {2025},
  url = {https://openreview.net/forum?id=nkV9PPp8R8},
}
Figure