Takeuchi's Information Criteria as Generalization Measures for DNNs Close to NTK Regime
Authors: Hiroki Naganuma
Taiji Suzuki
Rio Yokota
Masahiro Nomura
Kohta Ishikawa
Ikuro Sato
Venue: ICLR 2022 Submitted (2022)
Keywords: Generalization
correlation
experiments

Abstract: Generalization measures are intensively studied in the machine learning community for better modeling generalization gaps.  However, establishing a reliable generalization measure for statistical singular models such as deep neural networks (DNNs) is challenging due to the complex nature of the singular models. 
We focus on a classical measure called Takeuchi's Information Criteria (TIC) to investigate allowed conditions in which the criteria can well explain generalization gaps caused by DNNs. In fact, theory indicates the applicability of TIC near the neural tangent kernel (NTK) regime.
Experimentally, we trained more than 5,000 DNN models with 12 DNN architectures including large models (e.g., VGG16) and 4 datasets, and estimated corresponding TICs in order to comprehensively study the relationship between the generalization gap and the TIC estimates. 
We examine several approximation methods to estimate TIC with feasible computational load and investigate the accuracy trade-off. Experimental results indicate that estimated TIC well correlates generalization gaps under the conditions that are close to NTK regime. Outside the NTK regime, such correlation disappears, shown theoretically and empirically. We further demonstrate that TIC can yield better trial pruning ability for hyperparameter optimization over existing methods.

Under review as a conference paper at ICLR 2022
TAKEUCHI'S INFORMATION CRITERIA AS GENERALIZATION MEASURES FOR DNNS CLOSE TO NTK REGIME
Anonymous authors Paper under double-bling blind review
ABSTRACT
Generalization measures are intensively studied in the machine learning commu- nity for better modeling generalization gaps. However, establishing reliable gen- eralization measure for statistical singular models such as deep neural networks (DNNs) is challenging due to the complex nature of the singular models. We fo- cus on a classical measure called Takeuchi's Information Criteria (TIC) investi- gate allowed conditions in which the criteria can well explain generalization gaps caused by DNNs. In fact, the theory indicates the applicability of TIC near the neural tangent kernel (NTK) regime. Experimentally, we trained more than 5,000 DNN models with 12 DNN architectures including large models (e.g., VGG16) and 4 datasets, and estimated corresponding TICs in order comprehensively study the relationship between the generalization gap and the TIC estimates. We examine several approximation methods to estimate TIC with feasible computa- tional load and investigate the accuracy trade-off. Experimental results indicate that estimated TIC well correlates generalization gaps under the conditions that are close to NTK regime. Outside the NTK regime, such correlation disappears, shown theoretically and empirically. We further demonstrate that TIC can yield better trial pruning ability for hyperparameter optimization over existing meth- ods.
INTRODUCTION
Deep neural networks (DNNs) have been exhibiting great generalization abilities in many applica- tions, but the mechanism of the generalization has not been fully understood yet (Neyshabur et al., 2014: Zhang et al., 2016; Recht et al., 2019). Establishing reliable generalization measure is an important research topic for generating good model from limited data resources, including an ap- plication of hyperparameter search. Many attempts (Arora et al., 2018; Wei & Ma, 2019; Neyshabur et al., 2018) have been taken to better understand the generalization phenomenon in deep learning models from theoretical points of view. From empirical points of view, there have been intensive studies (Keskar et al., 2016; Liang et al., 2019; Bartlett et al., 2017) in search of learning conditions that likely yield high model performance.
Work by (Jiang et al., 2019) indicated that measure that includes both hessian H H0) and covari- ance (0) defined from the loss and the network parameters near a local minimum may poten- tially show good correlation with generalization performance. Another study indicated that use of only a single measure, either Hessian (0)) or covariance C()), fails to capture the generalization performance (Novak et al., 2018a).
The generalization gap inherently stems from a discrepancy between the empirical and true data distribution. A minimizer of the empirical loss will be affected by the noise due to finite number of samples and by the form of the loss landscape near the minimum. The former can be characterized noise (C()) and the latter as curvature (H (0)).
Taking these findings into account, we sought to model the generalization gap, then found that a classical information criterion called Takeuchi's Information Criteria (TIC) (Takeuchi, 1976) ex-
(0) and (()) defined in equation

---

Under review as a conference paper at ICLR 2022
presses generalization gap in the neural tangent kernel (NTK) regime. TIC has the following form
--Ell(y f(, (2, (H(O) (
(1)
Criteria
Mean Empirical Erro
Estimated Bias Term
where is smooth function over 0 Rd with input and target y, and is the negative log- likelihood, also denoted as loss function. The first term on the right-hand side is the log-likelihood, which takes the expectation over an empirical data distribution (24, 3/3 p. For the later discus- sion, we use 0 minimizes the empirical loss; i.e., i = arg ming Epp ( [[ f(x, 0))] and 0" as the parameters that maximizes the likelihood with respect to the true data distribution (ar, v) pt i.e.
0* arg mingEE, f(r, 0))]
For DNN of practical size, exact computations of the matrices H (0). C(0) are nearly infeasible due to large dimensionalityy To make the computation feasible, we adopted a strategy of using shared components of the matrix to estimate TIC with fewer computations, based relationship among matrices such as H (0), C(0), and Fisher Information Matrix F(0). To further reduce the computational costs for the bias term, we examined methods using approximations and lower bounds so that TIC estimations for DNNs of practical sizes are feasible.
In this work, make the following contributions:
We provide empirical and theoretical evidence that TIC is highly correlated with generalization gap of DNNs that are close to NTK regime, despite the fact that TIC not originally designed for singular model such as general DNNs.
We conduct comprehensive experiments in which more than 5,000 models, including ones close to NTK regime, with totally 12 DNN architectures, 4 datasets and 15 training settings are trained, and corresponding TICs are estimated with approximation techniques, to clarify con- ditions that TIC can well explain generalization gaps.
We use TIC as a threshold for pruning poorly performing trial models during hyperparameter optimization (HPO) and show that it can successfully prevent promising candidates from being pruned prematurely.
GENERALIZATION MEASURES
Generalization measures measure the generalization ability of statistical models. Typically, the generalization gap, which is defined as the difference between training loss and validation loss, is used to quantify the generalization ability.
2.1 WHICH GENERALIZATION MEASURE IS PROSPECTIVE?
To answer this question, before demonstrating the effectiveness of TIC, we highlight the develop- ment of research in this area and the motivation behind this work. For understanding generalization behavior, there are two major approaches by quantifying generalization bounds and complexity measures.
Approach of quantifying generalization bounds is pursued by theoretical groups to prove the bound of the generalization gap (Dziugaite & Roy, 2017). Although tight bounds can be proven, they are often based on assumptions that do not apply to practical DNN settings. In addition, no bounds have been shown to describe the performance of the current DNNs satisfactory level.
On the other hand, approach quantifying complexity measures, which do not necessarily certify bounds, follows the principle of Occam's 's razor and evaluates the complexity of the model. Theo- retically motivated complexity measures, including VC-dimension (Vapnik & Chervonenkis, 2015), PAC-Bayesian framework (McAllester, 1999). the norm of parameters (Neyshabur et al., 2015), are often discussed as significant components of generalization bounds, and a monotonic relationship between complexity measures and generalizations is mathematically established. In contrast, em- pirically motivated generalization measures, such as sharpness (Keskar et al., 2016), are justified by experiments and observations. In particular, for DNNs, Jiang al. (2019) have conducted exhaustive experiments to evaluate the effectiveness of generalization measures for three groups: norm-based measure, sharpness-base based measure, and moise-based measure.
2

---

Under review as a conference paper at ICLR 2022
Norm-based measure: |0]. Most of the proposed corm-based measures based on the Fisher- Rao Metric (Liang et al., 2019), which does not capture generalization well. In particular, it has been reported that spectral complexity such product of spectral norms of the layers (Bartlett et al., 2017) has a strong negative correlation with generalization. It is impossible to explain the success of DNN models with huge parameter sizes in recent years with these metrics.
metrics, such as sharp minima and flat minima (Keskar et al., 2016) and PAC-Bayesian framework (McAllester, 1999), are not only associated with intuitive understanding but also empirically show a strong correlation with the generalization gap. However, some model architectures are known show poor correlation (Dinh et al., 2017).
Sharpness-based based measure: H (Ø). Sharpness-basd
Noise-based measure: C(0). Experimental results show that generalization measure based on gradient has potential (Jiang et al., 2019). In particular, in their experiments, they observe that the variance of the gradient captures Sharpness, but they suggest that this is not good generalization measure depending on the architecture of the model.
These results suggest that studying generalization measures that can be estimated using H (0) and C()) is prospective. However, since the combination of H (0) and C(0) seen in TIC is not feasible to compute for practical DNN settings, so it was outside the scope of (Jiang et al., 2019).
2.2 INFORMATION MATRIX: ELEMENTS OF GENERALIZATION MEASURES
Previous research has highlighted information matrices such as H0) and C(0) in generalization measures DNNs. Thomas et (2020); Kunstner al. (2019) remarked that these matrices are often confused and misused, for example in the field of optimization, leading to wrong conclusions, even though these matrices play an essential role in the study of DNNs, especially in optimization (Amari et al., 2020; Martens & Grosse, 2015a), understanding implicit regularization in SGD (Wen et al., 2019; Zhu et al., 2019), and Bayesian inference (Zhang et al., 2018). Before discussing these generalization measures, it should be made clear how each of the information matrices defined.
In this paper, uncentered gradient covariance matrix is denoted as C(0). We define qe as a model distribution. Furthermore, we employ the data distributions ý and p introduced in the previous section as the empirical and true data distributions respectively. Matrices H()), C(0) and F(0) are then defined as:
Olly, f(x, 0))
H(0) E,
Rdxd
00002
al [1x, 0)) all,, 0))
C(0) Ep
RRd
00
10T
Olly,f(a 0)) olyy f(x, O() 00T
F()) Egg
E Rdxd
00
The conditions under which these matrices are equal will be discussed in detail in section 3.1. The relation between (0)) and F F(0) is often misunderstood because they both involve the outer product of the gradients but they a different distribution when computing the expectation.
As subsequent study, Novak et al. (2018a) concluded that consideration of either H C(0) alone is insufficient estimate the generalization of DNNs and that both are essential. In particular, H (0) is value that does not depend on the distribution of input data; however, as the generalization ability depends on the distribution of the data, it also natural to consider C(0). which related to noise in the gradient. Furthermore, supporting evidence of Novak et al. (2018a)² claim, Thomas et al. (2020) showed empirically the effectiveness of TIC, a generalization measure that considers both H0)) and C()) expressed by the equation 1. However, Thomas et al. (2020)'s work only experimented with very small-scale NNs because it is challenging to calculate TIC with DNNs of practical size. As matter of fact, even the ResNet-8 model used in the small-scale image classifi- cation benchmark CIFAR 10 is not feasible, as it requires nearly 200TB of memory to calculate the TIC exactly.
Remark 2.1. It should also be noted that TIC is an information criterion for regular models, not for singular models such as DNNs, and its theoretical justification in the domain of DNNs is not clear. One of the characteristics of singular models is that the Fisher information matrix is not positive definite.
3

---

