Sparsity-aware generalization theory for deep neural networks
Deep artificial neural networks achieve surprising generalization abilities
that remain poorly understood. In this paper, we present a new approach to
analyzing generalization for deep feed-forward ReLU networks that takes
advantage of the degree of sparsity that is achieved in the hidden layer
activations. By developing a framework that accounts for this reduced effective
model size for each input sample, we are able to show fundamental trade-offs
between sparsity and generalization. Importantly, our results make no strong
assumptions about the degree of sparsity achieved by the model, and it improves
over recent norm-based approaches. We illustrate our results numerically,
demonstrating non-vacuous bounds when coupled with data-dependent priors in
specific settings, even in over-parametrized models.
Ramchandran Muthukumar, Jeremias Sulam
# Sparsity-aware generalization theory for deep neural networks

###### Abstract

Deep artificial neural networks achieve surprising generalization abilities that remain poorly understood. In this paper, we present a new approach to analyzing generalization for deep feed-forward ReLU networks that takes advantage of the degree of sparsity that is achieved in the hidden layer activations. By developing a framework that accounts for this reduced effective model size for each input sample, we are able to show fundamental trade-offs between sparsity and generalization. Importantly, our results make no strong assumptions about the degree of sparsity achieved by the model, and it improves over recent norm-based approaches. We illustrate our results numerically, demonstrating non-vacuous bounds when coupled with data-dependent priors in specific settings, even in over-parametrized models.

## 1 Introduction

Statistical learning theory seeks to characterize the generalization ability of machine learning models, obtained from finite training data, to unseen test data. The field is by now relatively mature, and several tools exist to provide upper bounds on the generalization error, \(R(h)\). Often the upper bounds depend on the empirical risk, \(\hat{R}(h)\), and different characterizations of complexity of the hypothesis class as well as potentially specific data-dependent properties. The renewed interest in deep artificial neural network models has demonstrated important limitations of existing tools. For example, VC dimension often simply relates to the number of model parameters and is hence insufficient to explain generalization of overparameterized models (Bartlett et al., 2019). Traditional measures based on Rademacher complexity are also often vacuous, as these networks can indeed be trained to fit random noise (Zhang et al., 2017). Margin bounds have been adapted to deep non-linear networks (Bartlett et al., 2017; Golowich et al., 2018; Neyshabur et al., 2015, 2018), albeit still unable to provide practically informative results.

An increasing number of studies advocate for non-uniform data-dependent measures to explain generalization in deep learning (Nagarajan and Kolter, 2019; Perez and Louis, 2020; Wei and Ma, 2019). Of particular interest are those that employ the sensitivity of a data-dependent predictor to parameter perturbations - sometimes also referred to as _flatness_(Shawe-Taylor and Williamson, 1997; Neyshabur et al., 2017; Dziugaite and Roy, 2017; Arora et al., 2018; Li et al., 2018; Nagarajan and Kolter, 2019; Wei and Ma, 2019; Sulam et al., 2020; Banerjee et al., 2020). This observation has received some empirical validation as well (Zhang et al., 2017; Keskar et al., 2017; Izmailov et al., 2018; Neyshabur et al., 2019; Jiang* et al., 2020; Foret et al., 2021). Among the theoretical results of this line of work, Arora et al. (2018) study the generalization properties of a _compressed_ network, and Dziugaite and Roy (2017); Neyshabur et al. (2017) study a stochastic perturbed version of the original network. The work in (Wei and Ma, 2019) provides improved bounds on the generalization error of neural networks as measured by a low Jacobian norm with respect to training data, while Wei and Ma (2020) capture the sensitivity of a neural network to perturbations in intermediate layers. PAC-Bayesian analysis provides an alternate way of studying generalization by incorporating prior knowledge on a distribution of well-performing predictors in a Bayesian setting (McAllester,
1998; Guedj, 2019; Alquier, 2021). Recent results (Dziugaite and Roy, 2017, 2018; Zhou et al., 2019) have further strengthened the standard PAC-Bayesian analysis by optimizing over the posterior distribution to generate non-vacuous bounds on the expected generalization error of stochastic neural networks. Derandomized versions of PAC-Bayes bounds have also been recently developed (Nagarajan and Kolter, 2019; Banerjee et al., 2020) relying on the sensitivity or _noise resilience_ of an obtained predictor. All of these works are insightful, alas important gaps remain in understanding generalization in non-linear, over-parameterized networks (Perez and Louis, 2020).

**Our contributions.** In this work we employ tools of sensitivity analysis and PAC-Bayes bounds to provide generalization guarantees on deep ReLU feed-forward networks. Our key contribution is to make explicit use of the sparsity achieved by these networks across their different layers, reflecting the fact that only sub-networks, of reduced sizes and complexities, are active at every sample. Similar in spirit to the observations in Muthukumar and Sulam (2022), we provide conditions under which the set of active neurons (smaller than the number of total neurons) is stable over suitable distributions of networks, with high-probability. In turn, these results allow us to instantiate recent de-randomized PAC-Bayes bounds (Nagarajan and Kolter, 2019) and obtain new guarantees that do not depend on the global Lipschitz constant, nor are they exponential in depth. Importantly, our results provide data-dependent non-uniform guarantees that are able to leverage the structure (sparsity) obtained on a specific predictor. As we show experimentally, this degree of sparsity - the reduced number of active neurons - need not scale linearly with the width of the model or the number of parameters, thus obtaining bounds that are significantly tighter than known results. We also illustrate our generalization results on MNIST for models of different width and depth, providing non-vacuous bounds in certain settings.

**Manuscript organization.** After introducing basic notation, definitions and problem settings, we provide a detailed characterization of stable inactive sets in single-layer feed-forward maps in Section 2. Section 3 presents our main results by generalizing our analysis to multiple layers, introducing appropriate distributions over the hypothesis class and tools from de-randomized PAC-Bayes theory. We demonstrate our bounds numerically in Section 4, and conclude in Section 5.

### Notation And Definitions

Sets and spaces are denoted by capital (and often calligraphic) letters, with the exception of the set \([K]=\{1,\ldots,K\}\). For a Banach space \(\mathcal{W}\) embedded with norm \(\left\|\cdot\right\|_{\mathcal{W}}\), we denote by \(\mathcal{B}_{r}^{\mathcal{W}}(\mathbf{W})\), a bounded ball centered around \(\mathbf{W}\) with radius \(r\). Throughout this work, scalar quantities are denoted by lower or upper case (not bold) letters, and vectors with bold lower case letters. Matrices are denoted by bold upper case letters: \(\mathbf{W}\) is a matrix with _rows_\(\mathbf{w}[i]\). We denote by \(\mathcal{P}_{I}\), the index selection operator that restricts input to the coordinates specified in the set \(I\). For a vector \(\mathbf{x}\in\mathbb{R}^{d}\) and \(I\subset[d]\), \(\mathcal{P}_{I}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{|I|}\) is defined as \(\mathcal{P}_{I}(\mathbf{x}):=\mathbf{x}[I]\). For a matrix \(\mathbf{W}\in\mathbb{R}^{p\times d}\) and \(I\subset[p]\), \(\mathcal{P}_{I}(\mathbf{W})\in\mathbb{R}^{|I|\times d}\) restricts \(\mathbf{W}\) to the _rows_ specified by \(I\). For row and column index sets \(I\subset[p]\) and \(J\subset[d]\), \(\mathcal{P}_{I,J}(\mathbf{W})\in\mathbb{R}^{|I|\times|J|}\) restricts \(\mathbf{W}\) to the corresponding sub-matrix. Throughout this work, we refer to _sparsity_ as the _number of zeros_ of a vector, so that for \(\mathbf{x}\in\mathbb{R}^{d}\) with degree of sparsity \(s\), \(\left\|\mathbf{x}\right\|_{0}=d-s\). We denote the induced operator norm by \(\left\|\cdot\right\|_{2}\), and the Frobenius norm by \(\left\|\cdot\right\|_{F}\). In addition, we will often use operator norms of reduced matrices induced by sparsity patterns. To this end, the following definition will be used extensively.

