Impact of classification difficulty on the weight matrices spectra in Deep Learning and application to early-stopping

In the past decade, deep learning (LeCun et al., 2015) has achieved impressive success in numerous areas. Much research effort has since been concentrated on providing a rational explanation of the success. The task is difficult, particularly because the training of most successful deep neural networks (DNNs) relies on a collection of expert choices that determine the final structure of the DNNs. These expert choices include nonlinear activation, hidden layer architecture, loss function, back propagation algorithm and canonical datasets. Unfortunately, these empirical choices usually bring nonlinearity into the model, and nonconvexity of optimization into the training process. As a matter of consequence, practitioners of deep learning are facing certain lack of general guidelines about the “right choices” to design and train an effective DNN for their own machine learning problem.

To make progress on the understanding of existing trained and successful DNNs, it is important to explore their properties in some principled way. To this end, a popular way has recently emerged in the literature, namely spectral analysis of various large characteristic random matrices of the DNNs, such as the Hessian matrices of the back-propagation algorithm, weight matrices between different layers, and covariance matrices of output features. Actually, such spectral analysis helps to gain insights into the behavior of DNNs, and many researchers believe that these spectral properties, once better understood, will provide clues to improvements in deep learning training (Dauphin et al., 2014; Papyan, 2019b, a; Sagun et al., 2017; Yao et al., 2020; Granziol, 2020; Pennington and Worah, 2019; Ge et al., 2021). Recently, Martin and Mahoney (2021) studied the empirical spectra distributions (ESD) of weight matrices in different neural networks, and observed a “Phase Transition 5+1” phenomenon in these ESDs. Interestingly, the phenomenon highlights signatures of traditionally regularized statistical models even though there is no set-up of any traditional regularization in the DNNs. Here, traditional regularization refers to the minimization of an explicitly defined and penalized loss function of the form $L(\theta)+\alpha\cdot p(\theta)$ with some tuning parameter $\alpha$ ($\theta$ denotes all the parameters in the DNN). However, those well-known expert choices such as early stopping also produces a regularization effect in DNNs, and this is the reason why such expert choices are recommended for practitioners. Actually, Kukacka et al. (2017) presented about 50 different regularization techniques which may improve DNN’s generalization. Among them, batch normalization, early stopping, dropout, and weight decay are a few commonly used ones.

A main finding from Martin and Mahoney (2021) is that the effects of these regularization practices can be identified through the spectra of different weight matrices of a DNN. Moreover, the forms of these spectra in the “5+1 phase transition” help assess the existence of some regularization in the DNN. For instance, if these spectra are far away from the Marčenko-Pastur (MP) law, or the largest eigenvalue departs from the Tracy-Widom (TW) Law (see in AppendixA), there is strong evidence for the onset of more regular structures in the weight matrices. A connection between implicit regularization in a DNN and the forms of the spectra of its weight matrices is thus established. Particularly, they considered the evolution of weight matrices spectra during the training process of a DNN from its start to its final stage (usually 200-400 epochs), and pointed out that in the late stage of the training, the deviation between the spectra and MP Law (namely the emergence of Heavy Tail) indicates some regularization technique which will improve the generalization error in some way. Indeed, the emergence of Heavy Tail is due to the complex correlations which are generated from such regularization technique. Some theoretical analysis of Heavy Tail is proposed to illustrate such correlations. Recently, Gurbuzbalaban et al. (2021) pointed out that SGD can bring out heavy tails in linear regression settings, Hodgkinson and Mahoney (2021) prove the phenomenon under a more generalized case.

A generally accepted definition of the concept of Regularization in a DNN refers to any supplementary mechanism that aims at making the model generalize better (see in Kukacka et al. (2017)). In the next work from Martin et al. (2021), they claimed that the “Heavy Tail based metrics can do much better—quantitatively better at discriminating among series of well-trained models with a given architecture; and qualitatively better at discriminating well-trained versus poorly trained models.” An important issue we notice from spectral analysis is HT plays a more significant role for guiding the practice of Deep Learning . In our synthetic data experiments, an interesting phenomenon is that HT emerges when the training data quality is low. Unlike the factors proposed by Hodgkinson and Mahoney (2021) such as increasing the step size/decreasing the batch size or increasing $L_{2}$ regularization to achieve Heavy Tail, we emphasize a special factor that affect the emergence of Heavy Tail–classification difficulty in data sets. More difficult to classify, higher possibility HT appears. We say the factor is specical in the reason that it includes two different cases when HT appears. One case is the poor data quality, the emergence of HT indicates an attempt for DNNs to extract more features and increase testing accuracy. Another case is modern data sets with complex features and hard for the information extraction, the emergence of HT indicates an attempt for DNNs to identify data information and improve generalization error. Both cases are in high classification difficulty, but the training results could be entirely different. In the second case, the emergence of HT indicates the feature extraction and some regularization for improving the test accuracy. However, in the first case, HT indicates some excessive information extraction and thus overfitting happens.

