
\section{Introduction}
\label{section_introduction}
The gap between learning-theoretic generalization bounds for highly overparameterized neural networks and their empirical generalization performance remains a fundamental mystery to the field
\citep{zhang2016understanding, jiang2019fantastic, allen2019learning}. While these models are already successfully deployed in many applications, improving our understanding of how neural networks perform on unseen data is crucial for safety-critical use cases. By understanding which factors drive generalization in neural networks we may further be able to develop more efficient and performant network architectures and training methods. 

\begin{figure}[t]
\begin{center}
\centerline{\includegraphics[width=\columnwidth]{images/prunability_vs_model_size_based_gen_measures.pdf}} \vspace{-6pt} 
\caption{\textbf{Existing model size-based complexity measures fail to capture the observation that lager models generalize better.} Such measures based on norms or parameter-counts grow as model size is increased and the generalization error (orange) decreases. The same applies to existing measures based on the model size of \textit{compressed} models (green) and a particularly strong norm-based baseline (red) studied by \citet{jiang2019fantastic}. We propose a new generalization measure based on the relative model size after pruning (blue) and show that this measure correctly predicts the decrease in generalization error as model size increases. This example of ResNets trained on CIFAR-10 is merely an illustration of our claim. We provide a rigorous examination in Section \ref{section_experimental_results}. \vspace{-12pt} }
\label{figure_pruned_parameter_count_vs_prunability}
\end{center}
\vskip -0.2in

\end{figure}

Numerous theoretically and empirically motivated attempts have been made to identify \textit{generalization measures}, properties of the trained model, training procedure and training data that distinguish models that generalize well from those that do not \citep{jiang2019fantastic}. A number of generalization measures have attempted to quantify Occam's razor, i.e.\ the principle that \textit{simpler} models generalize better than complex ones  \citep{neyshabur2015normbased, bartlett2017spectrally}. This has proven to be non-trivial, as many measures, particularly norm-based measures, grow with the size of the model and thus incorrectly predict that larger networks will generalize worse than smaller networks.

In this paper, we propose a new way of quantifying a model's simplicity that avoids this failure mode. We leverage the empirical observation that large fractions of trained neural networks' parameters can be \textit{pruned} -- that is, set to 0 -- without hurting the models' performance \citep{gale2019state, zhu2017prune, han2015learning}. Based on this insight, we introduce a new measure of a model's simplicity which we call \emph{prunability}: the smallest fraction of weights we can keep while pruning a network without hurting its training loss.

In a range of empirical studies, we demonstrate that a model's prunability is highly informative of its generalization. In particular, we find that the larger the fraction of parameters that can be pruned without hurting a model's training loss, the better the model will generalize.
Overall, we show that the smaller the fraction of parameters a model actually ``uses" --  the \textit{simpler} it is -- the better the network's generalization performance. 

We illustrate the limitations of existing generalization measures based on parameter counts, norms and pruning in \ref{figure_pruned_parameter_count_vs_prunability}. We compare ResNets of varying widths that are trained on CIFAR-10. We remove the smallest parameters from each model up to the point where further pruning would cause a spike of the training loss. We observe that the absolute number of parameters that remain after pruning grows with the model width, while the test error decreases with model width. A strong norm-based baseline studied by \citet{jiang2019fantastic} also grows with the model size. The fraction of parameters that remains after pruning – the prunability – decreases with the model width, correctly predicting that wider models generalize better.

Recent empirical studies \citep{jiang2019fantastic, jiang2018predicting} identify three classes of generalization measures that do seem predictive of generalization: measures that estimate the \textit{flatness} of local minima, the speed of the optimization, and the margin of training samples to decision boundaries. We empirically compare our proposed generalization measure against strong baselines from each of these classes. We find that prunability seems competitive with most of these strong baselines and that our measure seems to capture a different aspect of generalization than the existing measures. Additionally, we study a particularly challenging setting for many generalization measures – Deep Double Descent \citep{nakkiran2019deep} – and show that prunability captures this phenomenon better than previously proposed baselines.

In summary, our main contributions are thus the following:
\begin{enumerate}
    \item We introduce a new generalization measure called \textit{prunability} that captures a model's simplicity (Sec. \ref{section_prunability}) and show that across a large set of models this measure is highly informative of a network's generalization performance (Sec. \ref{section_performance_of_prunability}). While we also provide some theoretical motivation for this measure, we see our empirical study as the main contribution of this paper and an important stepping stone towards a more comprehensive theoretical understanding of prunability.
    
    \item We show that even in a particularly challenging setting in which we observe a test loss double descent \citep{nakkiran2019deep, he2016identity}, prunability is informative of models' test performance and is competitive with an existing strong generalization measures (Sec. \ref{section_double_descent_results}).
    
    \item Lastly, we investigate whether the success of prunability can be explained by its relationship to flat local minima. We find that while prunability makes similar predictions to some existing measures that estimate the flatness of minima, it differs from them in important ways, in particular exhibiting a stronger correlation with generalization performance than these flatness-based measures (Sec. \ref{section_performance_of_prunability} and \ref{section_comparison_of_generalization_measures}).
\end{enumerate}


\section{Related Work}
\label{section_related_work}
\vspace{-3pt}