**Definition 1**: _(Sparse Induced Norms) Let \(\mathbf{W}\in\mathbb{R}^{d_{2}\times d_{1}}\) and \((s_{2},s_{1})\) be sparsity levels such that \(0\leq s_{1}\leq d_{1}-1\) and \(0\leq s_{2}\leq d_{2}-1\). We define the \((s_{2},s_{1})\) sparse induced norm \(\left\|\cdot\right\|_{(s_{2},s_{1})}\) as_

\[\left\|\mathbf{W}\right\|_{(s_{2},s_{1})}:=\max_{|J_{2}|=d_{2}-s_{2}}\ \ \max_{|J_{1}|=d_{1}-s_{1}}\ \ \left\|\mathcal{P}_{J_{2},J_{1}}(\mathbf{W})\right\|_{2}.\]

The sparse induced norm \(\left\|\cdot\right\|_{(s_{2},s_{1})}\) measures the induced operator norm of a worst-case sub-matrix. For any two sparsity vectors \((s_{2},s_{1})\preceq(\hat{s}_{2},\hat{s}_{1})\), one can show that \(\left\|\mathbf{W}\right\|_{(\hat{s}_{2},\hat{s}_{1})}\leq\left\|\mathbf{W} \right\|_{(s_{2},s_{1})}\) for any matrix \(\mathbf{W}\) (see Lemma 4). In particular,

\[\max_{i,J}\left|\mathbf{W}[i,j]\right|=\left\|\mathbf{W}\right\|_{(d_{2}-1,d _{1}-1)}\leq\left\|\mathbf{W}\right\|_{(s_{2},s_{1})}\leq\left\|\mathbf{W} \right\|_{(0,0)}=\left\|\mathbf{W}\right\|_{2}.\]
Thus, the sparse norm interpolates between the maximum absolute entry norm and the operator norm. Frequently in our exposition we rely on the case when \(s_{2}=d_{2}-1\), thus obtaining \(\left\|\mathbf{W}\right\|_{(d_{2}-1,s_{1})}=\max_{i\in[d_{2}]}\max_{|J_{1}|=d_{1} -s_{1}}\left\|\mathcal{P}_{J_{1}}(\mathbf{w}[i])\right\|_{2}\), the maximum norm of any reduced row of matrix \(\mathbf{W}\).

Outside of the special cases listed above, computing the sparse norm for a general \((s_{2},s_{1})\) has combinatorial complexity. Instead, a modified version of the babel function (see Tropp et al. (2003)) provides computationally efficient upper bounds1.

Footnote 1: The particular definition used in this paper is weaker but more computationally efficient than that introduced in Muthukumar and Sulam (2022).

**Definition 2**: _(Reduced Babel Function (Muthukumar and Sulam, 2022)) Let \(\mathbf{W}\in\mathbb{R}^{d_{2}\times d_{1}}\), the reduced babel function at row sparsity level \(s_{2}\in\{0,\ldots,d_{2}-1\}\) and column sparsity level \(s_{1}\in\{0,\ldots,d_{1}-1\}\) is defined as2,_

Footnote 2: When \(s_{2}=d_{2}-1,|J_{2}|=1\), we simply define \(\mu_{(s_{2},s_{1})}(\mathbf{W}):=0\).

\[\mu_{s_{2},s_{1}}(\mathbf{W}):=\frac{1}{\left\|\mathbf{W}\right\|_{(d_{2}-1,s_ {1})}^{2}}\max_{\begin{subarray}{c}J_{2}\subset[d_{2}],\\ |J_{2}|=d_{2}-s_{2}\end{subarray}}\max_{j\in J_{2}}\left[\sum_{\begin{subarray} {c}i\in J_{2},\\ i\neq j\end{subarray}}\max_{\begin{subarray}{c}J_{1}\subseteq[d_{1}]\\ i\neq j\end{subarray}}\left|\mathcal{P}_{J_{1}}(\mathbf{w}[i])\mathcal{P}_{J_{ 1}}(\mathbf{w}[j])^{T}\right|\right].\]

For the special case when \(s_{2}\) = 0, the reduced babel function is equivalent to the babel function from Tropp et al. (2003) on the transposed matrix \(\mathbf{W}^{T}\). We show in Lemma 5 that the sparse-norm can be bounded using the reduced babel function and the maximum reduced row norm \(\left\|\cdot\right\|_{(d_{2}-1,s_{1})}\),

\[\left\|\mathbf{W}\right\|_{s_{2},s_{1}}\leq\left\|\mathbf{W}\right\|_{d_{2}-1,s_{1}}\sqrt{1+\mu_{s_{2},s_{1}}(\mathbf{W})}. \tag{1}\]

See Appendix D for a computationally efficient implementation of the reduced babel function.

### Learning Theoretic Framework

We consider the task of multi-class classification with a bounded input space \(\mathcal{X}=\{\mathbf{x}\in\mathbb{R}^{d_{0}}\mid\left\|\mathbf{x}\right\|_{2 }\leq\mathbf{M}_{\mathcal{X}}\}\) and labels \(\mathcal{Y}=\{1,\ldots,C\}\) from an unknown distribution \(\mathcal{D}_{\mathcal{Z}}\) over \(\mathcal{Z}:=(\mathcal{X}\times\mathcal{Y})\). We search for a hypothesis in \(\mathcal{H}\subset\{h:\mathcal{X}\rightarrow\mathcal{Y}^{{}^{\prime}}\}\) that is an accurate predictor of label \(y\) given input \(\mathbf{x}\). Note that \(\mathcal{Y}\) and \(\mathcal{Y}^{{}^{\prime}}\) need not be the same. In this work, we consider \(\mathcal{Y}^{{}^{\prime}}=\mathbb{R}^{C}\), and consider the predicted label of the hypothesis \(h\) as \(\hat{y}(\mathbf{x}):=\operatorname*{argmax}_{j}[h(\mathbf{x})]_{j}\)3. The quality of prediction of \(h\) at \(\mathbf{z}=(\mathbf{x},y)\) is informed by the margin defined as \(\rho(h,\mathbf{z}):=\big{(}[h(\mathbf{x})]_{y}-\operatorname*{argmax}_{j\neq }[h(\mathbf{x})]_{j}\big{)}\). If the margin is positive, then the predicted label is correct. For a threshold hyper-parameter \(\gamma\geq 0\), we define a \(\gamma\)-threshold 0/1 loss \(\ell_{\gamma}\) based on the margin as \(\ell_{\gamma}(h,\mathbf{z}):=1\left\{\rho(h,\mathbf{z})<\gamma\right\}\). Note that \(\ell_{\gamma}\) is a stricter version of the traditional zero-one loss \(\ell_{0}\), since \(\ell_{0}(h,\mathbf{z})\leq\ell_{\gamma}(h,\mathbf{z})\) for all \(\gamma\geq 0\). With these elements, the _population risk_ (also referred to as _generalization error_) of a hypothesis \(R_{\gamma}\) is the expected loss it incurs on a randomly sampled data point, \(R_{\gamma}(h):=\mathbb{E}_{\mathbf{z}\sim\mathcal{D}_{\mathcal{Z}}}\left[\ell_{ \gamma}\big{(}h,\mathbf{z}\big{)}\right]\). The goal of supervised learning is to obtain a hypothesis with low population risk \(R_{0}(h)\), the probability of misclassification. While the true distribution \(\mathcal{D}_{\mathcal{Z}}\) is unknown, we assume access to an i.i.d training set \(\mathbf{S}_{T}=\{\mathbf{z}^{(i)},\ldots,\mathbf{z}^{(m)}\}\sim(\mathcal{D}_{ \mathcal{Z}})^{m}\) and we seek to minimize the _empirical risk_\(\hat{R}_{\gamma}\), the average loss incurred on the training sample \(\mathbf{S}_{T}\), i.e. \(\hat{R}_{\gamma}(h):=\frac{1}{m}\sum_{i=1}^{m}\ell_{\gamma}\left(h,\mathbf{z}^{ (i)}\right)\). We shall later see that for any predictor, \(R_{0}(h)\) can be upper bounded using the stricter empirical risk \(\hat{R}_{\gamma}(h)\) for an appropriately chosen \(\gamma>0\).