Under review as a conference paper at ICLR 2022
2.3 TIC IS DERIVED AS GENERALIZATION GAP IN NTK REGIME
This section outlines the derivation of the definition of TIC in equation 1, considering the gener- alization gap of DNNs in the framework of NTK's regime. We employ the setting introduced in section I, / is a smooth function over E Rd, a parameter of the statistical model. First, we further assume that the following holds for f and 0 E F in the NTK regime. Assumption 2.1.
(AI) Global convergence: the model has only one possible solution. However, it is not required to be yo p (allowing for misspecified situation).
(A2) Asymptotic normality:
the maximum likelihood estimator 0 from the empirical data dis- tribution ş and the maximum likelihood estimator 8* in the true data distribution p satisfy asymptotic normality.
Proposition 2.1 (Generalization Gap in NTK Regime is equal to TIC).
Under the assumptions (A1) and (A2), the estimated bias b (i.e. generalization gap) when evaluating using empirical data distribution ş would then be as follows.
b = E, Egllyy fae 0)) - Ep,yy (), 0)]]
(3)
T H (H,
Where (f*) and (0*) are the Hessian and Covariance respectively with regards l over true data distribution p. However, as the true data distribution p and parameter #* which maximizes the likelihood for that data distribution are unknown, the expected value in the empirical data distri- bution P and parameter i are generally used as a consistent estimator, which is consistent with the TIC. A more detailed proof is given in Appendix A.1.2.
The bias term of TIC is formulated as Tr (H(O)-IC(()) -C())) However, since there is no guarantee that H (0) is positive definite in practice. To prevent this problem, the addition of small identity matrix, called damping, is performed as (0) = (0) + AT)_ Alternatively, consider the case where the TIC is calculated by approximation with matrix of only the diagonal components of the respective matrices, as Tr [H (()) s Tr (Haing
Remark 2.2.
In this
case, the following lower bound is given for the diagonal approximated TIC.
Tr(Caing (0)) Tr(C(()) Tr Tr(Haing (0)) Tr(H(())
Tr H ding 0 -Caiigg
ding (0)) >
(4)
Remark 2.3. We note that not all DNNs are in the NTK regime. One indicator of whether a DNN is in the NTK regime is the ratio of the number of model parameters to the number of data. In general, unconstrained DNNs are singular models, so WAIC (Watanabe, 2013) appropriate instead of TIC or AIC (Akaike, 1998), but computational cost of WAIC is way too high to perform wide range of learning experiments. Furthermore, when the loss function includes a regularization term, GIC (Konishi & Kitagawa, 1996) is technically appropriate instead of TIC, but it has disadvantage that the calculation is further complicated.
3 APPROXIMATION OF TIC
3.1 HESSIAN, GENERALIZED GAUSS-NEWTY MATRIX (GGN) AND FIM
In this section, we describe the conditions for which the Hessian, GGN, and FIM become equivalent. This equivalence can be exploited to reduce the computational cost of computing the TIC. TIC requires the computation of H (0) and C(0), but the computational cost of H is relatively high. For NNs that consist of linear, convolutional, and pooling layers, along with piecewise linear activations, the Hessian is equal to the GGN (Schraudolph, 2002). This actually holds true for most CNNs used in practice. The GGN is an extension of the Ep ((Jo)TT Jo].
matrix G(
G(0) = Ep ((oo) Ho]
(5)
4

---

Under review as a conference paper at ICLR 2022
Where y is the Hessian of Uy. far ()) and Jø is Jacobian of f(z 0) with respect to 0. Further- more, the GGN is equal to the FIM for any NN that uses the softmax cross entropy. Therefore, we can assume the following for most practical DNN problem settings.
Assumption 3.1.
(B1) Loss function: 1 is the softmax cross-entropy function
(B2) Activation function: inside f. all activation functions' second derivative are always zero, such as ReLU or the identity function.
Proposition 3.1 (H (H(O) (0) is equal F(0) through GGN).
Under the assumption of (BI) and (B2), H (0) and F F(0) are exactly equal through GGN. They are also guaranteed to be positive semi-definite.
H = G(0) F())
(6)
A more detailed proof is given in Martens (2020).
3.2 APPROXIMATION OF MATRICES AND TRACE ESTIMATION
As noted in section 2.2, information matrices are in demand for many applications, including TIC. However, for model with large number of parameters d such as DNN, it is necessary compute a matrix with size of d2 For this reason, approximation methods ranging from approximating the information matrix itself (Le Roux et al., 2007) to approximating the product of the information matrix, and the vector directly is used in optimization (Pearlmutter, 1994) and other applications. We propose the following approximation method calculate the TIC and experimentally verify the trade-off between accuracy and computation time.
Replacing (0)) in F(0) and fast estimation of F()) in Monte-Carlo sampling. As shown in equation 6, (0) can used in place of (0) under the (B1) and (B2) assumption. We use this property to speed up the calculation by simultaneously computing C(0) and F(0), which have a common term. Furthermore, since the number of classes for the classification task is 10 in MNIST and 100 in CIFAR100 100, the computational cost of F(0) is huge,
approximate F()) using Fmmee(C ()), which is a Monte Carlo approximation. Martens & Grosse (2015b) use m = in the practical setting. We follow this setting Fi (0) for the approximation of F(0).
Block Block-diagonalizztton and diagonalization. In NTK Regime, the correlation between layers is ignored, so block -ian-aaaaanziztioonnn is reasonable approximation method. The computational complexity can be reduced from (dd)) to )² by the block-diagonal approximation. Diago- nalization is a simple approximation; it ignores the correlation between DNN units. It has been reported be sufficient for some applications (Singh & Alistarh, 2020). can also be calculated as a sum-of of-ouuuctss operation on vectors rather than matrices, significantly reducing computa- tional complexity and memory consumption. In particular, by using the diagonal approximation, the inverse calculation of H (0) can be reduced from ((d)) to the order of (dd).
Lower bound of diagonalization. As shown in equation 4, by giving the lower bound of the diagonal approximation, it is possible to calculate the trace of each matrix by calculating and dividing the trace of each matrix without calculating the diagonal component of the matrix. In other words, is possible to calculate without considering whether F(0) is positive definite.
Hutchinson's 's method for estimating Tr(H(O) in f'ast. Furthermore, rather than approximating the matrix itself, we will introduce a method to accelerate the computation of its eigenvalues and trace. For optimization in deep learning, it is enough to calculate not the Hessian itself but the product of the Hessian and an arbitrary vector (Hessian vector product; Hvp). In order to compute Hyp exactly, Pearlmutter (1994) proposed fast algorithm to compute Hvp in NNs during back- propagation. This Hvp can be applied to non-optimization applications, such as approximating Tr( Tr(H H (0)) (Avron & Toledo, 201 1). Hutchinson's 's method (Hutchinson, 1989) approximates the expectation value of the quadratic form of the Hessian and the Rademacher random vector (cach element takes 1 or -1 with probability 1/2).
2/ is the number of parameters for the layer with the largest number of parameters in the network.
5

---

Under review as a conference paper at ICLR 2022
(W') Wittrthae Lunder
(a): THIl Tr(F) (b): Exact block diagonal
(c): Exact diagonal
(d) Exact vs lower bound
Figure I: Approximation comparison experiments in small-scale setting. (a) shows equality of
Tr(H) and Tr(F). (b), (c), and (d) respectively compare how different the approximation method
of TIC estimation is from the exact case. All full results are shown in Appendix D.2.2.
EXPERIMENTS
4.1 OVERVIEW
The goal of our paper elucidate the correlation between the TIC estimates and the generalization gap. To make our study of TIC as comprchensive as possible, we trained on 4 different data sets and 12 different DNN models. Using these combinations, we searched for hyperparameters for each of the 15 problem settings and evaluated the parameters of the trained models. By comparing these results, we can observe how the effectiveness of TIC changes with the model and problem settings. In our experiments, the bias term of TIC is estimated by using validation data, and the generalization gap is the absolute value of the difference loss between training and test data, using all of the data in each dataset, not just part of the data. The problem settings for the experiment can be divided into two main categories along with dataset and model size as table 1.
Table I: 2 Categories of experimental settings. Problem settings with $ and * indicate to use linear neural network and to be considered almost in NTK regime respectively. For hyperparameter search, we conduct Bayesian optimization for all experimental settings. We describe the further detailed configurations of hyperparameters and other settings for the experiment in Appendix C.2. The remaining experimental settings are explained in Appendix C.
Category
TIC Estimates
Problem Setting: Dataset & Model TinyMNIST on 2-NN w/o SC
Ratio: d/n
Small-scale
Exact and Approx. (Block Diag, Diag and Lower Bound)
0.09
DM Model<50KB
TinyMNIST on 3-NN w/o and w/ SC
0.02
: TinyMNIST on 3-LNN w/o and w/ SC
0.02
MNIST on 6-NN w/o and w/ SC
2.50
* MNIST on 6-LNN w/o and w/ SC
2.50
Practical-scale
Approx. (Diag and
* MNIITT on Simple CNN
268.92
Data>>20MB Model>-05MBB
** CIFAR10 on 6-LNN w/o and w/ SC
8.72
Lower Bound)
* CIFAR10 on ResNet8 w/o BN
122.65
CIFAR10 on VGG16 w/o BN
3357.53
* CIFAR100 on ResNet8 w/o BN
122.65
In particular, ResNet-8, which is commonly used as a benchmark for training CIFARIO, requires over 200TB of memory to compute exact (0). Even state-of-the-art GPU NVIDIA A100 is impractical since has only 80 GB of device memory. Hence, as small-scale experiment, we use small dataset called TinyMNIST to limit the size of the DNN model, which is a resized version of the MNIST image, which reduces the dimension of the input layer of DNN, to compare our approximation method and exact calculation. As practical-scale experiments, we evaluated the real-world datasets and DNN models. We used diagonal approximations and their lower bound approximations estimate TIC.
4.2 SMALL SCALE EXPERIMENTS: COMPARING APPROXIMATION AND EXACT
As small-scale experiments, we trained Tiny MNIST on 5 experimental settings: 3-LNNs and NNs, each w/ and w/o SC, and a wide model, 2-NNs without SC. Afterwards, we evaluated the approx- imation of Tr (H (((())
C()),, the bias term of TIC, for (() and C(0), using block-diagonal
N2-NN and 3-I.NN denote 2-1 Layrr Non Linear Neural Network and 3-1 3-Layer Linear Neural Network respec- tively. SC denotes Skip-Connectian
*BN denotes Batch Normalization.

---

Under review as a conference paper at ICLR 2022
Gevealiation en Oayia TEC (M DeeM0iee
Gevenforae Oapsr Inraee Demut NINSST
Coarr knilen dap batraa
20d weoled
TEP Soloeie (SrVTP))
(a) TiNSTTIST
(b) MNIST
(c) CIFARIO and CI
Figure 2: Correlation between the generalization gap and the TIC estimates. (a) is a problem setting outside the NTK regime, where the correlation between TIC and the generalization gap weak; (b) (c) are a problem setting close to the NTK regime, where the correlation is stronger. All full results are shown in Appendix D.
Pearson's Coefficient vs d/n Ratio
1.0
Pearson's Coefficient
0.5
0.0
TinyMNSST on 2-NN
MNIST on 6-NN
X CITARIO on 6-NNN
TeyMNIST on
MNIST on 6-NN SC
CIFARIO 6-1
0.5
TayMNIST 3-NN W/
MNIST 6-LNN
CIFARIO VGGi
TiyyMNIST on 3 3-NNN
MNIST on 6-1NN SC
X
CITARIO on ReNNett wi DN
ThyMNIST on S-NNN SC
MNIST on SimpleCNN
CIFARI00 on ResNeiR wis RN
10 -1
10
10
10
10
d/n Ratio
Figure 3: Relationship between Pearson's 's Correlation (generalization gap and TIC estimates), and d/n. It should be noted that the correlation between the TIC estimates and the generalization gap is high in regions with large d/n, which are considered to be close to the NTK regime. All full results of its value and other metric's Spearman's 's Correlation and Kendall's Coefficient result including are shown in Appendix D.
approximation, diagonal approximation, and its lower bound. Furthermore, as mentioned in equa- tion 6, for the purpose of speeding up the process, also estimate TIC using F(0), which shares the same elements to be calculated as C(0) as an alternative.
Remark 4.1. It should be noted that the above five settings are different from the situation of NTK, since d < p. However, we observed that the estimation of TIC was effective for LNNs.
First, we show the results of our experiments on the quality of the approximations. In general, from the exact computation to the block-diagonal approximation, i.e., the approximation which ignores the correlation between layers, we can confirm that the value and the rank correlation are kept. As for the LNN, the rank correlation is maintained for the block-diagonal approximation, the diagonal approximation, and its lower bound, though the value fluctuates. On the other hand, in the case of NN w/ SC, we confirmed that the rank correlation is maintained between exact and block-diagonal approximation, between diagonal approximation and its lower bound. These results show that LNN or NN with more layers and SC has trend of the higher approximation quality.
Then we explain the correlation between the TIC estimates and the generalization gap. We observed that LNN is in the effective regime of TIC and has a high correlation with the generalization gap in all approximations. For NNs, similarly high correlations were observed for the models w/ SC. For the 3-NN w/o SC, the results were such that the inverse correlation was observed case. In the case of 2-NN, the approximate correlation was also collapsed, resulting in no correlation with the generalization gap.
in the exact
7

---

Under review as a conference paper at ICLR 2022
Conresation beturen TX: Eaimotes and izatin Cap is Training Process: MNISI on & LNN w/ SC
Conclltion hetworr TIC Fximmrios and Generiizaiion Coep
Training Process: CIFARUU ResNe8
45
40
Generalizttinn Cap
46
10
10
50
26
40
13
16
L1+110 TX(CTTAF)
13%10
10"
Tr(CYTHF)
(a) MNIST on 6-LNN
(b) CIFARIOO ResNet-8
Figure 4: Correlation between the generalization gap and the TIC estimates in training process. The color bar represents the number of epochs of trained models. All full results are shown in Appendix D.3
From these results, we conclude that the performance of TIC on the correlation with the general- ization gap is higher for NN models with more layers and SC, and the correlation does not change significantly before and after the approximation.
4.3 PRACTICAL SCALE EXPERIMENTS: CORRELATION GENERALIZATION GAP AND TIC LOWER BOUND, TIC WITH DIAGONAL APPROXIMATION
As practical-scale experiments, we experimented with the problems where d >> which is con- sidered to be NTK's Regime. Contrary small-scale experiments, we used MNIST, CIFARIO, and CIFAR100 100 datasets to evaluate practical settings.
First, we show the case of MNIST. The settings of LNN show a strong correlation with the gen- eralization gap in the lower bound approximation case of the NN model, a strong correlation with the generalization gap is observed, unlike in the small-scale setting. Furthermore, in the case of NN and LNN w/ SC, it has less variance and shows a stronger correlation with the generalization gap. In the Simple CNN case, the correlation with generalization gap is weaker than in previous cases but still shows correlation. Also, there is correlation with the generalization gap in the case of the value Tr (H)),), Tr (F(O)), Tr (C(0)) itself respectively. Detailed experimental results are shown in figure 13 in the Appendix D.3.
well as in the small-scale experiment. In the
In the cases of CIFARIO and CIFARI00 both the measures using lower bound and the diagonal approximation show high correlation with the generalization gap. For LNNs, the correlation is more linear in the case w/ SC. For VGG16 and ResNet8, the correlation is not as good as for LNN, but confirmed the effectiveness of TIC in NTK's regime. Furthermore, no correlation was found between the generalization gap and trace itself, respectively. These trace values have different patterns depending on the network. and it was found that this single factor alone is insufficient for estimating the generalization gap.
Remark 4.2. It should be noted that TIC estimates captured the trend of the generalization gap in the training process as shown in figure 4.
4.4 CALCULATION RUNTIME MEASUMENT EXPERIMENTS
Our runtime measurement experiments were run on an NVIDIA Tesla V100 16GB GPUs, with an average of 10 trials each. Significant speedup was achieved by approximating the shape of the matrix, replacing (0) by F(0). and Monte Carlo estimation of F(0), as shown in 3. Even in the case of small-scale problem setting, the diagonal approximation with F(0) and C(0) is 50 times faster than the exact version, while maintaining the rank correlation with H(0) and C(0). However, since the number of parameters the small problem setting is at most 720, and VGGI6 has 186,530 times as many parameters, the effect of increasing the computational order from (dd)
to (d) is more significant in the large-scale problem setting. The full details are shown in Appendix D.4. Notably, this speedup by using F F(0) and C(0) set instead of H (0) and C()), and the method of approximating the matrix form to drop the computation order dramatically reduces the computation time.
8

---

Under review as a conference paper at ICLR 2022
Valddnioo Ine0
Validation
Valibation
1.39
1.2
0.23
120
075
730
190
331
100
6.00
130
Spoch
Eguch
Epoch
(a) All Trials without Pruning
(b): SHA Pruning using Validation Loss
(c): SIIA Pruming using TIC
Figure 5: A comparative experiment using TIC as an evaluation value for pruning with SHA
in HPO for training of CIFARIO on ResNet-8: (a) shows the case where all hyperparameter candidates are trained to the end without pruning. (b) shows the case where pruning is performed based on validation loss as a baseline. (c) shows the pruning method using TIC. In the figure, all the legends on the right side show the trials with different hyperparameters. and the final generalization performance (validation loss) to be reached is in descending order. The 1st place trial is shown in dark purple and the 3rd place in light purple.
5 APPLICATION TO HYPERPARAMETER OPTIMIZATION
In previous sections, we have demonstrated that TIC is a reasonable estimator of the generalization gap that is also effective in the training process and can be computed fast. Motivated by these, in this section, we employ the TIC values on the training processes to accelerate hyperparameter opti- mization (HPO). HPO is essential task to achieve good performance in wide range of machine learning algorithms (Feurer Hutter, 2019). In particular, the performance of DNNs depends signif- icantly the selection of the hyperparameterss, such learning rates, weight decay, and momentum (Lucic et al., 2018; Henderson et al., 2018; Dacrema et al., 2019).
The Successive halving algorithm (SHA) (Jamieson & Talwalkar, 2016) shows promising perfor- mance in HPO by utilizing the iterative structure of DNNs. SHA prunes unpromising hyperparame- ters at early stage by utilizing not only final loss but also losses training process. The validation loss obtained by the hold out method is usually used as the intermediate loss for SHA. However, the validation loss is often numerically unstable, as shown in Figure 5.
To achieve stable optimization in SHA. we apply the TIC values for the intermediate loss. One advantage using TIC that can take into account the variance as bias term equation 1, which was not taken into account in the validation loss obtained by the hold out method. In particular, TIC known to be asymptotically close to leave-one-out cross-validation (LOOCV) (Stone, 1977), and is superior to Hold-Out in terms of the order of estimates error. Details are given Appendix B. We conduct an experiment to investigate the effectiveness of using the TIC values SHA. Figure shows the result of the experiment. The TIC values with the proposed approximation method can select 1st top trial, while the traditional method (SHA + the validation loss obtained by the hold out method) selects 3rd top trial.
CONCLUSION AND DISCUSSION
This study conducted a comprehensive experiment and observed that the TIC approximation method captures the generalization gap, even in the practical DNN setting close to the NTK regime. We have shown that the generalization gap could be captured in the training process, even if the model is not completed to train. Based on these results, we tested the validity of using TIC as an assessment value for HPO branch pruning and confirmed valid case. It is challenging to establish theory to discuss in the active regime (outside of the NTK regime) for future work. Especially, WAIC can handle singular models and applied to DNN: the difficulty arises for calculation; thus, it is required to have an approximation method. Still, is necessary to bridge the theory of DNN for the validity of the approximation.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Hirotugu Akaike. Information theory and an extension of the maximum likelihood principle. In Selected papers of hirotugu akaike, pp. 199-213. Springer, 1998.
Shun-ichi Amari, Jimmy Ba, Roger Baker Grosse, Xuechen Li, Atsushi Nitanda, Taiji Suzuki, Denny Wu, and Ji Xu. When does preconditioning help or hurt generalization? In International Conference on Learning Representations, 2020.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. In International Conference on Machine Learning, pp- 263-263. PMLR, 2018.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. arXiv preprint arXiv: 11955, 2019.
Haim Avron and Sivan Toledo. Randomized algorithms for estimating the trace of an implicit sym- metric positive semi-definite matrix. Journal of the ACM (JACM), 5802):133,,
Peter I. Bartlett, Dylan Foster, and Matus Telgarsky. Speccrally-norrmaiized margin bounds for neural networks. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 0241-62500 2017.
Dami Choi, Christopher J Shallue, Zachary Nado, Jaehoon Lee, Chris J Maddison, and George Dahl. On empirical comparisons of optimizers for deep learning. arXiv preprint arXiv: 191000546,, 2019.
Maurizio Ferrari Dacrema, Paolo Cremonesi, and Dietmar Jannach. Are really making much progress? a worrying analysis recent neural recommendation approaches. In Proceedings of the 13th ACM Conference Recommender Systems, pp. 101-109,
Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize for deep nets. In International Conference Machine Learning, pp. 1019-1028. PMLR, 2017.
Gintare Karolina Dziugaite and Daniel M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Proceedings of the 33rd Annual Conference on Uncertainty Artificial Intelligence (UAI), 2017.
Matthias Feurer and Frank Hutter. Hyperparameter Optimization. In Automated Machine Learning. pp. 3-33. 2019.
Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger. Deep Reinforcement Learning that Matters. In Thirty-Second AAAI Conference Artificial In- telligence, 2018
Michael F Hutchinson. A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines. Communications in Statistics-Siman Simulation and Computation, 18(3):1059-1077 1989.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: convergence and gen- eralization in neural networks. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 8580-8589, 2018.
Kevin Jamieson and Ameet Talwalkar. Non-stochastic best arm identification and hyperparameter optimization. In Artificial Intelligence and Statisties, pp. 240-248, 2016.
Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantas- tic generalization measures and where find them. In International Conference Learning Representations, 2019.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- ter Tang. On batch-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv: 1609 160.0043669 2016.
10

---

Under review as a conference paper at ICLR 2022
Sadanori Konishi and Genshiro Kitagawa. Generalised information criteria in model selection. Biometrika, 83(4):875-89) 8907,,990,11 1996.
Frederik Kunstner, Lukas Balles, and Philipp Hennig. Limitations of the empirical fisher approxi- mation for natural gradient descent. arXiv preprint arXiv: (90iv 12558, 2019.
Nicolas Le Roux, Pierre-Antoing Manzagol, and Yoshua Bengio. Topmoumoute online natural gradient algorithm. In NIPS, pp. 849-856. Citeseer, 2007.
Jachoon Lee, Yasaman Bahri, Roman Novak, Samuel Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks gaussian processes. In International Conference Learning Representations, 2018.
Jaehoon Lee, Lechao Xiao, Samuel S Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks any depth evolve as linear models under gradient descent. arXiv preprint urXiv:1902.06720 2019.
Tengyuan Liang, Tomaso Poggio, Alexander Rakhlin, and James Stokes. Fisher-rao metrie, ge- ometry, and complexity of neural networks. In The 22nd International Conference on Artificial Intelligence and Statisties, pp. 888 896. PMLR, 2019.
Mario Lucic, Karol Kurach, Marcin Michalski, Sylvain Gelly, and Olivier Bousquet. Are Gans Created Equal? Large-Scale Study. Advances in neural information processing systems, pp. 700-709, 2018.
James Martens. New insights and perspectives on the natural gradient method. Journal of Machine Learning Research, 21:1-76, 2020.
James Martens and Roger Grosse. Optimizing neural networks with kronecker-factored approximate curvature. In International conference on machine learning, pp. 1408-2417. PMLR, 2015a.
James Martens and Roger Grosse. Optimizing neural networks with frotecker-factoree approximate curvature, In International conference on machine learning, pp. 2408-2417. PMLR, 2015b.
David A McAllester. Pac-bayesian model averaging. In Proceedings of the twelfth annual confer- ence on Computational learning theory, pp. 164-170, 1999.
J Moody, The effective number of parameters: An analysis of generalization and regularization in nonlinear learning systems'. in je moody, sj hanson and lippmann (eds.), advances in neural information processing systems 4. san mateo, ca: Morgan kauffmann publishers. Neural Infor- mation Processing Systems 4, 1992.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint arXiv: 1eli:::112...4 2014.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pp. 1376-1401. PMIR, 2015.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to spectrally-normalizeed margin bounds for neural networks. International Conference on Learn- ing Representations, 2018.
Roman Novak, Yasaman Bahri, Daniel A Abolafia, Jeffrey Pennington, and Jascha Sohl-Dickstein. Sensitivity and generalization in neural networks: an empirical study. In International Conference on Learning Representations, 2018a.
Roman Novak, Lechao Xiao, Yasaman Bahri, Jaehoon Lee, Greg Yang, Jiri Hron, Daniel A Abo- lafia, Jeffrey Pennington, and Jascha Sohl-dickstein. Bayesian deep convolutional networks with many channels are gaussian processes. In International Conference on Learning Representationss 2018b.
Barak A Pearlmutter. Fast exact multiplication by the hessian. Neural computation, 611):147-160, 1994.
11