\citet{rissanen1986stochastic} formalizes Occam's razor as a model's Minimum Description length, a concept which was later applied to small neural networks by \citet{hinton1993keeping}. Similarly, \citet{neyshabur2015normbased, neyshabur2017exploring} and numerous other approaches suggest that networks with smaller parameter norms generalize better. These measures, however, incorrectly predict that \textit{smaller} models generalize better than larger models, the opposite of what is observed empirically \cite{jiang2019fantastic}. \citet{zhou2018non} formulate a generalization bound that is non-vacuous even for large network architectures based on the description length of a compressed (pruned, quantized and efficiently encoded) network. While this is an elegant approach, the authors acknowledge that the compressed model size also grows with the size of the original network and thus suffers from the same problem as the other approaches based on model size described above. In contrast, we propose and evaluate a pruning-based generalization measure that is able to overcome this limitation.
 See Figure \ref{figure_pruned_parameter_count_vs_prunability} for an example of this problem and Section \ref{section_performance_of_prunability}) for our empirical results on this. 

While generalization measures have been studied for a long time \citep{vapnik2015uniform, mcallester1999pac, neyshabur2015normbased, zhang2016understanding, keskar2016large, nagarajan2019generalization, dziugaite2017computing}, \citet{jiang2019fantastic} recently brought new empirical rigor to the field. They perform a large-scale empirical study by generating a large set of trained neural networks with a wide range of generalization gaps. Proposing a range of new evaluation criteria, they test how predictive of a model's generalization performance previously proposed generalization measures actually are. In this paper, we evaluate our new generalization measure in the same framework and use the strongest measures as baselines for comparison against our proposed measure, the neural network's prunability. 

According to \citet{jiang2019fantastic}, three classes of generalization measures seem to be particularly predictive of generalization. First, measures that estimate the \textit{flatness} of local minima, either based on random perturbations of the weights \citep{neyshabur2017exploring, dziugaite2017computing, jiang2019fantastic, mcallester1999pac, arora2018stronger} or directly based on the curvature of the loss surface \citep{maddox2020rethinking}. In a purely empirical study, \citet{morcos2018importance} find that a model's robustness to clamping the \textit{activations} of individual units to fixed values is predictive of its generalization performance. Second, margin-based measures that use the distance of training samples to decision boundaries \citep{jiang2018predicting}. Lastly, \citet{jiang2019fantastic, ru2020revisiting} have proposed measures that estimate the speed of optimization. 


We also evaluate our proposed generalization measure against another surprising phenomenon of generalization: Under certain conditions \textit{double descent} curves can be observed in which the test loss first decreases, then increases and then decreases again as a model's parameter count is increased \citep{he2016identity, nakkiran2019deep, belkin2018reconciling}. In contrast, many existing generalization measures grow monotonically with the model's size and thus fail to capture the double descent phenomenon, making it a particularly interesting setting to study new generalization measures \citep{maddox2020rethinking}.
 

Last, we provide a brief overview of recent research on neural network pruning. It is well established a large fraction of a network's parameters can be removed without impairing performance \citep{gale2019state, blalock2020state}; in fact, such pruning often \textit{improves} generalization performance \citep{thodberg1991improving}.  There are many approaches to selecting parameters for removal; we focus on randomly selected parameters (random pruning) and removing the smallest-magnitude parameters (magnitude pruning), though other approaches exist in the literature \citep{han2015learning, renda2020comparing, lee2018snip, Wang2020Picking, blalock2020state}. Random pruning is applied by the regularization method dropout \citep{srivastava2014dropout}, which is used to improve network generalization performance. Magnitude pruning can be used in an iterative pruning and retraining procedure \citep{frankle2018lottery} to identify sparse subnetworks that, for some sparsity levels, generalize better than their parent network. Both approaches are therefore natural candidates for a notion of network simplicity, which we will leverage in our proposed generalization measure.
In Dropout, random weights are temporarily removed during training to improve the models generalization performance at the end of training. In the Lottery Ticket research pruning is used to identify subnetworks which can be retrained to match the performance of the original network. In this paper, we study the distinct question of how we can use pruning after training and without any retraining to predict a model's generalization performance. In particular, we show that the larger the fraction of a model's parameters that can be removed without hurting the model's training loss, the better the model's generalization performance.

\vspace{-6pt}
\subsection{Notation}
\label{section_notation}
Following the notation of \citet{jiang2019fantastic}, we denote by ${\mathbb{D}}$ the distribution over inputs ${\tens{X}}$ and corresponding labels $y$.
We write ${\mathbb{S}}$ for a given data set containing $m$  tuples $\{({\tens{X}}_1, y_1),\dots, ({\tens{X}}_m, y_m)\}$ drawn i.i.d. from ${\mathbb{D}}$ where ${\tens{X}}_i \in \mathcal{X}$ is the input data and $y_i \in \{1,\dots,\kappa\}$ the class labels. In that, $\kappa$ is the number of classes. Furthermore, we denote a feedforward neural network by $f_{\bm{w}}: \mathcal{X} \rightarrow \mathbb{Z}$, its weight parameters by ${\bm{w}}$ and the number of its parameters by $\omega$. For the weight tensor of the $i^{th}$ layer of the network we write ${\tens{W}}_i$. The weight vector can be recovered as ${\bm{w}} = vec({\tens{W}}_1, \dots, {\tens{W}}_d)$, where $d$ is the depth of the network and $vec$ denotes the vectorization operator.