Footnote 3: The argmax here is assumed to break ties deterministically.

In this work, we study the hypothesis class \(\mathcal{H}\) containing feed-forward neural networks with \(K\) hidden layers. Each hypothesis \(h\in\mathcal{H}\) is identified with its weights \(\{\mathbf{W}_{k}\}_{k=1}^{K+1}\), and is a sequence of \(K\) linear maps \(\mathbf{W}_{k}\in\mathbb{R}^{d_{k}\times d_{k-1}}\) composed with a nonlinear activation function \(\sigma(\cdot)\) and a final linear map \(\mathbf{W}_{K+1}\in\mathbb{R}^{C\times d_{K}}\),

\[h(\mathbf{x}_{0}):=\mathbf{W}_{K+1}\sigma\left(\mathbf{W}_{k}\sigma\left( \mathbf{W}_{K-1}\cdots\sigma\left(\mathbf{W}_{1}\mathbf{x}_{0}\right)\cdots \right)\right).\]

We exclude bias from our definitions of feed-forward layers for simplicity4. We denote by \(\mathbf{x}_{k}\) the \(k^{th}\) hidden layer representation of network \(h\) at input \(\mathbf{x}_{0}\), so that \(\mathbf{x}_{k}:=\sigma\left(\mathbf{W}_{k}\mathbf{x}_{k-1}\right)\ \forall 1\leq k\leq K\), and
\(h(\mathbf{x}):=\mathbf{W}_{K+1}\mathbf{x}_{K}\). Throughout this work, the activation function is assumed to be the Rectifying Linear Unit, or ReLU, defined by \(\sigma(x)=\max\{x,0\}\), acting entrywise on an input vector.

## 2 Warm Up: Sparsity In Feed-Forward Maps

As a precursor to our sensitivity analysis for multi-layer feed-forward networks, we first consider a generic feed-forward map \(\Phi(\mathbf{x}):=\sigma(\mathbf{W}\mathbf{x})\). A naive bound on the norm of the function output is \(\left\|\Phi(\mathbf{x})\right\|_{2}\leq\left\|\mathbf{W}\right\|_{2}\left\| \mathbf{x}\right\|_{2}\), but this ignores the sparsity of the output of the feed-forward map (due to the ReLU). Suppose there exists a set \(I\) of inactive indices such that \(\mathcal{P}_{I}(\Phi(\mathbf{x}))=\mathbf{0}\), i.e. for all \(i\in I\), \(\mathbf{w}[i]\cdot\mathbf{x}\leq 0\). In the presence of such an index set, clearly \(\left\|\Phi(\mathbf{x})\right\|_{2}\leq\left\|\mathcal{P}_{I^{c}}(\mathbf{W} )\right\|_{2}\left\|\mathbf{x}\right\|_{2}\)5. Thus, estimates of the effective size of the feed-forward output, and other notions such as sensitivity to parameter perturbations, can be refined by accounting for the sparsity of activation patterns. Note that the inactive index set \(I\) varies with each input, \(\mathbf{x}\), and with the parameters of predictor, \(\mathbf{W}\).

Footnote 5: \(I^{c}\) is the complement of the index set \(I\), also referred to as \(J\) when clear from context.

For some \(\zeta_{0},\xi_{1},\eta_{1}>0\) and sparsity levels \(s_{1},s_{0}\), let \(\mathcal{X}_{0}=\left\{\mathbf{x}\in\mathbb{R}^{d_{0}}\mid\|\mathbf{x}\|_{2} \leq\zeta_{0},\;\|\mathbf{x}\|_{0}\leq d_{0}-s_{0}\right\}\) denote a bounded sparse input domain and let \(\mathcal{W}_{1}:=\left\{\mathbf{W}\in\mathbb{R}^{d_{1}\times d_{0}}\mid\| \mathbf{W}\|_{(d_{1}-1,s_{0})}\leq\xi_{1},\;\mu_{s_{1},s_{0}}(\mathbf{W})\leq \eta_{1}\right\}\) denote a parameter space. We now define a radius function that measures the amount of relative perturbation within which a certain inactive index set is stable.

**Definition 3**: _(Sparse local radius6) For any weight \(\mathbf{W}\in\mathbb{R}^{d_{1}\times d_{0}}\), input \(\mathbf{x}\in\mathbb{R}^{d_{0}}\) and sparsity level \(1\leq s_{1}\leq d_{1}\), we define a sparse local radius and a sparse local index set as_

Footnote 6: The definition here is inspired by Muthukumar and Sulam (2022) but stronger.

\[r_{\text{sparse}}(\mathbf{W},\mathbf{x},s_{1}):=\sigma\left(\text{\sc sort} \left(-\frac{\mathbf{W}\cdot\mathbf{x}}{\xi_{1}\zeta_{0}},\;s_{1}\right) \right),\quad I(\mathbf{W},\mathbf{x},s_{1}):=\text{\sc Top-k}\left(-\frac{ \mathbf{W}\cdot\mathbf{x}}{\xi_{1}\zeta_{0}},s_{1}\right). \tag{2}\]

_Here, \(\text{\sc Top-k}(\mathbf{u},j)\) is the index set of the top \(j\) entries in \(\mathbf{u}\), and \(\text{\sc sort}(\mathbf{u},j)\) is its \(j^{th}\) largest entry._

We note that when evaluated on a weight \(\mathbf{W}\in\mathcal{W}_{1}\) and input \(\mathbf{x}\in\mathcal{X}_{0}\), for all sparsity levels the sparse local radius \(r_{\text{sparse}}(\mathbf{W},\mathbf{x},s_{1})\in[0,1]\). We denote the sparse local index set as \(I\) when clear from the context. We now analyze the stability of the sparse local index set and the resulting reduced sensitivity of model output. For brevity, we must defer all proofs to the appendix.

**Lemma 1**: _Let \(\epsilon_{0}\in[0,1]\) be a relative input corruption level and let \(\epsilon_{1}\in[0,1]\) be the relative weight corruption. For the feed-forward map \(\Phi\) with weight \(\mathbf{W}\in\mathcal{W}_{1}\) and input \(\mathbf{x}\in\mathcal{X}_{0}\), the following statements hold for any output sparsity level \(1\leq s_{1}\leq d_{1}\),_

