Analyzing Deep PAC-Bayesian Learning with Neural Tangent Kernel: Convergence, Analytic Generalization Bound, and Efficient Hyperparameter Selection
Authors: Wei Huang
Chunrui Liu
Yilan Chen
Richard Yi Da Xu
Miao Zhang
Tsui-Wei Weng
Venue: Accepted by TMLR ()

Abstract: PAC-Bayes is a well-established framework for analyzing generalization performance in machine learning models. This framework provides a bound on the expected population error by considering the sum of training error and the divergence between posterior and prior distributions. In addition to being a successful generalization bound analysis tool, the PAC-Bayesian bound can also be incorporated into an objective function for training probabilistic neural networks, which we refer to simply as {\it Deep PAC-Bayesian Learning}. Deep PAC-Bayesian learning has been shown to achieve competitive expected test set error and provide a tight generalization bound in practice at the same time through gradient descent training. Despite its empirical success, theoretical analysis of deep PAC-Bayesian learning for neural networks is rarely explored. To this end, this paper proposes a theoretical convergence and generalization analysis for Deep PAC-Bayesian learning. For a deep and wide probabilistic neural network, our analysis shows that PAC-Bayesian learning corresponds to solving a kernel ridge regression when the probabilistic neural tangent kernel (PNTK) is used as the kernel. We utilize this outcome in conjunction with the PAC-Bayes $\mathcal{C}$-bound, enabling us to derive an analytical and guaranteed PAC-Bayesian generalization bound for the first time. Finally, drawing insight from our theoretical results, we propose a proxy measure for efficient hyperparameter selection, which is proven to be time-saving on various benchmarks. Our work not only provides a better understanding of the theoretical underpinnings of Deep PAC-Bayesian learning, but also offers practical tools for improving the training and generalization performance of these models.

Published in Transactions on Machine Learning Research (05/2023)
Analyzing Deep PAC-Bayesian Learning with Neural Tan- gent Kernel: Convergence, Analytic Generalization Bound, and Efficient Hyperparameter Selection
Wei Huang"
wei.buang ur Oriken..jp
RIKEN Center for Advanced Intelligence Project (AIP)
Chunrui Liu'
chunrwi lww@student..nmmmmmmoo uts. edua.
University of Technology Sydney
Yilan Chen University of California San Diego
Bulsdd edu
Richard Yi Da Xu
wuyida&hhkbrr edu..
Hong Kong Baptist University
Miao Zhang
miaozhang1999 @gmail. com
Harbin Institute of Technology (Shenzhen)
Tsui-Wei Weng
lweng Tacsd. edu
University of California San Diego
Reviewed on OpenReview: openreview. net/ forum? id=nEX295B2RQ
Abstract
PAC-Bayes is a well-established framework for analyzing generalization performance in ma- chine learning models. This framework provides a bound on the expected population error by considering the sum of training error and the divergence between posterior and prior distributions. In addition to being successful generalization bound analysis tool, the PAC-Baycsian bound can also be incorporated into an objective function for training prob- abilistic neural networks, which we refer to simply Deep PAC-Bayesian Learning. Deep PAC-Bayesian learning has been shown to achieve competitive expected test set eπror and provide a tight generalization bound in practice at the same time through gradient descent training. Despite its empirical success, thcoretical analysis of deep PAC-Bayesian learning for neural nelworks is rarely explored. To this end, this paper proposes theoretical con- vergence and generalization analysis for Deep PAC-Bayesian learning. For deep and wide probabilistic neural network, our analysis shows that PAC-Baycsian learning corresponds lo solving kernel ridge regression when the probabilistic neural langent kernel (PNTK) is used as the kernel. We utilize this outcome in conjunction with the PAC-Bayes C-bound, enabling us to derive an analytical and guaranteed PAC-Bayesian generalization bound for the first time. Finally, drawing insight from our theoretical results, we propose a proxy measure for efficient hyperparameter selection, which proven benchmarks. Our work not only provides a better understanding of the theoretical under- pinnings of Deep PAC-Bayesian learning, but also offers practical tools for improving the training and generalization performance of these models.
time-saving on various
"Equa Contribution.

---

Published in Transactions on Machine Learning Research (05/2023)
1 Introduction
Deep learning has demonstrated powerful learning capability due to its over-parameterization structure, in which various network architectures have been responsible for its significant leap in performance (LeCun et al. 2013). However, deep neural networks often suffer from over-fitting and complex hyperparameters, making the design of generalization guarantees a. crucial research goal (Zhang et al. 2021) One recent breakthrough in this area is the development of a learning framework that connects geometry of the loss landscape with the flatness of minima such Sharpness
Minimization Foret et al. (2021) and Deep
PAC-Bayesian learning, which trains probabilistic neural network using objective function based on PAC-Bayosien bounds [Bégin et al. 2016 Dziugaite & Roy, 2017 Neyshabur et al.) 2018 Raginsky ct al.
2017 Neyshabur et al.) 2017 London 2017 Smith & Le 2018 Pérez-Ortiz et al. 2021 Guan & Lu 2022).
Deep PAC-Bayesian learning provides a tight generalization bound while achieving competitive expected
test set error (Ding et al. 2022). Furthermore, this generalization bound can be computed from the training data, obviating the need to split data into training, testing, and validation sets, which is highly applicable
when working with limited data (Pérez-Ortiz et. al. 2021 Grünwald & Mehta 2020
The success of PAC-Bayesian learning has led to their widespread application in different deep neural network architectures, including convolutional neural networks (Zhou et al. 2019
Pérez-Ortiz et al. 2021], binary
activated multilayer networks (Tetarte et al., 2019), partially aggregated neural networks (Biggs & Guedj, 2021), and graph neural networks (Liao et al., 2021: Ju et al. 2023); different learning frameworks such as meeaa-eerring (Amit & Meir 2018: Rothfuss et al. 2021 Flynn et al. 2022), adversarial training and
robustness Wang et al. (2022b), contrastive unsupervised learning (Nozawa al. 2020). These advancements have enabled significant improvements in the gencralization performance of deep neural networks, making PAC-Bayesian learning a valuable tool for training robust and reliable models.
The remarkable empirical success of PAC- PAC-Bayesian learning has generated growing interest in understanding its theoretical properties. However, thcoretical invostigations have been largely limited to specific variants of the technique, such as Entropy-SGD, which minimizes an objective indirectly by approximaling stochastic gradient ascent. on the so-called local entropy (Dziugaite & Roy| 2018a),, and differential privacy (Dziugaite & Roy 2018b). Other investigations have relied heavily on empirical exploration (Neyshabur al. (017). To the best of our knowledge, there has been no systematic investigation into why PAC- Pay-Bayesian learning is successful and why the PAC-Bayesian bound is tight on unseen data after training. For example, it is still
unclcar when applying gradient descent to PAC-Bayesian learning:
Q1: How effective is gradient descent training on a training set?
Q2: How tight is the generalization bound after convergence on the unseen dataset?
These questions are particularly important because understanding the strengt and weaknesses of PAC- Bayesian learning can help improve its theoretical foundations and practical applications. For instance, answering the first question can shed light on the training dynamics and optimization challenges of PAC- Bayesian learning, while answering the second question can provide insights into the generalization perfor- mance of this learning framework.
Answering the questions posed earlier can be challenging due to the inherent non-convexity of optimization in neural networks (Jain et al. 2017), the additional randomness introduced by probabilistic neural networks Spechh 1990), and the challenges brought by the Kullback-Leibler divergence between posterior pesterior/prior /prior dis- tribution pairs. However, recent advances in deep learning theory with over-parameterized settings offer promising approach to tackling these challenges. It has been shown that wide networks optimized with gradient descent can achieve near-zero training error, and the neural tangent kernel (NTK) plays critical role in the training process. The NTK remains unchanged during gradient descent training (Jacot et al. 2018), providing a guarantee for achieving a global minimum (Du el al.) 2019 Allee-ZZuu et al., 2019). In the PACC-Baessan framework, the NTK is calculated based on the gradient of the distribution parameters of the weights, rather than the derivative of the weights themselves. We refer to this as the Probabilistic NTK (PNTK), which we use to develop convergence analysis for characterizing the optimization process of PAC-Bayesian learning. The PAC-Bayes bounds employed in Deep PAC-Bayesian learning typically stem
2

---