---

Under review as a conference paper at ICLR 2022
Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do imagenet classifiers generalize to imagenet? In International Conference on Machine Learning, pp. 5389-5400 PMLR. 2019.
Nicol N Schraudolph. Fast curvature matrix-vector products for second-order gradient descent. Neural computation, 14(7):1723- 1738, 2002.
Christopher J. Shallue, Jachoon Lee, Joseph Antognini, Jascha Sohl-Dickstein, Roy Frostig, and George E. Dahl. Measuring the effects of data parallelism neural network training. Journal of Machine Learning Research, 20(1 12): 1-, 2019.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In International Conference on Learning representations, 2015.
Sidak Pal Singh and Dan Alistarh. Woodfisher: Efficient second-order approximations for model compression. arXiv preprint 0r31v:2004.14340, 2020.
Mervyn Stone. An asymptotic equivalence of choice of model by cross validatio and akaike's criterion. Journal of the Royal Statistical Society: Series B (Methodological), 39(1):44-47 1977.
Kei Takeuchi. Distribution of information statistic and validity criterion of models,". Mathematical Science, (153):12-18, 1976.
Valentin Thomas, Fabian Pedregosa, Bart Merriënboer, Pierre-Antoine Manzagol, Yoshua Bengio, and Nicolas Le Roux. On the interplay between noise and curvature and its effect on optimization and generalization. In International Conference on Artificial Intelligence and Statistics, pp. 3503- 3513. PMLR, 2020.
Vladimir N Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. In Measures of complexity, pp. 11-30. Springer, 2015.
Sumio Watanabe. A widely applicable bayesian information criterion. Journal of Machine Learning Research, 14(Mar).867-897,22 2013.
Colin Wei and Tengyu Ma. Data Data-dependent sample complexity of deep neural networks via lipschitz augmentation. arXiv preprint arXiv: 2019.
Yeming Wen, Kevin Luk, Maxime Gazeau, Guodong Zhang, Harris Chan, and Jimmy Ba. Interplay between optimization and generalization of stochastic gradient descent with covariance noise. arXiv preprint arXiv:192.008..30 2019.
Halbert White. Maximum likelihood estimation misspecified models. Econometrica: Journal of the econometric society, pp. 1-25, 1982.
Greg Yang. Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation. arXiv preprint arXiv:1902.04700 2019.
Chiyuan Zhang, Samy Bengio. Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.03530 2016.
Guodong Zhang, Shengyang Sun, David Duvenaud, and Roger Grosse. Noisy natural gradient as variational inference. In International Conference on Machine Learning, pp. 5852-5861. PMLR, 2018.
Zhanxing Zhu, Jingfeng Wu, Bing Yu, Lei Wu, and Jinwen Ma. The anisotropic noise stochastic gradient descent: Its behavior of escaping from sharp minima and regularization effects, 2019.
12