Let $L$ be the 1-0 classification error under the data distribution ${\mathbb{D}}$ : $L(f_{{\bm{w}}}) \coloneqq \mathbb{E}_{({\tens{X}}, y) \sim {\mathbb{D}}}[f_{\bm{w}}(X) \not = y] $, and let $\hat L$ be the empirical 1-0 error on ${\mathbb{S}}$: $\hat L(f_{{\bm{w}}}) \coloneqq \frac{1}{m}\sum_{i=1}^m [f_{\bm{w}}(X_i) \not = y_i]$. We define the \textbf{generalization gap} as $g(f_{\bm{w}}) \coloneqq L(f_{{\bm{w}}}) - \hat L(f_{{\bm{w}}})$.
When training a network, we denote each hyperparameter by $\theta_i \in \Theta_i$ for $i = 1, \dots n$ where $n$ is the total number of hyperparameters.  We denote a particular hyperparameter configuration by ${\bm{\theta}} \coloneqq (\theta_1, \theta_2, \dots, \theta_n) \in \Theta$, where $\Theta \coloneqq  \Theta_1 \times \Theta_2 \times \dots \times \Theta_n$ is the space of hyperparameters.

\vspace{-6pt}
\section{Prunability}
\vspace{-3pt}
\label{section_prunability}
A generalization measure should satisfy three straightforward desiderata: 1) It should correlate with the generalization gap across a broad range of models. 2) Directly optimizing the measure during training should lead to improved generalization. 3) It provide new insights based on which theoretical understanding may be developed.

A measure based on magnitude- and random pruning presents a promising direction for satisfying all three desiderata. First, it is well-established that we can remove large fractions of a neural network's parameters without negatively impacting its train performance, while also improving its test performance \citep{blalock2020state, thodberg1991improving}. Second, training models using dropout, i.e. random pruning, is widely known to improve generalization \citep{srivastava2014dropout}.
Finally, pruning has a theoretical grounding in the minimum description length principle and in PAC-Bayesian bounds and further theoretical analysis might well tighten existing bounds.

\looseness -1 Indeed, we show how a simple extension of an existing PAC-Bayesian generalization bound \citep{mcallester1999pac} motivates the study of our proposed generalization measure. The PAC-Bayesian framework allows us to quantify the worst-case generalization performance of random predictors. PAC-Bayesian bounds define model complexity as the KL divergence between some fixed prior distribution $P$, and the probability distribution over functions induced by the random predictor (often called the posterior $Q$, although this may not correspond to a Bayesian posterior) to obtain generalization bounds of the following form.
\vspace{-4pt}
\begin{theorem}\cite{mcallester1999pac}
For any $\delta > 0$, data distribution ${\mathbb{D}}$, prior $P$, with probability $1 - \delta$ over the training set, for any posterior $Q$ the following bound holds:
$$\mathbb{E}_{{\bm{v}} \sim Q} [L(f_{\bm{v}})] \leq \mathbb{E}_{{\bm{v}} \sim Q} [\hat{L}(f_{\bm{v}})] + \sqrt{\frac{KL(Q||P) + \log(\frac{m}{\delta})}{2(m -1)}}$$
\end{theorem}
\citet{mcallester2013pacbayesian} shows that in the case where both the prior and posterior are distributions over networks to which dropout with a given dropout probability $\alpha$ is applied, the KL term becomes: $KL(Q||P) = \frac{1 - \alpha}{2}||{\bm{w}}||^2$. We can directly use this formalization to derive a generalization bound for networks that are randomly pruned to the largest $\alpha$, s.t. $\mathbb{E}_{{\bm{v}} \sim Q} [\hat{L}(f_{\bm{v}})] < \hat{L}(f_{\bm{w}}) \times (1 + \beta)$, i.e., such that the training loss does not increase more than a relative tolerance $\beta$. We have to adjust the bound to account for the search for $\alpha$. In particular, we make use of the fact that we search over a fixed number $c$ of possible values for $\alpha \in [0, 1]$, using a union bound argument which changes the log term in the bound to $\log(\frac{cm}{\delta})$. As a result, we obtain the following bound on the expected generalization gap:
\vspace{-4pt}
\begin{equation}\label{eq:pacbound}
\mathbb{E}_{{\bm{v}} \sim Q}[g(f_v))] \leq \sqrt{\frac{\frac{1 - \alpha}{2}||{\bm{w}}||_2^2 + \log(\frac{m}{\delta})  + \log(c)}{2(m -1)}}, \end{equation}
where $\mathbb{E}_{{\bm{v}} \sim Q}[g(f_v))] = \mathbb{E}_{{\bm{v}} \sim Q} [L(f_{\bm{v}})] - \mathbb{E}_{{\bm{v}} \sim Q} [\hat{L}(f_{\bm{v}})]$.
While this bound will be vacuous for many large neural networks, it does provide us with some intuition for why we should expect a model's generalization to be linked to its robustness to pruning. In particular, this bound suggests that, the larger the fraction $\alpha$ of weights that can be pruned without hurting the model's training loss, the smaller the generalization gap $g(f_{\bm{w}})$ will be. It is this prediction that we empirically investigate in our experiments. Details on the derivation in can be found in Appendix \ref{section_pruning_pac_bayes_bound}.  
\vspace{-6pt}
\subsection{Definition}
\vspace{-3pt}
Given a trained model and a pruning algorithm, we define the model's \textbf{prunability} as the smallest fraction of the model's parameters that we can keep while pruning without increasing the model's training loss by more than a given relative tolerance $\beta$. In Section \ref{section_experimental_results}, we show empirically that using the \textit{fraction} of remaining parameters as a measure of a model's complexity does indeed overcome the problems of using the absolute \textit{number} of parameters before or after pruning.
\vspace{-4pt}
\begin{definition}[Prunability] Let $L$ denote the cross-entropy loss. For a given model $f_{\bm{w}}$, a training data set ${\mathbb{S}}_{train}$, a relative bound on the change in train loss $\beta$ and a pruning method $\phi$, we thus define prunability as
\vspace{-4pt}
\begin{gather*}
\mu_{\textrm{prunability}}(f_{\bm{w}})  =  \argmin_\alpha  \phi(f_{\bm{w}}, \alpha) \\
\textrm{s.t.} L(\phi(f_{\bm{w}}, \alpha), {\mathbb{S}}_{train}) \leq (1 + \beta) \times L(f_{\bm{w}}, {\mathbb{S}}_{train}) ~,
\end{gather*}