1. _Existence of an inactive index set and bounded outputs:_ _If_ \(r_{\text{sparse}}(\mathbf{W},\mathbf{x},s_{1})>0\)_, then the index set_ \(I(\mathbf{W},\mathbf{x},s_{1})\) _is inactive for_ \(\Phi(\mathbf{x})\)_. Moreover,_ \(\left\|\Phi(\mathbf{x})\right\|_{2}\leq\xi_{1}\sqrt{1+\eta_{1}}\cdot\zeta_{0}\)_._
2. _Stability of an inactive index set to input and parameter perturbations:_ _Suppose_ \(\hat{\mathbf{x}}\) _and_ \(\hat{\mathbf{W}}\) _are perturbed inputs and weights respectively such that,_ \(\left\|\hat{\mathbf{x}}-\mathbf{x}\right\|_{0}\leq d_{0}-s_{0}\) _and,_ \[\frac{\left\|\hat{\mathbf{x}}-\mathbf{x}\right\|_{2}}{\zeta_{0}}\leq\epsilon_{ 0}\;\text{ and }\;\max\left\{\frac{\left\|\hat{\mathbf{W}}-\mathbf{W}\right\|_{(d_{1}-1,s_{0} )}}{\xi_{1}},\frac{\left\|\hat{\mathbf{W}}-\mathbf{W}\right\|_{(s_{1},s_{0})}}{ \xi_{1}\sqrt{1+\eta_{1}}}\right\}\leq\epsilon_{1},\] _and denote_ \(\hat{\Phi}(\mathbf{x})=\sigma(\hat{\mathbf{W}}\mathbf{x})\)_. If_ \(r_{\text{sparse}}(\mathbf{W},\mathbf{x},s_{1})\geq-1+(1+\epsilon_{0})(1+ \epsilon_{1})\)_, then the index set_ \(I(\mathbf{W},\mathbf{x},s_{1})\) _is inactive and stable to perturbations, i.e._7__\(\mathcal{P}_{I}(\Phi(\mathbf{x}))=\mathcal{P}_{I}(\hat{\Phi}(\hat{\mathbf{x}}))= \mathcal{P}_{I}(\hat{\Phi}(\hat{\mathbf{x}}))=\mathbf{0}\)_. Moreover,_ \(\left\|\hat{\Phi}(\hat{\mathbf{x}})-\Phi(\mathbf{x})\right\|_{2}\leq(-1+(1+ \epsilon_{0})(1+\epsilon_{1}))\cdot\xi_{1}\sqrt{1+\eta_{1}}\cdot\zeta_{0}\)_._

Footnote 7: For notational ease we suppress arguments and let \(I=I(\mathbf{W},\mathbf{x},s_{1})\).
3. _Stability of sparse local radius_: _For a perturbed input_ \(\hat{\mathbf{x}}\) _such that_ \(\left\|\hat{\mathbf{x}}-\mathbf{x}\right\|_{0}\leq d_{0}-s_{0}\)_, and perturbed weight_ \(\hat{\mathbf{W}}\)_, the difference between sparse local radius is bounded_

\[\left|r_{\text{sparse}}(\hat{\mathbf{W}},\hat{\mathbf{x}},s_{1})-r_{\text{ sparse}}(\mathbf{W},\mathbf{x},s_{1})\right|\leq-1+\left(1+\frac{\left\|\hat{ \mathbf{x}}-\mathbf{x}\right\|_{2}}{\zeta_{0}}\right)\left(1+\frac{\left\| \hat{\mathbf{W}}-\mathbf{W}\right\|_{(d_{1}-1,s_{0})}}{\xi_{1}}\right).\]

A key takeaway of this Lemma (see Appendix A.1.1 for its proof) is that one can obtain tighter bounds, on both the size of the network output as well as its sensitivity to corruptions, if the corresponding sparse local radius is sufficiently large. The results above quantify these notions for a given sample. In the next section, we will leverage this characterization within the framework of PAC-Bayes analysis to provide a generalization bound for feed-forward networks.

## 3 A Sparsity-Aware Generalization Theory

We shall construct non-uniform data-dependent generalization bounds for feed-forward networks based on a local sensitivity analysis of deep ReLU networks, employing the intuition from the previous section. To do so, we will first study the size of the layer outputs using Definition 2, then measure the sensitivity in layer outputs to parameter perturbations using Lemma 1 across multiple layers, and finally leverage a derandomized PAC-Bayes result from Nagarajan and Kolter (2019b) (see Appendix C.2). Before embarking on the analysis, we note the following convenient property of the margin for any two predictors \(h,\hat{h}\) from (Bartlett et al., 2017, Lemma A.3),

\[\left|\left(h(\mathbf{x})_{y}-\max_{j\neq y}h(\mathbf{x})_{j}\right)-\left( \hat{h}(\mathbf{x})_{y}-\max_{j\neq y}\hat{h}(\mathbf{x})_{j}\right)\right| \leq 2\left\|\hat{h}(\mathbf{x})-h(\mathbf{x})\right\|_{\infty}.\]

Hence, quantifying the sensitivity of the predictor outputs will inform the sensitivity of the loss. Similar to other works (Nagarajan and Kolter, 2019b; Banerjee et al., 2020), our generalization bound will be derived by studying the sensitivity of neural networks upon perturbations to the layer weights.

For the entirety of this section, we fix a set of _base hyper-parameters_ that determine a specific class of neural networks, the variance of a posterior distribution over networks, and the resolution (via a sparsity vector) at which the generalization is measured - see Table 1 for reference. We denote by \(\mathbf{s}=\{s_{1},\ldots,s_{K}\}\) a vector of layer-wise sparsity levels, which reflects the inductive bias of the learner on the potential degree of sparsity of a trained network on the training data. Next we define two hyper-parameters, \(\boldsymbol{\xi}:=\{\xi_{1},\ldots,\xi_{K+1}\}\) where \(\xi_{k}>0\) bounds the sparse norm \(\left\|\cdot\right\|_{(d_{k}-1,s_{k-1})}\) of the layer weights and \(\boldsymbol{\eta}:=\{\eta_{1},\ldots,\eta_{K}\}\) where \(\eta_{k}>0\) bounds the reduced babel function \(\mu_{s_{k},s_{k-1}}(\cdot)\) of the layer weights. Finally, we let \(\boldsymbol{\epsilon}:=\{\epsilon_{1},\ldots,\epsilon_{K+1}\}\) with \(\epsilon_{k}>0\) bound the amount of relative perturbation in the weights. This section treats the quartet \((\mathbf{s},\boldsymbol{\xi},\boldsymbol{\eta},\boldsymbol{\epsilon})\) as constants8, while in the next section we shall discuss appropriate values for these hyper-parameters.

Footnote 8: Unless otherwise specified we let \(s_{0}=s_{K+1}=0\) and \(\epsilon_{0}=0\).

**Definition 4**: _(Norm bounded feed-forward networks) We define below the parameter domain \(\mathcal{W}_{k}\) and a class of feed-forward networks \(\mathcal{H}_{K+1}\) with \(K\)-hidden layers,_

\[\mathcal{W}_{k}:=\left\{\mathbf{W}\in\mathbb{R}^{d_{k}\times d_{k- 1}}\ |\ \left\|\mathbf{W}\right\|_{(d_{k}-1,s_{k-1})}\leq\xi_{k},\quad\mu_{s_{k},s_{k- 1}}(\mathbf{W})\leq\eta_{k},\right\},\;\forall\;k\in[K],\] \[\mathcal{H}:=\left\{h(\cdot):=\mathbf{W}_{K+1}\sigma\left(\mathbf{W} _{K}\cdots\sigma\left(\mathbf{W}_{1}\cdot\right)\right)\ |\ \left\|\mathbf{W}_{K+1}\right\|_{(C-1,s_{K})}\leq\xi_{K+1},\ \mathbf{W}_{k}\in\mathcal{W}_{k},\;\forall\;k\in[K]\right\}.\]