---

Under review as a conference paper at ICLR 2022
APPENDIX
A PROOFS
A.1 DERIVATION OF THE TIC IN NTK REGIME
A.1.1 NTK: NEURAL TANGENT KERNEL
In general, DNNs have large number of parameters p, compared to the number of data, causing them to memorize data and hurt their generalization ability. Furthermore, all data are subjected to nonlinear transformations, which results in the problem of minimizing a nonconvex objective function. Due to this difficulty in analyzing the training dynamics of DNNs, the reasons for the generalization of practical DNNs and the mysteries related to the guarantee of global convergence remain unsolved. However, a theoretical framework called Neural Tangent Kernel (NTK) (Jacot al., 2018) has been developed to analyze the training dynamics of gradient descent in DNNs with a sufficiently large width.
Assuming that the loss function to be minimized in NN training is L [ parameters are updated by the gradient method with the learning rate v). the amount of change is AO,
0 y and the
(L( VoL(()
A -1 00
Continuing this equation using the continuous time (training step of NN) t, we obtain
00
Ot = 1, VoL(((())
(8)
= - Sd
(9)
where (x; is 0f(r:0) (z)( 00
Second, considering the time variation of the output of the function instead of the parameters we get
af((r; 0)
(5(r;;) 0) 00
(10)
Øt
00 Ōt mele Jz; V (())(((())
(11)
mK,, x) Sot
(12)
where (x( is Jr; ()]
Emyye=1 layer Je (z; myeer) Jt (x;; Quyer)
lnyer
The problem here is that K2, which the NTK time depends on 0 and x. However, was shown that if the width of the randomly initialized NN is large enough, it will be K2 x) ~ Ko(æ, x) (Jacot al., 2018).
Given the output of the neural network with its first-order Taylor expansion, we have flin (z; 01) = fo (z; 0,) + Vefo (z; 0u) (0,
0o)
(13)
The dynamics of training can be expressed in the following way.
0: 0 Vofu(x)) KG,1 (I (I- (I- nnkot (fo(z) (! = -(T (noo)))) y + -WCt fo(x))
(14)
(15)
Therefore, NTK theory determines the dynamies of gradients function space by introducing the NTK regime, which allows to assume that the weights follow a Gaussian process even in training progresses, based on the theory that the random initialized NN can be considered as a Gaussian process when the hidden layers become infinite in the study of Lee et al. (2018) Novak et al. (2018b).
NTK allows us to prove the global convergence of gradient descent, and furthermore, the equiva- lence between the trained model and the Gaussian process can be used to explain the generalization performance of DNN. Besides, NTK was extended to CNNs (Arora et al., 2019) and RNNs (Yang, 2019) as well as MIPs, and exhaustive experiments (Lee et al., 2019) were conducted.
13

---

Under review as a conference paper at ICLR 2022
A.1.2 PRELIMINARIES FOR TIC NTK REGIME
TIC requires that the statistical model be regular model. However, DNNs are generally singular models. The requirements for regular model follows,
The posterior distribution of the parameters can be approximated by a Gaussian distribution, and the number of samples is sufficiently large (as increases, the prior distribution is ignored).
There is only one optimal solution for arg max E(O).
(O*) is positive definite.
In machine learning, we often pursue to minimize the negative log-likelihood using it loss function. Let f be the predictive distribution of the model over the p-dimensional parameters O E @ Rº and the true distribution 9 We can compare the models by measuring the KL divergence of f and g to see how well f approximates the true distribution g as a predictive distribution.
DxL(9.f) = Ep log g(y(x)
(16)
fly x 0) = EE, log g x]] - Eollog fyl 0)]
(17)
Since the first term of equation 17 independent of 0, the model is better if maximizes the second term, i... the higher the mean log- likelihood (()) E,,log f [ (y),x, 0)].
The mean log-likelihood (()) is also an unknown quantity that cannot be calculated as it depends the true distribution of the data p However, suppose it is possible obtain valid estimator of the mean log-likelihood using the empirical distribution of the data p.In that case, it can be used as criterion for evaluating the model.
In model selection, we assume an output of DNN model [yllæ, 0). which is estimated by the maxi- mum likelihood method. We can calculate fy]r,, 0) by replacing the unknown parameters @ in the probability distribution with the maximum likelihood estimator θ_
i == arg max ((0) 0E
(18)
Where ((0)) f(ylz 0)] Ei log f (y/ 0) is the likelihood function over O.
Let S, = {(11 (1), )1), (Iz, v2)... (I Bn)) be the data observed according to the true data distri- bution p. Let á be the empirical distribution based on this Sn. By the law of large numbers, the mean of [2 / (y]æ,, 0) + Σ log (1 (u,,, 0) converges in probability to its expected value Eo,,og (v/ 0)] when the number of data becomes infinitely large.
log f 2i 0)
Ep llog f(y 0)]
(19)
Therefore, the estimator based on the empirical distribution function in equation 19 is a nat- ural estimator of the mean log-likeli.ood. While Egllog fz]22, 0)] is natural estimator of E, (log/ [v)(,,,)), Ô is model parameter estimated using empirical data (mt, ye) p. The data also used to evaluate the mean log- likeliiodooo of fzy|,, 0) of the model in terms of prediction, although fair model selection is not possible.
Therefore, it is necessary to evaluate and correct for this bias for fair model selection. The bias of estimating the mean log- likeelhodooo E,, Sg,log fy/2 0)] with equation Ep[log 2z/22, 0)] is formulated follows:
14

---