where $\phi(f_{\bm{w}}, \alpha)$ sets the fraction $1-\alpha$ of the weights of $f_{\bm{w}}$ to zero. 
\end{definition}
In our experiments we evaluate robustness to pruning both with regards to \textbf{magnitude pruning}, in which the parameters with the smallest absolute magnitude are set to 0, and \textbf{random pruning}, where random parameters are set to 0. Magnitude pruning can remove a greater number of model weights without affecting performance than random pruning \citep{blalock2020state}, and can therefore be considered a more effective pruning strategy. We hypothesize that using a more effective pruning method might yield a measure of prunability that is more predictive of generalization. Per default, we refer to a model's prunability with regards to magnitude pruning in the following. Note that while \textit{iterative} pruning is usually used when the aim is to achieve the best compression rate, we are only concerned with the generalization of the model at the end of training and thus apply one-shot pruning. In our experiments we use a tolerance $\beta$ of 0.1 and note that the particular choice of $\beta$ did not seem to have a large impact on the predictiveness of prunability. See Appendix \ref{section_prunability_algorithm} for pseudo-code of how prunability is computed for a given model.

While the above derivation serves as  motivation for our empirical study, further theoretical work will be necessary to fully explain the relation between a model's prunability and generalization. We see our empirical study as the central contribution of this paper and an important stepping stone towards a more comprehensive theoretical understanding of prunability.


\vspace{-6pt}
\section{Experimental Results and Analysis}
\label{section_experimental_results}
\vspace{-3pt}

The two main goals of our experiments are to show that prunability is an effective generalization measure and that it measures something distinct from existing baselines. Our experiments aim to demonstrate this in four steps: 1) We verify that prunability predicts generalization across a set of models trained with different hyperparameters and generalization performance. To this end, we use a similar experimental framework as \citet{jiang2019fantastic}. 2) We evaluate how prunability performs in a particularly challenging double descent setting. 3) To understand what notion of simplicity prunability quantifies and whether prunability captures a different aspect of generalization than existing baselines, we study the conditional mutual information between it and baselines that represent existing classes of different strong generalization measures. 4) Given that prunability and random perturbation robustness both measure the sensitivity of a model's training loss to a perturbation of its weights, we directly compare how pruning and random weight perturbations impact models' losses.
\vspace{-6pt}
\subsection{Baselines}
\vspace{-3pt}

That norm and parameter-count based generalization measures grow with model size is well established \citet{jiang2019fantastic} and the same applies for measures based on compressed models \cite{zhou2018non}. Instead, we compare our generalization measure to a number of strong baseline measures. Having somewhat tighter computational constraints than \citet{jiang2019fantastic}, we select one strong baseline per class of generalization measures as described by \citet{jiang2019fantastic} and \citet{jiang2018predicting}. 

From the class of generalization measures that aim to capture a model's simplicity using parameter-norms, we use the \textbf{Sum of Squared Frobenius Norms} \citep{jiang2019fantastic}: %
\vspace{-4pt}
$$\mu_{\textrm{fro}}(f_{\bm{w}}) = d\cdot(\prod_{i=1}^d||{\tens{W}}_i||_F^2)^{1/d},$$ where $d$ is the number of layers of the model.
 %

From the class of measures based on the idea that the speed of optimization is predictive of generalization, we use the negative \textbf{Sum of Train Losses} \citep{ru2020revisiting} throughout training:
\vspace{-4pt}
$$\mu_{\textrm{SoTL}}(f_{\bm{w}}) = - \sum_{t=1}^T \hat{L}(f_{w^t}),$$
where $T$ is the number of training epochs, $w^t$ the parameters at epoch $t$ and $\hat{L}$ the training cross-entropy loss.

 From the class of measures, based on the idea that models with flatter local minima generalize better, we use \textbf{magnitude aware random perturbation robustness} \citep{jiang2019fantastic}:
 %
 \vspace{-4pt}
 $$\mu_{\textrm{pac\_bayes\_mag\_flat}}(f_{\bm{w}}) = \frac{1}{\sigma^2},$$
 %
 where $u_i \sim \mathcal{N}(0, \sigma^2|w_i|+ \epsilon)$ and $\sigma^2$ is the largest number such that $\mathbb{E}_u[\hat{L}(f_{{\bm{w}} + {\bm{u}}})] \leq (1 + \beta) \times \hat{L}(f_{{\bm{w}}}) $, where $\beta$ is a relative tolerance, in our experiments 0.1.
 
 Lastly, we evaluate a measure that was not tested by \citet{jiang2019fantastic} and which is much more complex generalization measure than the previously describe measures. This measure is part of the class of measures based on the idea that models with wider margins between the training samples and decision boundaries generalize better, we use the \textbf{Normalized Margins} measure \citep{jiang2018predicting}: 
 %
 $$\mu_{\textrm{norm\_margins}}(f_{\bm{w}}) = {\bm{a}}^T{\bm{\phi}},$$
 %