\begin{table}
\begin{tabular}{|c|c|} \hline \(\mathbf{s}=\{s_{1},\ldots,s_{k}\}\), \(\ 0\leq s_{k}\leq d_{k}-1\) & Layer wise sparsity vector \\ \hline \(\boldsymbol{\xi}=\{\xi_{1},\ldots,\xi_{K+1}\}\), \(\ 0\leq\xi_{k}\) & Layer wise bound on \(\left\|\cdot\right\|_{(d_{k}-1,s_{k-1})}\) \\ \hline \(\boldsymbol{\eta}=\{\eta_{1},\ldots,\eta_{K}\}\), \(\ 0\leq\eta_{k}\) & Layer wise bound on \(\mu_{s_{k},s_{k-1}}(\cdot)\) \\ \hline \(\boldsymbol{\epsilon}=\{\epsilon_{1},\ldots,\epsilon_{K+1}\}\), \(\ 0\leq\epsilon_{k}\) & Layer wise bound on relative perturbation \\ \hline \end{tabular}
\end{table}
Table 1: Independent base hyper-parameters
To measure the local sensitivity of the network outputs, it will be useful to formalize a notion of local neighborhood for networks.

**Definition 5**: _(Local Neighbourhood) Given \(h\in\mathcal{H}\), define \(\mathcal{B}(h,\mathbf{\epsilon})\) to be the local neighbourhood around \(h\) containing perturbed networks \(\hat{h}\) with weights \(\{\hat{\mathbf{W}}_{j}\}_{k=1}^{K+1}\) such that at each layer \(k\)9,_

Footnote 9: For the last layer we only require \(\left\|\hat{\mathbf{W}}_{K+1}-\mathbf{W}_{K+1}\right\|_{C-1,s_{K}}\leq\epsilon_ {K+1}\cdot\xi_{K+1}\).

\[\max\left\{\frac{\left\|\hat{\mathbf{W}}_{k}-\mathbf{W}_{k}\right\|_{(s_{k},s_ {k-1})}}{\xi_{k}\sqrt{1+\eta_{k}}},\frac{\left\|\hat{\mathbf{W}}_{k}-\mathbf{W }_{k}\right\|_{(d_{k}-1,s_{k-1})}}{\xi_{k}}\right\}\leq\epsilon_{k}.\]

It will be useful to understand the probability that \(\hat{h}\in\mathcal{B}(h,\mathbf{\epsilon})\) when the perturbations to each layer weight are random, in particular from Gaussian distributions over feed-forward networks:

**Definition 6**: _(Entrywise Gaussian) Let \(h\in\mathcal{H}\) be any network with \(K+1\) layers, and let \(\mathbf{\sigma}^{2}:=\{\sigma_{1}^{2},\ldots,\sigma_{K+1}^{2}\}\) be a layer-wise variance. We denote by \(\mathcal{N}(h,\mathbf{\sigma}^{2})\) a distribution with mean network \(h\) such that for any \(\hat{h}\sim\mathcal{N}(h,\mathbf{\sigma}^{2})\) with layer weights \(\hat{\mathbf{W}}_{k}\), each entry \(\hat{\mathbf{W}}_{k}[i,j]\sim\mathcal{N}(\mathbf{W}_{k}[i,j],\sigma_{k}^{2})\)._

### Sensitivity Of Network Output

Given a predictor \(h\in\mathcal{H}\), note that the size of a network output for any given input is bounded by \(\left\|h(\mathbf{x}_{0})\right\|_{2}\leq\prod_{k=1}^{K+1}\left\|\mathbf{W}_{k} \right\|_{2}\mathsf{M}_{\mathcal{X}}\), which ignores the sparsity of the intermediate layers. We will now generalize the result in Lemma 1 by making use of the inactive index sets at every layer \(I_{k}\), such that \(\mathcal{P}_{I_{k}}(\mathbf{x}_{k})=\mathbf{0}\), obtaining a tighter (input dependent) characterization of sensitivity to perturbations of the network. For notational convenience, we define two additional dependent notations: we let \(\zeta_{0}:=\mathsf{M}_{\mathcal{X}}\) and \(\zeta_{k}:=\xi_{k}\sqrt{1+\eta_{k}}\cdot\zeta_{k-1}=\mathsf{M}_{\mathcal{X}} \prod_{n=1}^{k}\xi_{n}\sqrt{1+\eta_{n}}\) denote a bound on the layer-wise size of the outputs. At the final layer, we let \(\zeta_{K+1}:=\xi_{K+1}\zeta_{K}\) as a bound on the network output. Additionally, we define \(\gamma_{k}:=-1+\prod_{n=1}^{k}(1+\epsilon_{n})\) as a threshold on the sparse local radius evaluated at each layer - see Table 2 for a summary. In the last layer, we let this value \(\gamma_{K+1}\) represent the desired margin. For networks \(\hat{h}\) with perturbed weights \(\hat{\mathbf{W}}\), we denote by \(\hat{\mathbf{x}}_{k}:=\sigma\left(\hat{\mathbf{W}}_{k}\hat{\mathbf{x}}_{k-1}\right)\) the perturbed layer representation corresponding to input \(\mathbf{x}_{0}\).

**Definition 7**: _(Layer-wise sparse local radius) Let \(h\) be any feed-forward network with weighs \(\mathbf{W}_{k}\in\mathbb{R}^{d_{k}\times d_{k-1}}\), and let \(\mathbf{x}_{0}\in\mathbb{R}^{d_{0}}\). We define a layer-wise sparse local radius and a layer-wise inactive index set as below,_

\[I_{k}(h,\mathbf{x}_{0}):=\text{Top-k}\left(-\frac{\mathbf{W}_{k}\cdot \mathbf{x}_{k-1}}{\xi_{k}\zeta_{k-1}},s_{k}\right),\quad r_{k}(h,\mathbf{x}_{0 }):=\sigma\left(\text{sort}\left(-\frac{\mathbf{W}_{k}\cdot\mathbf{x}_{k-1}}{ \xi_{k}\zeta_{k-1}},\ s_{k}\right)\right).\]

Definition 7 now allows us, by employing Lemma 1, to generalize our previous observations to entire network models, as we now show.

**Theorem 1**: _Let \(h\in\mathcal{H}\), if at each layer \(k\) the layer-wise sparse local radius is nontrivial, i.e. \(\forall\ k\in[K],\ \ r_{k}(h,\mathbf{x}_{0})>0\). Then the index sets \(I_{k}(h,\mathbf{x}_{0})\) are inactive at layer \(k\) and the size of the hidden layer representations and the network output are bounded as follows,_

\[\forall\ k\in[K],\quad\left\|\mathbf{x}_{k}\right\|_{2}\leq\zeta_{k},\quad \text{and}\quad\left\|h(\mathbf{x}_{0})\right\|_{\infty}\leq\zeta_{K+1}. \tag{3}\]

\begin{table}
\begin{tabular}{|c|c|} \hline \(\zeta_{k}:=\xi_{k}\sqrt{1+\eta_{k}}\cdot\zeta_{k-1}\), & \(\forall\ k\in[K]\) \\ \hline \(\zeta_{K+1}:=\xi_{K+1}\zeta_{K}\) & Bound on norm of network output \\ \hline \(\gamma_{k}:=-1+\prod_{n=1}^{k}(1+\epsilon_{n}),\ \ \forall\ k\in[K+1]\) & Layer wise threshold for local radius \\ \hline \(r_{k}(h,\mathbf{z}):=\sigma\left(\text{sort}\left(-\left[\frac{\mathbf{w}_{k}[i] \cdot\mathbf{x}_{k-1}}{\xi_{k}\zeta_{k-1}}\right]_{i=1}^{d_{k}},\ d_{k}-s_{k}\right)\right)\) & Layer-wise sparse local radius \\ \hline \end{tabular}
\end{table}
Table 2: Layer-wise bounds and thresholds.
In a similar vein, we can characterize the sensitivity of the network to parameter perturbations.

