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
Organizations: Department of Computer Science and Operations Research, Université de Montréal, Canada · Mila – Quebec AI Institute, Canada · Department of Mathematical Informatics, The University of Tokyo, Japan · Center for Advanced Intelligence Project, RIKEN, Japan · Supercomputing Research Center, Institute of Science Tokyo, Japan · Department of Computer Science, Institute of Science Tokyo, Japan · DENSO IT Laboratory, Japan
Generalization measures have been studied extensively in the machine learning community to better characterize generalization gaps. However, establishing a reliable generalization measure for statistically singular models such as deep neural networks (DNNs) is difficult due to their complex nature. This study focuses on Takeuchi's information criterion (TIC) to investigate the conditions under which this classical measure can effectively explain the generalization gaps of DNNs. Importantly, the developed theory indicates the applicability of TIC near the neural tangent kernel (NTK) regime. In a series of experiments, we trained more than 5,000 DNN models with 12 architectures, including large models (e.g., VGG-16), on four datasets, and estimated the corresponding TIC values to examine the relationship between the generalization gap and the TIC estimates. We applied several TIC approximation methods with feasible computational costs and assessed the accuracy trade-off. Our experimental results indicate that the estimated TIC values correlate well with the generalization gap under conditions close to the NTK regime. However, we show both theoretically and empirically that outside the NTK regime such correlation disappears. Finally, we demonstrate that TIC provides better trial pruning ability than existing methods for hyperparameter optimization.
Figures & tables
Figure 1: Approximation comparison experiments in a small-scale setting. Panel (a) shows the equality of Tr(H) and Tr(F) . Panels (b), (c), and (d) compare different approximation methods for the TIC estimation to the exact case. Full results are shown in Appendix D.2.2 .
Category
TIC Estimates
Problem Setting: Dataset & Model
Ratio: d/n
Small-scale Data<1 MB Model<50 KB
Exact and Approx. (Block Diag, Diag, and Lower Bound)
TinyMNIST on 2-NN w/o SC 3 3 footnotemark: 3 TinyMNIST on 3-NN w/o and w/ SC ♯ TinyMNIST on 3-LNN w/o and w/ SC
0.09 0.02 0.02
Practical-scale Data>20 MB Model>0.5 MB
Approx. (Diag and Lower Bound)
⋆ MNIST on 6-NN w/o and w/ SC ♯⋆ MNIST on 6-LNN w/o and w/ SC ⋆ MNIST on Simple CNN ♯⋆ CIFAR10 on 6-LNN w/o and w/ SC ⋆ CIFAR10 on ResNet8 w/o BN 4 4 4 2-NN and 3-LNN denote the 2-Layer Nonlinear Neural Network and 3-Layer Linear Neural Network, respectively. SC denotes Skip-Connection. ⋆ CIFAR10 on VGG16 w/o BN ⋆ CIFAR100 on ResNet8 w/o BN
2.50 2.50 268.92 8.72 122.65 3357.53 122.65
Table 1: Two categories of experimental settings. Problem settings with ♯ and ⋆ indicate the use of a linear neural network and that the problem setting is considered to be nearly in the NTK regime, respectively. For hyperparameter search, we performed Bayesian optimization for all experimental settings. Appendix C.2 provides further detailed configurations of hyperparameters and other settings for the experiment. The remaining experimental settings are explained in Appendix C .
Figure 2: Correlation between the generalization gap and the TIC estimates. Panel (a) shows a problem setting outside the NTK regime, where the correlation between TIC and the generalization gap is weak; Panels (b) and (c) show a problem setting close to the NTK regime, where the correlation is stronger. Full results are given in Appendix D .
Figure 3: Relationship between Pearson’s correlation (generalization gap and TIC estimates) and d/n . Each point represents one workload (architecture and dataset combination); the Pearson correlation coefficient is computed across all trained models within that workload. The correlation between TIC estimates and the generalization gap is high in regions with large d/n , which are considered to be close to the NTK regime. Full results for other metrics, including Spearman’s correlation and Kendall’s τ , are shown in Appendix D .
Figure 4: Correlation between the generalization gap and the TIC estimates in the training process . The color bar represents the number of trained model epochs. Full results are shown in Appendix D.3 .
Figure 5: A comparative experiment using TIC as an evaluation value for pruning with SHA in HPO for training of CIFAR10 on ResNet-8 : Panel (a) shows the case in which all hyperparameter candidates are trained to the end without pruning. Panel (b) shows the case in which pruning is performed based on validation loss as a baseline. Panel (c) shows the pruning method using TIC. The legends on the right-hand side show the trials with different hyperparameters; the final generalization performance (validation loss) to be reached is shown in descending order. The 1st place trial is shown in dark purple; the 3rd place trial is in light purple.
Appendix figures & tables23 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 6: TIC takes into account the bias of the estimate.
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
Appendix
Table 2: Experiments: Workloads
Figure 7: Distribution of training loss and generalization gap on the trained models.
Figure 8: Relationship between correlation coefficient 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.
Model
Dataset
Spearman’s Correlation
Kendall’s τ
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
Appendix
Table 7: Correlation: TIC estimates Tr(C(θ))/Tr(F(θ)) and generalization gap
Figure 9: Small-scale experiments: comparison of the TIC estimate w/ H(θ) and F(θ) . Dataset: TinyMNIST.
Figure 10: Small-scale experiments: comparison of the TIC estimate.
Figure 11: Small-scale experiments: comparison of the TIC estimate and generalization gap.
Figure 12: Small-scale experiments: comparison of the TIC estimate and generalization gap.
Dataset
Model
Spearman’s Correlation
Kendall’s τ
Pearson’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
Appendix
Table 8: Correlation: TIC Estimates Tr(F(θ)−1C(θ)) and Generalization Gap
Dataset
Model
Spearman’s Correlation
Kendall’s τ
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 w/ 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
Appendix
Table 9: Correlation: TIC Estimates Tr(Fblockdiag(θ)−1Cblockdiag(θ)) and Generalization Gap
Dataset
Model
Spearman’s Correlation
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 w/ SC
0.932
0.796
0.918
Appendix
Table 10: Correlation: TIC Estimates Tr(Fdiag(θ)−1Cdiag(θ)) and Generalization Gap
Figure 13: Practical-scale MNIST experiments: comparison of the TIC estimates.
Figure 14: Practical-scale MNIST experiments: elements of the TIC estimates.
Figure 15: Practical-scale CIFAR experiments: comparison of the TIC estimates.
Figure 16: Practical-scale CIFAR experiments: elements of the TIC estimates.
Figure 17: Correlation between generalization gap and TIC estimates in MNIST experiments, through training process. The color map shows the epoch.
Figure 18: Correlation between generalization gap and TIC estimates in CIFAR experiments, through training process. The color map shows the epoch.
Dataset
Model
Exact w/FC
Block Diag w/FC
Diag w/FC
Lower Bound w/FC
Exact w/HC
Block Diag w/HC
Diag w/HC
Lower Bound w/HC
Lower Bound w/HC by Hutchinson’s Method
Tiny MNIST
2-wide NN
10.9093
6.7516
3.7273
1.9069
105.4282
96.0647
92.979
82.0081
2.7814
Tiny MNIST
3-NN
3.8641
3.8435
3.7937
1.994
23.9083
22.4055
21.7705
22.4203
2.5705
Tiny MNIST
3-NN w/ SC
3.8999
3.8568
3.8239
2.0225
26.2303
24.9561
25.0151
24.9217
2.8932
Tiny MNIST
3-LNN
3.8656
3.847
3.7991
1.9521
23.188
22.2685
22.1641
21.6511
2.8645
Tiny MNIST
3-LNN w/ SC
3.8771
3.8962
3.8159
1.9594
23.8571
22.8106
23.0338
22.0721
2.7198
MNIST
6-NN
N/A
N/A
3.7235
1.9172
N/A
N/A
N/A
N/A
2.8949
Appendix
Table 11: Full Details of the Runtime Measurement Experiment. Unit: seconds
Category
Problem Setting: Dataset & Model
Ratio: d/n
Small Scale Data Size <1 MB Model <50 KB
TinyMNIST on 2-NN w/o SC TinyMNIST on 3-NN w/o SC, 3-NN w/ SC TinyMNIST on 3-LNN w/o SC, 3-LNN w/ SC SmallTinyMNIST on 3-LNN w/o SC TinyMNIST on Wide 3-NN w/ SC
0.09 0.02 0.02 0.36 13.90
Appendix
Table 12: Additional problem settings are highlighted in bold text
Figure 19: Distribution of training loss and generalization gap on the trained models.
Figure 20: Relationship between TIC estimates and generalization gap.
Model
Dataset
Spearman’s Correlation
Kendall’s τ
Pearson’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
3-Wide NN w/ SC
Tiny MNIST
0.834
0.656
0.967
Appendix
Table 13: Correlation: TIC estimates Tr(C(θ))/Tr(F(θ)) and generalization gap
Understanding the generalization performance of over-parameterized neural networks has become a central topic in deep learning theory. While recent advances, particularly works under the Neural Tangent Kernel (NTK) regime, have shed light on the behavior of shallow architectures, the statistical generalization properties of deep neural networks (DNNs), especially in regression tasks, remain far less understood. In this paper, we make significant progress toward closing this gap by providing a comprehensive generalization analysis of DNNs trained using gradient-based methods. First, we establish, for the first time, a crucial connection between the learning dynamics of a DNN with smooth activation functions trained via gradient-based methods and those of kernel methods, showing that gradient-based methods on over-parameterized DNNs can fully inherit the favorable learning dynamics of their kernel counterparts. Building on this connection and the well-established optimality of kernel methods, we derive the first known minimax-optimal rates for the excess population risk of both gradient descent (GD) and stochastic gradient descent (SGD), under the assumption that network width scales polynomially with the sample size. Our results demonstrate that, with sufficient width, DNNs trained by GD or SGD can achieve generalization performance comparable to kernel-based methods.
Junyu Zhou, Puyu Wang, Yunwen Lei +2
Mathematical Institute for Machine Learning and Data Science, Catholic University of Eichstätt-Ingolstadt · Department of Computer Science, RPTU Kaiserslautern-Landau · Department of Mathematics, The University of Hong Kong +1
We derive a differential equation that governs the evolution of the generalization gap when a model is trained by gradient descent-based methods. This differential equation is driven by two key quantities, a contraction factor that brings together trajectories corresponding to slightly different datasets, and a perturbation factor that accounts for them training on different datasets. The coupled decay of contraction and perturbation guarantees a controlled accumulation of generalization gap during training. We analyze this differential equation to show that the generalization gap is given by a quadratic form that consists of an ``effective Gram matrix'' that depends upon the training trajectory and a certain residual of the predictor at initialization. Our framework is applicable to general deep networks and smooth loss functions. In numerical experiments on different neural network architectures, datasets and sample sizes, we show that this quadratic form accurately captures the actual generalization gap. We also show how to instantiate our framework in a number of examples via analytical calculations. For example, for high-dimensional linear regression, our framework matches existing calculations of generalization gap in the literature exactly in under-parameterized, over-parameterized and critical regimes.
Rubing Yang, Pratik Chaudhari
Department of Applied Mathematics and Computational Sciences, University of Pennsylvania Philadelphia, PA, 19104, USA · Department of Electrical and Systems Engineering, University of Pennsylvania Philadelphia, PA, 19104, USA
Recent progress has been made in understanding the statistical generalization performance of gradient descent methods for overparameterized neural networks within the neural tangent kernel (NTK) regime. However, most of the existing work on regression problems is limited to shallow network architectures, leaving a notable gap in the theory of deep neural networks. This paper addresses this gap by presenting a comprehensive generalization analysis for deep ReLU networks trained using gradient descent (GD) and stochastic gradient descent (SGD). Specifically, we establish the first known minimax-optimal rates of excess population risk for both GD and SGD with deep ReLU networks, under the assumption that the network width scales polynomially with respect to the network depth and training sample size. Our results demonstrate that with sufficient width, gradient descent methods for deep ReLU networks can achieve optimal generalization rates on par with kernel methods.
Junyu Zhou, Puyu Wang, Yunwen Lei +2
Mathematical Institute for Machine Learning and Data Science, KU Eichstätt-Ingolstadt, Ingolstadt, Germany · Department of Computer Science, RPTU Kaiserslautern-Landau, Kaiserslautern, Germany · Department of Mathematics, University of Hong Kong, Hong Kong, China +1