wherein ${\bm{\phi}}$ consists of five statistics of the normalized margins distribution for each layer of the model. 
That is, at each hidden layer of the network, the normalized distances of all samples to the decision boundary of the second most likely class are computed. Five statistics of each of these distance distributions are used as input for the linear regression. Note that this generalization measure is much more expensive to compute than the other measures under evaluation: it involves computing the margin for all training samples for multiple trained neural networks. Another limitation of this measure is that it is data set specific.
In Appendix \ref{appendix_generalization_measures} we provide further details on these generalization measures and additional baselines.
\vspace{-6pt}
\subsection{Models}
\vspace{-3pt}
To generate a large set of trained models, we build upon the DEMOGEN set of trained models introduced by \cite{jiang2018predicting}. Our data set consists of 324 models that resemble the Network-in-Network architecture by \citep{lin2013network} trained on CIFAR10. \cite{jiang2018predicting} propose this particular architecture because it is parameter-efficient and achieves relatively competitive performance on standard image classification benchmarks. We achieve a wide range of generalization gaps by varying a number of hyperparameters such as the width, depth or $L_2$-regularization of the models. We modify the original set of models, DEMOGEN, used by \cite{jiang2018predicting} to obtain an even stronger experimental set up: noticing that the \textit{depth} of neural networks has a large impact on generalization performance, we add models of different depths to the original DEMOGEN data set. Following \citet{jiang2019fantastic} we only use models that apply batch normalization. See Appendix \ref{section_demogen_details} for further details of our experimental set-up.

\vspace{-6pt}
\subsection{Evaluation Metrics}
\vspace{-3pt}
To study our generalization measures comprehensively, we consider 1) their Kendall's Rank correlation with the generalization gap, 2) how predictive they are in terms of the adjusted $R^2$ and 3) apply the conditional independence test of \citet{jiang2019fantastic}, in an attempt to understand the causal relations between the complexity measures and generalization. We briefly summarize the metrics in this section and provide a more detailed explanation in Appendix \ref{section_evaluation_metrics}