Published in Transactions on Machine Learning Research (05/2023)
These bounds study the expected risk, often referred to as Gibbs risk. Conversely, an alternative line of PAC-Bayes bounds, known as the C-bound Lacasse et al. (2006), presents an upper bound for the risk associated with the Majority Vote classifier, the risk expected output. Examining the risk of expected output within the PAC-Bayes bound presents the benefit of providing an explicit solution for optimization analysis the infinile-width limit. Moreover, we formulate the gencralization bound of PAC-Bayesian learning upon convergence for the first time.
from the PAC-Bayes-kl theorem, indicated by (Seeger 2002
We summarize our contributions follows:
We provide a detailed characterization of the gradient descent training process of the PAC-Bayesian objective function and show that the final solution corresponds to kernel ridge regression with its kernel being the PNTK.
Building upon the optimization solution, we derive an analytical and guaranteed PAC-Bayesian bound for deep networks after training for the first time. In contrast to other PAC-Bayesian bounds that require the distribution of the posterior, our bound, based on the C-bound under Gaussian posterior, where only the mean parameter is being trained, is entirely independent of computing the distribution of the posterior.
We design training-fri free proxy based theoretical bound to select hyperparameters efficiently, which is effective and time-saving. Our training-free proxy can help alleviate the compulations ional burden of hyperparameter selection, which is critical for practical applications of PAC-Bayesian learning.
Our technique of analyzing optimization and generalization of probabilistic neural networks through norrearramettrizztionn has wide range of applications, such as the Variational Auto-encoder (Kingma & Welling 2013 Rezende et al. 2014) and deep Bayesian networks (MacKay 1992. Neal
2012). We believe that our technique can provide the basis for the analysis of over-parameterized probabilistic neural networks.
2 Related Work
PAC-Bayes Bound The Probably Approximately Correct (PAC) Bayes framework (McAllester 1999a b
is useful tool for providing test performance (generalization) guarantee by incorporating knowledge about the learning algorithm and probability distribution over a set of hypotheses. This framework has been extended to the analysis of generalization bounds for probabilistic neural networks using the PAC- Bayesian method (Langford & Caruana 2002). While the original PAC-Bayes theory only works with bounded loss functions, Germain et al. (2016) proposed a PAC-Bayes bound for sub-gamma loss family and Haddouche et. al. (2021) expanded the PAC-Bayesian theory to learning problems with unbounded loss functions. Furthermore, several improved PAC-Bayesiar bounds suitable for different scenarios have been introduced by [éggin et al. (2014 2016). The flexibillity and generalization propertics of the PAC-Bayes framework make il a popular tool for analyzing complex, non-convex, and overparanetterized optimization problems, particularly for over-parameterized neural networks [Guedj 2019). In the context of feedforward neural networks with ReLU activations, Neyshabur et al. (2018) presented a generalization bound based on the product of the spectral norm of the layers and the Frobenius norm of the weights. This bound has been used a benchmark for evaluating the generalization performance of various neural network architectures and training methods.
PAC-Bayesian Learning. Obtaining numerical bound on generalization is just as important as achiev- ing a thcoretical analysis for the gencralization propertics of deep learning. One method for computing an error upper bound is by training a Bayesian neural network and using a refined PAC-Bayesian bound, as
introduced by Langford & Caruana 2002). Building on this work, Neyshabur et al. (2017) developed a training objective function derived from relaxed PAC-Bayesian bound to train deep neural networks. In standard PAC-Bayes, the prior is often chosen to be a spherical Gaussian centered the origin. However,
this approach might not be effective in cases where the KT. divergence is unreasonably large due to a lack of
3

---

Published in Transactions on Machine Learning Research (05/2023)
information about the data. To address this issue, growing body of literature proposes to obtain localized
PAC-Bayes bounds via distributionn-ependden priors informed by the data (Ambroladze et al. 2007 Negrea
et al. 2019 Dziugaite et al. 2021 Perez-Ortiz et al. 2021). Additionally, Dziugaite & Roy (018bb); Tinsi &
Dalalyan (2022) showed how a differentially private data-dependent prior can yicld a valid PAC-Bayes bound
in situations where the data distribution is unknown. Recently, researchers have been focused on providing
PAC-Baycsian bounds for more complex and realistic neural network architectures, such as convolutional
neural networks (Zhou et al. 2 binary activated multilayer networks (Letarte et al. 2019). partially aggregated neural networks Biggs & Guedi 2021,, attention- neural networks (Wang et al. 2022b),
and graph neural networks Liao et al.) 2021 Ju et al. 2023). In this work, our goal is to demystify the
success of deep PAC-Bayesian Learning by exploring the role of the Probabilistic Neural Tangent Kernel
(PNTK) in achieving light generalization bound.
3 Preliminary
Notation. In this paper, we use bold-faced letters for vectors and matrices (e.g., x and W), and non- bold-faced letters for scalars (e.g., n and t). We use || |l2 to denote the Euclidean norm of a vector and the spectral norm of a matrix, while -|- denotes the Frobenius norm of a matrix. For a neural network, use (I) to denote the activation function, which applies an element-wiss nonlinearity to its input. We denote the set .,2,...,77 n [n], and we use Ao(A) (A) to denote the least eigenvalue of matrix A. Throughout the paper, we will also use other common notation, such as O(.) for asymptotic notation and E[| for the expected value of a random variable. We will define any additional notation as needed.
3.1 Deep probabilistic neural network
In CAC-Bayesian learning, we use probabilistic neural networks (PNNs) instead of deterministic networks. In PNNs, the weights follow a certain distribution, and in this work, we use the Gaussian distribution. We define an L-layer PNN f governed by the following recursive expression:
x(1
1 o (w("x( Vm
ISIS f= V ((1)
(1)
where is width of hidden layers, x()) = E Rd is the input with d being the imput dimension, W(1) E Rm is the weight matrix at the first layer, W E Ruxm is the weight at the 1-th layer for 2 < s L 1, and
((1) e m is the weight at the output layer.
We employ the reparamcterization trick (Kingma & Welling, 2013 Kingma et al. 2015 to model the weights as Gaussian during gradient descent training, with trainable mean and variance parameters:
w
w(O w g E()) ~ (O,,), 1
where denotes the wlement-wide product operation. In this expression, for all 1 < < L, {d) share the same size their corresponding weight matrix vector. The re-parameterization trick involves sampling g()) for 1 1 L from normal distribution IO.
We randomly initialize the mean weights as follows: W!O N' c 1) for E [1, 4J. Here, we omit the size of the mcan 0 and variance I, which is determined by the corresponding weight matrix. For the variance weights, we use an absolute constant to initialize them, namely, w! = eg 1, where is a matrix with all clements equal to 1. Our assumption of an isotropic initialization for the covariance matrix is based on the empirical setting presented in Rivasplata et. al.) (2019).
3.2 PAC- Bayes bound
Suppose we have a set of n i.i.d. samples S = {(x,, R)) drawn from a non-degenerate distribution D. Let H denote the hypothesis space and h(x) the prediction of hypothesis h H for input x. The generalization error of classifier h with respect to D is denoted by RD(h) = (xx.))>D((() h(x)),, where e(.) is given loss function. The empirical error of classifier h with respect S is denoted by Rs(h) = Em h(x:))
4

---

Published in Transactions on Machine Learning Research (05/2023)
In PAC-Bayes, the prior distribution Q(0) H represents the distribution over the hypothesis space H before training or at initialization, and the posterior distribution Q É H represents the distribu- tion of parameters after training. The expected population risk and empirical error are defined as (D(Q)= = (xx.))D,.--l(f h(x)) = -E and Rs(Q) = @n-o@RR(tte respectively.
The PAC-Bayes theory (Seger 2002
Maurer 2004) provides the following theorem:
Theorem 3.1. For any 5 E (0,1), any loss function & R x R + [0, 1], the following inequality holds uniformly for all posteriors distributions Q E H with a probability of at least 1 - 6,
(((Rs(Q)IRo(()) KL(QIIQ(O) + log 2/"
(3)
n
where (L( EQ In Q the Kulbbeck-Leibler (KL) divergence and kl(glld') q logg( (g) + (1
q) log( ) the binary KL divergence.
Furthermore, by combining Pinsker's inequality for binary KL divergence, kl(plpp) 2 (p - (o-)))/(2p), where ş < p, we can obtain the following bound:
(Q - Rs(() S (Q) (L(Q)Q(()) + log 2yα
(4)
n
Equation (4) is classical result. This result be further combined with the inequality Vab S } )) for all Ā > 0, which leads to a PAC-Bayes-X bound in Theorem 3.2 as proposed by Thiemann et al. (0117)
Theorem 3.2. Let Q(0) H be some prior distribution over H. Then for any 5 E (0, 1], the following inequality holds uniformly for all posteriors distributions Q E H with probability of at least 1 - 8
(2( S Rs( 1- 1-2
(T(QIIQ(O)) + log 2/
+ ni(1 x/2)
(5)
Another line of PAC-Bayes C-bound research (Laviolette & Marchand 2007 Laviolette et al. 2011 Germain
ett al. 2015) focuses the upper bound of the Q-weighted majority vote classifier Bg sng( [ h (xx;) also known as the Bayes classifier. In this context, define the Q-margin realized on example (x, v), which is an important notion related to majority votes: MQ(x, y) y Bnx@h(x), We also consider the
first moment MB = E(x.))=DMM (x, y) and the second moment Mb = E(xx) ((( (x) of the
Q-margin. The genoralization bound of RD( is given as follows:
Theorem 3.3 (PAC Bayes C-Bound (Laviolette et al. 2011)). Let Q E H be any distribution over H. Then for any 8 E (0, for any n 2 8, for any culo-complemented famiiy H of B-bounded real value functions, the following inequality holds with probability of at least 1 1 -5:
Int 2m
(b( $1 (MB)2
(MS - 2B
51
V2n
(6)
MB
MS. 2 + 2B y (n(
v2n
where M
Mo(x.1) and M = = E I
The C-bound is an upper bound of the risk of Majority vote classifier, that depends on the first two moments of the margin of the Q-convex combination realized on the data. While the PAC-Bayes bounds (Theorems 3.1 and 3.2) deal with classifiers that use a fixed subset of the training examples. In contrast, the C-bound that applies a stochastic average (and a majority vote) of classifiers using different subsets (of different sizes) of the training examples. In particular, the C-bound proposed for the restricted case where the voters all classifiers, which is consistent with the kernel ridge regression derived in this work.
5

---

Published in Transactions on Machine Learning Research (05/2023)
3.3 Deep PAC-Bayesiag learning
In this work, we aim to use PAC-Bayes theory to design the training objective for PNNs, inspired by previous work such as Catoni (2077]; Rivasplata et al. (2019). Specifically, we choose Equation (5) as the training objective, which is a FAC-Bayes bound that guarantees generalization error. It is worth noting that the original interest of Theorem 3.2 in (Thiemann et al. 2017) was to allow the optimization of a quasiconvex objective with respect to both and Q. However, since our main goal is to study the optimization and gencralization properties of PNNs, we set = and omit the factor of two. Morcover, drawing inspiration from the Bayes classifier, which takes the expectation over Q inside the loss function, we define the objective function as follows:
L(Q)= (Q( + KL (T((()))(0)))
1 " n Σ e (v. + (T,(O())((()) _1
(7)
n
where f(t) A (x= t)] is an expected output function, À is hyperparameter introduced in a heuristic manner to make the method more flexible, and 0 is the collection of all weights. Contrasting the general- ization bound presented by Dziugaite & Roy (2017), which computes the average over the training set using random samples, our approach utilizes the empirical loss of the expected output function inspired by the is lower bound of the expected empirical loss (also known Gibbs empirical risk) Rs(Q), as per Jensen in- equality. This approach offers the advantage of yielding explicit solution for the expected output function in the infinite-width limit. To train the PNN, we use the reparamcterization trick to update the mean and variance of the weight matrices and vectors. Specifically, the update rule for w! and w! with s L at iteration is given by:
PAC-Bayes C-bound. In particular, the empirical loss Qq( _ 11E Ei= E (xi) used in Equation
A o ( ()) " ow?(()
AL(Q)
(++ = ()) -111)--0000
(8)
where 17 is the learning rate. In our theoretical analysis, we consider the gradient flow instead of gradient descent, but the same results can be extended to the gradient descent case with a careful analysis.
4 Main Theoretical Results
In this section, Theorem 4.2 gives precise characterization of how the objective function without KT. divergence decreases to zero. We then extend the convergence characterization to the full objective, and find the final solution is a kernel ridge regression, as demonstrated by Theorem As consequence, we are able to establish an analytic generalization bound through Theorem 4.4
4.1 Optimization analysis
We begin by simplifying the analysis to focus on optimizing probabilistic neural networks of the form ( with the objective function Rs(Q), neglecting the KL divergence term for now. We show that the results obtained for this simplified setting can be extended to the target function with KT. divergence in the next section. In particular, the objective function can be expressed as follows:
1 ||x 1>>-~ (x-f((;t))
Rs(Q:t) = 2n - Ey-=)-of(X:011 2n
(9)
where X (x R represents inputs and the corresponding label is y = (ys) E R". Given this
premise, we start by establishing that, for I-laaee probabilistic neural network of the form 1 the gradient flow of expected output function admits the following dynamics:
df(x;1) af(x;1) 1) a0 0f(x:1) 00, - ((-)(x:)) ((x:0)(0, +x, dt
(10)
00, 0t
00
0t
6

---

Published in Transactions on Machine Learning Research (05/2023)
where 02 A ((W*)))) and O,, - ((W?))=)) H+-) are collection of mean weights and variance weights. Without
loss of generality, set the learning rate 77 = 1. Furthermore, (X, E R=x= and O. X;t) R=x" are probabilistic newral tangent kernels (PNTKs), which are defined as follows:
Definition 4.1 (Probabilistic Neural Tangent Kernel). The tangent kernels associated with the expected oulput function f():)) al parameters 0y and O, are defined as,
(x(xxx:1) 0f(x;1)
(0((:1))
T
L
Σ
V
[X:
w (X:11),
00p
p
w
(11)
(x(x:t)
(0f(X:t)
θ (X,
(ao,
Σ
V W!!
V w!O f
00,
00.
A few remarks on Definition 4.1 are in order. Unlike standard (deterministic) neural networks, a probabilistic network has two sets of parameters, namely, 02 and ts, which lead to two corresponding tangent kernels. We introduce the expected output function f(t) in the definition to correspond to the expected empirical loss RQ( (9) which helps us to address the additional randomization problem caused by PNNs. Explicitly the analytic forms of PNKT are given as follows:
p.i (0)
(0) Σ
m
E
1 af(x;)
d(( T))
)11)
Eg
af(x;) vm dxy
d'(( d((ww!)) (1) x) (1-111)
(12)
mm Ox!
0s(x)) m dx
0f(x)
(0) = Σ Eg
((
(1) T 11-1))
Eg
d' d((
x 1) E!
(13)
0
m Ox
One of the key contributions of this work is the observation that the PNTKs @x X) and (x X) both converge to limiting deterministic kernels, at initialization and during training when m is sufficiently large. Specificallyy, we have mimo (X, Ø (x, and limm- O₂ (X( X) = Ox (X, This result is important because implies that the training dynamics of PNNs can be analyzed in terms of the corresponding deterministic kernels.
Thanks to the convergence of the PNTKs to deterministic kernels as the network width goes to infinity, the gradient flow dynamics of the output function become linear in the infinite-width limit. Specifically, the dynamics take the form:
(y- f(x:t) (xx)()
(X,
(14)
dt
This key finding allows us to establish our main convergence theory for deep probabilistic neural networks, which we state formally below.
Theorem 4.2 (Convergence of probabilistic networks with large width). Suppose o-) is H -ipschhit 8- dx are continuous in x, >o(k( > 0, and the network's n²
Smooth. Assume o(-) and its partial derivative da(a) width is of m Ω (0(1) max n² (on//)))
Then, with probability of at least 1 1-8 8 over the (
random imilialization, we have,
Rs(((t)) S exp (-Xo((( Rt)
(15)
where we defone NNGP kernel and ils derivalive as K(0) A (x (2(") 20)0 with (0) = RB(
1 (w(()((111)) /m
and in the infinite-wiin width limit k()) A -immm K!!) for 1 1 T..
11,00
The proof sketch of Theorem can can be found Scction 5.1 and all the detailed proof are shown in Appendix Our main convergence theory for deep probabilistic neural networks is based on the insight that in the infinite-width limit, the dynamics of the output function with gradient flow is linear. Specifically, if m is large
7

---

Published in Transactions on Machine Learning Research (05/2023)
enough, our theorem establishes that the expected training error converges to at linear rate, with the least eigenvalue of the NNGP kernel governing the convergence rate. Furthermore, we find that the change of weight is bounded during training, as shown in Lemma A.6 which is consistent with the requirement of the PAC-Bayes theory that the loss function bounded.
4.2 Training with KL divergence
We expand the KL-divergence in the objective function
7 with 0(1) -(0,0((0(0000000))
1
(0) log
(t) (0)2
(t,((t) -10 -1)
KL(O(())
(16)
2n
0a,(1))
(0)(0)²
(0)
where is the number of parameters. Furthermore, we assume that the variance weights are fixed during training, which is empirically verified in Appendix reduces to:
C.3 With this assumption, the objective function
1 | 1(x:0) 2n
A (1) (0)()
L(Q)
(17)
2ncg
is the collection of mean weights at time i, and Gr a. constant that controls the scale of variance weights. By analyzing the objective function (17 we arrive the conclusion that in the infinite-widh limit, probabilistic neural network performs kernel ridge regression, stated in the following theorem:
where (z( (WW(()))
Theorem 4.3. Suppose m 2 poly(n, 1/Au, 1/5,1/E) and the objective function follows the form
17 for any test imput Xte E RRd with probability at least 1 8 over the random initialization, we have
f (Xici ()tett)ee= = = (x, (x) (X. + N
(18)
where & is small ervor term between output function of finäte-width PNN and infinitewiddth PNN.
The detailed proof is provided in Section 5.2 and Appendix B Theorem 4.3 sheds light on the regularization
effect of the KL term in PAC-Bayesian lcarning and provides an explicit expression for the convergence of the output function.
4.3 Generalization analysis
We adopt general and suitable loss function [J to evaluate the PNN's generalization, while using squared loss for training. Theorem 3.2 provides the PAC-Bayesian bound concerning the distribution initialization and after optimization. By combining this result with Theorem 4.3 we can provide a general- ization bound for PAC-Bayesian learning under attra-wide conditions.
Theorem 4.4 (PAC-Baye C-bound with NTK). Suppose that S = {(x R= are i.i.d. samples from a non-degenerate distribution D, and m 2 poly(n, >5 .8).. Then with a probability of at least 1-8 over the random instialization and the training samples, the probabilistic neural network (PNN) trained by gradient descent for T 2 12,,o log )) àterations has RD(BQ) that is bounded as follows:
EE yi (x.) 2B
Int 2n
Ro(BQ) 51
22n
(19)
lat 4F)
(x,) 2B
/2n
The proof can be found in Section B.1 Theorem 4.4 provides a generalization bound for the PAC-Bayesian
learning framework under the ultra-wide condition, combining results from Theorem 3.3 and Theorem 4.3] Note that the generalization ability of kernel ridge regression has been studied in standard neural networks Hu et al. (2020): Nitanda Suzuki (2021): Nonnenmacher et al. (2021). In this work, the bound is analytic and computable, in contrast to the PAC-Bayes bound (5). thus providing a theoretical guarantee for the PA PAC-Bayesian learning approach.
8

---

Published in Transactions on Machine Learning Research (05/2023)
5 Proof Sketch
5.1 Proof of Theorem 4.2
To prove Theorem 4.2 observe that if O₂ and O converge deterministic kernel, then the dynamics of output function admit linear system, which is tractable during evolution. In this paper we focus on @ 0 + ! the gram matrix induced by the weights from L-th layer for simplicity the cost of minor degradation in convergence rate. Before demonstrating the main steps, we introduce the expected neural network model, which is recursively expressed as follows:
x0 = Equ) vm
o (W 1SISL-1; f Ben w(D)g(1-1) vm
Note that this definition is in contrast to the definition as expected empirical loss Neural Network Gaussian Process (NNGP) for PNN (Tee et al. 2018) is defined as follows:
9 in PAC-Bayes. The
K. = Tx
K 1,000
lim K 1
m-+00
where subscript j denote the index of input samples. We aim to show that ( is close to K(D) in large width. In particular, to prove Theorem 4.2 three core steps are:
Aa (K(
Step 1 Show at initialization Ao (0(4) 2
and the required condition on m.
Step 2
Show during training An (L) 2
Aa [
and the required condition on m.
2
Step 3 Show during training the expected empirical loss Rs(Q) has a linear convergence rate.
by analyzing do (O()) initialization through Lemma A.2 and Lemma A.3 For step 2, we construct Lemma A.4 Lemma A.5 and Lemma A.6 to
In proof, mainly focus deriving the condition
demonstrate that Ao (e(*(t)) Z Ao(K (o( This leads to the required condition on m during train. Finally,
we summarize the previous lemmnas and conclude that the expected training error converges at a linear rate through Lemma A.7
(t)
1 d dt
f(x:t) -- T (0,,() + (t,,()+
(y. f(X,
Ao (t) (t) ||o -f(()t)
< (t) -
< - (K (K(E)) ||- - ( 1(x:0)
Note our proof [ramework follows Du al. (2019hss s, especially, we share the same three core steps. However, the main difference is that our network architecture much more complex. Because the probabilistic network contains two sets of parameters, more claborately. For example, in Lemma A.3 and Lemma A.5 we bound the PNTK associated with variance. The detailed proof can be found in Appendix
have two NTKs. As result, the proof requires bounding many terms
5.2 Proof of Theorem
The proof of Theorem 4.3 utilizes an argument of lincarization of the network model in the infinitewwddth limit. This allows us to obtain an ordinary differential equation for output function.
According the linearization rules for infinitely-wicd wide networks (Lee et al. 2019), the output function can be expressed as,
foc 1) (0, (0) + (x) (0x)))(00,))) (0) o,)))).
9

---

Published in Transactions on Machine Learning Research (05/2023)
where (x) Ve,f(x:0), and (x(x) Vo. fx: 0). The next step is to show the difference between fintte-wilth neural network and infinitel-wwdde network:
[((xcc) - (xie) O(E),
where & Emi +
Vnšee with (xtei 0) S Ein and 1 - -xx(4)12 S Eg. The details to complete the Apt
proof are given in Appendix
6 Experiments
As extension of our finding of the PAC-Bayesian bound in Theorem 4.4 to approximate the PAC-Bayosian bound using PNTK, which can be used to select the best hyper-paramcters without the need for additional training and eliminate excessive computation time. Besides, we provide an empirical verification of our theory in Appendix C.2 to further demonstrate the correctness of theoretical analysis.
present training-fres metric
6.1 Experimental setup
In all experiments, we initialize the PNN parameters using the NTK parameterization given in Equation ① The initial mean weights 0₂ are sampled from truncated Gaussian distribution with mean and standard deviation 1, truncated at two standard deviations. To ensure positivity, the initial variance weights O, are set by transforming the specified value of through the formula Ca log(1 + exp(po)).
In Section 6.2 we conduct experiments on the MNIST and CIFAR-10 datasets to demonstrate the effective- ness of our training-free PAC-Baycsian network bound for hyperparameter search undor diffcrent network architectures. We consider both fully connected and convolutional neural networks, with a 3-layer fully connected network with 600 neurons on each layer and 13-layer convolutional architecture with around 10 million learnable parameters. We adopt data-dependent prior, which is practical and popular method Dziugaite et al., 2021 Perez-Ortiz al., 2021 Fortuin 2022), pre-trained on subset of the total training data with empirical risk minimization, and the networks for posterior training are initialized by the weights learned from the prior. To compute the generalization bound, we use Equation (5), with the relevant settings from the work by Pércz-Ortiz et al. (2021). such as confidence 8 for the risk certificate and 150,000 Monte Carlo samples to estimate the risk certilicate.
6.2 Selecting hyperparameters via training-free metric
The PAC-Bayesian learning framework provides competitive performance with non-vacuous generalization bounds. However, the tightness of this generalization bounds heavily depends on the hyperparameters used, such as the proportionality of data used for the prior, the initialization of Po, and the KT. penalty weight (A). While it is worth noting that there is "penalty" associated with ô (see Equation 5) this penalty is typically relatively small compared to the potential performance improvements that can be gained through optimal hyperparameter selection. As these values remain fixed during the training process, selecting optimal hyperparameters a critical and computationally challenging task. Grid search one possible approach, but it can be prohibitively expensive due to the significant computational resources needed to compute the generalization bounds for each combination of hyperparameters.
To this end, we propose approach using "training-free" metric to approximate the generalization bound without performing time-consuming training process based on a generalization bound developed in theorem 4.4 via NTK. As PNTK is constant during training, we use an upper bound Equation 7 with PNTK by as proxy metric, which can be formulated as follows:
( 1/22111
yy T
A
A/
2. yy"
PA = Tr
(20)
2
10

---

Published in Transactions on Machine Learning Research (05/2023)
Correlation between PA baund under FCN with different priors
Correlation between P.4 and bound under FCN with different
Correlation between P.1 and bound
0.35
FCN different Pr
0300
Ivry lcc
leed line
Error Bound
0:333
0:5)
25% aa dkia
disa
Error Bound
0154
1=1at
Error Bound
E3
8.40-
0:41--
(3. xx 18ll
0135
35% axx diia
0.100
0:30
1-5503
0:21
$22)
15.0
11.30
13:00
11:00
11.55
11.0
15.5
21.00
12-
13+ 12
14-10 15-20 1:0 15-30117-10
12.4
PA
Correlation between en P.A. and bound under CNN with different priors
Correlation between P.4 and bound
Correlation between P. and bound
under with different
under CNN with different Ps
0.55
0.50
Trend lne
pake
2.50
Jelly Lma
0.50
Liity line
Errer Bound
0.43
30% pror
Error Bound
Error Bound
0/4--
43%
prior dats
2:40
0:10
13%: cnne data
0.25
Do-DC
0.38
0.25
0.2
0:3-
022
0.0.0
30' 10"
2xi0
3x10 4x
5x:00
PA1
P.A
Figure 1: The first row shows correlation results between the generalization bound and the proportion of prior data, the coefficient of the KL penalty, and Po for the FCN structure on the MNIST dataset. To better visualize the trend, we have implemented a trend line, which represents the overall trend of a set of data points, and a 1-to-1 line, which represents a perfect relationship between two variables where the values on the x-axis are equal to the values on the y-axis. We find high Kendall-tau correlations of 0.89, 0.89, and 0.93. Similar results are obtained in the second row for the CNN structure on the CIFAR10 dataset, where the Kendall-tau correlations are 0.89, 0.83, and 0.57, respectively.
where @ is an empirical NTK measured on a finite-width neural network at initialization, and yy" T is a n X n label similarity matrix, where joint entry is one if two data points have the same label, and zero otherwise. We leave the derivation process in Appendix C. and note that the proposed proxy metric in Equation 220 is similar in spirit to kernel alignment, label similarity metrie, that is widely used in deep active learning (Wang et al. 2022a), model selection for fine-tuning (Deshpande et al.) 2021), and neural architecture search (NAS) (Mok et al. 2022). We should also mention that training-fres free methods for scarching neural architectures are not new, and can be found in NAS (Chen et al. 2021 Deshpande et al. 2021), MAE Random Sampling (Camnro et al.) 2021), pruning at initialization (A (Abdellattah el al. [202]] Further more both Yang et al. (2021) and Immer et al. (2021) focus on hyperparameter (HP) tuning and model selection. In contrast to both methods, which involve training, our approach is training-free. We have included comparison in the updated manuscript. To the best of our knowledge, this is the first training-free free method for selecting hyperparameters in the PAC-Bayesian framework, which we consider to be one of the novelties of this paper.
To demonstrate the computational practicality of this training-free metric, we compute PA using a subset of the data for each class (325 per class for FCN and 75 per class for CNN). Figure [ demonstrates a strong correlation between PAA and the actual generalization bound. Importantly, we show that using PA to yield result that is comparable to the best generalization bound, but with significantly reduced computational time. We compare the performance of three hyperparameter search methods (exhaustive scarch, Bayesian search, and P.A) on two architectures (FCN and CNN) and two datasets (MNIST and CIFAR10) in Table [ Exhaustive search evaluates 648 hyperparameter combinations (9 data-dependent prior with different subsets data for prior training, 9 different values of KL penalty, and different values of Po), while Bayesian search takes only 36 iterations to find the lowest bound, but still requires significant computation time when training a large and complex model. For instance, under the CIFAR10 dataset, it takes 45 hours to train CNN with the bound. In contrast, using P.A saves 83.33
search for hyperparameters
11

---

Published in Transactions on Machine Learning Research (05/2023)
Setup
Risk cert.
Test err.
Computation time (hours)
Date
Method
Network
Single
Total
Exhaustive Search
.0006
.0110
0000
0093
16.92
10961.16
MNIST
Bayesian Search
FCN
.0010
.0212
.0001
0189
.50
18.00
CNN
.0006
.0110
.0004
0093
16.92
609.12
FCN
.0011
.0264
.0002
.0208
.03
19.44
PA
CNN
.0099
.0160
.0088
.1088
.03
19.44
Exhaustive Search
.0051
CNN
.0142
.1969
.0033
1510
45.00
29,160.00
Bayeslan Search
FCN
.1740
.3377
.0051
-4866
1.09
39.24
CIFAR10
CNN
.0142
.1999
.0033
1110
45.00
1,620.00
FCN
.1780
.3190
.0018
1920
.03
19.44
PA
CNN
.0142
.1700
.0024
.1511
19.44
Table The performance of our training-free method, P.A, is compared with two other hyperparameter search methods, exhaustive search and Bayesian search, on two datasets (MNIST and CIFAR1O) and neural network structures (FCN and CNN). The evaluation is based on the risk certificates (cross-entropy groe and accuracy (h) test error (cross-entropy and accuracy acc.), and computation time. The best and second-best values of risk certificates and computation time are highlighted in boldface and underlining, respectively.
times the computational time to find bound that is close to the lowest risk certificate in accuracy. The results show that the PA method achieves comparable performance to the other methods while requiring significantly less computation time.
7 Conclusion and Discussion
In this work, have made several important contributions to the theoretical analysis and practical imple- mentation of deep probabilistic neural networks trained using objectives derived from PAC-Bayes bounds. Specifically, we have shown that the learning dynamics of these networks in an over-paraaeterized setting can be exactly described by the PNTK, and we have confirmed this through empirical investigation. We have also demonstrated that the expected output function trained with a PAC-Bayesian bound converges to the kernel ridge regression, leading an explicit generalization bound. Moreover, we have proposed a training- free method, which can effectively select syper-parameters and lead lower generalization bounds without the excessive computational cost of brute-force grid scarch. Our work opens up several promising directions for future research. One such direction is the study of PAC-Bayesian learning with data-dependent priors using PNTK. We hope that our contributions will help advance the understanding of Deep PAC-Bayesian Learning and implementation of deep probabilistic neural networks and their potential applications.
Acknowledgments
We express our gratitude the anonymous reviewers and Action Editors, whose insightful suggestions significantly enhanced the quality of our paper. Our special thanks go Tianyu Liu, whose constructive conversations during the preliminary stages of this project were invaluable.
12

---

Published in Transactions on Machine Learning Research (05/2023)
References
Mohamed S Abdelfattah, Abhinav Mehrotra, Lukasz Dudziak, and Nicholas D Lane. Zero-cost proxies for lightweight NAS. International Conference Learning Regresenlations, 2021.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for doep learning via over- parameterization. In International Conference on Machine Learning, pp. 242-252 PMLR, 2019.
Amiran Ambroladze, Emilio Parrado-Hernunder, and John Shawe-Taylor. Tighter PAC-Bayes bounds. Ad- vances in newral information processing systems, 19:9, 2007.
Ron Amit and Ron Meir. Meta-learning by adjusting priors based on extended PAC-Bayes theory. In International Conference on Machine Learning, pp. 205-214 PMLR, 2018.
Luc Bégin, Pascal Germain, François Laviolette, and -rancirancis Roy. PAC- CaC-Baycsian thoory for transductive learning. In Arlificial Intelligence and Stalistics, pp. 105-113 PMLR, 2014.
Luc Bégin, Pascal Germain, François Laviolette, and Jean-Francis Roy. PAC-Bayesian bounds based on the Rényi divergence. In Artificial Intelligence and Statistics, pp. PMLR, 2016.
Felix Biggs and Benjamin Guedj. Differentiable PAC-Bayes objectives with partially aggregated neural networks. Entropy, 23(1)):1280, 2021.
Andrés Camero, Hao Wang, Enrique Alba, and Thomas Bäck. Bayesian neural architecture search using training-free performance metric. Applied Soft Compuling, 106:107356, 2021.
Olivier Catoni. PAC-Bayesian supervised classification: the thermodynamics statistical learning. IMS, Beachwood, OH. MR2483528 5544465, 2007.
Wuyang Chen, Xinyu Gong, and Zhangyang Wang. Neural architecture search on imagenet in four GPU hours: A thcoretically inspired perspective. International Conference Learning Representations, 2021.
Aditya Deshpande, Alessandro Achille, Avinash Ravichandran, Hao Li, Luca Zancato, Charless Fowlkes, Rahul Bhotika, Stefano Soatto, and Pietro Perona. A linearized framework and a new benchmark for model selection for fine-tuning. arXiv preprint orXiv:2102. 000001, 2021.
Nan Ding, Xi Chen, Tomer Levinboim, Soravit Changpinyo, and Radu Soricut. PACTran: PAC-Bayesian metrics for estimating the transferability of pretrained models to classification tasks. In Computer Vision- ECCV 2022: 17th European Conference, Tel Aviv, Isruel, Oclober 23-27, 27, 2022, Proceedings, Part XXXIV, pp. 252-2653 252-268. Springer, 2022.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pp. 1675-1685. PMLR, 2019.
Gintare Karolina Dziugaite and Daniel Roy. Entropy-SGD optimizes the prior of PAC-Bayes bound: Generalization properties of Entropy-SGD and data-dependent priors. In Internalional Conference Machine Learning, 1377-1386. PMLR, 2018a.
Gintare Karolina Dziugaite and Daniel Roy. Computing nonvacuous generalization bounds for deep (stochastic) ncural networks with many more parameters than training data. Proceedings of the Thirty- Third Conference on Uncertointy in Artificial Intelligence, UAI 2016, August 11-15, 2017, Sydney, NSW, Australia, 2017.
Gintare Karolina Dziugaite and Daniel M Roy. Data-dependent PAC-Bayes priors via differential privacy. Advances in Newral Information Processing Systems, 31, 2018b.
Gintare Karolina Dziugaite, Kyle Hsu, Wascem Gharbich, Gabriel Arpino, and Daniel Roy. On the role of data in PAC-Bayes bounds. In International Conference on Artificial Intelligence and Statistics, pp. 604 612. PMLR, 2021.
13

---

Published in Transactions on Machine Learning Research (05/2023)
Hamish Flynn, David Reeb, Melih Kandemir, and Jan Peters. PAC-Bayesian lifelong learning for multi- armed bandits. Data Mining and Knowledge Discovery, 36(2):841 -76 2022.
Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware aware minimization for efficiently improving generalization. International Conference on Learaing Representations, 2021.
Vincent Fortuin. Priors in Bayesian deep learning: A review. International Statistical Review, 2022.
Pascal Germain, Alexandre Lacasse, Francois Laviolette, Mario March, and Jean-Francis Roy. Risk bounds for the majority vote: From a PAC-Bayesian analysis to learning algorithm. Journal of Machine Learning Research, 16(26):787- 860, 2015. URL http::///wll..oogpppees///eeeeee http:/ppprr/vvll/eeemmaaaaaaaa html
Pascal Germain, Francis Bach, Alexandre Lacoste, and Simon Lacoste-Julien. PAC-Bayesian theory meets Bayesian inference. Advances in Neural Information Processing Systems, 29, 2016.
Peter D Grünwald and Nishant A Mehta. Fast rates for general unbounded loss functions: From ERM to generalized Bayes J. Mach. Learn. Res., 21:56-1, 2020.
Jiechao Guan and Zhiwu Lu. Fast-rate PAC-Baycsian generalization bounds for Meta-learning. In Interna- tional Conference on Machine Learning, pp. 7948. PMLR, 2022.
Benjamin Guedj- A primer PAC-Bayesian learning. Proceedings of the 2nd congress of the Société Mathématique de France, 2019, pp. 391 414, 2019.
Maxime Haddouche, Benjamin Guedj, Omar Rivasplata, and John Shawe-Taylor. PAC-Bayes unleashed: gencralisation bounds with unbounded losses. Entropy, 23(10):1330, 2021.
Wei Hu, Zhiyuan Li, and Dingli Yu. Simple and effective regularization methods for training on noisily labeled data with generalization guarantee. International Conference on Learning Representations, 2020.
Alexander Immer, Matthias Bauer, Vincent Fortuin, Gunnar Rätsch, and Khan Mohammad Emtiyaz. Scal- able marginal likelihood estimation for model selection in deep learning. In International Conference on Machine Learning, pp. 4563 4573. PMLR, 2021.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural Tangent Kernel: Convergence and generalization in neural networks. Advances in Neural Information Processing Systems, 31, 2018.
Prateek Jain, Purushottam Kar, et al. Non-convex optimization for machine learning. Foundations and Trends@ in Machine Learning, 10(3-4):142-33 2017.
Haotian Ju, Dongyue Li, Ancesh Sharma, and Hongyang R Zhang. Generalization in graph neural networks: Improved PAC-Bayesian bounds on graph diffusion. International Conference on Artificial Intelligence PMLR, 2023.
and Statistics, pp.
Diederik P Kingmaa and Max Welling. Auto-encoding Variational Bayes. orXiv preprint drXiv:1312.6114, 2013.
Durk Kingma, Tim Salimans, and Max Welling. Variational Dropout and the local reparametcrizatioon trick. Advances in Newral Information Processing Systems, 28:2575 2583, 2015.
Alexandre Lacasse, François Laviolette, Mario Marchand, Pascal Germain, and Nicolas Usunier. PAC-Bayes bounds for the risk of the majority vote and the variance of the Gibbs classifier. Advances in Neural Information Processing Systems, 19, 2006.
John Langford and Rich Caruana. (Not) bounding the true error. Advances in Neural Information Processing Systems,
2002.
François Laviolette and Mario Marchand. PAC- BaC-Bayes risk bounds for stochastic averages and majority votes of sample-compressed classifiers. Journal of Machine. Learning Research, 8(7), 2007.
14

---

Published in Transactions on Machine Learning Research (05/2023)
François Laviolette, Mario Marchand, and Yean-Francis Roy. From PAC-Bayes bounds to quadratic programs for majority votes. In Proceedings of International Conference on Machine Learning, pp- 3-59. Citeseer, 2011.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521(7553) 444, 2015.
Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel $ Schoenholz, Jeffrey Pennington, and Jascha Sohl- Dickstein. Deep neural networks as Gaussian processes. International Conference on Learning Represen- tations, 2018.
Jachoon Lec, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl-Dickstein, and Jelfrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. Advances in Newral Information Processing Systems, 32, 2019.
Gaäl Letarte, Pascal Germain, Benjamin Guedj, and François Laviolette. Dichotomize and generalize: PAC- Bayesian binary activated deep neural networks. Aduances in Neural Information Processing Systems, 32, 2019.
Renjie Liao, Raquel Urtasun, and Richard Zemel. A PAC-Bayesian approach to generalization bounds for graph neural networks. International Conference Leorning Representations, 2021.
Ben London. PAC-Bayesian analysis of randomized learning with application to stochastic gradient descent. Advonces in Neural Information Processing Systems, 30, 2017.
David JC MacKay, A practical Bayesian framework for backpropagation networks. Neural Computation, 4 (3):448-477) 472, 1992.
Andreas Maurer. A note the PAC Bayesian theorem. Xrvev preprint cs/0411099, 2004.
David McAllester. PAC-Bayesian model averaging. In Proceedings of the Twelfth Annual Conference on Computational Learning Theory, pp. 164-170, 1999a.
David A McAllester. Some PAC-Bayesian theorems. Machine Learning, 37(3):355--30 1999b.
Jisoo Mok, Byunggook Na, Ji-Hoon Kim, Dongyoon Han, and Sungroh Yoon. Demystifying the neural tangent kernel from a practical perspective: Can it be trusted for neural architecture search without training? In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11861-11870, 2022.
Radford M Neal. Bayesion learning for neural networks, volume 118. Springer Science & Business Media, 2012.
Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M Roy. Information- theoretic generalization bounds for SGLD via data-dependent estimates. Advances Newral Information Processing Systems, 32, 2019.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring generalization in deep learning. Advances in Neural Information Processing Systems, 30, 2017.
Bchnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A PAC-Bayesian approach to spectrally- normalized margin bounds for neural networks. International Conference Learning Represenlations, 2018.
Atsushi Nitanda and Taiji Suzuki. Optimal rates for averaged stochastic gradient descent under neural tangent kernel regime. International Conference on Learning Representations, 2021.
Manuel Nonnenmacher, David Reeb, and Ingo Steinwart. Which minimizer does my neural network converge to? In Machine Learning and Knowledge Discovery in Databases. Research Track: European Conference, ECML PKDD 2021, Bilbao, Spain, September 13-17, 2021, Proceedings, Part III 21, pp. 8 87-102. Springer, 2021.
15

---

Published in Transactions on Machine Learning Research (05/2023)
Kento Nozawa, Pascal Germain, and Benjamin Guedj. PAC-Bayesiag contrastive unsupervised representa- tion learning. In Conference on Uncerlainty in Artificial Intelligence, pp. 21-30. PMLR, 2020.
Maria Perez-Ortiz Omar Rivasplata, Benjamin Guedj, Matthew Gleeson, Jingyu Zhang, John Shawe-Taylorr Miroslaw Bober, and Josef Kittler. Learning PAC-Bayes priors for probabilistic neural networks. arXiv preprinl ar Xiv:2100. 10304, 2021.
María Pérez-Ortiz, Omar Rivasplata, John Shawe-Taylor, and Csaba Szepesvári. Tighter risk certificates for neural networks. The Journal of Machine Learning Research, 22(1):10326 10365, 2021.
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis. In Conference on Learning Theory, pp. 1703. PMLR,
2017.
Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference in deep generative models. In International conference on machine learning, pp. PMLR, 2014.
Omar Rivasplata, Vikram M Tankasali, and Csaba Szepesvari. PAC-Bayes with Backprop. arXiv preprint arXiv:1908.. 07380, 2019.
Jonas Rothfuss, Vincent Fortuin, Martin Josifoski, and Andreas Krause. PACOH: Bayes-optimal meta- learning with PAC-guarantees. In International Conference on Machine Learning, pp. 111669126, PMLR, 2021.
Matthias Seeger.
PAC-Bayesian generalisation error bounds for Gaussian process classification. Journal of machine learning research, 3(Oct):233 269, 2002.
Samuel L Smith and Quoc Lc. A Bayesian perspective on genoralization and stochastic gradient descent. International Conference on Learning Represenlations, 2018.
Donald F Specht. Probabilistic neural networks. Neural Networks, 3(1):109 118, 1990.
Niklas Thiemann, Christian Igel, Olivier Wintenberger, and Yevgeny Seldin. A strongly quasiconvex PAC- Bayesian bound. In International Conference on Algorithmic Learning Theory, pp. 466-492. PMLR, 2017.
Laura Tinsi and Arnak Dalalyan. Risk bounds for aggregated shallow neural networks using Gaussian priors. In Conference on Learning Theory, pp. 227 253. PMLR, 2022.
Haonan Wang, Wei Huang, Ziwei Wu, Hanghang Tong, Andrew J Margenot, and Jingrui He. Deep active learning by leveraging training dynamics. Advances in Neurol Information Processing Systems, 35:25171- 25184, 2022a.
Zifan Wang, Nan Ding, Tomer Levinboim, Xi Chen, and Radu Soricut. Improving robust generalization by direct PAC-Bayesian bound minimization. arXiv preprinl XXiv:221111622, 2022b.
Greg Yang. Edward J Hu, Igor Babuschkin, Szymon Sidor, Xiaodong Liu, David Farhi, Nick Ryder, Jakub Pachocki, Weizhu Chen, and Jianfeng Gao. Tensor programs Tuning large neural networks via zero-shot hyperparameter transfer. Advances in Newral Information Processing Systems, 2021.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107- 115, 2021.
Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P Adams, and Peter Orbanz. Non-vacuous generaliza- tion bounds at the imagenet scale: PAC-Bayesian compression approach. International Conference Learning Representations, 2019.
16

---

Published in Transactions on Machine Learning Research (05/2023)
A Proof of Theorem 4.2
Theorem A.1 (Restatement of Theorem 4.2
Suppose of-) is H-Läpschilz, B-Smooth. Assume a(-)
and its partial derivative
[a(x)
are continuous in ) 0, and the network's width is of
dx
= Ω (200)) max " Ln/0)
6) n
} Then, with probability of at least - over the random 8 x
10g12/6)
initialization, we have,
Rs(Q(t)) exp (
Proof Skelch of Theorem down its dynamics
A.1 To study the behavior of output function under gradient flow, we first write
df (x:t) dt
-y
where O₂ and O are the PNTKs of the PNN. We observe that if O and O, converge a deterministic kernel, then the dynamics of output function admit lincar system, which is tractable during evolution. In this paper we focus on (L) @ + o!_, the gram matrix induced by the weights from I-thh layer for simplicity at the cost of a minor degradation in convergence rate. Before demonstrating the main steps, we introduce the expected neural network model, which is recursively expressed as follows:
x
Eg() vm
( (W I3IS f= Bgan Bgn V
1 w(D)
Note that this definition in inordinate to the the definition as expected empirical loss 9 in PAC-Bayes. Neural Network Gaussian Process (NNGP) for PNN (Lee et al., 2018). which defined as follows:
K = (x(") Tx) 90
K!l = lim K!l 11.00
where subscript i.j denote the index of input samples. We aim to show that ( close to K(!) in large width. In particular, prove Theorem three core steps are:
Step 1 Show at initialization do (0())(0) 2 Aa ( and the required condition on m.
Aa (
Step 2 Show during training Au (e))
2
and the required condition on m.
Step 3 Show during training the expected empirical loss Rs(Q) has a linear convergence rate.
In our proof, mainly focus on deriving the condition on m by analyzing Ao (O))) initialization through Lemma A.2 and Lemma A.3 For step 2, construet Lemma A.4 Lemma A.5 and Lemma A.6 to
Ao( This leads to the required condition on during train. Finally, we summarize all the previous lemmas and conclude that the expected training error converges at linear rate through Lemma A.7
demonstrate that Ao ()))())) >
A.1 Step 1. Bounding least eigenvalue of PNTK initialization
We first study the behavior of tangent kernels with an ultra-wide condition, namely m = poly 1/Ag, 1/8) initialization. Lemmas A.2 and A.3 demonstrate that is large, then the feature of each layer approx- imately normalized, (0) Aa(0) have lower bound the smallest. eigenvalue with high probability.
17

---

Published in Transactions on Machine Learning Research (05/2023)
Lemma A.2 (Initial norm at initialization). Suppose o(.) is H HiLisschitz. If m 52 n
where
6
C - (2) +2H), and the geometric series function gc(1) = Σ C³. Then with probability at least over random initialization, for each I E [L] and E [n], we have:
2 (0)l22 2.
( (n2log(Ln//8)200 then {3(k!!
Lemma A.3 (PNTK at initialization). Suppose a(-) is H Lipsschitz. If 8 with probability at least 1 - 6, we have:
3 Ao (0) 2 do (
4
The proof by induction method. The induction hypothesis is that with probability at least 1 - (1 mz over w-() (O)...., w (0), for every 1 15 S 11-1. 1, we have
Proof of Lemmaa A.
1 go(l")
| (0)122 ++ 90(l')
2 S
S 2,
(L)
2gc (L)
where we define the geometric series function as gc = E/E0 Cth
According the feed-forward expression, we know that
m Ege o ((w (x
(0))
Then we have the expectation:
E | (0)11
Ew,gw (((w() )0 1 (0))²
(c + (1 122
Here have used the fact that (0) ( (ch + (),(1 where w (0)) (0.1).
Because a(-) is H-Lipschitz, for s 2, have
(otwan//a(aa)) - E2 [2
< Ez- 2o]22 o(2)?]
< H|a - 1| 1z |
I Haa - 1| Ez- ( H|(a + 1)2
< Haa - 1
H|a + 1| Ez-N(o,)) 1291)
2
= H|a - 1 (2))(0)) V x
+ H 1))
< 2 c
a 11
where we define C A (c 2 (22
2 + 2H). For the variance we have:
Var
|
(1
[0>113
Var [o(w]! (0) 1 (o))
Ewii_gn [o((w(() + Tx (0))
- m
(c) + 222
[1000) H| T[
x/((0)) 4
E Ew-N
m
< C2
18

---

Published in Transactions on Machine Learning Research (05/2023)
where C2 - (c3 + (o))() + H (4) 64r(0))H + 512H*), and the last inequality used the formula for the first four absolute moments of Gaussian.
Applying Chebyshev's inequality and plugging in our assumption on m, we have with probability 1 8 over W
mZ
{ (0)1 0| S 3gc(L)
Thus with probability - d over w W
x (0) -1 1
|| (0)
Cga - 1)
+ 2g(L)
2gc (L)
goll)
(gc(T)
Using union bounds over E [n]] complete the proof of lemma.
Proof of Lemma (w(). (!) (/ (1)
For weight matrix, decompose it into weight vectors, namely Wil)
..... www Then the derivative of the expected output over the parameters w wa. and w!! can be
(1)
expressed
af(x))
0f(x))
EE
o' d'
((
(1) x
Ow
(1)
V a
(21)
0f(x.)
0f(x)) a
E8g
o (' x (1111)) c E!!
Ōwar
(1)
m
where we have interchanged integration and differentiation over activation o()). According to the definition PNTK for each layer can be expressed as:
4.1
m
m
f(:t)
t():).
(4) f(X:t) T o.r
f(X:t).
w
w
Through a standard calculation we show that:
m
[ x 2() BEco- [o((w(L- Te
1
E By
(22)
4.59
mm
(1)
(0)
>
E gu ml()
[[(((w((-1))
E Beu-
1 [
( -)
(1- (2)
(23)
Lym
Bounding ( The proof is by induction. By analyzing Equation
22 we find that for all pairs of i,
(ll) (0) is the average of m i.dd. random variables, with the expectation:
K (L)
1,00 = en EE-N(O.))
EE Lo + EE) &((-11))
EE
+ g3) T
Then we find the difference between @
t (0) and K (T)
1,000 can be recursively calculated through an induction { (w/) L-1
method. The induction hypothesis that with probability 1-6 over the
Jim1" for any 1 s
L - 1, sississ nn,
1 m ( m
k:00
SO
log(Ln/8)
(24)
m
19

---

Published in Transactions on Machine Learning Research (05/2023)
where C' is constant. We start from the first layer:
E
1 m
Σ
())
=k(()
$1.00
We can apply standar Hoeftding bound and obtain the following concentration inequalities. With probability at least 1 L. we have
1 1 (1) (())
2 1og(4Tn2)3/0)
11,00
J m
m
Now we prove the induction step. In the following, by EE()) mean taking expectation over w(l) (O 2. Suppose that. Equation (24g holds for S < 1 with probability at least - Eo, then we want to show the equations holds for T+1 with probability at least 8/L conditioned on previous layers satisfying Equation 24 Same as the base case, applying concentration inequalities, we have with probability at least T/L,
S log(4Ln2)3/0)
max E K
K
m
Now it remains to bound the differences:
max 1
E
K (1)
11.00
S E 200 (0) + +
+c + 2222)
C - AoolFF
- A Axc
s Ci max ||
K x(!--))| 1bx0
(-(1-))
Ki (1-1) k((-1)
[k(1-1)
K (1-11)
where A
((-1))
1i
and Ax
k(--1)
10.00
K ((-1)
(a) is by property of activation function and
jj
ji,c0
1j.00
Taylor's Theorem, and C1 and C2 are positive constants.
Thus by matrix perturbation theory we have,
|0%0
k
Σ
2 (1) mas
k!!)
s shh
S
12.00
m
Bounding (
(0).
By analyzing Equation
23 the independent random variable g!4) yields:
(L) (0) a.jj
m
E
(
[
x lL ((((((--))
2) ((())
E Ee,
[ (ym ((W(L-111) Tx x3 ( 0.
Therefore, at initialization and during. the (L) (0) keeps zero.
Finally, m = n² (8g()//8)200L)) then with probability at least 1 - 8, Ag(K(()
(L(((L))
0 (0) - K (1)
80
=
o 1 (0)
(L) 66
< 4
2
which completes the proof.
20

---

Published in Transactions on Machine Learning Research (05/2023)
A.2 Step 2. Bounding least eigenvalue of PNTK during training.
The next problem is that PNTKs time-dependent matrices, thus varying during training. To account for this problem, we establish following lemmas stating that if the weights during training are close to their initialization, then the corresponding PNTK is close to their initialization.
Lemma A.4. Suppose for every 1 [T], | (0)1l2 S c,ovmm (1x01 S ca.0 and (1) w (O)]l S vmRR for some conslant Cp,0, Cr,0 and R S cpo- If [.). H H-Lipschilz, then with probability at least - 6, we have
- (x))) S
where Oz = cp.0-
Lemma A.5. Suppose a(-) is H H Lipschitt and smooth.. Suppose for 1 E [L], TWPooll I cuoym,
6..0 - [0)())) S Cz,U- If / (t) w (0) S /mR where R S c9c, (o (L) )n- for some small constont and C2 HC then with probability at least 1 Ö, we have:
(00()) | -00(0)(0((0))
(0)
S 4
Lemma A.6. If Rs(()) S exp(- (L) )t') (0)) holds for 0 < t' S t, we have for any 0 0 t' S
(w)))//--000ll s R' R',
166, Vally f(x.0)l2 for some small constant with (2 1}. (o( /
where R'
Proof of Lemma
A.4
The proof sketch is by induction method.
For 1=0, where the target is input which fixed, thus satisfying the hypothesis. Now suppose the induction hypothesis holds for l' = 0....,, 1, we consider =l
(00 (t) - x (0)
E (W (1) Ego or (W (O((
Eews
(() (ew
m
+ vm
E Egw
(0)) Egno
1
< 1
H
E
w (0) 111 + Egw (t) - Egw (0)
x21 x((- - -x)-((0)
Vm
+ -
(1 (/ (t) Eço w w///o/// |
Vm
1 (c,ovm + R/m) HRC. (1- 1) m
1
11 VmRcs,,
Vm
< <H HC (Cagle, (1 1) 1)
H RCc, (I).
A.5 For simplicity, we define (1) ((--)(()) (1Tx x((--)(()) (1)
Proof of Lemma
21

---

Published in Transactions on Machine Learning Research (05/2023)
Now we bound the distance between O pl and + (L) (0) through the following inequality:
(0)(())
(L) (L) n.sg (0)
p.i (t)
B 11 σ (t)) Bea-n (2),(())
m Σ
1 (z))(0)) E (z))(()))))))
m
13 (2 (1)) ne (2),(1)) - Bea-no (z)) Ega- (z),
771
Bea 1 (zi,r (f)) Bea a (2),r(0)) lgga a (zir(()) Bea na (z))-
31
gg (1) (0) + Bea-n (().(()) - 20.(
m
BH
14, (4,
Vml
SnBHcc2,00c (L)R.
where we have used the result in Lemma
A.4
Therefore we can bound the perturbation:
(1) 6 (0)
o 10 (1)(() 2i (0) ,9Hc, (L)
i.j=1
Recall the bound R2 which is R < cg., (oo (K(
(L) yn
we have the desired result:
(0(0())0((000) )o((
Proof of Lemma
A.6
We first consider the derivative of w and have:
d
W (s)
ds
(ys - f(x;; (1 (
I J! (s) 117(()
m
Aml+1
L-H+1
1
f(x;; 6) |||||||| (|*(0
II
Eguo w(( H1
Sn
Mi
m
where
J(') A diag
..... ((wx)) Tx
mmm
are the derivative matrices induced by the activation function and we have used [s) 1 $ H.. H.
To bound |&x (s))la by Lemma A.4 we get:
x 1) (s)]12 < Hcr,oge, (I)R + Cz.0 S 20z.0-
22

---

Published in Transactions on Machine Learning Research (05/2023)
To bound |Egu ( -
|| W (5) we have:
L II (s) - II (IW/))0)1222 + (/) k=1+1
(009)--w0) (0)1))
1=++1
II (cuoVm + It' Vm) k=1+1
= =cu,, + R8) 1/1111 m h-d
S (2c
L-1 m tu!
Plugging in these two bounds back, we obtain
d ds
n
w
(s)
< 00 Σ
1y: - [(xx))]
F
S4nca,0c v y- -((x:s)
Se Se- po- (K))) ) Vm.
Integrating the derivative of weights, we obtain:
/ - - w= ds'
d (s')
S RR'm
A.3 Setp 3. Towards linear convergence rate of expected empirical loss
Now we process to analyze the convergence rate of expected empirical error. Combined with fact that least eigenvalue of PNTKs and change of weights are bounded during training, the behavior of the loss is traceable. To finalize the proof for Theorem
4.2 we show:
Lemma A.7. If R' < R, we have Rs(t) S exp(- do (K (L) Rs)
Proof of Lemma
A. 7
According to the gradient flow of output function, we have:
df df(x,,)) t) dl
0f(x;;t)
"w di
0f(x:t)
aw!)))
@w
ow!! di
1=1
of(x))
f(xx)
) (of(x)) 0f(xg) ow!! ow!! ))
(y: f(x;))
ow!!!
aw!!
1=1
Σ (y, f(x);tt)(( w.ys + Oo,is).
Then the dynamics of loss can be calculated:
d d Rs(t)= dt f(X:t) 3/2 2
1 y f(x,t) 1)) (t)
dt
+ o,(()) (y -(x,)))
S No (1,(1) + o.((1)) 1 y f(x:,) 1) |
s - (0) o 9 (1) | - -f(x;t) 1
S - (K(L) |y f(x: 1)
2
23

---

Published in Transactions on Machine Learning Research (05/2023)
where we have used the condition R' < R and do A (1) + O (0) Ao(O O, (1)). Therefore, we have the desired result:
Rs(t) & (t) R())
Finally, provide bound for Rs(Q(0)):
> - x Σ
(vt
= Σ (1 (1)) 0
==1
Recall that in Lemma A.5 and Lemma A.6
R cge, (L) do (K m R' 16c,, (cx) Vnlly foly-f(x,nn f(x,0)lz
do No(K? (L) V
Thus R' < R yields = ( n'20(4) X(
B Proof of Theorem 4.3
Theorem B.1 (Restatement of Theorem 4.3
Suppose m 2 poly(n, 1/Ao, 1/8,1/8) and the objective func-
tion follows the form 17), for any test input Xte R with probability at least 1 8 over the random initialization, have
+ = - (x, (X,
(25)
where E small ervor term between oulpuul function of finile-width PNN and inforile-wide widhh PNN.
To proceed the proof, we first establish the result of kernel ridge regression in the infinite-wddth limit, and then bound the perturbation on the predict. According the linearization rules for infinitely-wick networks (Lee et al., 2019), the output function can be expressed as,
Proof of Theorem B.
-x,x)))),xxx) - (x))) - (,) + &. (x) (x,) - (0),
where (x) Va, fx: 0), and (x)= Vo, f(x; 0). Recall that we assume that Oz does not change during training, then the KL divergence reduces to
KL 2nd
00,(t) (0)
Then the gradient flow equation for 0₂ becomes,
(t) OL()) (0 + A//21) (1)) + (X) (f)) -x) (t)
dt
which is an ordinary differential equation, and the solution is,
0, (t) (X) X, + (0--00))00000000000000-00-
Plug this result into the linearization of expected output function, we have,
(x:t) = e (x, XX 1/C31) -(1))-((I-0 (I- (X-x00000X
Then we take the time to be infinity and have:
fx0(x)]==> = (x, +
24

---

Published in Transactions on Machine Learning Research (05/2023)
The next step is to show the difference between finite-width neural network and infinitelywwide network:
[((xt)) pr (x(ee)) < ((E),
where & = Emit + Vnée with | [x(xx))) I Eiit and 110 (utlll I Eg. Note the expression of output A
function in the shhnite-wwdthh limit can be rewritten (xte ((xxe) ( and the solution to this equation can be further written as the result of applying gradient flow on the following kernel ridge regression problem
a Σ 2n
min /
|0(x;)
g- x; 1 A 11
with initialization ((0) = We use (()) denote this parameter at time trained by gradient flow and ooo (Xte, B(t)) be the predictor for Xte at time With these notations, we rewrite
(xio)= f df(B(t). xte) dl,
===
dt
where we have used the fact that the initial prediction is 0. We thus can analyze the difference between the PNN predictor and indinite-width PNN predictor via this integral form as follows:
f f (xte)
112
< (10, Xer)
1
+
100
[d((O((t),xcc)
(f() Xtc)
di
2
dt
dt
t=
[ xxx)
11a
+
1
Xtee X) (ff - X;t) (f(t) - X))dtt ( (xte:
1=0
- 2/22
(Ø (xtc)
TB(()= (xie))((()
- 0 (Xtci 1) ((t)dtt
1=0
12
1
(Xte: X;t) θ 8 (xte X)) T (f(t)- XX)dt + L (xx(Xtett) - (xxe)) B(t)dt
EEni +
( (
1150
0 (Xee: X) T)((fo0 ((t) 1/22
(Ø (xx)) T (B(1) 02 (t))dt
|1(() >11- dt
<Enit +
max OS1500
10
(Xtex X:t) -p (xte: X)
|10 # (Xte: X)1l2 /
x
X/e2 max 051500
( 1) (xte) 11 119912d1
+
max 051500
[1((1) f (1)
| 1=0
1=0
2/ max 0S1500
|1 (xte)
[|3(t) (t)ll
1=0
Einit + 122 + Jz.
where (1) = (l) - (0). For the second term 12, we know that (I((1) - y11 +3110,13 s exp(=(Aoo +
f/2 y :
Therefore, we can bound:
[l((t) -1l (t)l,t
<
exp(-(An + X/2 yl22)dt
Vn
=0
Au X/c2
25

---

Published in Transactions on Machine Learning Research (05/2023)
As a result, we have 1 0 AotA/eT To bound 13, we have
[1(()) (0)2 + A/2 - 02112dt
I1((1) y1/2 + 1/62 0 + So (1 (1)(11)X)))) -X|12 + A/6 11
Vn
do + 2/c
As a result, we have 1 =0
Lastly, we put things together and get
Au
1f(t) f (0) (1) 10 Emit + Eo Vn.
do +
B.1 Proof of Theorem 4.4
Proof of Theorem 44 Our proof is based on a characterization of the margin M& and Mg via the explicit
solution found in Theorem
a M V: Rnm@h(xx)) = Σ 71 i=1
fo (xx))
1=1
M
jo (xx))(((x)))
11
Then by Theorem 3.3
we have:
1 Σ foo (x+) 2B
v/2n
RD(Bq)= 51
1== Σ (xx, fro
2B2
In( 34
V2n
C Appendix for Experiments
This section contains additional experimental results and derivation process for proxy. Training is performed with a server with CPU with 5,120 cores, and a 32 GB Nvidia Quadro V100.
C.1 Derivation of proxy
Our derivation based on characterization of the empirical error and KL divergence term via the explicit
solution found in Theorem 4.3 The objective function consists of two terms, one is the empirical error,
and another KL divergence.
(i) We first bound the empirical error (f oo) y1) with
following inequality,
(xx = 20) -0)-110 -
+ XXX -ty
2
| (X +
-1y 1/08
2
y
26

---

Published in Transactions on Machine Learning Research (05/2023)
Then we bound the error term follows:
Σ
(xi) v11
(x:),
e (xi), 31) - Eluis vi)
1=1
1=1
(xi) - -ya
71
Σ
foo (x:)
1=1
( X, X) +
2d/
72
(ii) The next step is to calculate the KL divergence. According to the solution of differential equation Theorem B.1 we have:
- - = (xxx
Therefore, the KL divergence is,
KL = 1/6
XX)
y (0, + 1/2
Finally, by Equation
we have
Rs(Q)= - KL (L() (())
yT ( (X, X)
+
y
y ( (X, (x, +
+
+
n2
nc?
c
C.2 Validation of theoretical results
We first provide empirical support showing that the training dynamics of wide probabilistic neural networks using the training objective derived from PAC-Bayes bound are captured by PNTK, which validates Lemma A.6
Consider a three hidden layer ReLU fully-connected network of the training objective derived from the PAC- Bayesian lambda bound in Equation (5), using an ordinary MSE function as loss. The neural network is trained with a full-batch gradient descent using learning rates equal to one on a fixed subset of MNIST (ID)= = 128) of ten classifications. A random initialized prior with no connection to data is used since is in line with our thcoretical setting and we only intend to observe the change in parameters rather than the performance of the actual bound.
After T = 2 steps of gradient descent updates from different random initialization, plot the changes of ((()) and w of contt//utttttiit hiidden layer with respect to width m for each layer on Figure We observe that the relative Frobenius norm change in the input/output layer's weights scales as 1/ym while the hidden layers' weight scales is 1/m during the training, which verifies Lemma A.6
C.3 Comparison of gradient norm with respect mean weight and variance weight
We then conduct an experiment to compare the gradient of norm with respect o and 0,. The result is shown in Figure 3 We can see that the gradient norm of Ve, fxx is much larger than that of Ve. fxx). which implies that. 0, is effectively fixed during gradient descent training.
27

---

Published in Transactions on Machine Learning Research (05/2023)
(t) W /
- wWW0OO--O0000///00000000
2
2
2
21
2
13
2111
25
2-13
(input)
2
(input)
2
Layer
Layer
2
Layer
Layer
(output)
2 2
(output)
2 2
1im
1im
1A
2
1
2
24
2
26
27
28
29
200
211
24
2
26
27
28
2
20
2
m
Figure 2: Relative Frobenius norm change in / and respectively during training with MSE loss which is derived from the classic PAC-Bayesian bound, where m is the width of the network.
[V
vs
IVo.f
35
30
PM
28.
54
29. 2
25
21. 93
20
15
10
5
0.
65
0.83
0.
0
t=0
t=10
t=100
Figure 3: Comparison between the norm of derivative of output to mean and variance weights
Kendall-aaun 70
0.09
Error Bound
0.07
0.06
0.05
0.04
500
1000
1500
PA
Figure 4: Correlation between aggregated proxy PAA and generalization bound.
C.4 Correlation between generalization bound proxy metric and generalization bound
In Figure 1 we observe a positive and significant correlation between P.A and generalization bound held among different values of selected hyperparameter while fixing other hyperparameters. Furthermore, we provide a Figure presentin the correlation for aggregated values of Po and X, under the circumstance where 50% data is used for prior training. We can clearly see that lower P.A corresponds the lower bound, with strong positive Kendall-tau correlation of 0.7.
28

---

Published in Transactions on Machine Learning Research (05/2023)
C.5 Grid search
For selecting hyperparanettess, we conduct grid search over po: percent of prior data, and KL penalty X. Notably, we do grid sweep over the data for prior training with different proportion in [0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9] since 0.2 the minimum proportion required for obtaining a reasonably lower value generalization bound (Dziugaite et al., 2021). For the rest, we run over Po at value [0.03, 0.05, 0.07, 0.09, 0.1, 0.3, 0.5, 0.7] for FCN ((0.05, 0.07, 0.09, 0.1, 0.3, 0.5, 0.7, 0.9] for CNN) and KI. penalty [0.0001, 0.0005, 0.001, 0.005, 0.01, 0.05, 0.1, 0.5, 1] for both structures.
C.6 Scability of Proxy
In our proposed method for hyperparameter selection, we choose a subset data for computing NTK balance computational efficiency and accuracy. To investigate the scalability of P.A, we carry additional experiments to explore the relationship between the error bound and PA concerning the number of samples per class. The experimental results, depicted in Figure demonstrate that when the size of the data subset surpasses certain threshold (125 samples per class), the performance of P.A with different hyperparameters stabilizes.
29

---

Published in Transactions on Machine Learning Research (05/2023)
Correlation between PAA and bound under FCN with different A samples per class
Correlation between PA and bound under FCN with different
Correlation between PAA and bound under FCN with different
Correlation between PA and bound under FCN with different A
samples per
samples per
325 samples per
0.80
0305
Teedine
0.80
une
130
0.00
Uniy
0000
ume
0995
396 pto
0835
15% 010
0455
30% piar eda
0455
Error Bound
0:00
Efror Bound
0.800
Error Bound
0.006
65%
Bound
0.00
85% p0or (ats
15% your Aita
85% prar ddta
30% uner dids
0.43
0.445
00445
0006
0.40
0.04
00040
0008
0005
6088
0008
365
P.A
PAA
1.A
Correlation between PA and bound under FCN with different A samples per class
Correlation between P.A and bound under FCN with different A samples per
Correlation between P.A and bound under FCN with different.
Correlation between PA and bound under FCN with different A
225 samples per
325 samples per class
0.25
0335
0325
0201
180g Une
only
Umby
Use
Unay
1-5000
A-Sute*
A=
Error Bound
0100
100"
Error Bound
0:10
2-5-177
1-2115"
Error Bound
61350
A- 2-300
0150-
Ax500"
2-2x117
3-3x00"
0.000
0375
8.75
cors
0325
PA
PAA
PAA
PAA
Correlation between P.4 and bound under FCN with different Pe 25 samples per class
Correlation between P.4 and bound under FCN with different Po
Correlation between PA and bound under FCN with different Pe
Correlation between PA and bound under FCN with different Po
125 samples per
225 samples per class
325 samples per class
Tend
Trectine
012
012
A-1033
A-113
A--33
A--055
A--855
A--005
p--035
030
A-+000
2--031
033
A--227
018
P--007
A-0009
033
pV-029
PV-037
Error Bound
J-103
Error Bound
Error Bound
P-+01
Bound
pV-03
0.2
1008
600
0.20
60c
x1 13x30 115x2P 13x19
135x22' 33x 10--11152--1111--222222
12x32'
13x
14"127
15x
12x32
13x12
14417
15+17 15x2 13x32
PA
P.4
PA
PA
Figure 5: The correlation between P.A and error bound concerning the data size.
30


Reviews:
[{"review_id": "z28jjOtHIx", "reviewer": "Reviewer_4k6L", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nI like the swift move from risk bounds to zero shot hyperparameter tuning, which seems like a clear and compelling practical use case for these types of bounds.\n\nThe zero shot hyperparameter tuning experiments look very strong and convincing.\n\nWeaknesses: \n\nIt feels like there’s a bunch of related work that’s missing and should be compared to (maybe this is due to the area being reasonably crowded):\n\nZero shot hyperparameter tuning from the NTK: “Tensor Programs V: …”, Yang et al, ‘22\n\nModel selection from a Bayesian variant of the NTK: “Scalable Marginal Likelihood Estimation for Model Selection … “ Immer et al, ‘21\n\nPAC Bayesian generalization bounds:\n\nDzugaite and Roy ’17 analyze and train a very similar objective to yours, except that they compute instead the average over the training set with random samples, instead of your sampled mean. This enables both training and blind hyperparameter tuning using their bound. Maybe the authors could compare with their approach?\n\nMy understanding is that Eq 7 comes very close to their training objectives, and to reparameterization VI training objectives as well. However, you train on loss(E(net(data)), while the VI training objectives are E(loss(net(data)) and Dzugaite and Roy train on a single sample.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "sorry for the late review, but here it is.\n\nThe authors analyze a probabilistic training objective similar to (generalized) mean field variational inference objectives with gradient flow analysis, finding that there’s two separate neural tangent kernels (one for the mean parameters and one for the variance parameters) required to be considered for the analysis. However, the variance term washes out in the analysis of the mean function. Due to the training objective, the authors immediately get PAC-Bayesian generalization and risk bounds for the infinite neural networks that they analyze. They then are able to do some zero-shot hyperparameter tuning with these bounds.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Major: What is the connection with the broader “infinite width Bayesian NNs are Gaussian Processes?” literature. It seems like the analysis in Novak et al, ’19 (“Bayesian Deep convolutional networks with many channels…”) is more “exact” in the sense that the limiting function is derived for any Bayesian neural network under these conditions, not specifically under your PAC Bayesian objective.\n\nPerhaps more similarly, both Yang et al, and Immer et al (cited above) do zero-shot hyperparameter tuning with variants of the tangent kernel derived here. Specifically, Yang et al even study scaling laws, enabling the transfer of hyperparmeters and architectures from small models to much larger ones. Can such an analysis be done with your work?\n\nMedium: What is the connection with compressibility bounds for generalization (“PAC Bayes Compression bounds so tight they can explain generalization,” Lotfi et al, ’22; “non vacuous generalization bounds at the imagenet scale…,” Zhou et al, ’19) in the PAC Bayesian framework? They seem to be quite useful now, but your analysis, from what I can tell, uses the standard PAC Bayesian bounds and doesn’t rely on compressibility of the network.\n\nMinor: plot bottom row, right two figures on a log scale since the points are all bunch up. Maybe also plot the trend line and the dashed ‘1-1’ line.\n\nminor: eq 2: is W_\\sigma^{(l)} a vector or a matrix. Make this more clear please\n\nminor: eq 10, why is setting the learning rate = 1 fine?\n\nMinor: eq 16: I believe that \\lambda is \\lambda_0?\n\nMinor: thm 4.3: doesn’t this just become standard Gaussian process PAC Bayesian generalization analysis at this point, as this is a standard GP now. I believe this is analogous to reference Nitanda and Suzuki, ’20.\n", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "LIMpW7Pqej", "reviewer": "Reviewer_c5C9", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths*\n\n1. The paper tackles an interesting problem of analysing the behaviour of PAC-Bayesian trained NNs in the wide NN setting through the NTK.\n2. The authors use their theory to derive a practical way to automate the hyperparameter selection of NNs.\n3. The paper is reasonably well written and clear.\n\n*Weaknesses*\n\n1. It's not clear to me that the authors have shown that the NTK kernel and training dynamics limit *exists* for the PAC-Bayesian setting when the variance parameters exist in addition to the mean parameters. I think this is potentially an interesting area, but this seems different from existing NTK works, and would needs more of a rigorous treatment to be convincing to me. For example, the authors should write out explicitly the analytic forms of $\\Theta_{\\mu}$ and $\\Theta_{\\sigma}$ over different layers in an MLP, especially $\\Theta_{\\sigma}$ which is new as far as I can tell.\n2. I have some confusions regarding the theoretical contributions, which seem to be somewhat simplified, to the extent that it's not clear the extent to which the contributions are providing new interesting insights into the NTK regime behaviour of PAC-Bayesian NNs. For example:\na. it is not clear to me why theorem 4.2 is stated in terms of the NNGP not the NTK; the NNGP is a kernel that is obtained via training the last layer *only*, and treats the hidden layers solely as data-independent feature extractors.\nb. the variance parameters are treated as fixed in theorem 4.3, which I assume is for simplicity, but also reduces the analysis down to standard Kernel RR with mean parameter NTK (which is very similar to the non-probabilistic case).\nc. On this note, the function mean at initialisation is assumed to be zero in theorem 4.3 (which is important to obtain kernel RR, rather than a random GP as in Lee et al 2019, or He et al 2020 [https://arxiv.org/abs/2007.05864](https://arxiv.org/abs/2007.05864)).\nd. It would also be good to have some explanation why in Appendix A the authors consider the expected NN averaged over the PAC-Bayes randomness (e.g. in equation 19). Presumably this isn't what is being used in practice?\n\n2. In the experiments, it would be good to have the actual test accuracies and cross entropies in Table 1, in order to determine the tightness of the proposed bounds.\n3. The Scability of the proposed \"PAC-Bayesian bound score\" for hyperparameter selection seems poor to me, due to the vector-Matrix inverse-vector products in equation 18. Can the authors comment on how best to compute this efficiently, and/or if this should be a concern? For example, can the authors provide experiments that use different amounts of the training data to compute the bounds for hparam selection, and assess if one can get away with using a small fraction of the training data to do so?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the gradient descent dynamics of PAC-Bayesian learning in wide neural networks using the NTK framework. The authors identify a modified NTK, called Probabilistic NTK (PNTK), which accounts for the probabilistic nature of NNs in the PAC-Bayesian framework, as well as the fact that such settings have two sets of parameters: one for parameter mean and one for variances. Using this, the authors derive theoretical contributions including convergence analysis (which is shown to be kernel ridge regression using PNTK *if* one assumes that variance parameters are fixed), as well as generalisation analysis for probabilistic NNs. Finally, the authors use their bounds to suggest a method for automatic hyperparameter selection without needing to train, and demonstrate empirically the efficacy of their method compared to some standard baselines for hyperparameter selection.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "In addition to addressing/commenting on my above weaknesses, I'd appreciate it if the authors can clarify the following clarity concerns I have:\n\n1. What is a $\\textit{C}$-bound? This is introduced without explanation.\n2. I don't think the name \"Pac-Bayes bound score\", for the hparam selection method, is introduced until the conclusion. I would either not include it or introduce earlier.\n3. I would put section 2 somewhere after section 3, because it introduces things like prior and posterior in PAC-Bayesian setting which someone without previous knowledge would have access to.\n4. In section 3.2, does the loss function need to be bounded in order for Theorem 3.1 to apply? As currently written, this isn't clear (though the binary KL divergence doesn't make sense if loss isn't in [0,1]).", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "b4Wm9EMjQi", "reviewer": "Reviewer_Q6fj", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I have some concerns regarding the definitions made in the preliminaries (see below), which for now determined my negative response to the *Claims And Evidence* question below.\n\n*Randomized predictor vs average predictor*\n\nMy main concern / confusion is around the (empirical) risk of a randomized predictor, versus the risk of the average predictor: both seem to be used, and potentially a bound on one quantity is incorrectly applied to a PAC-Bayes bound, which uses another quantity (at least without an explanation).\n\nIn 3.2, the authors denote the \"expected population risk\" (what is often referred to as Gibbs risk) by R_D(Q), defined as the expectation of risk_D(h) when h~Q. Similarly, they denote the expected empirical risk by R_S(Q). The main theoretical results is stated in terms of the Gibbs Risk R_D(Q), but in equation (8), they state that R_S(Q) is equal to the risk of the average predictor , risk (E(h)). By Jensen's, I would expect equation (8) to be expressing a lower bound on the Gibbs empirical risk, not an equality.\n\nIn fact, risk are defined in terms of expected losses, but we arrive at (8) without any mention of the underlying loss, which only suppose is 1/2 squared error. It would be nice for readers to not have to intuit the origins of the equality given in (8). One concern is that a lower bound is being used and combined with an upper bound, which in general yields no bound at all. I'm assuming there's a misunderstanding, but it is critical to address this.\n\n*Proof techniques and results relationship to previous work*\n\nSimilar results for deterministic networks exist in the literature. Intuitively, it seems like those results would straightforwardly extend to probabilistic networks when the average output is being studied (instead of a randomized predictor, see my comment above). \n\nHow do the proofs presented in this paper (e.g., for Thm 4.2) relate to those for NTK in deterministic networks? If they are basically the same, or could be made the same, then the authors should cite appropriate work that their proofs are following. If not, then I think it would be worth highlighting what the obstacles are and why studying the average output of a randomized network is more challenging or different. \n\nIn particular, the results in Theorem 4.3 (since only the mean parameter is being updated, as in Eq 14) seem to be a fairly straightforward consequence of standard NTK results (and the existing relationship between PAC-Bayes with Gaussian priors/posteriors and ridge regression). If not, what are the key differences? \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors study training and generalization of infinite width deep neural networks \"trained by\" gradient descent, by minimizing an objective that is based on a PAC-Bayes bound with Gaussian priors/posteriors. They extend existing theoretical results for infinite width neural networks to probabilistic networks, where the weights are being sampled from a Gaussian, and the mean of the Gaussian is being trained. They then characterize convergence of the appropriate Gram matrix, as well as generalization of the average output of this randomized predictor. Some empirical results and evaluation of the bound is presented. The authors also propose a way to select hyperparameters (effectively adjusting the amount of regularization coming from the PAC-Bayes bound).", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. I would appreciate the authors clearing up the confusion I see between Gibbs risk and risk of average predictor at equation (8). Please, edit the text to carefully deal with these quantities, highlighting the differences and using different notation to capture these differences ( see my comment under weaknesses). The loss being considered should be specified before any derivation based on it. If (8) requires derivation, it should be given. Known bounds relate average predictor risk to Gibbs risk (a factor of 2 suffices; see work on PAC-Bayes \"C-bounds\" for more sophisticated approaches).\n\n2. The results and proofs appear to be very connected to those existing in the literature for deterministic networks (see my comment above under weaknesses), and thus including a discussion around this seems prudent.\n\n\n3. The second bullet point in the contributions seems to suggest that the bound is independent of the posterior. While explicitly it is true, isn’t the bound valid under a Gaussian posterior, where only the mean parameter is being trained? As written, the contribution statement seems to be at the very least confusing, but potentially either inaccurate or misleading.\n\n4. Based on the paragraph above 3.2, it looks like the covariance matrix is restricted to be diagonal, or even isotropic? It might be worth adding a comment here for the readers. In particular, late in the experiment section, the authors note that they only train the mean and not the variance, and show some empirical results to justify (Section C.2). However, such results may be highly affected by the fact that the authors do not model the correlations between the weights. Also, just because the gradients of the variance parameters are much smaller compared to mean parameter updates, it does not mean that the changes in the variance are insignificant. Perhaps adjusting the learning rate for variance parameters or applying other learning tricks could allow the variance to be learnt more effectively. Could the authors comment more on this observation and provide further justification for their choice to only train the mean parameters? \n\n5. In Equation 9: it seems like the learning rate is missing. In particular, I believe the authors use gradient flow dynamics to replace \\dee theta / \\dee t with a gradient update, but this part requires the learning rate to appear. I suppose it does not really matter since no discretization of the dynamics is going on, but it would be good to clarify. \n\n6. In Section 5.1, the authors mention that they focus on the kernel associated to the final layer, and say “at the cost of a minor degradation in convergence rates”. I did not get this comment and do not obviously see how the convergence rate is affected by dropping the rest of the terms, could the authors expand?\n\nMinor comments and citation edits:\n - In the introduction, 1st paragraph, seems like it would be natural to cite Sharpness Aware Minimization (SAM) work;\n - Top of page 2 “...making PAC-Bayes learning an essential tool..” seems like an overstatement. In particular, I do not think that PAC-Bayes is standard practice in training best-performing models.\n - Dziugaite et al. 2020 work focuses on showing that distribution and data-dependent priors is in some cases are necessary to get tight generalization guarantees and perform better than just distribution-dependent priors. This work seems to be mis-cited (top of page 1, and missing in Section 6.1 where data-dependent prior is being justified).\n - Related work first paragraph, along the Haddouche et al 2021 citation, i believe one should cite Germain et al. 2016 paper (PAC-Bayesian theory meets Bayesian inference) where they provide bounds for sub-gamma loss functions.\n - Page 4, just above equation two, the authors say “To ensure that the weights follow a Gaussian distribution during gradient descent training, we use the re-parameterization trick”. While I understand what the authors meant, this initially confused me. I think it is worth highlighting instead that _based on_ the re-parameterization, the weights are being modeled as Gaussian, with tranable mean and variance parameters.\n - While the meaning of X in Eq 8 is obvious, I believe it may be not defined. \n - Typo: first paragraph in Sec 6 (a empirical)\n - 6.2 first paragraph on grid search, might be worth noting that there is a “penalty” associated with hyperparameter search, though relatively small. \n - Typo: 5.3 first paragraph, “consists two terms”\n", "broader_impact_concerns": "No concerns. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "qSYFFrc6cf", "reviewer": "Reviewer_PSU9", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": " * This is to my knowledge the first attempt to analyze probabilistic neural networks using the PAC-Bayesian theory and from a Neural Tangent Kernel point of view. Hence the content is novel.\n\n * Providing generalization guarantees for deep neural networks is an important and interesting problem with significant potential to impact real-world applications as safety-critical use cases.\n\n * The paper exhibits an excellent scientific writing practice. It is easy and enjoyable to read and technically precise. It also gives insightful verbal descriptions of the presented theoretical results, which facilitates the task of the reader.\n\n * One minor weakness is that the paper does not allocate much effort to clarifying the practical implications of the proposed solution. It sounds intuitively nice to have training-free risk certificates for a model but the text will be improved if the paper gives one or two down-to-earth examples about what one can do with them in real life.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper reports a PAC-Bayesian analysis for deep neural networks with randomized weights. Starting from the well-established generic PAC-Bayesian bounds, the paper develops a theoretical analysis of the convergence behavior, the characteristics of the resulting function approximation as width goes infinity, and the resulting generalization bound.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "There may be a typo on the r.h.s. of Eq (4). Should there really be a multiplicative empirical risk term there\n\nWhile the PAC Bayes aspect is a clear novelty, generalization behavior of NTKs has been previously analyzed. The paper will be more complete if some of this body of work is cited and the advantages of the PAC-Bayesian framework on the state of the art there are clarified. For instance:\n\nM. Nonnenmacher et al., Which Minimizer Does My Neural Network Converge To?, ECML-PKDD, 2021\n\n---\nAfter rebuttal: The author response addressed my concerns satisfactorily.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Dear authors,
After reading the reviews, (detailed -- thanks!) rebuttals and discussion, I am happy to recommend acceptance of your submission. I believe you make a significant contribution to theoretical analysis of deep learning through PAC-Bayes -- thank you for revising your work along the reviewers' suggestions and congratulations on a fine piece of work.
I am happy with most of the manuscript but I have however a request before the article gets published: the bibliography is a bit sloppy and requires some careful editing. Please capitalise properly all words that require it ('PAC' instead of 'pac', etc.) and do make sure your citations are accurate: I came across a few papers listed as arXiv preprint when they are in fact long published.
Best,
Benjamin
Decision: Accept (poster)