Determinant Estimation under Memory Constraints and Neural Scaling Laws

We thank the reviewer for their careful review of our paper and positive feedback on our work. We acknowledge that some points need clarification and aim to do so below.

Regarding the implicit value of $m=10$: this is the number of classes used in all the classification datasets we used in experiments. We will state this explicitly in Section 4, as we understand the confusion. We further thank the reviewer for their suggestion regarding plot and variable labeling, as well as algorithm naming. We have included these improvements and corrections in the updated version of the paper.

Regarding Section D: this is included as algorithmic analysis of MEMDET. Many of these were conducted for our own benefit to choose appropriate block sizes, and to predict how long the computations would take. MEMDET is an exact algorithm (with no approximation occurring) and was required as a baseline for our experiments, since we could not fit the full NTKs into memory on the machines we were using. We believe that exact methods will always have a place, and so hope the information in Appendix D will be useful to others.

To clarify the difference between algorithms: Pseudo-NTK summarizes the data by summing over rows and columns $m\times m$ block, then dividing by $m$. This gives a good approximation with respect to the operator norm. However, it should not be expected to give refined determinant estimates. Both SLQ and FLODANCE build their approximations from cheaper quantities. In the case of SLQ, matrix vector products are used in a Monte Carlo approximation. This gives a low bias estiamte with high variance, particularly when the condition number of the matrix is large. On the other hand, in FLODANCE we use extrapolation from matrix minors. This gives a low variance estimate in our experience (see http://anonymous.4open.science/r/memdet-E8C1/notebooks/scale_law_pred_uq.pdf), while the magnitude of the bias is unclear, and subject to the stationarity of the process in the training region (see http://anonymous.4open.science/r/memdet-E8C1/notebooks/stationarity.pdf). We agree that including more details of these methods will improve our work, and have added a short description in the main body, and a more in-depth section in the appendix of the updated version of the document.

Please let us know if anything else needs verification or clarification, as we are eager to engage further if necessary to improve our work.

We thank the reviewer for their constructive feedback and positive review of our work. The reviewer has raised a few points that deserve addressing, and we believe that doing so will improve our work.

The first of these is our dependence on the scaling law assumption. In the submitted version of the document, we provided criteria on the kernel which guarantees the scaling-laws hold in Appendix F. However, these are technical conditions, and their satisfaction is non-trivial to check (although we have discussed some possible verification in the response to Reviewer zrLg). This means that like most of the literature exploring scaling laws, we are relying on empirical behavior to check that the scaling laws are satisfied. To this end, http://anonymous.4open.science/r/memdet-E8C1/notebooks/stationarity.pdf contains a figure that compares the ratio of successive determinants to the fitted scaling law. Note that the log-scale on the $y$-axis turns this into a residual plot. These residuals are approximately normally distributed, which is evidence that Assumpsions 1 and 2 are satisfied. This plot has been included in the updated version of our document, along with discussion.

Regarding the focus of our numerics on the NTK: this was simply done because these matrices are known to be a particularly difficult class of kernel matrices to work with. For modern neural networks, the corresponding kernels are non-stationary, and the matrices tend to be highly ill-conditioned and very large, often not being feasible to compute explicitly: hence the need for our algorithm. We believe that this makes NTK matrices particularly useful examples to highlight the utility and efficacy of our method. However, we do recognize that other Gram matrices are commonly used in machine learning applications. In particular, we computed the Gram matrix associated to the linear model of coregionalization [1], with 10 outputs and a Matern kernel over 10,000 data points. Plots demonstrating the performance of FLODANCE on this dataset, with experimental details, can be found at http://anonymous.4open.science/r/memdet-E8C1/notebooks/matern.pdf . We have included this experiment in the appendix of an updated version of our work.

Other reviewers have also drawn attention to the lack of the distinction between our methods and their competitors. To this end, we have included a brief section in the the appendix outlining the stochastic Lanczos methods, as well as the Pseudo-NTK. We believe this will help our exposition, in addition to a brief higher-level summary in the main document.

Thank you for your suggestions regarding Table 2. An updated version of this table containing relative error can be found at http://anonymous.4open.science/r/memdet-E8C1/notebooks/relative.pdf . We remark that MEMDET is an exact method that allows for determinant computation of large matrices that do not fit into memory. It achieves this through block-decompositions, relying on an underlying algorithm (LDL$^\top$, LU, or Cholesky) that is amenable to this type of decomposition. As such, the use of MEMDET in our FLODANCE approximations reduces to LDL$^\top$, since the training sample is small enough to fit in memory. We have emphasised this in the final version of the document.

Please let us know if anything else needs verification or clarification, as we are eager to engage further if necessary to improve our work.

[1] https://doi.org/10.1007/BF02066732

We thank the reviewer for their constructive feedback and positive review of our work. This work is indeed part of a broader active research program aimed at providing computational tools for estimating linear algebraic quantities at scale. We will make this more clear in the final version of our paper, and cite the related work for hyperparameter selection that you suggested.

Regarding the assumptions underlying the scaling law behavior, we acknowledge that these technical assumptions have been identified but not verified. To do so for the empirical neural tangent kernel matrix may not be realistic, however, we have come across [1], which examines the spectral decomposition of the analytic NTK (an approximation of the empirical variant we consider) on the sphere. In [1, Theorem 4.8], it appears that our Assumption F.1 is verified over a bounded eigenbasis (Assumption F.2), and Assumption F.3 is automatically satisfied as we consider $f_p^\ast = 0$. If desired, we are happy to include this discussion in the final manuscript. More generally, however, the theory is instead used to establish plausibility of the scaling law, since there is a well-characterized class of kernels for which these assumptions hold. We then use the scaling laws as an empirical theory in much the same way that others do in the ML literature.

In terms of this empirical behavior, a plot of the residuals of the successive $\log$-determinant increments after removal of the scaling law can be found at http://anonymous.4open.science/r/memdet-E8C1/notebooks/stationarity.pdf. This figure demonstrates that these values are approximately normally distributed, empirically validating the scaling law in Assumption 1 (as well as Assumption 2). This figure is included in the updated version of our work, and clarification has been added regarding the distinction between this empirical verification and the assumptions stated in Appendix F.

Regarding downstream applications, we note that the $\log$-determinant is typically only one of multiple terms appearing in quantities of interest. For this reason, we believe it is premature to include studies computing these partial quantities as approximations, until we have developed the toolkit to treat the other terms.

The non-asymptotic terms that appear in the exponent model sublinear behavior that occurs in the pre-limit. To be clear, they model the function $\nu = \nu(n)$ by allowing for subsequent terms beyond the constant in its Laurent series. These terms were included for flexibility as we found that they do improve accuracy for matrices at the scale of our experiments. However, they are not strictly necessary: when the exponent is treated as a constant in $n$, we found that our method still outperforms SLQ (see http://anonymous.4open.science/r/memdet-E8C1/notebooks/relative.pdf for a version of Table 2, updated to display relative error for reviewer ikyx). Errors and cost also now appear in an updated version of Table 1 found at http://anonymous.4open.science/r/memdet-E8C1/notebooks/comparison.pdf . Algorithm 1 has also been updated to explicitly state how the terms are computed.

Please let us know if anything else needs verification or clarification, as we are eager to engage further if necessary to improve our work.

[1] Murray, M., Jin, H., Bowman, B., & Montufar, G. (2023, February). Characterizing the Spectrum of the NTK via a Power Series Expansion. In International Conference on Learning Representations.

We would like to thank the reviewer for taking the time to review our paper, and for their constructive feedback. Regarding general applicability of our methods: we stress that MEMDET computes the exact (64-bit) determinant, and is a general method that works for arbitrary matrices. On the other hand, our neural scaling law approach, FLODANCE, is only suggested to work for Gram matrices satisfying Assumption 1. In our writeup and experiments, we focus on NTK matrices, since they are known to be a particularly difficult class of kernel matrices. Other algorithms (e.g. SLQ) already perform very well on better behaved, more traditional classes of matrices. For modern neural networks, the corresponding NTK kernels are non-stationary, and the Gram matrices tend to be highly ill-conditioned and very large, often not being feasible to compute explicitly: hence the need for our algorithm. We believe that this makes NTK matrices particularly useful examples to highlight the utility and efficacy of our method. However, we do recognize that other Gram matrices are commonly used in ML applications. In particular, we computed the Gram matrix associated to the linear model of coregionalization [1], with 10 outputs, and Matern kernel over 10,000 data points. Plots demonstrating the performance of FLODANCE on this dataset, along with experimental details, can be found at http://anonymous.4open.science/r/memdet-E8C1/notebooks/matern.pdf .

As the reviewer has pointed out, the $\log$-determinant often appears as one term in more elaborate quantities of interest. Examples of this are the quadratic-form term in the $\log$-marginal likelihood of a Gaussian process (along with their gradients for the purposes of training), and the curvature term that appears in the IIC. Estimating these quantities is a clear goal. However, the other terms appearing in these quantities are highly challenging to estimate as well, requiring separate novel techniques that we believe will each be of independent interest. This work is part of a broader research program under active development, and the current submission already contains two novel techniques for computing and estimating a crucial term, with corresponding software. We believe this strikes an appropriate balance of utility, impact and digestibility for an outlet such as ICML.

To clarify the sensitivity of FLODANCE to subsample size and seed subset, we have conducted the following experiments. First, http://anonymous.4open.science/r/memdet-E8C1/notebooks/param_selection.pdf shows the effect of the number of training samples on prediction accuracy, and describes the experimental setup. As is to be expected, the general trend is that using more samples results in better prediction. There is a natural tradeoff between computation time and accuracy that is up to the practitioner to determine.

Second, we tested the sensitivity of the estimate to the training sample. To this end, we sampled an ensemble of 15 submatrices of the NTK for ResNet-50 trained on CIFAR10. Each submatrix contians 10,000 datapoints with 10 classes, forming a $100,000\times100,000$ NTK matrix. Experimental details and plots can be found at http://anonymous.4open.science/r/memdet-E8C1/notebooks/scale_law_pred_uq.pdf

Third, we upgraded our computations on both architectures to use the full CIFAR-10 dataset with $(n = 50,000)$, resulting in NTK matrices of size $(m = 500,000)$. For ResNet9, we also recomputed log-determinants using 64-bit precision via MEMDET. The updated results are provided in http://anonymous.4open.science/r/memdet-E8C1/notebooks/scale_law_fit.pdf (was Figure H.1) and http://anonymous.4open.science/r/memdet-E8C1/notebooks/scale_law_pred.pdf (was Figure 4). The 64-bit computation for ResNet50 is underway and will be completed in a few days, with updated results included in the final version.

We note that while the new plots are derived from the same NTK kernel and methodology, their appearance differs from earlier versions due to a technical adjustment. To improve quantization in 32-bit precision, we had previously scaled the NTK matrices, giving an additive term proportional to $n$ in the $\log$-determinant. Hence, the curves differed from the current ones by a linear function of $n$. This shift does not affect the fitting behavior or predictive quality, but it alters the shape of the curve. In the updated 64-bit computations, this scaling was no longer necessary, resulting in cleaner and more interpretable visualizations without any transformation applied.

As is evident by these additional studies, FLODANCE is quite robust to these factors. We thank the reviewer for suggesting these experiments, as we believe their inclusion in the final version of the document will improve the quality of our work. Please let us know if anything else needs verification or clarification, as we are eager to engage further if necessary to improve our work.

[1] https://doi.org/10.1007/BF02066732