**Theorem 2**: _Let \(h\in\mathcal{H}\) and let \(\hat{h}\in\mathcal{B}(h,\boldsymbol{\epsilon})\) be a nearby perturbed predictor with weights \(\{\hat{\mathbf{W}}_{k}\}\). If each layer-wise sparse local radius is sufficiently large, i.e. \(\forall\ k\in[K],\ r_{k}(h,\mathbf{x}_{0})\geq\gamma_{k}\), then the index sets \(I_{k}(h,\mathbf{x}_{0})\) are inactive for the perturbed layer representations \(\hat{\mathbf{x}}_{k}\) and the distance between the layer representations and the network output are bounded as follows,_

\[\forall\ k\in[K],\quad\left\|\hat{\mathbf{x}}_{k}-\mathbf{x}_{k}\right\|_{2} \leq\zeta_{k}\cdot\gamma_{k},\quad\text{and}\quad\left\|\hat{h}(\mathbf{x}_{0} )-h(\mathbf{x}_{0})\right\|_{\infty}\leq\zeta_{K+1}\cdot\gamma_{K+1}. \tag{4}\]

Proofs of the above propositions can be found in A.1.2 and A.1.3 respectively.

### Sparsity-Aware Generalization

We are now ready to state our main theorem on generalization of feed-forward networks that leverages improved sensitivity of network outputs due to stable inactive index sets.

**Theorem 3**: _Let \(\mathcal{P}\) be any prior distribution over depth-\((K+1)\) feed-forward network chosen independently of the training sample. Let \(h\in\mathcal{H}\) be any feed-forward network (possibly trained on sample data), with \(\mathcal{H}\) determined by fixed base hyper-parameters \((\mathbf{s},\boldsymbol{\epsilon},\boldsymbol{\delta},\boldsymbol{\eta})\), and denote the sparse loss by \(\ell_{\mathrm{sparse}}(h,\mathbf{x})=\mathbb{I}\{\exists\,k,\ r_{k}(h, \mathbf{x})<3\gamma_{k}\}\). With probability at least \((1-\delta)\) over the choice of i.i.d training sample \(\textbf{S}_{T}\) of size \(m\), the generalization error of \(h\) is bounded as follows,_

\[R_{0}(h)\leq\hat{R}_{4\zeta_{K+1}\gamma_{K+1}}(h)+\frac{2K}{m}\sum_{\mathbf{x }^{(i)}\in\mathcal{S}_{T}}\ell_{\mathrm{sparse}}(h,\mathbf{x}^{(i)})+\tilde{ \mathcal{O}}\left(\sqrt{\frac{\mathrm{KL}\left(\mathcal{N}\left(h,\boldsymbol{ \sigma}_{\mathrm{sparse}}^{2}\right)\ ||\ \mathcal{P}\right)}{m}}\right)\]

_where \(\boldsymbol{\sigma}_{\mathrm{sparse}}=\{\sigma_{1},\ldots,\sigma_{K}\}\) is defined by \(\sigma_{k}:=\epsilon_{k}\cdot\frac{\xi_{k}}{4\sqrt{2d_{\mathrm{eff}}+\log\left( 2(K+1)\sqrt{m}\right)}}\), and where \(d_{\mathrm{eff}}:=\max_{k\in[K]}\frac{(d_{k}-s_{k})\log(d_{k})+(d_{k-1}-s_{k-1} )\log(d_{k-1})}{2}\) is an effective layer width10._

Footnote 10: We note the effective width is at worst \(\max_{k}d_{k}\log(d_{k})\) and could be larger than actual width depending on the sparsity vector \(\mathbf{s}\). In contrast, for large \(\mathbf{s}\), \(d_{\mathrm{eff}}\ll\max_{k}d_{k}\).

The notation \(\tilde{\mathcal{O}}\) above hides logarithmic factors (see Appendix A.3 for a complete version of the bound). This result bounds the generalization error of a trained predictor as a function of three terms. Besides the empirical risk with margin threshold \(4\zeta_{K+1}\gamma_{K+1}\), the risk is upper bounded by an empirical sparse loss that measures the proportion of samples (in the training data) that do not achieve a sufficiently large sparse radius at any layer. Lastly, as is characteristic in PAC-Bayes bounds, we see a term that depends on the distance between the prior and posterior distributions, the latter centered at the obtained (data-dependent) predictor. The posterior variance \(\boldsymbol{\sigma}_{\mathrm{sparse}}^{2}\) is determined entirely by the base hyper-parameters. Finally, note that the result above holds for any prior distribution \(\mathcal{P}\). Before moving on, we comment on the specific factors influencing this bound.

Sparsity.The result above depends on the sparsity by the choice of the parameter \(\mathbf{s}\). One can always instantiate the above result for \(\mathbf{s}=\mathbf{0}\), corresponding to a global sensitivity analysis. At this trivial choice, the sparsity loss vanishes (because the sparse radius is infinite) and the bound is equivalent to an improved (derandomized) version of the results by Neyshabur et al. (2018). The formulation in Theorem 3 enables a continuum of choices (via hyper-parameters) suited to the trained predictor and sample data. A larger degree of sparsity at every layer results in a tighter bound since the upper bounds to the sensitivity of the predictor is reduced (as only reduced matrices are involved in its computation). In turn, this reduced sensitivity leads to a lower empirical margin risk by way of a lower threshold \(4\zeta_{K+1}\gamma_{K+1}\). Furthermore, the effective width - determining the scale of posterior - is at worst \(\max_{k}d_{k}\log(d_{k})\) (for \(\mathbf{s}=0\)), but for large \(\mathbf{s}\), \(d_{\mathrm{eff}}\ll\max_{k}d_{k}\).
Sensitivity.Standard sensitivity-based generalization bounds generally depend directly on the global Lipschitz constant that scales as \(\mathcal{O}(\prod_{k=1}^{K}\|\mathbf{W}_{k}\|_{2})\). For even moderate-size models, such dependence can render the bounds vacuous. Further recent studies suggest that the layer norms can even increase with the size of the training sets showing that, even for under-parameterized models, generalization bounds may be vacuous (Nagarajan and Kolter, 2019). Our generalization bound does _not_ scale with the reduced Lipschitz constant \(\zeta_{K+1}\): while larger (reduced) Lipschitz constants can render the empirical sparse loss closer to its maximum value of \(1\), the bound remains controlled due to our choice of modelling _relative_ perturbations of model parameters.

Dependence On Depth.Unlike recent results (Bartlett et al., 2017; Neyshabur et al., 2015, 2018, 2019), our bound is not exponential with depth. However, the sensitivity bounds \(\zeta_{k}\) and radius thresholds \(\gamma_{k}\) are themselves exponential in depth. While the empirical risk and sparse loss terms in the generalization bounds depend on \(\zeta_{k},\gamma_{k}\), they are bounded in \([0,1]\). In turn, by choosing the prior to be a Gaussian \(P=\mathcal{N}(h_{\mathrm{prior}},\mathbf{\sigma}_{\mathrm{sparse}}^{2})\), the KL-divergence term can be decomposed into layer-wise contributions, \(\mathrm{KL}\left(\mathcal{N}\left(h,\mathbf{\sigma}_{\mathrm{sparse}}^{2} \right)\;||\;\mathcal{N}(h_{\mathrm{prior}},\mathbf{\sigma}_{\mathrm{sparse}}^ {2})\right)=\sum_{k=1}^{K+1}\frac{\|\mathbf{W}_{k}-\mathbf{W}_{\mathrm{prior},k}\|_{2}^{2}}{2\sigma_{k}^{2}}\). Hence, the KL divergence term does not scale with the product of the relative perturbations (like \(\gamma_{k}\)) or the product of layer norms (like \(\zeta_{k}\)).