We compute \textbf{Kendall's rank correlation coefficient} which quantifies to what extent the ranking of models according to a given generalization measure corresponds to the ranking according to the generalization gaps. For a given generalization measure $\mu$, we consider: $\mathcal{T} \coloneqq \cup_{{\bm{\theta}} \in \Theta}\{(\mu({\bm{\theta}}), g({\bm{\theta}}))\}$ where $g({\bm{\theta}})$ is the generalization gap of the model trained with hyperparameters ${\bm{\theta}}$. Kendall's rank correlation coefficient is then defined as the fraction of pairs of tuples that are correctly ranked according to the generalization measure:
$\tau(\mathcal{T}) \coloneqq \frac{1}{|\mathcal{T}|(|\mathcal{T}| - 1)} \sum_{(\mu_1, g_1) \in \mathcal{T} } \sum_{(\mu_2, g_2) \in \mathcal{T} \backslash (\mu_1, g_1)} \text{sign}(\mu_1 - \mu_2)\text{sign}(g_1 - g_2)$.
While Kendall's rank correlation coefficient is generally a useful metric, it does not adequately reflect whether a generalization measure's performance is consistent across all hyperparameter axes. Thus, we also consider the \textbf{granulated Kendall's rank correlation coefficient} which is essentially the average of Kendall’s rank coefficients $\psi_i$ obtained by only varying one hyperparameter dimension at a time: $\Psi \coloneqq \frac{1}{n} \sum_{i=1}^n \psi_i$

To go beyond correlation, \citet{jiang2019fantastic} use a conditional independence test inspired by \citet{verma1991equivalence}. The main goal here is to understand whether there exists an edge in a causal graph between a given generalization measure $\mu$ and the generalization gap $g$: this tells us whether models generalize well \textit{because} of the value of the generalization measure, or whether the two values are only correlated. This is achieved by estimating the \textbf{conditional mutual information} between the generalization measure and the generalization gap conditioned on different hyperparameters that are observed. Formally, we have that for any function $\phi: \Theta \rightarrow \mathcal{R}$, let $V_\phi: \Theta_1 \times \Theta_2 \rightarrow \{+1, -1\}$ be as $V_\phi(\theta_1, \theta_2)  \coloneqq sign(\phi(\theta_1) - \phi(\theta_2))$. Let $U_\mathcal{S}$ be a random variable that corresponds to the values of the hyperparameters in $\mathcal{S}$. Intuitively, the higher this metric is, the more likely it is that there is indeed an edge in the causal graph between the generalization gap and the generalization measure:  $\mathcal{K}(\mu) = \min_{U_\mathcal{S} s.t. |\mathcal{S}|\leq 2} \hat{\mathcal{I}}(V_\mu, V_g | U_\mathcal{S}),$ where $\hat{\mathcal{I}}(V_\mu, V_g | U_\mathcal{S})$ is the normalized conditional mutual information between the generalization measure and the generalization gap conditioned on observing the hyperparameter set $\mathcal{S}$.

\looseness -1 To evaluate how well we can predict a model's generalization using a linear function of a given generalization measure and following \cite{jiang2018predicting}, we additionally evaluate the generalization measures' predictiveness in terms of their adjusted $R^2$, i.e. the proportion of the variance of the generalization gap $g({\bm{\theta}})$ across hyperparameters ${\bm{\theta}} \in \Theta$ that can be explained by the generalization measure $\mu({\bm{\theta}})$.

\vspace{-6pt}
\subsection{Results}
\vspace{-3pt}
\subsubsection{Performance of Prunability on extended DEMOGEN data set}
\vspace{-3pt}
\label{section_performance_of_prunability}
Table \ref{table_generalization_measures_summary} holds a summary of our experimental results on the extended DEMOGEN data set. We find that prunability is highly informative of generalization across all of our evaluation metrics and that our measure is competitive with some of the strongest existing generalization measures from \citet{jiang2019fantastic}'s study of more than 40 generalization measures. In particular, it outperforms random perturbation robustness, the training loss itself and the Frobenius norm measures in terms of Kendall's rank correlation coefficient. The negative sum of training losses slightly outperforms prunability.
\begin{table}[tp]
\centering
\caption{\textbf{Prunability is competitive with strong baseline generalization measures.} Comparison of generalization measures' correlation with test performance on a set of convolutional networks trained on CIFAR-10. Higher values are better across all metrics. The standard error of the Kendall's $\tau$ is $s_{\tau} = 0.037$. \vspace{4pt}}
\label{table_generalization_measures_summary}
\resizebox{\columnwidth}{!}{%
\begin{tabular}{l l l l}
\toprule
\textbf{Generalization Measure} & \textbf{Kendall's $\bm{\tau}$} & \textbf{Adjusted R2} & \textbf{CMI} \\ \hline 
Low-complexity Measures & & & \\ \addlinespace
Prunability (ours)            & 0.6496 & 0.5440           & 0.0324                                 \\ 
Random Prunability (ours)                 & 0.584                & 0.3015               & 0.0377                                   \\ 
Random Perturbation Robustness  & 0.4253                 & 0.2440                & 0.0230                                  \\ 
Frobenius-norm                  & -0.6055                & \textbf{0.7778}               & \textbf{0.0612}                                 \\ 
Negative Sum of Train Losses          &\textbf{ 0.7085}                 & 0.4923    &     0.0186         \\

Train loss                      & 0.0201                &  0.0746             & 0.0004      \\
\hline
High-complexity Measures & & & \\
\addlinespace
Normalized Margins              & \textbf{0.8061}                 & \textbf{0.8866}   & \textbf{0.1761}             \\ 

Best Margin Variable            & 0.6344                & 0.6623    &   0.0743           \\ 
\bottomrule                         
\end{tabular}%
 }%
\vspace{-16pt}
\end{table}

In addition to the generalization measures studied by \citet{jiang2019fantastic}, we also compare prunability to the much more complex and computationally expensive Normalized Margins baseline. It is also the only of the measures we study which is based on the data space rather than the parameter space.  This baseline clearly outperforms prunability while the Best Margin Variable seem similarly informative of generalization as prunability. Note that the margin-based measures achieve much higher conditional mutual information scores than the other baselines, providing further evidence for the causal connection between wide margins and good generalization performance. The conditional mutual information between \textit{prunability} and generalization is relatively low, suggesting that it seems somewhat less likely that there is a direct causal connection between a model's prunability and its generalization performance. 

We find that while prunability based on magnitude pruning outperforms prunability based on random pruning, the difference in performance is relatively small.

In Table \ref{table_generalization_measures_detailed_kendall}, we compare the granulated and regular Kendall's coefficients of some additional baselines. The results reconfirm the weak performance of norm and parameter count-based complexity measures both for pruned and unpruned networks. While this a well known issue, we point out that this is also problematic for recently proposed generalization measures based on the size of the compressed network such as \citet{zhou2018non}. We also note that the Frobenius norm measure is strongly negatively correlated with generalization rather than positively correlated as one would expect based on \cite{jiang2019fantastic}. It seems that this result is largely due to a strong negative correlation for models with different dropout rates and relatively weak correlation coefficients along other hyperparameter axes.

\begin{table*}[h]
    \centering
     \caption{\textbf{Prunability achieves a stronger granulated rank correlation than measures based on random perturbation robustness or norms.} Columns labeled with hyperparameters (width, dropout rate, etc.) indicate Kendall $\tau$ if we only vary this hyperparameter. The last two columns are the Overall Kendall's $\tau$ and the Granulated Kendall's coefficient $\psi$, which is the average of the per-hyperparameter columns. Higher values are better across all columns \vspace{4pt}}
    \label{table_generalization_measures_detailed_kendall}
    \resizebox{\textwidth}{!}{%
    \begin{tabular}{l l l l  l l l l}%
\toprule    
\textbf{Generalization Measure}&\textbf{Width}&\textbf{Dropout Rate}&\textbf{Data Augment.}&\textbf{Weight Decay}&\textbf{Depth}&\textbf{Kendall $\tau$}&\textbf{$\mathbf{{\bm{\psi}}}$}\\%
\hline \addlinespace%
prunability (ours)&\textbf{0.1582}&0.6986&0.0122&{-}0.001&0.2254&0.6496&0.2187\\%
 %
random\_prunability (ours)&0.0714&0.6261&0.0464&0.0422&0.259&0.584&0.209\\%
random\_perturbation&0.1161&0.5154&0.0962&0.0755&0.1829&0.4253&0.1972\\%
frobenius\_norm&{-}0.0778&{-}0.7955&{-}0.067&{-}0.0591&0.4577&{-}0.6055&{-}0.1083\\%
normalized\_margins&0.0671&\textbf{0.8325}&\textbf{0.1121}&0.0799&\textbf{0.5789}&\textbf{0.8061}&0\textbf{.3341}\\%
best\_margins\_variable&0.054&0.7756&0.0415&{-}0.039&0.4798&0.6344&0.2624\\%
sum\_of\_train\_losses&-0.0639&0.8078&0.0498&0.0345&0.4156&0.7085&0.2487\\%
train\_loss&0.0143&{-}0.0652&{-}0.0762&{-}0.0349&0.1142&0.0201&{-}0.0096\\%
sum\_two\_norms&{-}0.0513&{-}0.5728&0.0214&0.0746&{-}0.1359&{-}0.2096&{-}0.1328\\%
parameter\_count&{-}0.0866&0.0&0.0&0.0&{-}0.4218&{-}0.0911&{-}0.1017\\%
sum\_two\_norms\_pruned&{-}0.0749&{-}0.6828&0.0857&\textbf{0.0866}&{-}0.2654&{-}0.2234&{-}0.1701\\%
pruned\_parameter\_count&{-}0.0893&0.6986&0.0122&{-}0.001&{-}0.3798&0.0417&0.0481\\%
\bottomrule
\end{tabular}%
}%
   
\end{table*}
\vspace{-6pt}
\subsubsection{Double Descent}
\label{section_double_descent}
\vspace{-6pt}
\label{section_double_descent_results}
\begin{figure}[]
    \centering
   
    \subfloat[]{\label{sublable1}\includegraphics[width=0.9\columnwidth]{images/double_descent_3101.pdf}} \\
    \centering
    \subfloat[]{
\resizebox{0.8\linewidth}{!}{\begin{tabular}{l l l}
\toprule 
\textbf{Kendall's} $\tau$                         & \textbf{Test Loss} & \textbf{Test Error} \\ \hline \addlinespace
Prunability              & \textbf{0.3613 } & 0.1277       \\ 
Eff. Dim. &   -0.0197 & -0.0753       \\
Random Perturbation &   0.1398  & -0.2166       \\ 
Frobenius Norm &   0.0996 & -0.5367       \\ 
Margins &   0.1296 & \textbf{0.4258}       \\ 
-Sum of Train Losses &   -0.2890 & -0.9381       \\ 
\bottomrule
\end{tabular}}}
\caption{\textbf{Prunability is correlated with test loss in double descent setting:} Across a set of convolutional networks of varying width trained on CIFAR-100, we show that prunability captures double descent behavior better than a previously proposed metric \textit{Effective Dimensionality} – which is based on the eigenspectrum of the Hessian of the training loss of the model – and other strong baselines.} \label{tab:plot_double_descent}
\label{figure_double_descent}
\end{figure}%
In addition to our experiments on the DEMOGEN data set, we also evaluate prunability on a set of models that exhibit a test loss double descent \citep{nakkiran2019deep}. This phenomenon is particularly interesting for the study of generalization measures, since many measures that aim to capture a model's complexity grow monotonically as we increase a network's width and thus do not display any form of double descent. In the previous section we saw that \textit{prunability} seems highly predictive of generalization for models of different widths. The double descent setting allows us to test whether there is more to prunability's success than its correlation with model size. We use the experimental setup proposed by \citet{maddox2020rethinking}, and compare our new measure to their curvature-based generalization measure which also aims to capture double descent. Note that up to now we studied the generalization gap in terms of the $0-1$ loss. In this section, however, we focus on another aspect of generalization and study the relation between prunability and models' cross-entropy test loss.


\citet{maddox2020rethinking} introduce a generalization measure called Effective Dimensionality which is defined as:
$N_{\text{eff}}({\tens{H}}, z) = \sum_{i=1}^k \frac{\lambda_i}{\lambda_i + z}$ where $\lambda_i$ are the eigenvalues of the Hessian of the training loss ${\tens{H}} \in \mathcal{R}^{k \times k}$, and $z > 0$ is a regularization constant. Intuitively, the Effective Dimensionality measures the flatness of the local minimum of a network in terms of the number of eigenvalues of the Hessian of the training loss that are "large". To get a measure on the same scale as our new generalization measure, we use a normalized version of $N_{eff}$: $\mu_{\textrm{effective\_dimensionality}} = \frac{N_\text{eff}}{k}$. Additionally, we also evaluate a number of the strongest baselines from Section \ref{section_performance_of_prunability} in the double descent setting.
We refer to Appendix \ref{section_double_descent_appendix} for further details on the experimental setup.


We find that prunability does indeed display a double descent and is more strongly rank correlated with the test loss than the baseline measures (Kendall's $\tau$ of 0.3613, $p < 0.0005$). See Figure \ref{figure_double_descent} for an overview of the results.

In Appendix \ref{section_double_descent_bonus_experiment} we study an additional double descent setting and obtain results that are consistent with the results presented in this section.



\vspace{-6pt}
\subsubsection{Pruning and Flatness-based Measures}
\vspace{-6pt}
\label{section_comparison_of_generalization_measures}
We now investigate whether a neural network's robustness to pruning can be explained by other established generalization measures, or whether it is measuring something entirely distinct from previous notions of model simplicity. To better understand the relation between prunability and the other generalization measures we perform the conditional independence test described in section \ref{section_conditional_independence} between them. Recall that, up to now, we used this test to study the relation between the generalization measure and the generalization gap and that the higher the $\kappa$ between two variables, the likelier it is that they neighbors in the causal DAG. See Table \ref{table_cmi_between_generalization_measures} for a summary of the results. 

First, we observe that the conditional mutual information between prunability and random perturbation robustness is the highest across the baselines we are evaluating. Because pruning is a special case of perturbation, some connection between the two methods is expected. However, prunability is clearly measuring something subtly different from flatness of the loss surface, as it outperforms random perturbation robustness in our evaluations. Thus, we investigate whether this distinction may arise from the differential effects of pruning and random perturbations in function space. 

 To evaluate this, we directly compare the impact of both pruning and random perturbations on some of the models in our double descent experimental setting by performing pruning and random perturbations of the same magnitude and computing their respective impact on the loss. We find that pruning has a larger negative impact on a model's training loss than a random perturbation of the same magnitude (see Figure \ref{figure_pruning_versus_random_perturbations}). In contrast, pruning can lead to an improvement of the test loss which we do not observe for random perturbations; we conjecture that this relationship may be responsible for the difference between the two methods, though disentangling this phenomenon is left for future work. We also note that prunability achieves much higher Kendall's $\tau$, Adjusted $R^2$ and Conditional Mutual Information than random perturbation robustness.

In conclusion, pruning affects models differently from randomly perturbing their weights. Because pruning can in certain settings improve test performance (and hence seems to be more aligned with network simplicity) we suggest that this difference leads to the stronger performance of prunability as compared to random perturbation robustness.
We compare the impact of pruning and random perturbations on a model's training and test loss for an additional architecture in Appendix \ref{section_pruning_versus_random_perturbations_bonus_experiment}, and find that the results are consistent with the results presented in this section.
\begin{table}[h]
\centering
\resizebox{\columnwidth}{!}{%
\begin{tabular}{l l l l l l l}
\toprule
\textbf{}          & Margins     & Rand. Perturb. & Param. Count & Train Loss & F-Norm & SoTL \\ \hline \addlinespace

Prunability       & 0.0122             & \textbf{0.04541 }              & 0.0038          & 0.0004     & 0.0105  & 0.0013     \\
\bottomrule
\end{tabular}
}
\caption{\textbf{Prunability is similar to Random Perturbation Robustness.} The conditional mutual information (CMI) between prunability and random perturbation robustness.}
\label{table_cmi_between_generalization_measures}
\end{table}

\begin{figure}[h]
\begin{center}
\resizebox{1\columnwidth}{!}{\includegraphics{images/pruning_versus_random_perturbations.pdf}}
\end{center}\vspace{-16pt}
\caption{\textbf{Pruning affects models very differently than random perturbations.} Here we compare pruning of weights and randomly perturbing the same weights by the same amount. We study a ResNet18 trained on CIFAR100. Generally speaking, pruning will have a larger negative impact on a model's loss than randomly perturbing the same weights by the same amount but in some cases pruning actually improves the test loss of models.}
\label{figure_pruning_versus_random_perturbations}
\end{figure} 

\vspace{-6pt}
\section{Conclusion}
\label{section_conclusion}
\vspace{-3pt}
In this paper, we have shown that a network's prunability, the smallest fraction of parameters we can keep while pruning without hurting the model's training loss, is highly informative of the network's generalization performance. Unlike many existing measures of model complexity, prunability correctly predicts that larger models generalize better than smaller models in contrast to many previous measures of model simplicity based on parameter counting and norms. Prunability further seems to capture something distinct from previously suggested measures based on robustness to random perturbations or the curvature of the loss landscape. 

\looseness -1 Empirical studies of surprising phenomena of generalization in deep neural networks have previously served as a valuable stepping stone towards more comprehensive theories of generalization \citep{nakkiran2019deep, frankle2018lottery}. Similarly, we believe that our empirical observations lay the foundation for further theoretical work to analyze the relationship between pruning and generalization. One direction is to build upon the PAC-Bayesian approach outlined in Section \ref{section_prunability}, e.g. similar to \citet{dziugaite2017computing}. 

\looseness -1 An additional direction of future work is to build on the mutual information experiments of Section~\ref{section_comparison_of_generalization_measures} to study the relationship between pruning and other generalization measures: for example, how the direction of pruning relates to the span of the main eigenvectors of the Hessian studied by \citet{maddox2020rethinking}. Given the conceptual similarity, it may also prove fruitful to study the relation between pruning \textit{after} training and pruning \textit{during} training, that is dropout, more closely.



\nocite{langley00}