The paper is aim to give a more comprehensive understanding of HT phenomenon. Intuitively, the classification difficulty is a metric for how difficult the data sets will get classification or get prediction under certain model architectures. Nevertheless the classification difficulty is vague and hard for a clear definition, there are a lot of indicators that give a significant impact. For example, the decrease of signal-to-noise ratio (SNR), the increment of class numbers $K$ or the complex features in the data sets would all increase the difficult level for the data sets to get classification. The factor we find is indeed consistent with the statement in Martin and Mahoney (2021). In line with Martin et al. (2021), the weight matrix spectrum could be regarded as information encoder during training procedure. Leveraging on this findings, a spectral criterion is proposed in section 4 to guide the early stopping in practice. To our best knowledge, it is the first quantitative criterion based on the spectra to guide early stopping in practice. Without prior information, HT indicates some regularization at play or some problematic issues such as overfitting in the training procedure. The spectral criterion depends on the detection of appearance of HT. We summarize our contributions below:

1. 1.

   We identify that the classification difficulty is a driving factor for the appearance of heavy tail in weight matrices spectra. Experiments are conducted on both synthetic and real data sets. Decrease of SNR or increment of class numbers $K$ in Gaussian data experiments, which both bring in higher classification difficulty, will generate heavy tail at the end of training. In real data experiments, heavy tails appears more in experiments with CIFAR10 than with MNIST due to the complex features in CIFAR10.

2. 2.

   Following the previous work in Martin and Mahoney (2021), the terminal spectrum bulk type in our paper are divided into three parts: Light Tail (LT), Bulk Transition period (BT) and Heavy Tail (HT). With decrease of classification difficulty, the terminal weight matrix spectrum has the phase transition from HT $\to$ BT $\to$ LT.

3. 3.

   Leveraging on this finding, we propose a spectral criterion to guide the early stopping without access of testing data. The HT(BT)-based spectral criterion could not only cut off a large training time with just a little drop of test accuracy, but also avoid over-fitting even when the training accuracy is increasing.

The paper summarizes experimental results in the sections 2 and 3, and the details of spectral criterion for early stopping could be refered in section 4.

Most deep neural networks are applied to real world data. These networks are however too complex in general for developing a rigorous theoretical analysis on the spectral behavior. For a theoretical investigation, a widely used and simplified model is the Gaussian input model (Lee et al., 2018). By examining a well-defined Gaussian model for classification, we establish the evidence for a classification difficulty driving regularization via the confirmation of a transition phenomenon in the spectra of network’s weight matrices in the order of HT $\to$ BT $\to$ LT. Moreover, the transition is quantitatively controlled by a single parameter of data quality in the Gaussian model, namely its signal-to-noise ratio (SNR).

Table 1 gives a short summary of the findings.

We empirically observe the spectrum transition in all settings. The transition is fully driven by the classification difficulty. Therefore, in this Gaussian model, the indicated implicit regularization in the trained DNN is data-effective, directly determined by the difficulty. Precisely, under low level SNR or high class numbers, the weight matrices of a DNN deviates far away from the common MP model. Instead, they are connected to very different complex Random Matrix models. The decrease of classification difficulty drives the weight matrices from Heavy Tailed model into MP models at the final training epoch.

The previous results are based on synthetic Gaussian data. Here we conduct experiments with real data sets to show the impact of complex features in data on weight matrices spectra. The DNNs chosen for these experiments are LeNet, MiniAlexNet and VGG11 (LeCun et al., 1998; Krizhevsky et al., 2012), which are the most classic and representative DNNS in pattern recognition. We consider two data sets, the MNIST and CIFAR10. Note that in Martin and Mahoney’s work, the data sets such as CIFAR10, CIFAR100 and Image1000 all bring in HT type spectra due to complex features unlike the MNIST data set. In our experiments, we select MiniAlexNet instead of the more extensive AlexNet to reduce computing complexity. Table 6 gives the type of spectra obtained in the trained NNs with each data set.

In training with MNIST, the spectra of weight matrices are always LT type, independently of the used NN; for CIFAR10, the spectra are always HT type in all networks. The testing accuracies of detection on MNIST are 99% in all networks, while those on CIFAR10 are 64% with LeNet, 76% with MiniAlexNet and 81% with VGG11 respectively. The differences in testing accuracy give evidence that CIFAR10 has much more complex features than MNIST, and the complex features indicate more classification difficulty in CIFAR10 than MNIST. In the real data experiments, it shows that training on CIFAR10 is more likely to bring in the HT, which gives new evidence on the impact of classification difficulty on weight matrices spectra. Moreover, The complex features will also bring in the complex correlations during training procedure and thus HT emerges. Full details for these experimental results are reported in Section 3.2.