Comparison To Related Work.Besides the relation to some of the works that have been mentioned previously, our contribution is most closely related to those approaches that employ different notions of reduced effective models in developing generalization bounds. Arora et al. (2018) do this via a _compression_ argument, alas the resulting bound holds for the compressed network and not the original one. Neyshabur et al. (2017) develops PAC-Bayes bounds that clearly reflect the importance of _flatness_, which in our terms refers to the loss effective sensitivity of the obtained predictor. Similar in spirit to our results, Nagarajan and Kolter (2019) capture a notion of reduced active size of the model and presenting their derandomized PAC-Bayes bound (which we centrally employ here). While avoiding exponential dependence on depth, their result depends inversely with the minimum absolute pre-activation level at each layer, which can be arbitrarily small (and thus, the bound becomes arbitrarily large). Our analysis, as represented by Lemma 1, circumvents this limitation. Our constructions on normalized sparse radius have close connections with the _normalized margins_ from Wei and Ma (2020), and our use of augmented loss function (such as our _sparse loss_) resemble the ones proposed in Wei and Ma (2019). Most recently, Galanti et al. (2023) analyze the complexity of compositionally sparse networks, however the sparsity stems from the convolutional nature of the filters rather than as a data-dependent (and sample dependent) property.

### Hyper-Parameter Search

For any fixed predictor \(h\), there can be multiple choices of \(\mathbf{s},\mathbf{\xi},\mathbf{\eta}\) such that \(h\) is in the corresponding hypothesis class. In the following, we discuss strategies to search for suitable hyper-parameters that can provide tighter generalization bounds. To do so, one can instantiate a grid of candidate values for each hyper-parameter that is independent of data. Let the grid sizes be \((T_{\mathbf{s}},T_{\mathbf{\xi}},T_{\mathbf{\eta}},T_{\mathbf{\epsilon}})\), respectively. We then instantiate the generalization bound in Theorem 3 for each choice of hyper-parameters in the cartesian product of grids with a reduced failure probability \(\delta_{\mathrm{red}}=\frac{\delta}{T_{\mathbf{\tau}}T_{\mathbf{\xi}}T_{\mathbf{\eta}}T_{ \mathbf{\epsilon}}}\). By a simple union-bound argument, all these bounds hold simultaneously with probability \((1-\delta)\). In this way, for a fixed \(\delta\), the statistical cost above is \(\sqrt{\log(T_{\mathbf{\ast}}T_{\mathbf{\xi}}T_{\mathbf{\eta}}T_{\mathbf{\epsilon}})}\) as the failure probability dependence in Theorem 3 is \(\sqrt{\log\left(\frac{1}{\delta_{\mathrm{red}}}\right)}\). The computational cost of a naive search is \(\mathcal{O}(T_{\mathbf{s}}T_{\mathbf{\xi}}T_{\mathbf{\eta}}T_{\mathbf{\epsilon}})\). In particular, for multilayer networks, to exhaustively search for a sparsity vector requires a grid of size \(T_{\mathbf{s}}:=\prod_{k=1}^{K}d_{k}\) rendering the search infeasible. Nonetheless, we shall soon show that by employing a greedy algorithm one can still obtain tighter generalization bounds with significantly lesser computational cost. Moreover, these hyper-parameters are not independent, and so we briefly describe here how this optimization can be performed with manageable complexity.
Norm Hyper-Parameters (\(\mathbf{\xi},\mathbf{\eta}\)):One can choose \((\mathbf{\xi},\mathbf{\eta})\) from a grid (fixed in advance) of candidate values, to closely match the true properties of the predictor. For networks with zero bias, w.l.o.g. one can normalize each layer weight \(\mathbf{W}_{k}\rightarrow\tilde{\mathbf{W}}_{k}:=\frac{1}{\|\mathbf{W}_{k\|(d_{k }-1,\epsilon_{k-1})}}\mathbf{W}_{k}\) to ensure that \(\left\|\tilde{\mathbf{W}}_{k}\right\|_{(d^{k}-1,s_{k-1})}=1\) without changing the prediction11. The predicted labels, label function, sparse local radius, margin and the generalization bound in Theorem 3 are all invariant to such a scaling. For the normalized network we can simply let \(\xi_{k}:=1\) for all \(k\). Fixing \(\mathbf{\xi}\) this way results in no statistical or computational cost (beyond normalization). For discretizing \(\mathbf{\eta}\), we can leverage the fact that for all \((s_{k},s_{k-1})\), the reduced babel function is always less than \(d_{k}-s_{k}-1\) - since the inner products are scaled by the square of the sparse norms. Thus, we can construct a grid in \([0,1]\) with \(T_{\eta}\) elements, which can be searched efficiently (see Appendix B for further details).

Footnote 11: This is not true for networks with non-zero bias. In networks with bias, one can still employ a grid search like in Bartlett et al. (2017).

Sparsity Parameter s:The sparsity vector \(\mathbf{s}\) determines the degree of structure at which we evaluate the generalization of a fixed predictor. For a fixed predictor and relative sensitivity vector \(\mathbf{\epsilon}\), a good choice of \(\mathbf{s}\) is one that has sufficiently large sparse local radii on the training sample resulting in small average sparse loss, \(\frac{1}{n}\sum_{\mathbf{x}^{(i)}\in\mathbf{S}_{T}}\ell_{\text{sparse}}(h, \mathbf{x}^{(i)})\). At the trivial choice of sparsity \(\mathbf{s}=\mathbf{0}\), for any choice of \(\mathbf{\epsilon}\), the above loss is exactly zero. In general, at a fixed \(\mathbf{\epsilon}\), this loss increases with larger (entrywise) \(\mathbf{s}\). At the same time, the empirical margin loss term \(\hat{R}_{4\zeta_{K+1}\gamma_{K+1}}(h)\) decreases with increasing \(\mathbf{s}\) (since \(\zeta_{K+1}\) grows). This reflects an inherent tradeoff in the choice of \((\mathbf{s},\mathbf{\epsilon})\) to balance the margin loss and the sparse loss (in addition to the KL-divergence).

For any \(\mathbf{\epsilon}\) and a data point \(\mathbf{z}=(\mathbf{x},y)\), we employ a greedy algorithm to find a sparsity vector \(s^{*}(\mathbf{x},\mathbf{\epsilon})\) in a layer wise fashion such that the loss incurred is zero, i.e. so that \(r_{k}(h,\mathbf{x})\geq 3\gamma_{k}\) for all \(k\). At each layer, we simply take the maximum sparsity level with sufficiently large radius. The computational cost of such an approach is \(\log_{2}\left(\prod_{k=1}^{K}d_{k}\right)\). One can thus collect the sparsity vectors \(s^{*}(\mathbf{x},\mathbf{\epsilon})\) across the training set and choose the one with sample-wise minimum, so that the average sparse loss vanishes. Of course, one does not necessarily need the sparse loss to vanish; one can instead choose \(\mathbf{s}\) simply to _control_ the sparse loss to a level of \(\frac{\alpha}{\sqrt{m}}\). We expand in Appendix B how this can done.

Sensitivity Vector \(\mathbf{\epsilon}\):Lastly, the relative sensitivity vector \(\mathbf{\epsilon}\) represents the size of the posterior and desired level of sensitivity in layer outputs upon parameter perturbations. Since \(\epsilon_{k}\) denotes _relative perturbation_ we can simply let it be the same across all layers. i.e. \(\mathbf{\epsilon}=\epsilon\cdot[1,\ldots,1]\).