Under review as a conference paper at ICLR 2022
b nBp log fly 0)] Eyllog f 0)]
(20)
R
((0) [()
(21)
= nds
(()) {(0))
(22)
+ nB (e(00) [()))]
(23)
+ nle, [((0)) C(0)
(24)
Where 0t is the maximum likelihood estimator of (()). thus, equation 21 can be decomposed as equation 22, 23, 24. Also, equation 23 converges to O .since taking the expectation of the left-hand side by p coincides with the right-hand side, and equations 22 and 24 converge to Tr (pp00)--D "D,,(("))) in n - oc, respectively. Technically, this asymptotic validity holds under the regularity condition (White, 1982).
A.1.3 APPLY NTK REGIME FOR TIC DERIVATION
Now satisfy the above condition by using the training dynamics of DNN in the NTK regime. Specifically, the regime in NTK satisfies the first condition because it uses a locally linear approx- imation, in equation 13, and considers the training of the NN Gaussian process. Also, as shown in equation 14, the optimal solution at the 1-th step is uniquely determined, and the optimiza- tion is convex.
The positive definiteness of KG x) is proved in Appendix A4 of Jacot et al. (2018), under the as- sumption of non-polynomial Lipschitz nonlinearity. From the definition of (x, .r), the eigenvalues of Fisher Information Matrix (FIM) are positive definite in NTK Regime because K2 x) and FIM have a duality that shares eigenvalues.
This condition is true when the DNN is considered to be in the NTK Regime, i.c., when Assumption 2.1 is satisfied.
Figure 6 shows schematic diagram of the bias term b. The matrices Hp()") and Dp(0") is as follows:
(0*)") = Ep H₂(0") = Ep
T log / (vlx.0) 00
Bog fllax
80
0=--
(25)
log flyl m.
0030
0=
If the true distribution g included in the assumed statistical model f(y xz, 0), then (0*) Hy()") is valid and b Tr(I) = d, and thus AIC can be derived. In the DNN setting, this assumption does not hold, i.e., we need to use the respective matrices for the misspecified situation.
Since the bias depends on the true data distribution p, it needs to be estimated based the ob- served data. Assuming that the consistent estimators for (O*) and (0*) are C(θ)) and H (θ). respectively, the estimates in equation 20 are as follows:
C(Ô)
0 log f(ys le 0) a Blog f(y, la.
80
0=0
(26)
(())
D
log f(u: (0
Using equation 2, b an estimate bias can be described as follows.
b- Tr (H(0))
(27)
The term of b is called Moody's effective number of parameters (Moody, 1992). The TIC is derived in equation by estimating the asymptotic bias the mean log- likeliiol with the log- likeliiod of the statistical model.
15

---

Under review as a conference paper at ICLR 2022
((0)
Tr H, (00) (6m)
(0)
Figure 6: TIC takes into account the bias of the estimate
B ASYMPTOTIC EQUIVALENCE OF TIC TO CROSS- VALIDATION
Since deep learning usually requires lot of data and huge amount of time for training, the Hold- Out method is commonly used to divide the training data into train data for training, validation data for model selection, especially for hyperparameter optimization, and test data to verify the performance of the model. This method is relatively fast, but its evaluation varies depending on how the data divided, and it is not used when the number of data is small. In K-fold cross-validation, the entire train data is divided into K pieces. Then, one of them is used as the validation data, and the remaining K-1 groups are decomposed into training data. The validation data and training data are swapped and repeated, and the verification is repeated that all cases become validation cases. The leave-one-out cross cross-validation (LOOCV) is method that uses only one piece of the entire train data as validation data. LOOCV is empirically known to have high performance and is often used when the overall data is small. If the number of data is n, the bias of the estimation error is O(1/ /T) for the Hold-Out method and (11nn) for LOOCV (Stone, 1977). However, LOOCV requires times the computational cost. In a case such as ImageNet-IK. 1.2 million images can be used as training data, and the current trend is to the Hold-Out method, which allows the estimation error to be 0(1/v Vn) with small computational cost, instead of reducing the estimation error to ((1nn) at the expense of huge computational cost.
C TIC EXPERIMENTAL DETAILS
C.I IMPLEMENTATION AND ENVIRONMENT FOR EXPERIMENT
We perform our experiment with supercomputer A (These names will be deanonymized after pub- lication). For supercomputer A, each node is composed of NVIDIA Tesla V100x and Intel Xeon Gold 6148 2.4 GHz, 20 Cores x xCPUU. As software environment, we use Red Hat 4.8.5, gec 7.4, Python 3.6.5, Pytorch 1.6.0, cuDNN 7.6.2, and CUDA 10.0. Our code can be found at the link below.
ht https:// http:///noommous...m 4open. wwwwece/:/eccccccceeeeeee -n-
http://eeeeeicee///ooooooata/aaa 02A2/
C.2 HYPERPARAMETERS AND DETAILED CONFIGURATION
We will report the hyperparameter's search space. We search learning rate 7), learning rate decay rate P and the timing to decay learning rate and regularization coefficient of weight decay X. When 5 0.7, it means that the learning rate decays when training passes 70 % of the total iterations. Furthermore, a parameter to control momentum y is added to the hyperparameters.
To set the range in which to search for each hyperparameter, et al. (2019),Shallus) et al. (2019). We summarize the workloads we use in the experiment in Table 2. We do not use batch normalization and the input image is just normalized and any data augmentation
follow the configuration of Choi
16

---

Under review as a conference paper at ICLR 2022
is not employed. Hyperparameter ranges summarized in Tables 3,4,5 and 6. We conduct
bayesian optimization to explore hyperparameters in the range described in these tables.
Table 2: Experiments: Workloads
Model
Dataset
Batch size
Step Budget
Epoch
2-NN w/o SC (Thomas et al., 2020)
TinyMNIST
512
11343
120
3-LNN w/ SC
TinyMNIST
8192
300
60
3-LNN w/o SC
TinyMNIST
8192
300
60
3-NN w/ SC
TinyMNIST
8192
300
60
3-NN w/o SC
TinyMNIST
8192
300
60
6-LNN w/ SC
MNIST
8192
300
60
6-LNN w/o SC
MNIST
8192
300
60
6-NN w/ SC
MNIST
8192
300
60
6-NN w/o SC
MNIST
8192
300
60
Simple CNN Base (Shallue et al., 2019)
MNIST
256
9350
60
6-LNNN w/ SC
CIFAR-10
256
10205
60
6-LNN w/o SC
CIFAR-10
256
10205
60
VGG-16 w/o BN (Simonyan & Zisserman, 2015)
CIFAR-I0
128
78000
250
ResNet-8 w/o BN (Shallue et al., 2019)
CIFAR-10
256
15800
120
ResNet-8 w/o BN (Shallue et al., 2019)
CIFAR-100
256
15800
120
Table 3: Hyperparameter Search Range for TinyMNIST Dataset Experiments
Model
"
p
8
A
2-LNN w/o SC
[le-3, le-1]
[le-2, 1]
[le-2, 1]
[0]
[0. 0.999]
3-NN w/o and w/ SC
[le-4, le-1]
[5e-1, I]
[5e-1, 1]
[0]
[0, 0.999]
3-LNN w/o and w/ SC
[lc-4, le-1]
[5e-1, 1]
[5c-1, 1]
[0]
[0. 0.999]
Table 4: Hyperparameter Search Range for MNIST Dataset Experiments
Model
"
8
6-NN w/o and w/ SC
[lc-4, le-1]
[5e-1, I]
[5e-1, 1]
[0]
[0, 0.999]
6-LNN w/o and w/ SC
[le-4, le-1]
[5e-1, 1]
[5e-1, 1]
[0]
[0, 0.999]
Simple CNN
[le-4, 1]
[Se-1, 1]
(5e-1, 1]
[0]
[0, 0.999]
Table Hyperparameter Search Range for CIFARIO Dataset Experiments
Model
77
p
8
A
6-LNN w/o and w/ SC
[le-4, le-1]
[0.5, 1]
[0.5, 1]
[0]
[0, 0.999)
ResNet-8 w/o BN
[le-6, le+1]
[0.5, I]
[0.5, 1]
[le-5, le-4]
[1e-4, 0.999]
VGG-16 w/o BN
[1e-3, le-0]
[0.5,
[0.5, 1]
[1e-4, 1e-1]
[1e-4, 0.999]
Table 6: Hyperparameter Search Range for CIFAR100 Dataset Experiment
Model
6
R w/o BN
[1e-6, let1]
[0.5, 1]
[0.5, 1]
[le-5, le-4]
[le-4, 0.999]
17

---

Under review as a conference paper at ICLR 2022
C.3 DISTRIBUTION OF TRAIN LOSS AND GENERALIZATION GAP
Cop
23
Tiaie Low
Gesendianiin Gap
Histogra of T'sin
Ulraggam Generltttiin
10
10"
16'
Geserdization Gup
Histograzi of Loos
Hisoyrati Geacraliztion Cup
GHARCE Builel
12
307
18
Gesondaaiiaa
Figure Distribution training loss and generalization gap on the trained models
18

---

Under review as a conference paper at ICLR 2022
D ADDITIONAL EXPERIMENTAL RESULTS
D.1 FULL RESULTS OF CORRELATION BETWEEN GENERALIZATION GAP AND TIC LOWER BOUND ESTIMATES
We summarize these results, evaluated with three different correlation coefficients, in Table 7. These results are the calculated types of correlation coefficients for the plot shown in figure 4a, 4b and 2c Furthermore, the relationship between these correlation coefficients and the values of the ratios of parameters to number of data shown Figure 8. The result of plotting these results along with d/n is shown in Figure 8.
Table 7: Correlation: TIC estimates Tr(C(())TT<(()))) and generalization gap
Model
Dataset
Spearman's
Kendall's 7
Pearson's Correlation
2-NN
Tiny MNIST
-0.456
-0.313
-0.309
3-NN
Tiny MNIST
-0.631
-0.44
-0.766
3-NN w/ SC
Tiny MNIST
-0.19
-0.137
-0.347
3-LNN
Tiny MNIST
0.277
0.238
0,256
3-LNN w/ SC
Tiny MNIST
0.932
0.795
0.898
6-NN
MNIST
0.882
0.708
0.425
6-NN w/ SC
MNIST
0.969
0.87
0.478
6-LNN
MNIST
0.682
0.465
0.774
6-LNN w/ SC
MNIST
0.593
0.512
0.848
Simple CNN
MNIST
0.923
0.553
0.763
6-LNN
CIFARIO
0.951
0.82
0.888
6-LNN w/ SC
CIFARIO
0.976
0.877
0.965
VGG-16 16 w/o BN
CIFARIO
0.904
0.725
0.933
ResNet-8 w/o BN
CIFARIO
0.912
0.766
0.983
ResNet-8 w/o BN
CIFARI00
0.966
0.855
0.978
19

---

Under review as a conference paper at ICLR 2022
Spearman's Correlation Coefficient
Spearman's Correlation Coefficient vs d/n Ratio
1.0
0.5
0.0
TisyMNIST on 2-NN
MNIST on 6-NN MNIST
CIFARIO on 6-NNN
TaayMNIST 3-M8
CIFARIO
TinyMNIST on 3 w/ SC
MNIST 6-LNN
CIFARIO VGGL6 noo ON
-0.5
TiyyMNIST on 1-NN
MNIST on 6-1 NNN WC
CIFARIO on Re-NaR win
TiayMNIST
SimpleMN
10 -1
10
10'
10
10
d/n Ratio
Kendall's Coefficient vs d/n Ratio
Kendall's t Coefficient
0.75
0.50
0.25
0.00
TRYMMIST on N-NN
MNIST on 6-NN
CEFARIO o
TRyMNIST on NN
MNIST on 6.N w:
CIFARIO on LNN w/
0.25
TayMNIST WISC
MNIST 6-LNN
CIFARIO VGG16 BN
TRyMNIST on 3-INN
MNIST cm 6-LNK SC
CIFAR1O om ReNNek win RN
ThyMNIST on
SimpleNN
-0.50
10"
100
10 d/n Ratio
10a
10
Pearson's Coefficient vs d/n Ratio
1.0
Pearson's Coefficient
0.5
0.0
TlayMNIST on 2-NK
MNIST on 6-N
X
CIFARIO on 6 LNN
TiyyMNIST
CIFARIO 6-LNN
-0.5
TisyMNIST on NK W/ SC
MINEST on LLN
CIFARIO on. VGGL6 weo BN
TiyyNISS om 3-INN
MNIST om 6-INN w/SC
CIFARIO on ReaNet&
TiyyMNIST 3-NN
SimpleCMMN
ResNett
10
10
10 d/n Ratio
10²
10
Figure 8: Relationship between correlation coefficient and d/n. It should noted that the correla- tion between the TIC estimates and the generalization gap is high in regions with large d/n, which are considered to be close to the NTK regime.
20

---

Under review as a conference paper at ICLR 2022
D.2 ADDITIONAL RESULTS OF SMALL-SCALL EXPERIMENTS
In this chapter, we provide details of the experimental results on small-scale that could not be included in the main paper. In particular, we investigate the goodness of approximation of the information matrix in the small-scale case, since it can be computed exactly, although the execution time is longer.
D.2.1 EMPIRICAL RELATIONSHIP BETWEEN H AND F
First of all, we examine the behavior of (0) when is approximated by F()). or more precisely, Fime (0). Figure shows that (0) is not in perfect agreement with F()) due to the effect of the damping term. However, For cases that do not require inverse calculations, such as trace calcu- lations and lower bounds, these effects can be eliminated and relatively good approximation can be achieved. Furthermore, in the case of linear neural networks, H (0) and F(0) show strong correlation.
TMF (MF-AC)- THH TiyMMNIT
THF TMFF aornan Cancnnay is TrlM Cunconay Dulast: TRyMNIST
TriF Seeteto Canchitee
3'10
Thyke SLM
2x10
Toyke 530 w/sc
10
TIlH -C)
Rooote Cuoctaigg
TrlFa) Coog) Trupgi ThsMNIST
T/IC)TT(F) v. Tr(CI/THH) Dnnseet: TingMNIST
10*
TriFatg Soug!
TNCHTTP)
Tianeder en taae
6-16"
10
Tr Cang)
Tr(CUTAN)
Tr(F) vs TMHH) Dataset TinyMNIST
100
40-
40-
Teahi 24B
TheliK 54300 Teeltti
Tr(t)
100
Figure 9: Small-scale experiments: comparison of the TIC estimate w/ H(0) and F(0) respec- tively.
21

---

Under review as a conference paper at ICLR 2022
D.2.2 EFFECT OF MATRIX SHAPE APPROXIMATION ON ESTIMATION OF TIC
Next, we fixed the use of F()) instead of H (0) and observed the change in the TIC estimates and the correlation with the generalization gap when form of the matrix is changed by approximation methods.
Figure 10 and 11 show the correlation between the TIC estimates and the generalized gaps in the case of approximation. Figure 10 shows the comparison of the shape of matrix and its estimates, and Figure 11 shows the correlation between generalization gap and tic estimates. These values are evaluated using three different correlation metric and summarized in Table 8, 9 and 10.
22

---

Under review as a conference paper at ICLR 2022
1/P Chocena Rid-- Drwwon TISMANT
Tor. Edeety Ctotow Tay (C) thasoe MoIT
souett Groanel onr Tay 1c) Iclilaee VoisT
Ter Cavenn)
Aph
Teddkih 200
2nd
201d
Fig-iiy
4:30
TRT (Mandag) in TTg.TC Viaee VXST
Ter Soooad to S0 Duases
toty to Dheurt
19 10 Conaatt
14
TXF 10
(a) Exact vs diock-diagonal.
miral 5.
Figenigg
TrFoly Thr Bakeet HDBS?
Trl Cleel DWte Duases MESST
TH Dog MINES
40007
2013
(b) Exact diagonal.
2113
Tigr-tay THC/Th vs TC /Daauc SONIT
6113
2
4000
TXY
(c) Exact vs lower bound.
Figure 10: Small-scale experiments: comparison of the TIC estimate.
23

---

Under review as a conference paper at ICLR 2022
Graedirkee Cag D2 "Cy Dimee B677
Chocestod Rervs (n Cleeed HANT
Orend of dop PoP PRP-AC Chioee MORT
27
Crocst cnlirs Copir high T Desst SKET
Dop
Tege
20x
(a)
Gennrraiiztioon gap exact TIC.
Grp to trgglaa Cuasinel Drasd Tey
Ceveritat Op THi ylase Chontee Obracc searT
Gouniarkos Cop so Po Soutaal! Deuceeess
Mitr with
779 (aienn))
Grecllaris Cip vs 17 Secornal MrSS
Omand Tep Ohcsted Whate Moci
THl Tel Sarakaed
TeF Tere
TV Fieeees
(b) Generalization gap vs block-disgonal TIC.
Gountatee Ga hor dife Datuer 188T
Decad led toethey Tel Cangl Diiese
21
Garca buaine Ogyis Ter Coegl Drane VAI
Goacal HDRST
Gountarkee Oogir Er O MEORT
Leee
Goat
(c) Generalization gap vs diagonal TIC.
Gevntoatiolla TrCVTTrT Drase TesNUST
2008
THCNT90
Orove be Dagin pooottpti Boran VIET
Diract
Grend Clev TeCo Deant UNIT
mGcango
(d) GGeneralization gap lower bound TIC.
Figure 11: Small-seale experiments: comparison of the TIC estimate and Generalization Gap.