As a regularization technology in Deep Learning, early stopping is adopted to improve generalization accuracy of a DNN. People may use testing data set to obtain convenient stopping time in practice, but when we model the data set, it is a trade off to separate data set into training and testing. Sometimes as Martin et al. (2021) pointed out, it is more expensive to acquire the testing data set. There are also situations where practioners of Deep Learning are laid to use pre-trained and existing DNNs without access to test data.

So an important question we address here is: Without any testing data set, shall we early stop or not? And how to define an early stopping time?

The spectra of weight matrices encode information during the training time, according to this we construct an application to guide the early stopping through a Spectral Criterion. Precisely, we introduce a distance between an observed weight matrix spectrum and the reference MP Law. When this distance is judged large enough, we obtain evidence for the formation of a HT or BT type spectrum, thus the implicit regularization in the DNN leads to the decision of stopping the training process. Note that this spectral criterion for early stopping does not need any test data.

We now describe this spectral criterion in more detail. Consider a $n\times N$ ($n\leq N$) weight matrix $W$ and let $X_{1},X_{2},...,X_{n}$ be the $n$ non-zero eigenvalues of the square matrix $WW^{T}$. (These are also, by definition, the squares of the singular values of the matrix $W$. The initialization of $W$ has been rescaled with $1/\sqrt{N}$.) We then construct a histogram estimator $\hat{p}_{M}(x)$ for the joint density of the eigenvalues using $M$ bins. Next, let $p_{c,\sigma^{2}}(x)$ be the reference Marčenko-Pastur density (Appendix A) depending on a scale parameter $\sigma^{2}$ and a shape parameter $0<c<1$, with a compact support $[a,b]$ ($0<a<b$). In practice, the parameters $c$ and $\sigma^{2}$ in the reference MP density $p_{c,\sigma^{2}}(x)$ are also estimated by using $X_{1},...,X_{n}$. This leads to an estimated MP density function $p_{\hat{c},\hat{\sigma}^{2}}(x)$. The estimation of distance between the distribution of the $n$ eigenvalues and the MP density is defined as $L_{1}$ distance

Under the null hypothesis that the eigenvalues $\{X_{i}\}$ follow the MP law, we have a precise rate for $\hat{s}_{n}\to 0$, which leads to our spectral criterion.

The whole details on the determination of the distance value $\hat{s}_{n}$ and the threshold value $s_{*}$ are given later in Section 4.1. One may ask why the appearance of a HT spectrum is a good early stopping time? Let us elaborate more on the important reasons for the early stopping rule above based on the appearance of a HT spectrum. Martin et al. (2021) mentioned that MP Law spectra could not evaluate the performance of the trained model, but Heavy Tail spectra could. The Heavy Tail spectra may correspond to better or worse test performance. From information encoder perspective, we argue that the emergence of Heavy Tail or Rank Collapse in weight matrices could be viewed in two ways:

• •

  Indication of the poor quality in the training data or the poor ability in the whole system: in synthetic data experiments, the poor training data or system quality will lead to instability or overfitting during the whole training dynamics. So the emergence of Heavy Tail can be treated as an alarm for these hidden and problematic issues in the network.

• •

  Indication of a regularized structure that has acquired considerable information from the training data: from another point of view, the HT phenomenon is far from the initial MP Laws introduced with random weight initialization. Its emergence can be viewed as an indication of a well-trained structure that has already captured sufficient information from the input data. Such structure will somehow ensure the testing accuracy of the whole system, and additional training will not bring much improvement.

The spectra criterion is validated in both synthetic and real data experiments. Evidence for this spectral criterion is developed in details with extensive experimental results in Sections 4.2 and 4.3. In synthetic data experiments, the spectral criterion provides an early stopping epoch where the testing accuracy is much higher than the final testing accuracy, even when the training accuracy is still increasing. In real data experiments, the spectral criterion could also offer high-quality stopping time, ensuring testing accuracy and cutting off a large unnecessary training time.

Data classification difficulty has a great impact on the spectra of weight matrices. We study it from three aspects: SNR, class numbers and complex features, and find that more difficult to classify, higher probability HT emerges. Further, in line with Martin and Mahoney (2021), HT could be regarded as a training information encoder and indicates some implicit regularization. Such implicit regularization in the weight matrices provides a new way of understanding the whole training procedure. We apply this phenomenon to derive an early stopping procedure in order to avoid over-training (in case of poor data quality) and cut off large training time. From the encoded information, spectral criterion could even provide an early stopped time when the training accuracy is increasing.

Spectral Analysis provides a new way for the understanding of Deep Learning. Once understood spectra in DNNs better, more practical guidance for the whole learning procedures may be provided. Our study in weight matrices spectra also leads to several questions to explore in the future, such as how SGD generates Heavy Tail in the poor data quality but Light Tail in the high data quality in DNNs.