In summary, as we expand in Appendix B, we can compute a best in-grid generalization bound in \(\mathcal{O}\left(T_{\mathbf{\epsilon}}\cdot\log_{2}\left(\prod_{k=1}^{K}d_{k} \right)\cdot\log_{2}(T_{\mathbf{\eta}})\cdot(\sum_{k=1}^{K}d_{k}d_{k-1})\right).\)

## 4 Numerical Experiments

In this last section we intend to demonstrate the derived bounds on a series of feed-forward networks, of varying width and depth, on MNIST. As we now show, the resulting bounds are controlled and sometimes non-vacuous upon the optimization over a discrete grid for hyper-parameters, as explained above.

Experimental Setup:We train feed-forward networks \(h\) with weights \(\{\mathbf{W}_{k}\}_{k=1}^{K+1}\) where \(\mathbf{W}_{k}\in\mathbb{R}^{d_{k}\times d_{k-1}}\) using the cross-entropy loss with stochastic gradient descent (SGD) for 5,000 steps with a batch size of 100 and learning rate of 0.01. The MNIST training set is randomly split into train and validation data (55,000 : 5,000). The models are optimized on the training data and the resulting measures are computed on validation data. To evaluate scaling with the number of samples, \(m\), we train networks on randomly sampled subsets of the training data of increasing sizes from 20% to 100% of the training set. Because of the chosen architectures, all of these models are over-parametrized (i.e. having more parameters than training samples).
Recall that the bound on generalization error in Theorem 3 depends on the KL divergence between a posterior centered at trained predictor \(h\), \(\mathcal{N}(h,\mathbf{\sigma}_{\text{sparse}}^{2})\), and the prior \(P=\mathcal{N}(h_{\text{prior}},\mathbf{\sigma}_{\text{sparse}}^{2})\). Thus, each model is encouraged to be close to its initialization via a regularization term. In this way, we minimize the following regularized empirical risk based on the cross-entropy loss as well as a regularization term with penalty \(\lambda\) (set as \(\lambda=1.0\) for all experiments for simplicity),

\[\min_{\left\{\mathbf{W}_{k}\right\}_{k=1}^{K+1}} \frac{1}{m}\sum_{i=1}^{m}\ell_{\text{cross}-\text{ent}}\Big{(}h, \left(\mathbf{x}_{i},y_{i}\right)\Big{)}+\frac{\lambda}{K+1}\sum_{k=1}^{K+1} \left\|\mathbf{W}_{k}-\mathbf{W}_{\text{prior},k}\right\|_{F}^{2}.\]

Choice Of Prior:As with any PAC-Bayes bound, choosing a prior distribution with an appropriate inductive bias is important. For example, optimizing the choice of prior by instantiating multiple priors simultaneously was shown to be an effective procedure to obtain good generalization bounds (Langford and Caruana, 2001; Dziugaite and Roy, 2017). In this work, we evaluate our bounds for two choices of the prior: _a)_ a data-independent prior, \(P_{0}:=\mathcal{N}(h_{\mathbf{0}},\mathbf{\sigma}_{\text{sparse}}^{2})\) centered at a model with zero weights, \(h_{\mathbf{0}}\); and _b)_ a data-dependent prior \(P_{\text{data}}:=\mathcal{N}(h_{\text{init}},\mathbf{\sigma}_{\text{sparse}}^{2})\) centered at a model \(h_{\text{init}}\) obtained by training on a small fraction of the training data (\(5\%\) of all training data). Note that this choice is valid, as the base hyper-parameter \((\mathbf{s},\mathbf{\xi},\mathbf{\eta},\mathbf{\epsilon})\) are chosen independent of data, and the empirical risk terms in the bound are not evaluated on the small subset of data \(h_{\text{init}}\) is trained on.

Generalization Bounds Across Width:We first train a 2-layer (1 hidden layer) fully connected neural network with increasing widths, from 100 to 1,000 neurons. Note that in all cases these models are over-parametrized. In Figures 0(a) to 0(c) we plot the true risk (orange curve) and the generalization bounds (blue curve) from Theorem 3 across different sizes of training data and for the two choices of priors mentioned above. We observe that our analysis, when coupled with data-dependent prior \(P_{\text{data}}\), generates non-vacuous bounds for a network with width of 100. Even for the naive choice of the prior \(P_{0}\), the bound is controlled and close to 1. Furthermore, note that our bounds remain controlled for larger widths. In Appendix E, we include complementary results depicting our generalization bounds for 3-layer networks.

Figure 1: Generalization error of a 2-layer model of different widths trained on MNIST.
Effective Activity Ratio:Lastly, we intend to illustrate the degree of sparsity achieved in the obtained models that allow for the bounds presented in Figure 1. For each data point \(\mathbf{x}\) and relative perturbation level \(\epsilon\), we define the Effective Activity ratio \(\kappa(\mathbf{x},\epsilon):=\frac{\sum_{k}(d_{k}-s_{k})(d_{k-1}-s_{k-1})}{\sum_{ k}d_{k}d_{k-1}}\) where \(\mathbf{s}=s^{*}(\mathbf{x},\epsilon)\), the greedy sparsity vector chosen such that the sparse loss in Theorem 3 is zero. In this way, \(\kappa(\mathbf{x},\epsilon)\) measures the reduced local dimensionality of the model at input \(\mathbf{x}\) under perturbations of relative size \(\epsilon\). When \(\kappa(\mathbf{x},\epsilon)=1\), there are no sparse activation patterns that are stable under perturbations, and the full model is considered at that point. On the other hand, when \(0<\kappa(\mathbf{x},\epsilon)\ll 1\), the size of stable sparse activation patterns \(s^{*}(\mathbf{x},\epsilon)_{k}\) at each layer is close to the layer dimension \(d_{k}\). Theorem 3 enables a theory of generalization that accounts for this local reduced dimensionality.

We present the effective activity rations for a trained 3-layer model in Figure 2, and include the corresponding results for the 2-layer model in Appendix E for completeness. The central observation from these results is that trained networks with larger width have _smaller_ effective activity ratios across the training data. In Figure 1(a) (as well as in Figure 1(a) for the 2-layer model), the distribution of effective activity ratio across the training data at \(\epsilon=10^{-4}\) shows that smaller width networks have less stable sparsity. In turn, Figure 1(b) and Figure 1(b) demonstrate that this effect is stronger for smaller relative perturbation levels. This observation is likely the central reason of why our generalization bounds do not increase drastically with model size.

## 5 Conclusion

This work makes explicit use of the degree of sparsity that is achieved by ReLU feed-forward networks, reflecting the level of structure present in data-driven models, but without making any strong distributional assumptions on the data. Sparse activations imply that only a subset of the network is active at a given point. By studying the stability of these local sub-networks, and employing tools of derandomized PAC-Bayes analysis, we are able to provide bounds that exploit this effective reduced dimensionality of the predictors, as well as avoiding exponential dependence on the sensitivity of the function and of depth. Our empirical validation on MNIST illustrates our results, which are always controlled and sometimes result in non-vacuous bounds on the test error. Note that our strategy to instantiate our bound for practical models relied on a discretization of the space of hyper-parameters and a greedy selection of these values. This is likely suboptimal, and the grid of hyper-parameters could be further tuned for each model. Moreover, in light of the works in (Dziugaite and Roy, 2017, 2018; Zhou et al., 2019), we envision optimizing our bounds directly, leading to even tighter solutions.

Figure 2: Effective activity ratio \(\kappa(\mathbf{x},\epsilon)\) based on greedy sparsity vector \(s^{*}(\mathbf{x},\epsilon)\) for 3-layer networks (smaller implies sparser stable activations).
## Acknowledgments

We kindly thank Vaishnavh Nagarajan for helpful conversations that motivated the use of de-randomized PAC-Bayesian analysis. This work was supported by NSF grant CCF 2007649.