---

Under review as a conference paper at ICLR 2022
Table 8: Correlation: TIC Estimates Tr(F(0) (C(()))((()) and Generalization Gap
Dataset
Model
Spearman's
Kendall's
Pearson's 's Correlation
Tiny MNIST
2-NN
0.532
0.38
0.27
Tiny MNIST
3-NN
-0.62
-0.427
-0,679
Tiny MNIST
3-NN w/ SC
0.258
0.175
-0,332
Tiny MNIST
3-LNN
0.292
0.271
0.305
Tiny MNIST
3-LNN w/ SC
0.886
0.75
0.922
Table Correlation: TIC Estimates Tr(Folockdigg (0)
Cblockding (0) and Generalization Gap
Dataset
Model
Spearman's 's
Kendall's 7
Pearson's ' Correlation
Tiny MNIST
2-NN
0.524
0.372
0.288
Tiny MNIST
3-NN
-0.549
-0.366
-0.622
Tiny MNIST
3-NN SC
0.364
0.244
-0.08
Tiny MNIST
3-LNN
0.26
0.257
0.252
Tiny MNIST
3-LNN w/ SC
0.937
0.823
0.944
Table 10: Correlation: TIC Estimates Tr( (raiiigg (0)
Cding (0)) and Generalization Gap
Dataset
Model
Spearman's
Kendall's
Pearson's ' Correlation
Tiny MNIST
2-NN
-0.309
-0.23
-0,234
Tiny MNIST
3-NN
-0.297
-0,203
-0,415
Tiny MNIST
3-NN w/ SC
-0.176
-0.128
-0.415
Tiny MNIST
3-LNN
0.275
0.237
0.288
Tiny MNIST
3-LNN SC
0.932
0.796
0.918
25

---

Under review as a conference paper at ICLR 2022
D.3 ADDITIONAL RESULTS OF PRACTICAL-SCALE EXPERIMENTS
In this section, we present results of practical-scale setting that we have not presented in the main paper. We observed that in a small-scale setting, DNNs with large number of layers and SC tend to have a high rank correlation in the TIC estimator and a strong correlation with the generalization gap. Since it is not computationally feasible compute TIC in practical DNNs, this section de- tails experimentalresults on the performance of two approximate estimators of TIC using diagonal approximation and its lower bound.
D.3.1 PRACTICAL-SCALE EXPERIMENTS: MNIST CASE
As shown in Figure 12, we observed the correlation between the TIC estimator and the generalization gap for the diagonal approximation and the lower bound. Both were found to be highly correlated and good estimators of the generalization gap.
Gencralizziion Gup Tr(F dxp Cabp) Datmett MNIST
Gmerlizatio Cup vs. Tr(CI/T((F) Datsset: MNIST
10
Geverniizztinn Cap
10
SPERT aaREAN
10
10
107
TriF Caral
TX(CTT/FF)
TX TriFad vs TRC)M Datsee MNIST
10'
1985T $438 19457 SLW a Suepices
10²
Tr(CYTHF)
Figure 12: Practical-scale MNIST experiments: comparison of the TIC estimates.
Here, we also investigated whether the estimated TIC from lower bounds is due to only one of the components of the trace, respectively. As shown in figure 13, the value of trace itself was not correlated with the generalization gap. It was also confirmed that different models behaved differently. At the same time, we also confirmed that Tr (F(O) is good approximation of trace Tr (H)).
26

---

Under review as a conference paper at ICLR 2022
Generaliaatio Gap vi Tr(C) Dataset, MNNST
Generalization Gap Tr(F): Dutaset, MINIST
Geperilizztion Cap
Comeritration
VASST datlin
SeVET 5430
VOUST GLNN
32
10
TrCC)
TX(F)
Gup Dalaset
Tr(Hi Tr(F): Dutasct MNIST
10'
10
Coneraizatiee Cop
TntH)
HABST 54.20
10
NARST 54.00
Sipgacoo
TriH)
7X(F)
Figure 13: Practical-scale MNIST experiments: elements of the TIC estimates.
27

---

Under review as a conference paper at ICLR 2022
D.3.2 PRACTICAL-SCALE EXPERIMENTS: CIFARIO AND CIFAR 100 CASE
Gmmmlization Cap Tr1F Casp! Dataset CIBAR
Gap vs Tr(Cl/Tr(F)) CIFAR
Golerslaatinn Gap
107
-07
10
(TARDS vn Rathas
CEARIS en Ranket
Bucken
00
TrF Caral Carol
10'
16
TX(CTTTFF)
Trus) MCCTAF Datnnet: CIPAR
10'
40*
TrFFs Fauul
CEARIS is SERM
CIARSS Baciul CIAR 10700000000 bodics
TrCCTTT(F)
Figure 14: Practical-scale CIFAR experiments: comparison of the TIC estimates.
Generalization Cap va Tr(C): Dainset CIFAR
Geseralization Gap TriF), Daineet:
/Ditest CIPAR
10
Geveriiattion Cap
10²
1D
CRACIS of
CPARIS
107
10'
10
TXC
TX(F)
Generniizatonn Cap vs Tr(H) / Datsect: CIFAR
Tr(H) vs T Datnatt CIFAR
10
10'
Gesemlizatium Chp
Tr(e))
CEARZO uy DONN
VORTA
CITARIO ou VOGUS
Tr(H)
7r(F)
Figure 15: Practical-scale CIFAR experiments: elements of the TIC estimates.
28

---

Under review as a conference paper at ICLR 2022
D.3.3 CORRELATION BETWEEN TIC ESTIMATES AND GENERALIZATION GAP IN TRAINING PROCESS
Within the scope of our experiments, we find that TIC can estimate the generalization gap even in the middle of learning for problem settings that are considered to belong NTK.
Conrelzatinn betwzen TXC Estimoies and izatiolizaiion Gap
Correlation between TIC Estimates and Generalizatio Gxp Thiiting Process MNNST
Trainin Process/ MNIST
50
45
Generaliation Cap
22
40
10
25
25
20
101
20
2- 935-12
Los -tdiiss 10l.2- 10
4x10"
13-10
1.2 mn
TYCCMT(F
Tr(CH/
Conrelation between TC Estimaici and Generaiization Gup
Conclation between TIC Estimates and Generaliation Clap in Training Process MNIST on 6-LNN w/
in Training Process MNNST on 6-LNN
Genemilzziion zatio Gol
4B
-5
30"1
15
1t/1xxtdiis 1ol 10
11x10 Tr(CW/H1FF
L2x10"
L3*
TX(CMTMFF
Couriition
Gentrrizzation
Trining Process: MNIST SimpleCNN
10"
to
Cenerlizzaion
35
30
10'
10'
Tr(CWTTtF)
Figure 16: Correlation between generalization gap and TIC estimates in MNIST experiments, through training process. The color map shows the epoch.
29

---

Under review as a conference paper at ICLR 2022
Conrelation betweenn TXC Eeiimiic and cenneniiaaiins Cap
Conelatiin between TIC Estimates and Gereraliation Clep in Training Process/ CIFARIO en 5 LNN WSC
i Trnining Process: CIIA LNN
10
Goser Geserallattton Cap
10
101
11-11
12"
1.3-10
165 10
if
TXCVTM(F)
TrICH/1(F)
Comelation between TIC Eatimates Gmeenizatioon Gap
Commettion between Entimates and Gmneraization Cap
Traiting Process CIFARIO VG316
Training Process CIFARI0 RedNett
10
10¹
Caicalizttnn Gop
340
120
110
10
10'
2-1d
300dd TACHTTFF
6-10
Tr(CNT((F
Conrlation betwear TDC Estmates and Generolization Gup in Trieiing Procos / C ARI ResNes
Gonee
10
Tr(m//
Figure 17: Correlation between generalization gap and TIC estimates in CIFAR experiments, through training process. The color map shows the epoch.
30

---

Under review as a conference paper at ICLR 2022
D.4 CALCULATION TIME MEASUMENTS EXPERIMENT
First of all, we explain the execution time of the small NN/LNN case. In the case of using Tr (0) and Tr (C())), the computation time by block diagonal approximation is only 40% faster than exact computation. The computational complexity should have been reduced from ((d)) to O by the block diagonal approximation. However, the overhead such as memory copying dominant, and there is no significant difference in execution time compared to the theoretical amount of computa- tion. From block diagonal diagonal approximation, the experimental results show a reduction of up to 50% in computation time. The computational complexity is reduced from O(di) ) to (d).
Secondly, the use of Tr (H)) and Tr (C()) requires up 900% more time than the use of Tr (F(O)) and Tr (C(O)) in the Exact case. The choice to use Tr (F(0)) instead of Tr (H())) is therefore justified in terms of the reduction computational time. In the case block diagonaliza- tion. the speed-up was observed, but the speed-up was more than 40 times when Trace's ' approximation was performed using the Hutchinson method. However, the estimation using Tr (F(O)) and Tr (C(0)) is faster in the Small Scale problem setting.
only few percent. In the case of diagonalization,,
significant speed-up
It is observed that in such small scale problem setting, there is a 50 times difference in execu- tion time between using Tr (0) and Tr (C(()) with Exact TIC and computing Tr (F(O)) and Tr (C(0)) simultaneously and using diagonal approximation.
This speed-up should be more significant for larger models. As mentioned in section 2.2, it was not feasible to caleulate of Tr (() in ResNet-8 which requires more than 2,00 TB of memory without approximation. While execution time is also important, the most important aspect is that it made possible to calculate TIC by approximation.
Secondly, we compare the execution time at practical scale. Among the cases where Tr (F))) and Tr (C(0) is used, we investigate how much the time can be reduced when Tr (F)) and Tr (C())) are computed simultaneously compared to the case where they are computed separately. In the case of Small Scale and Practical Scale networks, the time is reduced by half, but in the case of SimpleCNN, VGG16, ResNet8, etc., the time is not reduced significantly. For relatively small models, which could be reduced by about 50%, the approximation by simultaneous Tr (F(0)) and Tr (C(0)) calculations was faster than using the Hutchinson method. In contrast. For networks with a large number of dimensions in the final layer, such as VGGI6, etc., the calculation of Tr (C(0)) and fast approximation of Tr [H (0)) resulted in speedup of 10%-25% faster than the simulta- ncous calculation of Tr (F()) and Tr (C)))).
31

---

Under review as a conference paper at ICLR 2022
w/HC by Hutchinson's 's Method
Lower Bound
2.7814
2.5705
2,8932
2.8645
2.7198
2.8949
3.3679
2.8089
2,9382
8.7958
4.1043
2. 2,8996
90.9633
60.716
88.7 74.7423
Lower Bound w/HC
82.0081
22.4 22.4203
24.9217
21.6511
22.0721
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
92.979
21.7705
25.0151
22. 22.1641
23.0338
Table 11: Full Details of Runtime Measuments Experimemnt. Unit: second
Diag w/HC
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
Block Diag w/HC
96.0647
22.4 22.4055
24.9561
22.2685
22.8106
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
105. 4282
Exact w/HC
23 23.9083
26.230X
23.188
23.8571
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
Lower Bound w/FC
1,9069
1.994
2.0225
1.9521
1,9594
1.9172
1,9459
1.9188
1.9329
2.6337
1,9295
1.9453
10.0031
11.3721
9.9655
Diag w/FC
3.7273
3.7937
3.8239
3,7991
3,8159
3.7235
3.6813
3 3,4822
3.502
4.7059
3.6742
3.7003
12.4677
13.3077
12,4292
Block Diag
6.7516
3.8435
3.8568
3,8962
w/FC
3.847
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
NA
10.9093
Exact w/FC
3.8641
3 3,8999
3.8656
3,8771
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
3-LNN W/ SC
6-INN W/ SC
6-LNN w/ SC
3-NN w/ SC
6-NN SC
Simple CNN
2-wide NN
Model
3-NN
3-LNN
6-NN
6-LNN
6-LNN
ResNet8
VGG16
ResNer8
Tiny MNIST
Tiny MIISTT
Tiny MIIST
Tiny MNIST
Tiny MNIST
CIFARTOO
CIFARIO
CIFARIO
CIFARIO
CIFARIO
Dataset
MNIST
MNIST
MNIST
MNIST
MNIST
32

---

Under review as a conference paper at ICLR 2022
D.5 EXPERIMENTS WITH d/n CHANGES WITHIN TINYMNIST
We created a restricted dataset, SmallTinyMNIIST which uses only 5% of the TinyMNIST data.
Table 12: Additional problem settings are highlighted in bold text
Category
Problem Setting: Dataset & Model
Ratio: d/n
TinyMIIST on 2-NN w/o SC
0.09
Small Scale
TinyMNIST on 3-NN w/o SC, 3-NN W/ SC
0,02
Data Size < <1MB
TinyMNIST on 3-LNN w/o SC, 3-LNN w/ SC
0.02
Model <50KB
SINITT on 3-LNN w/o SC TinyMNIST on Wide 3-NN w/ SC
0.36
13.90
We conducted training evaluations using SmalTTinyMNIST investigate the relationship between the TIC estimator and the generalization gap for patterns with relatively large d/n ratios.
Furthermore, we prepared network with large number of d 3-layer Wide-NN, and confirmed the effectiveness of TIC in settings where the d/n ratio exceeds 10.
The distributions of the loss and the generalization gap are shown in figure 18. For the comparative purpose, problem settings with the same or relative networks are included in comparison plots and tables. The correlation between the TIC and the generalization gap shown figure 19.
Histagaam
Haluggun of Generaliatioon Gap
TaMMOS NAW
Taskece 1-00wtt
30
23
03
Tral
Geseralzatioo Cop
Figure 18: Distribution of training loss and generalization gap on the trained models
Table 13: Correlation: TIC estimates Ir(C(0))/I(((())) and generalization gap
Model
Dataset
Spearman's 's
Kendall's
Pearson's 's Correlation
3-LNN
Tiny MNIST
0.277
0.238
0.256
3-LNN
Small Tiny MNIST
0.806
0.622
0.811
3-NN w/ SC
Tiny MNIST
-0.19
-0.137
-0.347
W-di NN w/ SC
Tiny MNIST
0.834
0.656
0.967
33

---

Under review as a conference paper at ICLR 2022
Generalization Gap vs TIC Estimate
0.040
SmalITuyMMISST on 3-LNN
0.035
TinyMNIST 3-LNN
TinyMNIST on 3-NN w/CC
0.030
TimyMNIST Wide 3-NN SC
Generalization Gap
0.025
0.020
0.015
0.010
0.005
0.000
6x 10
10t
2 2x10
TIC Estimate: Tr(C/T((F)
Figure 19: Relationship between TIC estimates and generalization gap
34


Reviews:
[{"review_id": "wR4vhbrSGoe", "reviewer": "Reviewer_VPJq", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros: \n-\tEmpirical study is extensive and refined. Results are obtained from both small and practical scale architectures and image datasets. Approximation using block diagonal matrices is justified by empirical experiments. \n-\tMinimizing the TIC seems to be a promising guideline for selecting hyperparameters as shown by empirical experiments\n\nCons:  \n-\tSome previous papers, e.g. Ghorbani et al. (2019) [Sect. 4.1], Gur-Ari et al (2018), Li et al. (2020), show that there is significant alignment in top eigenspace between the Hessian and gradient covariance matrix using various architectures and datasets. Under conjecture that H and C are simultaneously diagonalizable around theta^*, the TIC in Eq. (3) of Prop. 2.1 may be approximated by the sum of product between the eigenvalues of $H^{-1}$ and $C$ matrices. The relative magnitude of the eigenvalues of $H$ and $C$ may be indicative to the generalization gap given that the TIC is a good measure of generalization gap. Does Figure 4 enable one to draw conclusion that the rate of eigenvalues of $H$ and $C$ are constant, so TIC may approximately be a measure of effective dimension?\n-\tAs far as I am concerned, the NTK regime only warrants the convergence to “a” global minimizer, but it does not warrant a unique model minimizer. Therefore, Assumption (A1) may still be unrealistic even in the NTK regime, so (A1) is restrictive. More explanation may be required. In addition, does the solution in “the model has only one possible solution” refer to the empirical minimizer $\\hat\\theta$ or $\\theta^*$? \n-\tTheory that can be applied on singular models may be more appropriate for deep learning. In particular, recent results show that the singularity, e.g. flatness, of deep neural networks is highly correlated with its generalization performance, and effort has been made to explicitly use this to achieve the state-of-the-art performance, e.g. SAM (https://arxiv.org/abs/2010.01412). As suggested in Remark 2.3, some papers have studied the WBIC of Watanabe by empirically estimating the real log canonical threshold (RLCT) for neural networks, e.g. Murfet et al. (2020). Much effort is still needed to scale up the computation to deep neural networks. RLCT has a fascinating interpretation of the dimension of singularity, which connects with the loss landscape.\nAs said in Remark 2.1, TIC only applies to non-singular models, so theoretically it is incapable of explaining the generalization of deep learning. However, the empirical results appear to suggest the contrary, at least in NTK regime. Is this just a coincidence, or is there anything that TIC can do beyond that can be covered in theory? Perhaps TIC also affords an interpretation that is related to the loss landscape?\n-\tGiven that many measures have been proposed to explain the generalization gap, e.g. Jiang et al. (2019), the performance of TIC should have been compared with other measures to further document the advantage of TIC.\n-\tI am unsure how relevant TIC is in selecting hyperparameters, especially when its use is prohibitive on large scale models due to cost, and the validation loss curve of TIC pruning looks similar to that based on the validation loss from panel (b) and (c) of Figure 5. This may not be directly relevant to this paper, but training variance has been a more important issue for generative neural network than for a typical predictive neural network. Therefore, maybe using TIC on hyperparameter tuning for GAN could be a more interesting problem to study.\n\nMinor comments:\n-\tTypo: 3rd line under Eq. (2), “they a different different …”", "summary_of_the_paper": "This paper proposes to use TIC as a metric for measuring the generalization gap. Using an extensive set of architectures and datasets, this paper present empirical results that show the correlation between the TIC and generalization gap.", "summary_of_the_review": "Although this paper presents many empirical results, my main reservation is how much they can afford a deeper theoretical insight that can motivate follow-up studies. In addition, the approximation method to compute the Hessian matrix essentially follows by the existing methods which does not seem very novel. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "tXFAco0BI2b", "reviewer": "Reviewer_2vba", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n- Studying what causes a smaller generalization gap is an important problem in deep learning. Given that the NTK regime leads to zero training loss, the generalization gap directly leads to generalization performance in the NTK regime. \n- Extensive empirical evaluation is important given the complexity of the deep learning model/dataset/training. The paper is working towards such a goal. \n\nWeakness\n\n- Main idea of TIC’s usefulness as a generalization measure is already demonstrated in Thomas et al., 2019. In comparison to Thomas et al., 2019, the authors’ claimed difference is investigation beyond small scale and studying DNNs of practical size which requires estimation of TIC. However, the general lesson of TIC as a generalization measure and using efficient approximation of TIC  with Tr(F^{-1}C) and Tr(C) / Tr(F) has been explored in (Thomas et al., 2019). Possibly a new contribution is the message about “close to NTK regime” and looking at the correlation/ranking coefficients as a function of overparameterization ratio (d/n). \n\n- To estimate TIC, we require a separate data (validation)  as well as trained parameter \\theta^*for H and C computation. In this case,  why not just compute validation acc/loss which we know is a good estimate of generalization performance? [know without training? But needs trained params…]\n\n- The reviewer tried looking for detailed model descriptions used (beyond simple names) for experiments but did not appear in paper nor in code. \n\n- Overall, there’s issues with clarity. The paper needs significant proofreading to the point that deters understanding the main message. \n   - Numerous typos or un-proofread sentences throughout the paper\n   - Some of the main figures are not fully legible or explained.  e.g. Figure 1/2 is not so legible due to small fonts. Figure 1 appearing below the footnote is confusing. Moreover, neither captions for Figure 1 / 2 are self-explanatory nor they are properly referenced in the main text. In Figure 4, what does the color bar indicate? (In the appendix some figures denote that color bars are epochs. Main figure should explain this as well)\n    - Please put proper references to which figure/table the main text is explaining. \n\n- HPO experiments are promising. However, just showing one set of cases in Figure 5, it’s unclear whether the proposed method and described phenomena is robust. \n\nQuestions\n\n- Could you provide the argument / reference showing that layer-wise block diagonal structure of Hessian in the NTK regime (section 3.2 part 2)? As far as the reviewer is aware, there’s block diagonal structure for NTK regards to output unit or K-FAC approximation (irrespective of NTK limit) but is not familiar with layer-wise block diagonality. \n\n- According to remark 2.3., one would consider WAIC/GIC should be a more principled information criteria to be used for models near the NTK regime. TIC is also intractable due to high computational cost. Shouldn’t one also try to approximate the WAIC as similarly be done in the paper? Is there a chance that various approximations taken for TIC make it more like WAIC?\n\nCorrections:\n- Remark 2.3: I believe the exact criteria of being in the NTK regime is not precisely defined but beyond linear models, one often needs the number of model parameters to be much larger that number of the data points. \n\nNit:\n- Typo: p2 in contribution part two, “with totally 12 architectures”?\n- Type: p3 “but they a different different distribution when computing the expectation”\n- “n” is not defined early enough also often used as “p” (e.g. section 4.3). \n- Term GIC (possibly generalized information criteria) is not defined or referenced. \n- Typo: Section D.4: “As mentioned in section X” (there’s no section X), “2,00TB”\n\n-------------------------------------------------------\nPost rebuttal:\nI thank the authors for the response and clarification. I have read the response and other reviews and my assessment still remains as is. \n\nIn regards to block-diagonal approximation in Karakida-Kazuki NeurIPS 2020, to my understanding the approximation(block-diagonal, block tri-diagonal, K-FAC) is not valid due to infinite-width limit but taken **on top** of studying the NTK limit. I maybe misreading the reference but indicating large width limit justifies block-diagonal approximation of FIM seems ungrounded. ", "summary_of_the_paper": "The paper empirically studies the effectiveness of Takeuchi’s information criteria (TIC) for deep neural networks near the NTK regime. Since exact computation for TIC (Tr(H^{-1} C)) is often intractable for practical DNNs, the authors explore various approximations of TIC. \n\nThe authors’ claimed contributions are:\n- Empirical and theoretical evidence that TIC is highly correlated with the generalization gap in DNNs that are close to the NTK regime. Given TIC is not designed for singular models, this is a surprising finding.\n- Conduct comprehensive experiments (varying models, datasets, training settings) showing TICs estimate generalization gaps\n- Application of these findings to prune poorly performing models in hyperparameter optimization demonstrates this can successfully prevent promising candidates being pruned prematurely. \n", "summary_of_the_review": "While study of generalization measure and extensive empirical study is important problem towards understanding generalization behaviour of deep neural networks, the current submission has issues that needs to be addressed before being presented to general audience. 1) The main message / lessons beyond Thomas et al., 2019 is unclear or not existent 2) usefulness of TIC as generalization measure need to explained 3) overall clarity needs to be improved 4) HPO experiments at the currently presented results doesn't demonstrate robustness and requires validation on more diverse settings. The reviewer believes addressing these issues requires major revision and won't be able to  suggest acceptance for ICLR 2022.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "rfqZVrqrtTC", "reviewer": "Reviewer_fZpy", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nContributions:\n\n1. The authors propose to use a simple but effective metric, TIC, to estimate the generalization gap.\n\n2. The authors show how to speed up the estimation via Monte-Carlo sampling.\n\n3. The experiments validate the utility of TIC by showing a large correlation between TIC and the generalization gap.\n\nConcerns:\n\n1. The authors claim that: “estimated TIC well correlates generalization gaps under the conditions that are close to NTK regimes. Outside the NTK regime, such correlation disappears.” Do the authors mean a large d/n when referring to NTK regimes? What about the other requirements in NTK, for example, small initialization. \n\n2. In Figure4 and Figure3, how do the authors calculate the Pearson’s coefficient (for example, by repeated experiments?)? I have not found the descriptions. \n\n3. Beyond the generalization gap, I am wondering how large the test error is. Are the models trained to be zero training loss?\n\n4. I think the authors can conduct some experiments (maybe small-scale is enough) on TinyMNIST with a large d/n, does the Pearson’s coefficient act as MNIST? \n\nSome other comments:\n\n1. Could the authors explain further what is “model distribution” q_{\\theta}? Did the authors consider a Bayesian regime where the model distribution represents the distribution of the parameters? I am still puzzled about the differences between C(\\theta) and F(\\theta).\n\n2. What is the role of G(\\theta) in the main text? Do the authors use it during the TIC estimation process? \n\nTypos:\n1. Page3: they a different different distribution.\n\n2. The font size of Fig2 is too small.\n\n3. d in d/n (experiment section): d is the number of parameters?", "summary_of_the_paper": "This paper focuses on a fascinating, challenging problem: evaluating the generalization performances of neural networks based on the training set with some criteria. Specifically, the authors propose to measure the generalization ability via Takeuchi’s Information Criteria (TIC). Besides, the authors approximate the TIC to accelerate the process of estimation. The proposed method is promising and works well when d/n is large (where d = #parameters and n = #samples). \nHowever, I am still puzzled about some details. I will raise my score if the authors could clarify those concerns (see the following).", "summary_of_the_review": "Overall, I think this paper focuses on a challenging topic and has the potential to be accepted. I would like to see more explanations on the details and update my score after the rebuttal period. \n\n\n==========================\nAfter reading the authors' response, I decided to keep my scores unchanged.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "aqEnCZXjXFp", "reviewer": "Reviewer_Z8n4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "One positive point here is that the authors have really run a very large amount of experiments, which deserves credit. On the other hand, the paper is extremely poorly written and organised to the point where it just doesn't look like a serious submission by the standards of a top tier conference such as ICLR. The text is rambling, the theoretical \"results\" can only be understood by reading the related works rather than by reading the current paper. Assumptions and statements are often vague, not only in content but even in pagination: there are \"propositions\" which merge into the text with no clear beginning or end. So called \"Proofs\" also appear to be more like an informal and aimless discussion that ends with a reference to the supplementary, where one finds another casual and rambling discussion which ends in a reference to related works. Even the experiments are not discussed in an organised way and many of the graphs are blurry with illegible legends. The english is poor (this wouldn't be a problem if the paper was well organised). Furthermore, other ability-agnostic metrics attest to the simple lack of time/effort invested by the authors into the polishing: there are issues with punctuation/presentation and some of the key references are incorrectly cited. \n\nLast but not least, there is (pretty much by the authors' own admission) almost no original content in the proposed methods (except approximations (2) and (3) from the summary above).\n\n\n\n\n\n\n=======================After Rebuttal==================\n\n\nI took a quick look at the rebuttal. The authors seem to commit to making many of the necessary changes that I asked for (which I am happy about), but some of the replies are still relatively vague. Assuming the current pdf is the last revision, it is difficult to compare to earlier versions (it would be customary to highlight the changes in a specific colour for instance). At least some of the problems I mentioned are still there, including the inaccurate big picture description of the related works. \n\n\nStill, I think the paper is below the borderline for ICLR including assuming every issue was fixed (which is not the case). I would change my score to 4 if it were possible but the only allowed scores are 3 and 5 and I still think 5 is a bit too much for the paper in its current state. \n\n\n\n\n/\n===========\nSpecific comments/questions\n===========\n\n1.  The motivation behind the main method, and the reason why the term $\\tr(H^{-1}C)$ appears, is not provided in the paper. I understand that this is \"known\" from the related work, but it would be nice to make the paper more accessible by explaining it. Furthermore, it is claimed in the main paper (page 4 near equation (3)) that \"a more detailed proof is provided in Appendix A1\". This is not true. First of all, Appendix A1 is quite long and it is not immediately clear which part of it they are referring to. After some thought it appears to be the end of Appendix A.1.2 on page 14, specifically equations (20) to (24) inclusive. It is not explained why 22 and 23 converge to $\\frac{1}{2}\\tr(H^{-1}D)$. Note that there is also an extra factor of $n$ in the definition of $b$ in the appendix compared to in the main text. \n\n2. In the introduction, the TIC is introduced via formula (1) and the matrices H,C at this point were only defined as \"Hessian\" and \"Covariance\" respectively, which is not enough information even for an informal reading. At least a pointer to the more formal definition on page 3 (equation (2)) would be nice. \n\n3. Question: on page 3 (near the bottom), you say that $H(\\theta)$ is a measure which doesn't depend on the distribution of the input data. What do you mean? As far as I understand, this quantity still involves an expectation over a sample, which depends on the sampling distribution. \n\n\n4. One big problem with this paper is that it is not clearly explained why the method provided is specific to the NTK regime and assumptions and statements are not rigorously stated. For instant, Assumption 2.1 is not clear. First of all, $q_\\theta$ is not defined anywhere in the paper as far as I can tell. Secondly, it appears the authors are stating that there can only exist one set of parameters that minimizes the loss. This is certainly not true *at face value* for neural networks. I agree that it is approximately true for the NTK itself, as the authors clumsily explain in appendix A1.1. Still, it is no longer clear if we are speaking about an \"assumption\" or something which is deduced from that part of the appendix. The \"uniqueness\" is kind of trivial once we accept that we define the \"solution\" as whatever happens when we run gradient descent to convergence (this isn't even specific to NNs in the NTK regime). The second assumption of asymptotic normality is not explained in detail. \n\n5. Question: what is going on in the graph at the bottom of Figure 3. It appears inconclusive (same for the graphs on page 19)\n\n6. What is the strategy employed to use the TIC to improve hyper parameter search. As far as I can tell, the only sentence in the relevant section (Section 5) which attempts to explain that is the following: \" To achieve stable optimization in SHA, we apply the TIC values for the intermediate loss. There is no formula anywhere in the section which involves such an \"intermediate loss\", or any reasonable explanation of the optimization strategy there. \n\n\n7. Question: by \"Linear neural networks\" do the authors really mean neural networks without any activation functions? It would seem that large scale experiments are difficult to perform in this context as linear functions cannot match the ground truth well at all in realistic scenarii\n\n\n8. The section on related works is a bit chaotic and incomplete. The authors are splitting the work into two categories: one the one hand \"generalisation bounds\" (with one citation, which deals with a PAC Bayesian approach) and on the other hand \"complexity measures\", with a rather incomplete description of some of the work in the statistical learning theory of neural networks. The logic in the three first lines of page three doesn't seem to stand: the strong negative correlation between the spectral norm of the layers and generalization is a point in favour of the validity of the approach, not against, as appears to be intimated by the authors. \n\n9. The authors seem to hint that the reason one cannot use the AIC is because of the misspecification of the model, but I don't think that is true. There are plenty of reasons in the SLT of NNs why parameter counting is inadequate to explain generalization (including in the realisable, \"well specified\" case), I think these reasons still hold here: the optimization of a NN in NTK regime behaves more like kernel ridge regression than like the problem of finding the global optimum of the loss minimization problem over the whole set of parameters. \n\n\n10. The concept of \"singular models\" is not explained in the introduction, though it is referenced many times. The explanation which is given later (page 13, top of Section A.1.2. in the supplementary!) is not very satisfactory either. \n\n11.Question I might have missed that but what is \"SC\" in the experiments when describing the various architectures?\n\n\n12. Question for the authors (I might be wrong here, I am just genuinely curious): on page 5 in the explanation of the block diagonalization procedure, you claim that this approach reduces the complexity from $O(d^3)$ to $O(d)$. That is a bit confusing.... \n If the width is $d_1$, I guess the complexity should be $d_1^3$ to invert each individual matrices, times $d/d_1$ (the number of layers), which gives $d_1^2 d$.\n\nAre you surreptitiously treating the width of the intermediary layers as constant?!?\n\n\n\n /\n=====================\nMinor issues, typos, etc. (Highly non exhaustive)\n=====================\n\n1. abstract: \"In fact, theory indicates...\" =======> \"In fact, the theory indicates...\"\n2. Beginning of the last two paragraphs of page 1: determinant (\"the\") missing before \"generalization gap\"\n3. Top of page 2: \"$\\hat{\\theta}$ is the solution to the empirical loss\" ===>\n\"$\\hat{\\theta}$ minimizes the empirical loss\"\n4. Page 2, \"We provide empirical and theoretical evidences\" =====> \"We provide empirical and theoretical evidence\" \n(uncountable)\n5. page 2 \"estimate TIC with less computations\" ====>\"estimate TIC with fewer computations\"\n6. Page 5, assumption B2: improve sentence structure\n7. Middle of page 5: \"In NTK's regime\" ====> \"In the NTK regime\"\n 8. Page 5 \"for estimate $\\tr(H)$ fast\"====>  \"to estimate $\\tr(H)$ fast\" OR  \"for estimating $\\tr(H)$ fast\"\n9. Page 7 (question)  \"we can confirm that the value and the rank correlation are kept\": what does this mean? \n10. Page 8, section 4.4, third line, there is an extra space after $F(\\theta)$.\n11. Page 9: \"Successive halving algorithm shows promising...\" =====>\"The successive halving algorithm shows promising...\"\n\n12. References [2] and [1] appear incorrectly cited. [2] is published in JMLR and [1] is published in AiStats.\n\n13. Conclusion: \"even if the model is not completed to train\": what does this mean? \n14. Page 15 above equation (25):  \"the matrix H and D\" ====> \"the matrices H and D\"\n15. Below equation (25): \"respective matrice\" ===> \"respective matrices. \n16. Page 16:  \"when publication ===>\"when published\" OR \"after publication\"\n17. Page 16 \"For what hyperparameter in what range to search, we follow configuration of...\" ====>\"To set the range in which to search for each hyperparameter, we follow the configuration of...\"\n18. Page 29: \"Exact case\" is capitalised in the middle of a sentence. As is \"small Scale\". \n\n\n19. The last two sentences of page 12 (at the beginning of the Appendix) mean the same thing. I guess one of them should be deleted. \n\n\n\n\n\n\n\n\n/\n==========\nReferences\n==========\n\n[1] Valentin Thomas, Fabian Pedregosa, Bart van Merrie ̈nboer, Pierre-Antoine Mangazol, Yoshua Ben- gio, and NL Roux. Information matrices and generalization. 2019 arXiv preprint\n\n(Appears to have in fact been published at AiStats 2020  with the title \" On the interplay between noise and curvature and its effect on optimization and generalization\". )\n\n\n[2] James Martens. New insights and perspectives on the natural gradient method. JMLR 2020 \n\n\n[3] Haim Avron and Sivan Toledo. Randomized algorithms for estimating the trace of an implicit sym- metric positive semi-definite matrix. Journal of the ACM 2011\n\n", "summary_of_the_paper": "The authors experimentally investigate the ability of Takeuchi's information criterion to predict generalization gaps in various neural network architectures, with a particular focus on the Neural Tangent Kernel (NTK) regime. This was previously done only on small scale networks [1], and the authors extend it to state-of-the-art large scale architectures. In order to do this successfully, the authors propose to use various approximations, including the following: \n(1) The equivalent representation of the expected Hessian matrix H via the Gauss-Newton Matrix  (with the equivalence proven in [2]). \n(2) A block diagonalization approach that ignores correlations between layers. \n(3) An even coarser approximation that consists in ignoring the off-diagonal elements of the relevant matrices H (expected hessian) and C (correlaction of the gradient)\n(4) Hutchinson's method to estimate the trace of the Hessian (from [3])\n\n\nThe authors run a vast number of experiments and demonstrate that Takeuchi's information criterion exhibits significant correlation with the generalization gap and that many of their approximations perform well. The authors also propose to use the TIC to improve hyperparmeter search, with encouraging results. \n\n\n\n\n\n/\n==========\nReferences\n==========\n\n[1] Valentin Thomas, Fabian Pedregosa, Bart van Merrie ̈nboer, Pierre-Antoine Mangazol, Yoshua Ben- gio, and NL Roux. Information matrices and generalization. 2019 arXiv preprint\n\n(Appears to have in fact been published at AiStats 2020  with the title \" On the interplay between noise and curvature and its effect on optimization and generalization\". )\n\n\n[2] James Martens. New insights and perspectives on the natural gradient method. JMLR 2020 \n\n\n[3] Haim Avron and Sivan Toledo. Randomized algorithms for estimating the trace of an implicit sym- metric positive semi-definite matrix. Journal of the ACM 2011\n", "summary_of_the_review": "The authors deserve credit for funning a lot of experiments. However, there is minimal original contribution. Furthermore, the paper is poorly written and organised, and of insufficient mathematical rigour to warrant publication at ICLR. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: While the reviewers acknowledge the broad experimental work done in this paper, they all find several issues, which in their combination show that the paper is simply not in a good enough shape. This impression has not changed during the rebuttal phase and as a result, this is a clear reject.
Decision: Reject