Smoothness-Based Derandomization of PAC-Bayes Bounds

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Smoothness-Based Derandomization of PAC-Bayes Bounds

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

arXiv:2606.19105v1 [cs.LG] 17 Jun 2026

Smoothness-Based Derandomization of PAC-Bayes Bounds Alexandre Lemire Paquin Brahim Chaib-Draa Philippe Giguère Department of Computer Science and Software Engineering Université Laval, Québec, Canada [email protected] [email protected] [email protected] June 2026

Abstract We study PAC-Bayes derandomization for smooth loss functions. Our goal is to obtain generalization bounds that hold with high probability for deterministic predictors by exploiting smoothness properties of both the loss and the predictor class. We show that passing from the Gibbs predictor to the deterministic predictor at the posterior mean has a precise cost, given by the generalization gap of the Jensen gap class. We control this class through its Rademacher complexity, leading to bounds for deterministic predictors that involve flatness quantities expressed in terms of parameter Jacobians and Hessians of the score map. The framework applies to both bounded and unbounded smooth loss functions, and we specialize the results to linear predictors and smooth neural networks. Finally, the Jacobian and Hessian quantities appearing in the theory motivate a practical regularizer. For BatchNorm networks, we compute this regularizer with respect to effective BatchNorm weights obtained by folding the BatchNorm transformation into the adjacent affine weights. Experiments on CIFAR-10 illustrate the behavior of this regularizer under different batch sizes.

Contents 1

Introduction

Motivation and relation to existing derandomization approaches

Generalization bounds for unbounded loss functions from the PAC-Bayes framework

Specialization of the results to linear hypothesis classes

Generalization bounds for bounded loss functions from the PAC-Bayes framework

Uniform upper bounds for the Jensen gap for smooth neural networks

Generalization bound for the Jensen gap from Rademacher complexity

Bound comparisons for linear classifiers

9 A Regularizer Inspired by Our Theory for Batch-Normalized Networks

10 Conclusion

Introduction

Flatness measures defined through parameter perturbations are among the more promising predictors of the generalization gap in large-scale empirical studies on neural networks [Jiang et al., 2020, Dziugaite et al., 2020]. PAC-Bayes theory provides a natural framework for deriving high-probability generalization bounds involving such measures [McAllester, 1998, 1999, Seeger, 2002, Catoni, 2007, Haddouche et al., 2025]. However, standard PAC-Bayes bounds apply to stochastic Gibbs predictors, whereas a single deterministic predictor is often used in practice. Derandomization of PAC-Bayes bounds provides a rigorous bridge between guarantees for stochastic classifiers and guarantees for deterministic predictors [Langford and Shawe-Taylor, 2002, Viallard et al., 2021, Neyshabur et al., 2018, Banerjee et al., 2020, Biggs and Guedj, 2022]. Existing results connect ideas involving classification margins and flatness through an analysis of parameter perturbations. While this provides an important connection, it ties the resulting guarantees to margin losses, which cannot be directly optimized using gradient-based methods. In this work, we consider a new general strategy for PAC-Bayes derandomization that relies on smoothness assumptions. This strategy yields bounds involving flatness measures that apply directly to deterministic predictors, for both classification and regression with bounded or unbounded smooth loss functions. We show that one can pass from a PAC-Bayes bound for the stochastic Gibbs predictor to a bound for the deterministic predictor at the posterior mean by paying an additional penalty term. This penalty is the generalization gap of the Jensen gap of the loss class; see Theorem 3.3 and Corollary 3.5. The Jensen gap of a function f with respect to a posterior Q is the difference f (Ew∼Q [w]) − Ew∼Q f (w); see Definition 3.6. This penalty therefore identifies the cost of replacing the Gibbs classifier by its posterior mean. The remaining task is to control this Jensen gap class uniformly with high probability. For this purpose, we use a Talagrand comparison inequality for sub-Gaussian processes to upper bound its Rademacher complexity; see Section 7. The resulting bounds explicitly depend on smoothness and flatness properties of both the loss and the hypothesis class. In particular, Theorem 3.7 gives the general result in the unbounded case, while Theorem 4.1 gives its specialization to linear predictors. The main contributions of this work are as follows. 1. We obtain uniform high-probability control of the Jensen gap class by bounding its Rademacher complexity (Corollary 7.6, Proposition 7.9, and Proposition 7.10). 2. We derive general derandomized PAC-Bayes bounds for unbounded and bounded smooth loss functions. The unbounded case is treated in Section 3, with the main general result stated in Theorem 3.7. The bounded case is treated separately in Section 5, leading in particular to Theorem 5.1 and to the inverse-kl bound of Theorem 5.3. 3. We specialize the theory to linear predictors. In the unbounded case, Theorem 4.1 gives the corresponding linear bound, while Theorem 5.2 gives the analogue for bounded losses. A key step in the unbounded analysis is the evaluation of the PAC-Bayes complexity term under Gaussian priors. Lemma 3.8 gives a square root dependence on the dimension for this term. This improves over the dimension dependence obtained in Haddouche et al. [2020]. Specific results for classification with the multi-class unhinged loss [Shoham et al., 2021, Zhou et al., 2023, Lemire Paquin et al., 2026] and for regression are given in Proposition 4.4, Corollary 4.5, and Corollary 4.6. A comparison with a classical Rademacher complexity bound for a bounded smooth loss is presented in Section 8 and Figure 2. 4. We propose a practical regularizer inspired by the Jacobian and Hessian quantities appearing in the theory. For BatchNorm networks, we investigate a parametrization obtained by combining the BatchNorm transformation with the preceding affine weights, leading to effective BatchNorm weights weff,B ′ . The resulting experiments are presented in Section 9, Figures 3–5, and Table 1.

Structure of the document. In Section 2, we contextualize our general method. The presentation in Section 3 follows the conceptual development of the bounds. Some of the technical ingredients required for Theorem 3.7 are established later in Sections 6–7. For clarity of exposition, we state the main results first and refer to those later sections within the proofs when the corresponding technical estimates are needed.

Motivation and relation to existing derandomization approaches

We first motivate the role of the Jensen gap through the simple case where the loss is convex in the parameters. If a loss function L(hw (x), y) is convex with respect to w, then Jensen’s inequality implies L(hw (x), y) ≤ Ew∼Q [L(hw (x), y)], where w = Ew∼Q [w]. Starting from a PAC-Bayesian bound for L, one can then obtain in a straightforward manner a generalization bound for the deterministic classifier w of the form n h i 1X e √1 LD (w) ≤ LS (w) + Ew∼Q L(hw (xi ), yi ) − L(hw (xi ), yi ) + O . n i=1 n

The quantity

n h i 1X Ew∼Q L(hw (xi ), yi ) − L(hw (xi ), yi ) n i=1

can be interpreted as an empirical measure of flatness of the loss L around the mean w. This direct argument constitutes perhaps the simplest form of derandomization of a PAC-Bayes bound. However, it relies on convexity and therefore cannot be applied to typical neural network hypothesis classes. Moreover, even for linear predictors, it does not apply for example to non-linear symmetric loss functions L(z, y), which are non-convex [Ghosh et al., 2015]. This motivates the development of a more general approach. The framework developed in this work replaces this convexity argument by an exact decomposition. The additional term required for derandomization is the generalization gap of the Jensen gap of the loss class, and the resulting bounds take the schematic form smoothness/flatness terms e √1 √ +O . n n

LD (w) ≤ LS (w) +

This perspective can be advantageous even in convex settings, since the empirical flatness term appearing in the direct convexity argument need not vanish with the sample size. We now position our approach within the literature that seeks guarantees on deterministic classifiers derived from PAC-Bayesian bounds. Viallard et al. [2021] develop a general framework for deriving pointwise PAC-Bayesian generalization bounds that apply to an individual hypothesis sampled from the posterior, rather than to the Gibbs predictor. This form of derandomization is referred to as the disintegration of PAC-Bayesian bounds. Related deterministic PAC-Bayesian perspectives were later developed by Clerico et al. [2025]. In the disintegrated setting, for instance, if one assumes an explicit posterior family (e.g., a Gaussian centered at the algorithm’s output), the resulting guarantee applies to a specific hypothesis drawn from that posterior and is probabilistic with respect to this sampling step (in addition to the randomness of the sample S). In contrast, our bounds apply directly to the deterministic classifier at the posterior mean in the classical sense and do not introduce additional hypothesis level randomness. Among direct derandomization approaches, a prominent line of work relies on margin-based arguments. Early PAC-Bayesian margin formulations appear in Langford and Shawe-Taylor [2002]. Subsequent developments derived results for modern neural network architectures [Neyshabur et al., 2018, Biggs and Guedj, 4

2022, Banerjee et al., 2020]. These approaches provide sharp guarantees when suitable margin notions are available, but they depend on margin-specific constructions and are therefore not directly adapted to arbitrary loss functions, such as the symmetric loss functions considered in this work. Define the margin of an example (x, y) as mw (x, y) = hw (x)y − max hw (x)k . k̸=y

For a margin parameter γ > 0, the corresponding margin loss is defined by Lγ (hw (x), y) = 1{mw (x, y) ≤ γ}, which upper bounds the 0-1 loss. Margin-based PAC-Bayesian approaches exploit inequalities involving the 0-1 loss, the margin loss and the margin loss under a posterior Q. Consider as an illustration the strategy of Neyshabur et al. [2018]. They define a subset Sw of weights w such that the outputs of hw remain uniformly close to those of hw , namely n

Sw ⊆ w : sup ∥hw (x) − hw (x)∥∞ < γ/4 . x∈X

e under which the inequalities Conditioning the posterior on this set yields a truncated posterior Q

L0-1 D (hw ) ≤ Ew∼Q e LD,γ/2 (hw )

and

Ew∼Qe LS,γ/2 (hw ) ≤ LS,γ (hw )

hold. This enables the conversion of a stochastic PAC-Bayes guarantee into a deterministic margin-based bound. A related derandomization strategy, developed in Banerjee et al. [2020], also relies on inequalities that directly relate the margin loss of the deterministic predictor to the corresponding Gibbs (i.e., posterioraveraged) margin loss under Q. These inequalities are obtained by controlling how Gaussian perturbations of the parameters affect the margin, and they introduce a residual term of the form c0 exp − min(c2 γ 2 , c1 γ) ,

which captures the probability that the margin changes significantly under the perturbation. This term is intrinsic to their derandomization step and does not vanish with the sample size n. In contrast, our approach preserves statistical consistency in the sense that all additional terms in the bound vanish as n → ∞. Fundamentally, the Jensen gap framework adopted in this work does not rely on such “derandomization inequalities” for the margin loss. Instead, it starts from an exact decomposition relating deterministic and stochastic risks through the Jensen gap. This gives a conceptually distinct route to derandomization that is naturally suited to smooth loss functions beyond margin-based constructions. Moreover, the empirical loss appearing in our bounds can coincide with the loss used for training, so gradient-based optimization directly acts on a term that enters the bound. By contrast, the margin loss Lγ cannot be directly optimized using gradient-based methods and therefore requires a surrogate training loss that is different from the loss appearing in the bound. Another line of work obtaining deterministic guarantees from PAC-Bayes bounds is the literature on weighted majority-vote classifiers [McAllester, 1999, Langford and Shawe-Taylor, 2002]. Explicit bounds for the risk of the majority vote were derived in terms of the mean and variance of the error of the Gibbs classifier in [Lacasse et al., 2007], leading to the C-bound and the MinCq learning algorithm [Germain et al., 2015]. Second-order refinements of the C-bound were later established in [Masegosa et al., 2020]. More recently, Leblanc and Germain [2025] proposed a general framework for extracting deterministic risk guarantees from stochastic PAC-Bayesian bounds, with applications to majority-vote classifiers. While powerful, this line of work is inherently tied, in its main applications, to vote-based predictors and does not directly address deterministic predictors defined through the posterior mean of parameters. 5

3 Generalization bounds for unbounded loss functions from the PAC-Bayes framework Unbounded loss functions arise naturally in several learning problems. Standard examples include regression losses such as the squared loss, the absolute loss, and the Huber loss, as well as classification losses such as the cross-entropy loss. They also arise in classification through symmetric losses such as the multi-class unhinged loss [Shoham et al., 2021, Zhou et al., 2023] and through related symmetrized losses studied in Lemire Paquin et al. [2026]. In this section, we rely on a PAC-Bayes result applicable to unbounded loss functions from Alquier et al. [2016]; see also [Rivasplata et al., 2020, Casado et al., 2024] for related PAC-Bayesian treatments beyond the bounded loss setting. We then exploit the assumption that, for each individual hypothesis h, the loss function L(h(x), y) is bounded on X (typically a bounded domain) in order to apply Hoeffding’s inequality. This strategy is in the same spirit as Haddouche et al. [2020], where hypothesis-dependent boundedness is used to extend PAC-Bayes bounds to learning problems involving unbounded regression loss functions. Theorem 3.1 (Alquier et al. [2016]). Given a distribution D over X × Y , a hypothesis set H , a loss function L : H × X × Y → R, a prior distribution P over H , a δ ∈ (0, 1], and a real number λ > 0, with probability at least 1 − δ over the choice of S ∼ Dn , we have: ∀Q on H :

1 1 DKL (Q∥P ) + ln + ΨL,P,D (λ, n) , λ δ

Eh∼Q LD (h) ≤ Eh∼Q LS (h) +

where ΨL,P,D (λ, n) := ln Eh∼P ES∼Dn exp [λ (LD (h) − LS (h))] . ■

Proof: see Alquier et al. [2016] and Germain et al. [2016]. Our next step is to upper bound ΨL,P,D (λ, n) under a hypothesis-dependent boundedness condition.

Proposition 3.2. Assume that ∥h(x)∥ ≤ ah on X for every h ∈ H . Furthermore, assume that L(z, y) is ℓ-Lipschitz in z for every y, and that L(0, y) is independent of y. Then, for every λ > 0, λ2 ℓ2 a2h ΨL,P,D (λ, n) ≤ ln Eh∼P exp 2n

Proof: Without loss of generality, assume that L(0, y) = 0, since adding a constant to the loss does not affect LD (h) − LS (h). Then, for every fixed h, |L(h(x), y)| ≤ ℓ∥h(x)∥ ≤ ℓah . Thus, by Hoeffding’s lemma, λ2 ℓ2 a2h ES∼Dn exp(λ(LD (h) − LS (h))) ≤ exp 2n

Taking expectation over h ∼ P and then the logarithm gives λ2 ℓ2 a2h ΨL,P,D (λ, n) = ln Eh∼P ES∼Dn exp(λ(LD (h) − LS (h))) ≤ ln Eh∼P exp 2n

. ■

We now convert the bound on the Gibbs risk from Theorem 3.1 into a bound at the mean of the distribution. 6

Theorem 3.3. Let D be a distribution on X × Y , let S = {(xi , yi )}ni=1 ∼ Dn , let H = {hw : w ∈ Rm }, and let P be a prior on Rm . Fix δ ∈ (0, 1] and λ > 0. For any distribution Q on Rm and any sample S, define

ΩL,Q,D,S (n) := LD (hw ) − Ew∼Q LD (hw ) − LS (hw ) − Ew∼Q LS (hw ) ,

w := Ew∼Q [w].

Then, with probability at least 1 − δ over the draw of S, for all distributions Q on Rm , LD (hw ) ≤ LS (hw ) + ΩL,Q,D,S (n) +

i 1h DKL (Q∥P ) + ln 1δ + ΨL,P,D (λ, n) , λ

where ΨL,P,D (λ, n) is as in Theorem 3.1. Proof: Start from the identity

LD (hw ) = Ew∼Q LD (hw ) + LD (hw ) − Ew∼Q LD (hw ) . On the event of probability at least 1 − δ given by Theorem 3.1, we have simultaneously for all Q: Ew∼Q LD (hw ) ≤ Ew∼Q LS (hw ) +

i 1h DKL (Q∥P ) + ln 1δ + ΨL,P,D (λ, n) . λ

Substituting this bound into the previous identity yields

LD (hw ) ≤ Ew∼Q LS (hw ) + LD (hw ) − Ew∼Q LD (hw ) +

i 1h DKL (Q∥P ) + ln 1δ + ΨL,P,D (λ, n) . λ

Next, decompose the Gibbs empirical risk by adding and subtracting LS (hw ):

Ew∼Q LS (hw ) = LS (hw ) + Ew∼Q LS (hw ) − LS (hw ) . Plugging this decomposition into the last inequality gives LD (hw ) ≤ LS (hw ) + +

LD (hw ) − Ew∼Q LD (hw ) − LS (hw ) − Ew∼Q LS (hw )

i 1h DKL (Q∥P ) + ln 1δ + ΨL,P,D (λ, n) , λ

■

which concludes the proof.

Remark 3.4. The term ΩL,Q,D,S (n) is the exact penalty term needed to obtain a bound on the deterministic classifier at the mean of the distribution Q from a bound on the stochastic classifier. Corollary 3.5. Let D be a distribution on X × Y , let S ∼ Dn , and let L be a loss function. Let Θ be a nonempty subset of probability distributions on Rm . Assume that there exists a function g(Θ, L, S, δ, n) such that, for any δ ∈ (0, 1], with probability at least 1 − δ over S ∼ Dn , sup ΩL,Q,D,S (n) ≤ g(Θ, L, S, δ, n). Q∈Θ

Fix δ ∈ (0, 1], λ > 0, and a prior P on Rm . Then, with probability at least 1 − δ over S ∼ Dn , we have simultaneously for all Q ∈ Θ, LD (hw ) ≤ LS (hw ) + g(Θ, L, S, δ/2, n) + 7

i 1h DKL (Q∥P ) + ln 2δ + ΨL,P,D (λ, n) . λ

■

Proof: This is a direct union bound.

Corollary 3.5 reduces the problem of controlling deterministic predictors to obtaining a uniform upper bound on ΩL,Q,D,S (n) over a family of posteriors. Such a bound will be established in Section 7. In the next definition, we formalize the key object that will control this penalty term: the Jensen gap. Definition 3.6. Let f : Rm → Rn be a measurable function and let Q be a probability distribution on Rm . We will refer to JenQ [f (w)] := f (Ew∼Q [w]) − Ew∼Q [f (w)] as the Jensen gap of f with respect to Q. The quantity ∥JenQ [f (w)]∥ (or |JenQ [f (w)]|) is a measure of non-linearity of the function f . Note that f is not required to be convex. Combining Corollary 3.5 with Proposition 3.2 and Proposition 7.9 from Section 7 leads to the following result: Theorem 3.7. Assume that L(z, y) is a real-valued loss function such that, for every y, the map z 7→ L(z, y) is ℓ-Lipschitz and β-smooth, and that L(0, y) is independent of y. Let D be a distribution over X × Y and let S = {(xi , yi )}ni=1 ∼ Dn . Let H = {hw : w ∈ Rm } be a hypothesis class. Assume that for every hw ∈ H there exists aw > 0 such that ∥hw (x)∥ ≤ aw for all x ∈ X. Let Θ := {w ∈ Rm : ∥w∥2 ≤ R}, and fix σ > 0. For each w ∈ Θ, define Q := N (w, σ 2 Im ),

so that

w = Ew∼Q [w].

Assume that the hypotheses of Corollary 7.6 (Section 7) hold, and assume moreover that there exists B > 0 such that, for all (x, y) and all w ∈ Θ, |JenQ L(hw (x), y) | ≤ σ 2 B.

Let P be any prior distribution on Rm , let δ ∈ (0, 1], and let λ > 0. Then, with probability at least 1 − δ over S ∼ Dn , we have uniformly for all w ∈ Θ, s

Rσ q 2 LD (hw ) ≤ LS (hw ) + 2c √ β JS,σ + ℓ2 HS,σ + 8σ 2 B n "

1 2 λ2 ℓ2 a2w + DKL (Q∥P ) + ln Ew∼P exp λ δ 2n

2 ln(8/δ) n

! #

where c > 0 is an absolute constant, and JS,σ and HS,σ are defined as in Corollary 7.6 and are empirical measures of flatness depending on the hypothesis class. Lemma 3.8 (Evaluation of the PAC-Bayes complexity term for Gaussian P ). Let P be a prior distribution on the full parameter space of a T -layer model, denoted W1:T . Let WT ∈ RmT be the weights of the last linear layer, and assume that the marginal distribution of WT under P is WT ∼ N (0, σ 2 ImT ),

σ > 0.

Assume that there exists M > 0 such that, for all x ∈ X, ∥hW1:T (x)∥ ≤ M ∥WT ∥. This holds both in the linear case hWT (x) = WT x with ∥x∥ ≤ M , and in the neural-network case when the representation vector entering the last layer has norm upper bounded by M . Let ℓ > 0, n ≥ 1, and choose √ n √ . λ= M ℓσ mT + 1 Then, with aW1:T := M ∥WT ∥, we have λ2 ℓ2 a2W1:T 1 ln EW1:T ∼P exp λ 2n

≤

√ M ℓσ mT + 1 √ . 2 n

Proof: The quantity inside the expectation depends on W1:T only through WT . Writing PT for the marginal distribution of WT under P , we have λ2 ℓ2 a2W1:T EW1:T ∼P exp 2n

λ2 ℓ2 M 2 ∥WT ∥2 = EWT ∼PT exp 2n

Let t=

M 2 λ2 ℓ2 . 2n

Since WT ∼ N (0, σ 2 ImT ), we have

EWT ∼PT exp t∥WT ∥2 = (1 − 2tσ 2 )−mT /2 , when 2tσ 2 < 1. For the chosen value

√ n √ λ= , M ℓσ mT + 1

we have 2tσ 2 = Therefore,

Hence,

1 . mT + 1

λ2 ℓ2 a2W1:T EW1:T ∼P exp 2n λ2 ℓ2 a2W1:T 1 ln EW1:T ∼P exp λ 2n

mT + 1 mT

mT /2

√ M ℓσ mT + 1 mT 1 √ = ln 1 + . n 2 mT

Using 1 mT

λ2 ℓ2 a2W1:T 1 ln EW1:T ∼P exp λ 2n

mT ln 1 + we obtain

≤ 1, √ M ℓσ mT + 1 √ ≤ . 2 n ■

Lemma 3.8 turns the PAC-Bayes logarithmic term into an explicit expression when the prior is Gaussian on the last layer. We now illustrate how the full derandomized bound simplifies in the linear case. 9

Specialization of the results to linear hypothesis classes

Theorem 4.1 (Linear case of Theorem 3.7). Assume that each hypothesis hW ∈ H is given by hW (x) = W x with W ∈ RC×d , and let m := Cd. Assume that ∥x∥ ≤ M for all x ∈ X. Let L(z, y) be a real-valued loss function such that, for every y, the map z 7→ L(z, y) is ℓ-Lipschitz and β-smooth, and assume that L(0, y) is independent of y. Let Θ := { W ∈ RC×d : ∥W ∥F ≤ R }. Fix σ > 0 and let δ ∈ (0, 1]. Then, with probability at least 1 − δ over S ∼ Dn , we have uniformly for all W ∈ Θ, s √ βRσCM 2 2 ln(8/δ) √ LD (hW ) ≤ LS (hW ) + 2 2 + 4βCM 2 σ 2 n n √ √ 2 1 Mℓ m + 1 M ℓσ m + 1 √ √ ln + . + ∥W ∥2F + 2σ n n δ 2 Proof: Let the prior P and posterior Q be isotropic Gaussian distributions with the same covariance matrix σ 2 Im×m , with prior mean 0 and posterior mean W . Then, DKL (Q∥P ) =

∥W ∥2F . 2σ 2

We apply Theorem 3.7 to the linear hypothesis class hW (x) = W x with parameter set Θ = {W ∈ RC×d : ∥W ∥F ≤ R} and with ∥x∥ ≤ M . The data-dependent complexity term appearing in Theorem 3.7 satisfies √ βRσCM 2 Rσ q 2 √ 2c √ β JS,σ + ℓ2 HS,σ ≤ 2 2 n n (see Remark 7.7 and Theorem 7.2 in Section 7). Moreover, specializing the Jensen-gap upper bound in Theorem 6.5 from Section 6 to the linear case (T = 1) yields σ2 |JenQ [L(hW (x), y)]| ≤ β C M 2. 2 Thus, the uniform assumption |JenQ [L(hW (x), y)]| ≤ σ 2 B in Theorem 3.7 holds with B=

βCM 2 . 2

The corresponding concentration term therefore becomes s 2

8σ B

2 ln(8/δ) = 4βCM 2 σ 2 n

2 ln(8/δ) . n

Finally, using Lemma 3.8 and the above value of the KL divergence, the PAC-Bayes complexity term is bounded by √ √ √ Mℓ m + 1 M ℓσ m + 1 2 M ℓσ m + 1 2 √ √ √ ∥W ∥F + ln + . 2σ n n δ 2 n ■ Remark 4.2. In the scalar-output case C = 1, Theorem 4.1 is also true but can be sharpened by replacing Maurer’s vector-contraction inequality with the scalar contraction lemma in the analysis. This removes the

√

2 constant in the Rademacher complexity term. Consequently, the first complexity term in Theorem 4.1 becomes βRσM 2 2 √ n instead of

√ βRσCM 2 √ 2 2 . n

We now want to apply this result to the multi-class unhinged loss function. We first define a proper surrogate version of the loss that can be used within our generalization bounds. Lemma 4.3. Let C > 2 and r > 0. Assume that ∥z∥ ≤ r. Define the multi-class unhinged surrogate as Lunh r (z, y) := a with

√ a= r

√

C −1−

C 1 X zk −zy + C k=1

, C−2

b = ar

C −1 1 q = . C−2 C 1− 2(C−1)

Then, we have 1. inf ∥z∥≤r Lunh r (z, y) = 0, 2. L0-1 (z, y) ≤ Lunh r (z, y), 3. The Lipschitz constant of Lunh r (z, y) is 1

r 1− Proof: Let us write unh

C−2 2(C−1)

C 1 X (z, y) = a −zy + zk C k=1

for some constants a, b > 0. We want inf ∥z∥≤r Lunh (z, y) = 0. This infimum can be computed by standard Lagrangian optimization. The solution is s C −1 inf Lunh (z, y) = −ar + b. C ∥z∥≤r To make the infimum equal to 0, we set: s

b = ar

C −1 . C

We now turn our attention towards upper bounding the 0-1 loss. Suppose there exists k ̸= y such that P zk ≥ zy , so the 0-1 loss is 1 at this value of (z, y). We want to compute the infimum of −zy + C1 C k=1 zk under the constraints ∥z∥ ≤ r and zk ≥ zy . At a global minimizer, we must actually have zk = zy (this can be seen by a simple perturbation argument). We may therefore restrict the optimization to the set B(0, r) ∩ {z : zk = zy }. 11

Both the objective and the constraint are invariant under permutations of the coordinates {zj }j̸=y,k . Therefore, if z is a minimizer, any permutation of these coordinates is also a minimizer. Averaging over all such permutations gives another feasible point satisfying (∀j ̸= y, k)

zj = t for some t ∈ R, and

zy = zk = s for some s ∈ R. The optimization problem thus reduces to C −2 (t − s) s,t∈R C min

subject to 2s2 + (C − 2)t2 ≤ r2 . The solution of this problem can be obtained using Lagrange multipliers. One obtains s

t − s = −r

C . 2(C − 2)

Therefore, inf

∥z∥≤r zk ≥zy

C 1 X zi −zy + C i=1

and

Substituting b = ar

= −r

Lunh (z, y) ≥ −ar q

C −2 2C

C −2 + b. 2C

C−1 C , we obtain

s

Lunh (z, y) ≥ ar 

C −1 − C



C − 2 . 2C

Therefore, L0-1 (z, y) ≤ Lunh (z, y) provided √

a≥ r

C−1 C −

C−2 2C

√

C −1−

C−2 2

With the choice of a in the statement of the Lemma, we thus indeed have L0-1 (z, y) ≤ Lunh (z, y). Finally, the gradient of the function −zy + C1

k=1 zk has norm

s unh

sup ∥∇z L

(z, y)∥ = a

C−1 unh is C , so the Lipschitz constant of L

C −1 . C ■

Simplifying concludes the proof.

The multi-class unhinged loss is typically studied in the context of learning with uniform label noise; see, for example, Lemire Paquin et al. [2026]. We therefore state below a result for this setting. 12

Proposition 4.4. Let C > 2 be the number of classes. Define bC :=

1 1−

C−2 2(C−1)

Assume that ∥x∥ ≤ M . Furthermore, assume that each hypothesis hW ∈ H is given by hW (x) = W x, where W ∈ RC×d . We will simplify notations by replacing hW with W . Let µunh be the unhinged multi-class S data centroid (see Lemire Paquin et al. [2026]), defined by: µunh := N1 S

⊤ i=1 cyi xi ,

−1 where cy is a column vector having its y th entry given by C−1 C and every other entry given by C . Given a distribution D over X × Y , a probability of corruption p ∈ [0, 1) and a confidence parameter δ ∈ (0, 1], n with probability at least 1 − δ over the choice of S ∼ D , we have:

unh L0-1 D (µS ) ≤ bC

1−

√ ∥µunh ∥ b C dC C S √ . + Õ C − 1 (1 − p)M (1 − p) n

Proof: Consider the multi-class unhinged surrogate Lunh r (z, y) with r = M . We will omit the subscript r to simplify notation. Then, for any S, unh 0-1 L0-1 D (µS ) = LD

µunh S

∥µunh ∥ S

≤ Lunh D =

µSunh ∥µSunh ∥

unh unh C X µS µS 1 p unh L Lunh − x, y E 1 − p D ∥µunh ∥ C x∼Dx y=1 ∥µunh ∥ S S

unh µS 1 unh L − pbC . = 1 − p D ∥µunh ∥ S

For any 0 < σ < 1 and with m = dC, applying Theorem 4.1 with β = 0 and ℓ = bC /M , we obtain that n with probability at least 1 − δ over the draw S ∼ D , unh L0-1 D (µS ) ≤

√ unh µS 1 bC dC + 1 unh √ L − pbC + 1−p S 2(1 − p)σ n ∥µunh ∥ S √ bC σ dC + 1 2 1 √ + ln + . (1 − p) n δ 2

The proof is completed by exploiting bC Lunh (W ) = − S M

C Trace(µunh W T ) + bC S C −1

µunh

with W = ∥µSunh ∥ and simplifying.

■

We can also apply our results to the problem of linear regression. Corollary 4.5 (Linear regression with absolute loss). Let hw (x) = ⟨w, x⟩, ∥x∥ ≤ M and L(z, y) = |z − y|. 13

Assume that |y| ≤ Ymax almost surely. Let P = N (0, σ 2 Id ) with σ > 0. Then, with probability at least 1 − δ over S ∼ Dn , for all probability distributions Q on Rd , s √ 2 1 Mσ d + 1 ln(2/δ) √ DKL (Q∥P ) + ln + + Ymax Ew∼Q LD (hw ) ≤ Ew∼Q LS (hw ) + . n δ 2 2n In particular, the explicit Gaussian-prior complexity term has a square root dependence on the dimension d. e Proof. The absolute loss is 1-Lipschitz in its prediction argument and Proposition 3.2 applies to L(z, y) = e L(z, y) − L(0, y) with aw = M ∥w∥. Applying Theorem 3.1 and Lemma 3.8 to L, with confidence parameter δ/2, we obtain that, with probability at least 1 − δ/2 over S ∼ Dn , for all probability distributions Q on Rd , √ n Mσ d + 1 2 1 1X √ Ew∼Q LD (hw ) ≤ Ew∼Q LS (hw ) + DKL (Q∥P ) + ln + + ED [|y|] − |yi |. n δ 2 n i=1

■

Applying Hoeffding’s inequality with a union bound completes the proof.

Since the absolute loss is not smooth, our derandomized framework does not apply to it directly. Nevertheless, it can be approached by the following smooth family of Huber losses, which converges uniformly to the absolute loss as the smoothing parameter tends to zero. Corollary 4.6 (Linear regression with Huber losses). Let hw (x) = ⟨w, x⟩, assume that ∥x∥ ≤ M , and fix ρ > 0. Define the Huber loss by

Lρ (z, y) :=

  (z − y)2  

, if |z − y| ≤ ρ, 2ρ ρ   |z − y| − , if |z − y| > ρ. 2

Assume that |y| ≤ Ymax almost surely and define Yρ,max :=

sup

Lρ (0, y).

|y|≤Ymax

Let Θ := {w ∈ Rd : ∥w∥ ≤ R} and let P = N (0, σ 2 Id ) with σ > 0. Then, with probability at least 1 − δ over S ∼ Dn , we have uniformly for all w ∈ Θ, s

2 RσM 2 4M 2 σ 2 2 ln(16/δ) √ Lρ,D (hw ) ≤ Lρ,S (hw ) + + + Yρ,max ρ n ρ n √ √ Mσ d + 1 4 1 M d+1 2 √ √ ∥w∥ + ln + . + 2σ n n δ 2

ln(2/δ) 2n

Proof: For every y, the map z 7→ Lρ (z, y) is 1-Lipschitz and 1/ρ-smooth. We can apply Theorem 4.1 with e ρ (z, y) = Lρ (z, y) − Lρ (0, y). We then obtain that, with C = 1 (see Remark 4.2), ℓ = 1 and β = 1/ρ to L probability at least 1 − δ/2 over S ∼ Dn , uniformly for all w ∈ Θ, s

n 2 RσM 2 4M 2 σ 2 2 ln(16/δ) 1X √ Lρ,D (hw ) ≤ Lρ,S (hw ) + + + ED [Lρ (0, y)] − Lρ (0, yi ) ρ n ρ n n i=1 √ √ M d+1 Mσ d + 1 4 1 2 √ √ + ∥w∥ + ln + . 2σ n n δ 2

Applying Hoeffding’s inequality with a union bound completes the proof. 14

■

5 Generalization bounds for bounded loss functions from the PAC-Bayes framework When the loss is uniformly bounded, one can instead invoke standard bounded-loss PAC-Bayes inequalities, leading to a cleaner square root complexity term. Using the same proofs as in the case of unbounded loss functions, but replacing Theorem 3.1 with Theorem 31.1 from Shalev-Shwartz and Ben-David [2014], we get the following result for bounded loss functions: Theorem 5.1. Assume that the loss L(z, y) takes values in an interval [A′ , A] ⊂ R on the domain RC , and that, for every y, the map z 7→ L(z, y) is ℓ-Lipschitz and β-smooth. Let D be a distribution over X × Y and let S = {(xi , yi )}ni=1 ∼ Dn . Let H = {hw : w ∈ Rm } be a hypothesis class. Let Θ := {w ∈ Rm : ∥w∥2 ≤ R}, and fix σ > 0. For any w ∈ Θ, define a posterior Q := N (w, σ 2 Im ). Assume that the hypotheses of Corollary 7.6 hold, and assume moreover that there exists B > 0 such that, for all (x, y) and all w ∈ Θ, |JenQ L(hw (x), y) | ≤ σ 2 B.

Let P be any prior distribution on Rm , and let δ ∈ (0, 1). Then, with probability at least 1 − δ over S ∼ Dn , we have uniformly for all w ∈ Θ, Rσ q 2 LD (hw ) ≤ LS (hw ) + 2c √ β JS,σ + ℓ2 HS,σ + 8σ 2 B n s ′

+ (A − A )

2 ln(8/δ) n

DKL (Q∥P ) + ln 2n δ , 2(n − 1)

where c > 0 is an absolute constant, and JS,σ and HS,σ are defined as in Corollary 7.6. Similarly to Theorem 4.1, we can obtain a straightforward specialization to the linear case: Theorem 5.2 (Linear case of Theorem 5.1). Assume that each hypothesis hW ∈ H is given by hW (x) = W x with W ∈ RC×d , and let m := Cd. Assume that ∥x∥ ≤ M for all x ∈ X. Let L(z, y) be a loss function taking values in an interval [A′ , A] ⊂ R on the domain RC , and assume that, for every y, the map z 7→ L(z, y) is ℓ-Lipschitz and β-smooth. Let Θ := { W ∈ RC×d : ∥W ∥F ≤ R }. Fix σ > 0 and let δ ∈ (0, 1). Then, with probability at least 1 − δ over S ∼ Dn , we have uniformly for all W ∈ Θ, s √ βRσCM 2 2 ln(8/δ) √ LD (hW ) ≤ LS (hW ) + 2 2 + 4βCM 2 σ 2 n n v u ∥W ∥2 2n u F ′ t 2σ 2 + ln δ

+ (A − A )

2(n − 1)

One can alternatively invoke Theorem 5 of Maurer [2004], which provides an inverse-kl PAC-Bayesian bound for bounded losses. This may lead to a sharper complexity term, but at the cost of an implicit final expression that is less transparent. We obtain the following variant of Theorem 5.1.

Theorem 5.3 (Bounded-loss PAC-Bayes bound in kl−1 form, uniform over {σi }i≥1 ). Assume that the loss L(z, y) takes values in an interval [A′ , A] ⊂ R on the domain RC , and that, for every y, the map z 7→ L(z, y) is ℓ-Lipschitz and β-smooth. Let D be a distribution over X × Y , let S = {(xj , yj )}nj=1 ∼ Dn , with n ≥ 8, and let Θ := {w ∈ Rm : ∥w∥2 ≤ R}. Fix σmax > 0 and for i ≥ 1 define σi := 2 1−i σmax . For w ∈ Θ, let Qw,σi := N (w, σi2 Im ). Assume the same conditions as in Corollary 7.6. Assume moreover that there exists B > 0 such that, for all (x, y), all w ∈ Θ and all i ≥ 1, JenQw,σi L(hw (x), y) ≤ σi2 B. Let P be any prior distribution on Rm and let δ ∈ (0, 1). Then, with probability at least 1 − δ over S ∼ Dn , we have uniformly for all i ≥ 1 and all w ∈ Θ, Rσi q 2 LD (hw ) ≤ 2c √ β JS,σi + ℓ2 HS,σi + 8σi2 B n 

+ (A − A′ ) kl−1  where

4 ln(i) + 2 ln(16/δ) + A′ + JenQw,σi LS (hw ) n

Ew∼Qw,σi LS (hw ) − A′ A − A′

√



DKL (Qw,σi ∥P ) + ln 4 δ n , n

kl−1 (q | ε) := sup p ∈ [q, 1] : kl(q∥p) ≤ ε with

q 1−q kl(q∥p) := q ln + (1 − q) ln . p 1−p

Proof: Apply Theorem 5 of Maurer [2004] to the rescaled loss (L − A′ )/(A − A′ ) and then use Proposition 7.10 with a union bound after rearranging terms. ■ For linear hypothesis classes, we use the square root form in Section 8 for simplicity and clarity. Our Rademacher complexity bounds for the Jensen gap class require a uniform upper bound on the Jensen gap. In the next section, we provide such bounds for smooth neural networks, treating separately the cases of bounded and unbounded activation functions.

Uniform upper bounds for the Jensen gap for smooth neural networks

We start with a general result for bounding the Jensen gap of the composition of a function f with a neural network hw (x) exploiting the Lipschitz constant and the β-smoothness of the function f . Lemma 6.1. Assume that the hypothesis class is parameterized by w ∈ Rm and Q is a probability distribution on Rm . Denote by hw a neural network mapping inputs x ∈ Rd to vectors in RH . Let f : RH → RK (or f : RH × Y → RK if f is a loss function) be differentiable. Furthermore, assume that f is ℓ-Lipschitz and β-smooth (for all y ∈ Y if there is a dependency on y). We will omit the variable y in order to simplify notations in what follows. The property of β-smoothness means that the Jacobian ∇f ∈ RK×H is β-Lipschitz with respect to the spectral norm ∥ · ∥2 , that is, ∥∇f (z) − ∇f (z ′ )∥2 ≤ β∥z − z ′ ∥, 16

for all z, z ′ ∈ RH .

For any fixed input x ∈ Rd , f (hw (x)) is a function of w. Then, we have that the Jensen gap of f (hw (x)) with respect to Q satisfies ∥JenQ [f (hw (x))]∥ ≤ ℓ∥JenQ [hw (x)]∥ +

β VarQ [hw (x)], 2

where VarQ [hw (x)] denotes the total variance of the vector hw (x) under distribution Q (trace of the covariance matrix). Proof: Let w = Ew∼Q [w] and z = Ew∼Q [hw (x)]. Then, ∥JenQ [f (hw (x))]∥ = ∥f (hw (x)) − Ew∼Q [f (hw (x))]∥ ≤ ∥f (hw (x)) − f (z)∥ + ∥f (z) − Ew∼Q [f (hw (x))]∥. For the first term, the ℓ-Lipschitz property of f gives ∥f (hw (x)) − f (z)∥ ≤ ℓ∥hw (x) − z∥ = ℓ∥JenQ [hw (x)]∥. For the second term, we apply the integral form of first-order Taylor’s theorem to f (z) around z: f (z) = f (z) + ∇f (z)(z − z) +

Z 1

(∇f (z + t(z − z)) − ∇f (z)) (z − z) dt.

Taking expectation over w on both sides with z = hw (x), we obtain Z 1

EQ [f (hw (x))] = f (z) + Ew∼Q

(∇f (z + t(hw (x) − z)) − ∇f (z)) (hw (x) − z) dt , 0

Using the β-smoothness of f , we get ∥∇f (z + t(hw (x) − z)) − ∇f (z)∥2 ≤ βt∥hw (x) − z∥. Thus, ∥f (z) − EQ [f (hw (x))]∥ ≤ Ew∼Q

Z 1

βt∥hw (x) − z∥2 dt =

β VarQ [hw (x)]. 2 ■

Our proof for bounding the variance term for neural networks will be in the form of an inductive argument on the number of layers and will exploit the following lemma. Lemma 6.2. Assume that f : Rm → − Rk is ℓ-Lipschitz. Then, Var[f (x)] ≤ ℓ2 Var[x]. Proof: On one hand, Var[f (x)] = Ex [∥f (x) − Ex f (x)∥2 ] = Ex [∥f (x)∥2 − 2(f (x) · Ex f (x)) + ∥Ex f (x)∥2 ] = Ex [∥f (x)∥2 ] − ∥Ex f (x)∥2 . On the other hand, if x′ follows the same distribution as x but is independent from x, Ex Ex′ [∥f (x) − f (x′ )∥2 ] = Ex′ Ex [∥f (x)∥2 − 2Ex′ Ex (f (x) · f (x′ )) + Ex′ Ex ∥f (x′ )∥2 ] = 2Ex [∥f (x)∥2 ] − 2∥Ex f (x)∥2 . 17

Therefore,

1 Var[f (x)] = Ex Ex′ [∥f (x) − f (x′ )∥2 ]. 2 We can now exploit the Lipschitz property to conclude the proof: 1 ℓ2 Var[f (x)] = Ex Ex′ [∥f (x) − f (x′ )∥2 ] ≤ Ex Ex′ [∥x − x′ ∥2 ] = ℓ2 Var[x]. 2 2 ■ We are now ready to upper bound the variance of the outputs of a neural network. Proposition 6.3 (Bounded activation functions). Consider a feedforward fully connected neural network with T layers hW1:T (x) = WT gT −1 (WT −1 gT −2 (· · · g1 (W1 x))) where each non-linear function gt : Rdt → − Rdt is ℓt -Lipschitz. We further assume that these functions are bounded: ∥gt (z)∥ ≤ Mt for all z ∈ Rdt . We let dT := C be the number of classes. Assume that ∥x∥ ≤ M0 and let Q be an isotropic Gaussian distribution centered at W 1 , · · · , W T with covariance matrix given by σ 2 times the identity matrix. Then, VarQ [hW1:T (x)] ≤ σ 2

T X

2 dt Mt−1

TY −1

ℓ2t′ ∥W t′ +1 ∥22 ,

t′ =t

t=1

where the product is equal to 1 if t = T . Proof: The proof is done by induction on the number of layers T . For T = 1, we have hW1 (x) = W1 x. If wi denotes the ith row of W1 , then wi ∼ N (wi , σ 2 I) and therefore Var(wiT x) = σ 2 ∥x∥2 . Summing over the d1 output coordinates gives VarQ [hW1 (x)] =

d1 X

Var(wiT x) = d1 σ 2 ∥x∥2 ≤ d1 σ 2 M02 ,

i=1

which matches the claimed bound since the product in the statement equals 1 when T = 1. Assume that the result is true for T − 1 layers. We have VarQ [hW1:T (x)] = EW1:T −1 EWT [∥WT gT −1 (hW1:T −1 (x)) − W T EW1:T −1 [gT −1 (hW1:T −1 (x))]∥2 ]. To simplify notations, write W := WT , u := gT −1 (hW1:T −1 (x)), W := W T and u := EW1:T −1 [gT −1 (hW1:T −1 (x))]. Then, EW [∥W u − W u∥2 ] =

Ewi [(wiT u − wTi u)2 ] =

Ewi [(wiT u)2 − 2(wiT u)(wTi u) + (wTi u)2 ],

where wi is the vector corresponding to the ith row of W and wi is the vector corresponding to the ith row of W . Since Ewi [(wiT u)2 ] = σ 2 ∥u∥2 + (wTi u)2 , we get EW [∥W u − W u∥2 ] =

σ 2 ∥u∥2 + (wTi u)2 − 2(wTi u)(wTi u) + (wTi u)2

= dT σ 2 ∥u∥2 +

(wTi u − wTi u)2

= dT σ ∥u∥ + ∥W u − W u∥2 2

≤ dT σ 2 MT2 −1 + ∥W ∥22 ∥u − u∥2 .

Therefore, VarQ [hW1:T (x)] ≤ dT σ 2 MT2 −1 + ∥W T ∥22 VarQ [u] ≤ dT σ 2 MT2 −1 + ∥W T ∥22 ℓ2T −1 VarQ [hW1:T −1 (x)], where we used Lemma 6.2 for the last inequality. Using the induction hypothesis, we get VarQ [hW1:T (x)] ≤ dT σ 2 MT2 −1 + σ 2 ∥W T ∥22 ℓ2T −1

TX −1

2 dt Mt−1

= dT σ 2 MT2 −1 + σ 2

t=1

= σ2

T X

2 dt Mt−1

TY −1

2 dt Mt−1

TY −1

ℓ2t′ ∥W t′ +1 ∥22

t′ =t

t=1 TX −1

TY −2

ℓ2t′ ∥W t′ +1 ∥22

t′ =t

ℓ2t′ ∥W t′ +1 ∥22 .

t′ =t

t=1

■ Proposition 6.4 (Unbounded activation functions). Consider a feedforward fully connected neural network with T layers hW1:T (x) = WT gT −1 (WT −1 gT −2 (· · · g1 (W1 x))), where each non-linear function gt : Rdt → Rdt is ℓt -Lipschitz and satisfies gt (0) = 0. We let dT := C be the number of classes. Assume that ∥x∥ ≤ M0 , and let Q be an isotropic Gaussian distribution centered at W 1 , · · · , W T with covariance matrix given by σ 2 times the identity matrix. Then, 2

VarQ [hW1:T (x)] ≤ σ M02

T X

t−1 Y

ℓ2t′ σ 2 dt′ + ∥W t′ ∥22

! T −1 Y

t′ =1

t=1

ℓ2t′ ∥W t′ +1 ∥22

t′ =t

where the first product is equal to 1 if t = 1 and the second product is equal to 1 if t = T . Proof: Define recursively u0 := x,

ut := gt (Wt ut−1 ).

2 is replaced by The proof is almost identical to that of Proposition 6.3, but Mt−1

E∥ut−1 ∥2 ≤ M02

t−1 Y

ℓ2t′ σ 2 dt′ + ∥W t′ ∥22 .

t′ =1

This inequality is true since h

E∥ut−1 ∥2 ≤ ℓ2t−1 E EWt−1 ∥Wt−1 ut−2 ∥2

= ℓ2t−1 E dt−1 σ 2 ∥ut−2 ∥2 + ∥W t−1 ut−2 ∥2 h

≤ ℓ2t−1 E σ 2 dt−1 + ∥W t−1 ∥22 ∥ut−2 ∥2

= ℓ2t−1 σ 2 dt−1 + ∥W t−1 ∥22 E∥ut−2 ∥2

≤ ··· ≤ M02

t−1 Y

ℓ2t′ σ 2 dt′ + ∥W t′ ∥22 .

t′ =1

■ Propositions 6.3 and 6.4 control the variance term appearing in Lemma 6.1 for deep networks. The next two theorems combine this with layerwise smoothness to yield an explicit σ 2 -scaling upper bound on the Jensen gap of the loss. Theorem 6.5 (Bounded activation functions). Consider the same assumptions as in Proposition 6.3 and also assume that each non-linear function gt : Rdt → − Rdt is βt -smooth. Then, we have T X t σ2 X 2 |JenQ [L(hW1:T (x), y)]| ≤ βt du Mu−1 2 t=1 u=1

t−1 Y

ℓ2t′ ∥W t′ +1 ∥22

TY −1

ℓt′ +1 ∥W t′ +1 ∥2 ,

t′ =t

t′ =u

where the first product is equal to 1 if u = t and the second product is equal to 1 if t = T . Proof: Let gT (z) := L(z, y). The dependency on y does not matter for the proof. The β-smoothness of the loss function L(z, y) will be denoted by βT and the Lipschitz constant by ℓT . We will show by induction on the number of layers that |JenQ [gT (hWT (x))]| ≤

T X βt t=1

VarQ [hW1:t (x)]

TY −1

ℓt′ +1 ∥W t′ +1 ∥2 ,

t′ =t

where the product is equal to 1 if t = T . For T = 1, the result follows immediately from Lemma 6.1. Assume that the result is true for T − 1 layers. From Lemma 6.1 and the induction hypothesis, we have βT VarQ [hW1:T (x)] 2 βT ≤ ℓT ∥W T ∥2 ∥Jen[gT −1 (hW1:T −1 (x))]∥ + VarQ [hW1:T (x)] 2

|JenQ [gT (hW1:T (x))]| ≤ ℓT ∥JenQ [hW1:T (x)]∥ +

≤ ℓT ∥W T ∥2 =

TY −2 βt βT VarQ [hW1:t (x)] VarQ [hW1:T (x)] ℓt′ +1 ∥W t′ +1 ∥2 + 2 2 ′ t=1 t =t

TX −1

TY −1 βt βT VarQ [hW1:t (x)] VarQ [hW1:T (x)] ℓt′ +1 ∥W t′ +1 ∥2 + 2 2 t=1 t′ =t

T X βt t=1

VarQ [hW1:t (x)]

TY −1

ℓt′ +1 ∥W t′ +1 ∥2 .

t′ =t

The proof of the Theorem is now completed by using the upper bound on VarQ [hW1:t (x)] obtained in Proposition 6.3. ■ Theorem 6.6 (Unbounded activation functions). Consider the same assumptions as in Proposition 6.4 and also assume that each non-linear function gt : Rdt → Rdt is βt -smooth. Then, we have |JenQ [L(hW1:T (x), y)]| ≤

T X t σ 2 M02 X βt du 2 t=1 u=1

u−1 Y

ℓ2t′ σ 2 dt′ + ∥W t′ ∥22

t′ =1

t−1 Y t′ =u

ℓ2t′ ∥W t′ +1 ∥22

TY −1

ℓt′ +1 ∥W t′ +1 ∥2 ,

t′ =t

where the first product is equal to 1 if u = 1, the second product is equal to 1 if u = t, and the third product is equal to 1 if t = T . Proof: The proof is the same as that of Theorem 6.5, but using Proposition 6.4 instead of Proposition 6.3. ■ We now turn to generalization bounds for the Jensen gap itself, viewed as a function class indexed by w. 20

Generalization bound for the Jensen gap from Rademacher complexity

In the linear case, we can obtain a result from a simple contraction argument. We state a well known contraction lemma in the multi-class case next. Lemma 7.1 (Contraction inequality in the multi-class case [Maurer, 2016]). Let x1 , . . . , xn be fixed and let F be a class of functions f : X → RC with components fk . For each i ∈ {1, . . . , n}, let ψi : RC → R satisfy |ψi (u) − ψi (v)| ≤ Li ∥u − v∥2 , ∀u, v ∈ RC , for some constants Li > 0. Then, "

Eε sup

n X

εi ψi (f (xi ))

≤

√

2 Eεik sup

n X C X

εik Li fk (xi ) ,

f ∈F i=1 k=1

f ∈F i=1

where (εi ) and (εik ) are independent Rademacher variables. Proof: This is a slight extension to Corollary 4 of Maurer [2016] where we allow the Lipschitz constants to depend on i. Assume Li > 0 for all i. Define hi : RC → R by hi (z) := ψi (z/Li ). Then, each hi is 1-Lipschitz. Let G := {g : X → RC : ∃f ∈ F s.t. g(xi ) = Li f (xi ) ∀i}. For any f ∈ F , letting g ∈ G satisfy g(xi ) = Li f (xi ) gives hi (g(xi )) = ψi (f (xi )), hence sup

n X

εi ψi (f (xi )) = sup

f ∈F i=1

n X

εi hi (g(xi )).

g∈G i=1

Applying Maurer’s contraction inequality [Maurer, 2016] to the hi ’s yields h

Eε sup

n X

εi ψi (f (xi )) ≤

f ∈F i=1

√

2 Eεik sup

C n X X

εik gk (xi ) .

g∈G i=1 k=1

Finally, by the definition of G , sup

C n X X

εik gk (xi ) = sup

C n X X

εik Li fk (xi ).

f ∈F i=1 k=1

g∈G i=1 k=1

■ We can now bound the Rademacher complexity of the Jensen gap class in the linear case. Theorem 7.2. Let S = {(xi , yi )}ni=1 with xi ∈ Rd and yi ∈ {1, · · · , C}. Consider the linear multiclass score function hW (x) = W x with W ∈ RC×d and Θ := {W ∈ RC×d : ∥W ∥F ≤ R}. Assume that for any y, the map z 7→ L(z, y) is differentiable and β-smooth. For σ > 0, let Q be an isotropic Gaussian distribution with mean W and covariance matrix σ 2 ICd×Cd . Define

Fσ (W ; x, y) := L(hW (x), y) − EW ∼Q L(hW (x), y) . and let Fσ := {(x, y) 7→ Fσ (W ; x, y) : W ∈ Θ}. Then, the empirical Rademacher complexity of Fσ satisfies v √ u n X 2βRσC u t RS (Fσ ) ≤ ∥xi ∥4 . n i=1 In particular, if ∥xi ∥ ≤ M for all i, then √ RS (Fσ ) ≤

2βRσC M 2 √ . n

Proof: Let W ∈ Θ and let W = W + U , where U ∼ N (0, σ 2 ICd×Cd ). For each i, set zi = W xi ∈ RC and Ui = U xi ∈ RC , so that hW (xi ) = zi + Ui . By the first-order integral theorem, Z 1

L(zi + Ui , yi ) − L(zi , yi ) =

⟨∇z L(zi + tUi , yi ), Ui ⟩ dt,

and therefore

Z 1

Fσ (W ; xi , yi ) = −EU

⟨∇z L(zi + tUi , yi ), Ui ⟩ dt.

Using sup E ≤ E sup and sup RS (Fσ ) ≤

≤

sup, we obtain "

Z 1

Eε,U

n 1X sup εi − ⟨∇z L(zi + tUi , yi ), Ui ⟩ dt, W ∈Θ n i=1

where ε = (ε1 , · · · , εn ) ∈ {±1}n are Rademacher random variables. For fixed t and U1 , . . . , Un , define ψi (z) := −⟨∇z L(z + tUi , yi ), Ui ⟩. By β-smoothness of L(·, yi ), |ψi (z) − ψi (z ′ )| ≤ β ∥Ui ∥ ∥z − z ′ ∥, so ψi is (β∥Ui ∥)-Lipschitz. Applying Maurer’s vector contraction inequality (Lemma 7.1) to the class fW (x) = W x with Lipschitz constants Li = β∥Ui ∥, we obtain √

2β Eεik ,U n

RS (Fσ ) ≤

sup

C n X X

εik ∥Ui ∥ (W xi )k .

∥W ∥F ≤R i=1 k=1

The supremum over W can be obtained explicitly: sup

C n X X

εik ∥Ui ∥ (W xi )k = R

∥W ∥F ≤R i=1 k=1 (C)

where εi

n X

(C)

∥Ui ∥ εi x⊤ i

i=1

= (εi1 , . . . , εiC )⊤ ∈ RC . This is true since C n X X

εik ∥Ui ∥ (W xi )k =

i=1 k=1

n X

(C)

∥Ui ∥ (εi )⊤ W xi

i=1 n D X

(C)

W , ∥Ui ∥ εi x⊤ i

i=1

= W,

n X

(C)

∥Ui ∥ εi x⊤ i

i=1

E F

where ·, · denotes the Frobenius inner product. Therefore, the empirical Rademacher complexity is upper F bounded as follows: √ n X 2βR (C) RS (Fσ ) ≤ Eεik ,U ∥Ui ∥ εi x⊤ . i n F i=1 By Jensen’s inequality and independence of Rademacher random variables,

Eεik ,U

n X i=1

(C)

∥Ui ∥ εi x⊤ i

v u n u X ≤ tC EU [∥Ui ∥2 ] ∥xi ∥2 . i=1

This is true since Eε

n X

(C)

∥Ui ∥ εi x⊤ i

i=1

2 F

C X

Eε

∥Ui ∥∥Uj ∥εik εjk ⟨xi , xj ⟩

i,j

k=1 C X n X

∥Ui ∥2 ∥xi ∥2 = C

k=1 i=1

n X

∥Ui ∥2 ∥xi ∥2 .

i=1

Since Ui = U xi ∼ N (0, σ 2 ∥xi ∥2 IC ), we have EU ∥Ui ∥2 = Cσ 2 ∥xi ∥2 , and therefore Eεik ,U

n X

(C)

∥Ui ∥ εi x⊤ i

i=1

v u n uX ≤ σC t ∥xi ∥4 . i=1

Substituting into the previous bound gives √ RS (Fσ ) ≤ If ∥xi ∥ ≤ M for all i, then

v u n X 2βRσC u t ∥xi ∥4 .

i=1

4 4 i=1 ∥xi ∥ ≤ nM , and thus

√ RS (Fσ ) ≤

2βRσC M 2 √ . n ■

For bounding the Rademacher complexity of the Jensen gap class for non-linear neural networks, we will need more advanced techniques than a contraction argument. The next lemma is the key technical result. It bounds the pseudo-metric induced from the Jensen gap (defined in the lemma) with a peudo-metric involving the properties of the loss function and measures of sensitivity to noise (first order and second order) of the neural networks in the class. Lemma 7.3 (Bounding the metric induced by the Jensen gap). Let S = {(xi , yi )}ni=1 and let hw : X → RC be a neural network parameterized by w ∈ Θ ⊂ Rm . Assume that Θ is convex. Fix σ > 0 and let u ∼ N (0, Im ). For each i ∈ {1, . . . , n} define Fi (w) := L(hw (xi ), yi ) − Eu [L(hw+σu (xi ), yi )] , and the sample-dependent pseudo-metric dS (w1 , w2 ) :=

n X

!1/2 2

(Fi (w1 ) − Fi (w2 ))

i=1

Assume that for each y, the map z 7→ L(z, y) is differentiable, ℓ-Lipschitz and β-smooth. Assume moreover that, for each i, the map w 7→ hw (xi ) is twice continuously differentiable on Rm , and that the Gaussian expectations below are finite and may be differentiated under the expectation sign. Write Ji (w) := ∇w hw (xi ) ∈ RC×m ,

Hi,k (w) := ∇2w hw (xi ) k ∈ Rm×m .

Assume that there exist sample-dependent positive semi-definite matrices Gi ⪰ 0 such that, for all w ∈ Θ, Ji (w)⊤ Ji (w) ⪯ Gi . Define Z 1

Ai,σ := sup w∈Θ 0

Eu u⊤ Ji (w + tσu)⊤ Ji (w + tσu)u dt,

and assume that Ai,σ < ∞ for all i. For each w ∈ Θ, define the Gaussian averaged Hessian matrix Z 1

Bi,σ (w) := 0

" C X

# ⊤

⊤

Hi,k (w + tσu) uu Hi,k (w + tσu) dt.

k=1

Assume that there exist sample-dependent positive semi-definite matrices Bi,σ ⪰ 0 such that, for all w ∈ Θ, Bi,σ (w) ⪯ Bi,σ . Define the sample-dependent matrix MS,σ := 2σ 2

n X

β 2 Ai,σ Gi + ℓ2 Bi,σ .

i=1

Then, for all w1 , w2 ∈ Θ,

dS (w1 , w2 )2 ≤ (w1 − w2 )⊤ MS,σ (w1 − w2 ).

Proof: Fix i and abbreviate zi (w) := hw (xi ) and gi (w) := ∇z L(zi (w), yi ) ∈ RC . By the chain rule, ∇w L(zi (w), yi ) = Ji (w)⊤ gi (w). Differentiating under the expectation gives h

∇Fi (w) = Ji (w)⊤ gi (w) − Eu Ji (w + σu)⊤ gi (w + σu) . Add and subtract Eu [Ji (w)⊤ gi (w + σu)] to obtain

∇Fi (w) = Ji (w)⊤ gi (w) − Eu gi (w + σu) + Eu (Ji (w) − Ji (w + σu))⊤ gi (w + σu) . Fix v ∈ Rm and write ⟨∇Fi (w), v⟩ = T1,i (w, v) + T2,i (w, v) with T1,i (w, v) := ⟨gi (w) − Eu gi (w + σu), Ji (w)v⟩, T2,i (w, v) := Eu ⟨gi (w + σu), (Ji (w) − Ji (w + σu))v⟩. Then, (a + b)2 ≤ 2a2 + 2b2 gives ⟨∇Fi (w), v⟩2 ≤ 2T1,i (w, v)2 + 2T2,i (w, v)2 . We first bound T1,i . By Cauchy–Schwarz and β-smoothness of L(z, y), |T1,i (w, v)| ≤ ∥Ji (w)v∥ Eu ∥gi (w) − gi (w + σu)∥ ≤ β ∥Ji (w)v∥ Eu ∥zi (w) − zi (w + σu)∥. Using the fundamental theorem of calculus, zi (w + σu) − zi (w) = σ

Z 1

Ji (w + tσu) u dt, 0

so Jensen’s inequality gives Eu ∥zi (w + σu) − zi (w)∥2 ≤ σ 2

Z 1 0

Eu u⊤ Ji (w + tσu)⊤ Ji (w + tσu)u dt ≤ σ 2 Ai,σ .

Thus, q

Eu ∥zi (w + σu) − zi (w)∥ ≤ σ Ai,σ . Since ∥Ji (w)v∥2 = v ⊤ Ji (w)⊤ Ji (w)v ≤ v ⊤ Gi v, we obtain 2T1,i (w, v)2 ≤ 2β 2 σ 2 Ai,σ v ⊤ Gi v. We now bound T2,i . Since L(z, yi ) is ℓ-Lipschitz and differentiable, ∥gi (w)∥ ≤ ℓ, so by Cauchy–Schwarz and Jensen,

|T2,i (w, v)| ≤ Eu ∥gi (w + σu)∥ ∥(Ji (w + σu) − Ji (w))v∥ ≤ ℓ

Eu ∥(Ji (w + σu) − Ji (w))v∥2 .

Applying the fundamental theorem of calculus yields Ji (w + σu) − Ji (w) = σ

Z 1 0

where

∇2w hw+tσu (xi )[u] dt,

(Hi,1 (w′ )u)⊤   .. ∇2w hw′ (xi )[u] :=  . . ′ ⊤ (Hi,C (w )u) 



By Jensen’s inequality, ∥(Ji (w + σu) − Ji (w))v∥2 ≤ σ 2

Z 1 0

∇2w hw+tσu (xi )[u]v

dt.

For any w′ , the vector ∇2w hw′ (xi )[u]v ∈ RC has k-th coordinate u⊤ Hi,k (w′ )v. Therefore, C X 2 ∇2w hw′ (xi )[u]v = (u⊤ Hi,k (w′ )v)2 = v ⊤ k=1

C X

! ′ ⊤

⊤

′

Hi,k (w ) uu Hi,k (w ) v.

k=1

Consequently, Eu ∥(Ji (w + σu) − Ji (w))v∥2 ≤ σ 2 v ⊤ Bi,σ (w)v ≤ σ 2 v ⊤ Bi,σ v. Therefore, 2T2,i (w, v)2 ≤ 2ℓ2 Eu ∥(Ji (w + σu) − Ji (w))v∥2 ≤ 2ℓ2 σ 2 v ⊤ Bi,σ v. Combining the bounds gives, for all w ∈ Θ and all v ∈ Rm ,

⟨∇Fi (w), v⟩2 ≤ v ⊤ 2β 2 σ 2 Ai,σ Gi + 2ℓ2 σ 2 Bi,σ v. Now fix w1 , w2 ∈ Θ, set v = w1 − w2 , and define wt = w2 + tv. By the fundamental theorem of calculus, Fi (w1 ) − Fi (w2 ) =

Z 1

⟨∇Fi (wt ), v⟩ dt,

and Jensen’s inequality implies 2

(Fi (w1 ) − Fi (w2 )) ≤

Z 1 0

⟨∇Fi (wt ), v⟩2 dt.

Using the bound above yields

(Fi (w1 ) − Fi (w2 ))2 ≤ v ⊤ 2β 2 σ 2 Ai,σ Gi + 2ℓ2 σ 2 Bi,σ v. Summing over i gives 2

dS (w1 , w2 ) ≤ v

⊤

2σ

n X

β Ai,σ Gi + ℓ Bi,σ

i=1

■

which is the claimed bound.

It follows from Talagrand-type comparison inequalities [Talagrand, 2005] that we can bound the Rademacher complexity of the Jensen gap class from the trace of the matrix MS . The next two results are what we need to prove this fact. Proposition 7.4 (Talagrand comparison inequality [Vershynin, 2018, Cor. 8.5.6]). Let (Xt )t∈T be a mean-zero random process and (Yt )t∈T a mean-zero Gaussian process. Assume that for all t, s ∈ T , ∥Xt − Xs ∥ψ2 ≤ K∥Yt − Ys ∥L2 . Then, E sup Xt ≤ cK E sup Yt , t∈T

t∈T

where c > 0 is an absolute constant. For a real-valued random variable X, the L2 norm is defined as 1/2

∥X∥L2 := E[X 2 ]

The ψ2 norm of X is defined by "

X2 ∥X∥ψ2 := inf t > 0 : E exp 2 t n

≤2 .

Proposition 7.5. Let S = {(xi , yi )}ni=1 be a sample and let Θ := { w ∈ Rm : ∥w∥2 ≤ R }. Let f : Θ × (X × Y ) → R and define F := { (x, y) 7→ f (w, (x, y)) : w ∈ Θ }. Define the sample-dependent pseudo-metric n X

dS (w1 , w2 ) :=

f (w1 , (xi , yi )) − f (w2 , (xi , yi ))

!1/2

i=1

Assume there exists a sample-dependent positive semi-definite matrix MS ∈ Rm×m such that dS (w1 , w2 ) ≤

(w1 − w2 )⊤ MS (w1 − w2 )

Then, the empirical Rademacher complexity of F satisfies RS (F ) ≤ c

Rq Trace(MS ), n

where c > 0 is a constant. 26

∀w1 , w2 ∈ Θ.

Proof: The proof is a direct application of Proposition 7.4 together with a standard computation of the Gaussian width of an ellipsoid (see e.g. [Vershynin, 2018, Chapter 7]). Let ε1 , . . . , εn be independent Rademacher random variables and define Xw :=

n X

εi f w, (xi , yi ) .

i=1

Then, Eε [Xw ] = 0 for every w and i 1 h Eε sup Xw . n w∈Θ

RS (F ) =

For w1 , w2 ∈ Θ, set ∆i := f (w1 , (xi , yi )) − f (w2 , (xi , yi )) and Z := ni=1 εi ∆i . The random variable P Z is subgaussian with variance proxy ni=1 ∆2i = dS (w1 , w2 )2 . This is true since the moment generating function of Z satisfies P

Eε eλZ =

n Y

Eε eλεi ∆i =

i=1

n Y

cosh(λ∆i ) ≤

i=1

n Y

exp

λ 2 ∆2

i=1

n λ2 X

= exp

2 i=1

∆2i ,

u /2 for all u ∈ R. It follows that there exists a constant c > 0 such that where we used 0 q cosh(u) ≤ e

n 2 ∥Z∥ψ2 ≤ c0 i=1 ∆i = c0 dS (w1 , w2 ) (see for example exercice 2.40 from Vershynin [2018]). From our assumption on dS (w1 , w2 ), we therefore have

∥Xw1 − Xw2 ∥ψ2 ≤ c0 (w1 − w2 )⊤ MS (w1 − w2 ). In order to apply the Talagrand comparison inequality, we need to specify a mean-zero Gaussian process (Yw )w∈Θ . Let g ∼ N (0, Im ) and define the Gaussian process 1/2

Yw := ⟨g, MS w⟩,

w ∈ Θ.

For ∆ := w1 − w2 and using E[gg ⊤ ] = Im , we get 1/2

∥Yw1 − Yw2 ∥2L2 = E g ⊤ MS ∆

1/2

= E ∆⊤ MS gg ⊤ MS ∆ = ∆⊤ MS ∆.

Hence, ∥Yw1 − Yw2 ∥L2 = (w1 − w2 )⊤ MS (w1 − w2 ). We can therefore apply the Talagrand comparison inequality with K = c0 . Thus, there exists a constant c1 > 0 such that Eε sup Xw ≤ c1 c0 Eg sup Yw . w∈Θ

w∈Θ

Furthermore, 1/2

Eg sup Yw = R E∥MS g∥2 ≤ R

w∈Θ

1/2

E∥MS g∥22 = R

Trace(MS ),

Combining the above inequalities and dividing by n yields RS (F ) =

1 c1 c0 q Rq Eε sup Xw ≤ R Trace(MS ) = c Trace(MS ), n w∈Θ n n

with c := c1 c0 > 0 a constant.

■

We can now provide an upper bound on the Rademacher complexity of the Jensen gap class for neural networks. 27

Corollary 7.6 (Rademacher complexity of the Jensen-gap class). Let S = {(xi , yi )}ni=1 and let Θ := { w ∈ Rm : ∥w∥2 ≤ R }. Fix σ > 0 and let Fσ be the Jensen gap class for the loss function L(hw (x), y). Assume that for each y, the map z 7→ L(z, y) is differentiable, ℓ-Lipschitz and β-smooth. Assume moreover that the hypotheses of Lemma 7.3 hold. Define JS,σ :=

n 1X Ai,σ Trace(Gi ), n i=1

HS,σ :=

n 1X Trace(Bi,σ ). n i=1

Then, the empirical Rademacher complexity of Fσ satisfies Rσ q 2 RS (Fσ ) ≤ c √ β JS,σ + ℓ2 HS,σ , n where c > 0 is a universal constant. Proof: By Lemma 7.3, the pseudo-metric induced by the Jensen gap class is dominated by the quadratic form associated with MS,σ = 2σ 2

n X

β 2 Ai,σ Gi + ℓ2 Bi,σ .

i=1

Applying Proposition 7.5 gives RS (Fσ ) ≤ c Since

Rq Trace(MS,σ ). n

Trace(MS,σ ) = 2σ 2 n β 2 JS,σ + ℓ2 HS,σ , √ the result follows after absorbing the factor 2 into the universal constant c.

■

Remark 7.7. As a sanity check of the result, consider the case of linear hypothesis classes (hW (x) = W x). Then, the Hessian term HS,σ is zero and the Jacobian term JS,σ is easily seen to be bounded by C 2 M 4 if ||x|| ≤ M . Therefore, Corollary 7.6 implies RS (Fσ ) ≤ c

RσβCM 2 √ . n

This is exactly the same result as the one obtained in Theorem 7.2 up to a constant. Remark 7.8 (Explicit constant). Corollary 7.6 leaves us with an unspecified universal constant c. In the √ present setting, it is possible to alternatively obtain the explicit constant c = π, which is useful for numerical evaluation. First, we have the following comparison between the Rademacher and Gaussian complexity: r

Eε sup Xw ≤ w∈Θ

n X π Eg sup gi f (w, (xi , yi )). 2 w∈Θ i=1

This follows by writing gi = εi |gi | and applying Jensen’s inequality together with E|gi | = for every w1 , w2 ∈ Θ, the L2 norm satisfies n X

gi f (w1 , (xi , yi )) − f (w2 , (xi , yi ))

i=1

= dS (w1 , w2 ).

2/π. Second,

Third, by assumption, this quantity is upper bounded by the L2 norm of Yw1 − Yw2 . Finally, by the Gaussian comparison inequality (Sudakov–Fernique; see [Vershynin, 2018, Theorem 7.2.8]), Eg sup

n X

w∈Θ i=1

gi f (w, (xi , yi )) ≤ Eg sup Yw , w∈Θ

which yields the result after considering the factor

√

2 that was absorbed into the universal constant c.

We are now ready to state and prove the main result of this section. Proposition 7.9 (Uniform generalization bound for the Jensen-gap class). Let S = {(xi , yi )}ni=1 ∼ Dn and let Θ := { w ∈ Rm : ∥w∥2 ≤ R }. Fix σ > 0 and let Q denote an isotropic Gaussian distribution Q := N (w, σ 2 Im ),

w ∈ Θ.

Consider the same assumptions as in Corollary 7.6. Assume moreover that there exists B > 0 such that for all (x, y) and all w ∈ Θ, |JenQ L(hw (x), y) | ≤ σ 2 B. Then, for any δ ∈ (0, 1), with probability at least 1 − δ over S ∼ Dn , we have uniformly for all w ∈ Θ, h

E(x,y)∼D JenQ(L(hw (x), y)) ≤

n 1X JenQ(L(hw (xi ), yi )) n i=1

Rσ q 2 β JS,σ + ℓ2 HS,σ + 8σ 2 B + 2c √ n

2 ln(4/δ) , n

where c > 0 is an absolute constant. Proof: Using Theorem 26.5 from Shalev-Shwartz and Ben-David [2014] and Corollary 7.6, for any δ ∈ (0, 1), with probability at least 1 − δ over S ∼ Dn , we have uniformly for all w ∈ Θ, h

E(x,y)∼D JenQ(L(hw (x), y)) ≤

n 1X JenQ(L(hw (xi ), yi )) n i=1

s 2

+ 2 RS (Fσ ) + 8σ B

2 ln(4/δ) n

n 1X ≤ JenQ L(hw (xi ), yi ) n i=1

Rσ q 2 + 2c √ β JS,σ + ℓ2 HS,σ + 8σ 2 B n

2 ln(4/δ) , n ■

concluding the proof.

If needed, a standard argument can be used to obtain a result holding uniformly over a set of standard deviations {σi }.

Proposition 7.10 (Uniform generalization bound on {σi }i≥1 ). Let S = {(xj , yj )}nj=1 ∼ Dn and let Θ := { w ∈ Rm : ∥w∥2 ≤ R }. Fix σmax > 0 and for i ≥ 1 define σi := 2 1−i σmax . For w ∈ Θ and i ≥ 1, let Qw,σi := N (w, σi2 Im ). Assume the same conditions as in Corollary 7.6. Assume moreover that there exists B > 0 such that for all (x, y), all w ∈ Θ and all i ≥ 1, |JenQw,σi L(hw (x), y) | ≤ σi2 B. Then, for any δ ∈ (0, 1), with probability at least 1 − δ over S ∼ Dn , we have uniformly for all i ≥ 1 and all w ∈ Θ, h

E(x,y)∼D JenQw,σi L(hw (x), y)

≤

n 1X Rσi q 2 JenQw,σi L(hw (xj ), yj ) + 2c √ β JS,σi + ℓ2 HS,σi n j=1 n

+ 8σi2 B

4 ln(i) + 2 ln(8/δ) . n

Proof: This is a standard union bound argument. For fixed σ > 0 and η ∈ (0, 1), define n 1X Rσ q 2 JenQw,σ L(hw (xj ), yj ) + 2c √ B(σ, η; w) := β JS,σ + ℓ2 HS,σ + 8σ 2 B n j=1 n

2 ln(4/η) . n

By Proposition 7.9, for every fixed σ and η, h

PS ∀w ∈ Θ : E JenQw,σ L(hw (x), y)

≤ B(σ, η; w) ≥ 1 − η.

For i ≥ 1, choosing η = δi := δ/(2i2 ) and σ = σi , we then have

PS ∀w ∈ Θ : E JenQw,σi L(hw (x), y)

≤ B(σi , δi ; w) ≥ 1 − δi .

Taking a union bound over i ≥ 1 and using i≥1 δi ≤ δ gives that with probability at least 1 − δ, the inequality holds simultaneously for all i ≥ 1 and all w ∈ Θ. It remains to simplify the confidence term: P

δi

= ln

8i2

= ln

+ 2 ln(i). ■

Remark 7.11 (From Gaussian averaged controls to simpler global controls). The quantities Ai,σ and Bi,σ appearing above are averaged along the perturbation path w + tσu. This is the appropriate form for ordinary Gaussian posteriors, since the perturbation is not confined to the original parameter set Θ. However, in settings where the posterior perturbation has bounded support, we can obtain a simpler expression. Suppose e in the sense that that the perturbed parameter is supported in a larger parameter set Θ, e w + tσu ∈ Θ

for all w ∈ Θ, t ∈ [0, 1], 30

almost surely. Assume also that E[uu⊤ ] ⪯ Im , and that, for each i, there exists a positive semidefinite matrix Gi ⪰ 0 such that e Ji (v)⊤ Ji (v) ⪯ Gi for all v ∈ Θ. Then, the Gaussian averaged Jacobian quantity satisfies Z 1

Ai,σ = sup w∈Θ 0

Eu u⊤ Ji (w + tσu)⊤ Ji (w + tσu)u dt

≤ Eu [u⊤ Gi u] = Tr Gi E[uu⊤ ] ≤ Tr(Gi ).

Consequently, JS,σ =

n n 1X 1X Ai,σ Tr(Gi ) ≤ Tr(Gi )2 . n i=1 n i=1

Similarly, suppose that there exist positive semidefinite matrices Mi ⪰ 0 such that C X

Hi,k (v)⊤ Hi,k (v) ⪯ Mi

e for all v ∈ Θ.

k=1

Then, the proof of Lemma 7.3 can be modified by using this global Hessian control directly in the estimate of the second order term. In that setting, the Hessian contribution in the final Rademacher bound becomes HS :=

n 1X Tr(Mi ). n i=1

Therefore, under bounded support perturbations, Corollary 7.6 implies the simpler bound Rσ q 2 RS (Fσ ) ≤ c √ β JS + ℓ2 HS , n where JS :=

n 1X Tr(Gi )2 , n i=1

HS :=

n 1X Tr(Mi ). n i=1

For ordinary Gaussian posteriors, the perturbation has unbounded support, so the bounded support simplification does not apply directly. A possible extension would be to use a localization argument: control e that contains the perturbation path with high probability and then the Jacobian and Hessian on a larger set Θ bound the contribution of the complementary event separately. This would lead to a global bound as above together with a residual term. The practical regularizer introduced in Section 9 takes a much simpler route. Instead of keeping the supremum over parameters and the Gaussian average along the perturbation path, it evaluates empirical Jacobian and Hessian quantities at the current effective parameters. Thus, it should be viewed as a convenient proxy inspired by the structure of the bound, rather than as a direct evaluation of JS,σ and HS,σ .

Bound comparisons for linear classifiers

When the loss function is bounded, both the bounded and unbounded variants of the derandomized PACBayes bounds can be applied. We first introduce a convenient bounded smooth multi-class loss obtained by extending the sigmoid loss.

Lemma 8.1 (Surrogate multiclass sigmoid loss function). Fix R > 0 and C > 2, and let σ(z) := (1+e−z )−1 . For z ∈ RC and y ∈ {1, . . . , C}, define L(z, y) :=

σ(zk − zy ).

k̸=y

Let



mR := (C − 1)σ −R



C  , C −1

and a(R) :=

1 qR := + (C − 2)σ −R 2

1 , qR − m R

C , 2(C − 2)

b(R) := −a(R) mR .

Define the surrogate loss ΦR (z, y) := a(R)L(z, y) + b(R). Then the following hold: (i) On the domain ∥z∥ ≤ R: L0-1 (z, y) ≤ ΦR (z, y). (ii) The infimum of ΦR on the domain ∥z∥ ≤ R equals 0, whereas on the domain RC it equals b(R). (iii) The supremum of ΦR on the domain ∥z∥ ≤ R equals  s

a(R)(C − 1) 2σ R



C  −1 , C −1

whereas on the domain RC it equals  s

a(R)(C − 1)σ R



C  . C −1

(iv) ΦR is ℓR -Lipschitz on the domain RC with a(R) q ℓR = C(C − 1). 4 (v) ΦR is βR -smooth on the domain RC with βR ≤

a(R) C √ . 6 3

Proof: Fix y. We start by proving that the infimum of ΦR on the domain ∥z∥ ≤ R equals 0. At a minimizer of L(z, y), we must have zy ≥ zk for k ̸= y (this can be seen by a simple perturbation argument). We may therefore restrict the optimization to the set B(0, R) ∩ {z : zy ≥ zk for all k ̸= y}. This set is convex. Moreover, on this domain the arguments of σ satisfy zk − zy ≤ 0, and since σ is convex on (−∞, 0], the function X L(z, y) = σ(zk − zy ) k̸=y

is convex on this domain. Both the objective and the constraint are invariant under permutations of the coordinates {zk }k̸=y . Therefore, if z is a minimizer, any permutation of the incorrect-class coordinates is also a minimizer. Averaging over all such permutations gives another feasible point satisfying (∀k ̸= y)

zk = t

for some t ∈ R. By convexity of L(·, y) on the feasible set, this averaged point achieves a value of the objective no larger than the original one. Therefore, there exists a minimizer with all incorrect-class coordinates equal. The optimization problem thus reduces to min (C − 1)σ(t − s)

s2 + (C − 1)t2 ≤ R2 ,

subject to

s,t∈R

s ≥ t.

Since σ is increasing, this is equivalent to max (s − t)

s2 + (C − 1)t2 ≤ R2 ,

subject to

s,t∈R

s ≥ t.

The solution of this problem can be obtained by using Lagrange multipliers. The infimum of L(z, y) is then found to be given by s C (C − 1)σ − R = mR C −1 and (ii) for the bounded domain follows. For the unbounded domain, the result is obtained by observing that the infimum of L(z, y) is 0 on RC . Applying the same argument to −L(z, y) allows to find the supremum of the function L(z, y) on the domain ∥z∥ ≤ R. It is given by s

(C − 1)σ R

C . C −1

Substituting into the expression for ΦR (z, y) and simplifying proves (iii) for the bounded domain. For the unbounded domain RC , the result follows from observing that the supremum of L(z, y) is then C − 1. We now prove (i). If L0-1 (z, y) = 1, then zk ≥ zy for some k ̸= y, so σ(zk − zy ) ≥ 21 . Minimizing the remaining terms under ∥z∥ ≤ R gives 1 L(z, y) ≥ + (C − 2)σ −R 2

C 2(C − 2)

= qR

(this can be obtained by the same argument as in the proof of (ii)). Therefore, ΦR (z, y) = a(R)(L(z, y) − mR ) ≥ 1, concluding the proof of (i). In order to prove (iv), we compute the gradient of L(z, y): ∇z L(z, y) =

σ ′ (zk − zy )(ek − ey ).

k̸=y

On one hand, the norm of the gradient evaluated at 0 is equal to 41 2

∥∇z L(z, y)∥ =

k̸=y

′

σ (zk − zy ) + 

C(C − 1). On the other hand,

2

 X

′

σ (zk − zy ) ≤ (C − 1)

k̸=y

1 1 + (C − 1) 16 4

C(C − 1) , 16

where we used that 0 ≤ σ ′ (x) ≤ 1/4. We conclude that the Lipschitz constant of L(z, y) is equal to p 1 4 C(C − 1). Multiplying by a(R) then gives the Lipschitz constant of ΦR . Finally, in order to prove (v), we compute the Hessian of L(z, y): ∇2z L(z, y) =

σ ′′ (zk − zy )(ek − ey )(ek − ey )⊤ .

k̸=y

This Hessian has a convenient simple form. We get the following upper bound on its spectral norm: ∥∇2z L(z, y)∥2 ≤ max |σ ′′ (zk − zy )| · ∥ k̸=y

(ek − ey )(ek − ey )⊤ ∥2 .

k̸=y

The eigenvalues and eigenvectors of k̸=y (ek − ey )(ek − ey )⊤ are straightforward to obtain. We have the eigenvalue 0 with eigenvector 1, an eigenvalue C with eigenvector v = (1, . . . , 1, −(C − 1) , 1, . . . , 1). P

}

y-th coordinate

Also, the subspace defined by X

vy = 0,

vk = 0

k̸=y

is an eigenspace of dimension C − 2 associated with an eigenvalue of 1. We conclude that the spectral P 1 norm of k̸=y (ek − ey )(ek − ey )⊤ is equal to C. Multiplying by a(R) and using supx∈R |σ ′′ (x)| = 6√ 3 concludes the proof. ■ In Figure 1, we compare the generalization bound terms obtained from the unbounded derandomized PAC-Bayes bound of Theorem 4.1 with those obtained from the bounded derandomized PAC-Bayes bound of Theorem 5.2, both applied to the multi-class sigmoid surrogate of Lemma 8.1. We set n = 100000, d = 50 and δ = 0.05, and vary R over the interval [0.1, 1]. The bounded version gives a looser bound for very small values of R, but becomes substantially tighter than the unbounded version as R increases. This behavior reflects, in part, the less favorable dimensional dependence of the unbounded bound. The unbounded bound is tighter only in a restricted regime of very small parameter norms and low dimension. Outside this regime, when both results are applicable, the bounded version should be preferred. We next compare our bounded derandomized PAC-Bayes bound with a Rademacher complexity bound for the same class of linear predictors. The Rademacher complexity bound is given by the following proposition. Proposition 8.2. Let S = {(xi , yi )}ni=1 . Assume that ∥x∥ ≤ M and consider the hypothesis class F := x 7→ W x ∈ RC : ∥W ∥F ≤ R .

Let L(z, y) take values in [0, A] and assume that, for every y, the map z 7→ L(z, y) is ℓ-Lipschitz. Then, with probability at least 1 − δ over S ∼ Dn , we have uniformly for all W with ∥W ∥F ≤ R, s √ RM C 2 ln(4/δ) LD (hW ) ≤ LS (hW ) + 2 2 ℓ √ + 4A . n n

√

Proof: Immediate from Maurer’s vector-contraction inequality applied to p L(·, y), Theorem 26.5 (item 2) of Shalev-Shwartz and Ben-David [2014], and the bound RS (F ) ≤ RM C/n for the linear class with ∥W ∥F ≤ R. ■ The relative improvement of our bound over the Rademacher bound is shown in Figure 2. Our bound is better for moderate values of R and then becomes similar to the Rademacher bound for much larger values of R.

(a) C = 3

(b) C = 10

Figure 1: Comparison between the bounded and unbounded derandomized PAC-Bayes generalization bound terms for the multi-class sigmoid loss.

(a) C = 3

(b) C = 10

Figure 2: Relative improvement of our derandomized PAC-Bayes bound over the Rademacher complexity bound as a function of R ∈ [2, 100] for the multi-class sigmoid loss.

A Regularizer Inspired by Our Theory for Batch-Normalized Networks

The Rademacher complexity bound for the Jensen-gap class obtained in our theory (see Corollary 7.6 and Remark 7.11) motivates data-dependent quantities that can be used as regularizers for neural networks. Rather than attempting to compute a fully faithful version of the quantity appearing in the bound, we evaluate a local and computationally tractable proxy at the current network parameters during training. Let SB denote the current training minibatch of size B, and let SB ′ ⊆ SB denote a possibly smaller minibatch of size B ′ used to estimate the regularizer for computational efficiency. We define JH(w; SB ′ ) :=

β 2 J(w; SB ′ )2 + ℓ2 H(w; SB ′ ),

where

′

B 1 X J(w; SB ′ ) := ′ ∥Ji (w)∥2F B i=1

and

′

H(w; SB ′ ) :=

B X C 1 X ∥Hi,k (w)∥2F . B ′ i=1 k=1

The constants ℓ and β denote the Lipschitz and smoothness constants of the loss with respect to the network output. For batch-normalized networks, we assume that each batch-normalization layer is applied before the nonlinearity. To remain close to the setting of the theoretical results, we work with an effective parametrization in which each batch-normalization layer is folded into the preceding affine layer. Indeed, for fixed batchnormalization statistics, batch normalization acts as an affine transformation of the pre-activation. Its composition with the preceding affine map can therefore be represented as a single effective affine map. More precisely, consider an affine layer followed by batch normalization, zt = Wt ut−1 + bt ,

ut = gt (BNt (zt )).

Equivalently, we absorb the bias into an augmented weight matrix by defining !

ūt−1 :=

ut−1 , 1

W̄t := Wt bt ,

so that zt = Wt ut−1 + bt = W̄t ūt−1 . Let µt,B ′ and vt,B ′ denote the empirical mean and variance of zt . For convolutional layers, these statistics are computed channelwise over both the batch and spatial dimensions. If the batch-normalization layer has affine parameters γt and δt , then z − µt,B ′ BNt (z) = γt ⊙ √ + δt , vt,B ′ + εt where ⊙ denotes componentwise multiplication, and the division and square root are also taken componentwise. Define γt st,B ′ := √ . vt,B ′ + εt Then, the affine map followed by batch normalization can be written as a single effective affine map BNt (zt ) = W̄t,eff,B ′ ūt−1 , where

W̄t,eff,B ′ := Diag(st,B ′ )Wt st,B ′ ⊙ (bt − µt,B ′ ) + δt . For convolutional layers, Diag(st,B ′ )Wt means that each output channel of the convolutional kernel is multiplied by the corresponding batch-normalization scale. In the augmented notation, the final column of W̄t,eff,B ′ represents the corresponding effective bias, which is shared across spatial locations. We denote by

weff,B ′ = W̄t,eff,B ′ t the collection of all such effective affine parameters. Layers that are not followed by batch normalization are included unchanged in this collection. The regularizer is computed with respect to the effective parametrization weff,B ′ . In other words, the Jacobian and Hessian terms are formed in the effective coordinates and evaluated at the effective parameters induced by the current network weights. The parameters being optimized remain the original weights w. The gradient of the regularized objective is backpropagated through the map

w 7→ weff,B ′ (w). We emphasize that the batch statistics µt,B ′ and vt,B ′ are not treated as constants: they depend also on w and gradients are propagated through this dependence as well. Since, for any matrix A, ∥A∥2F = Tr(AA⊤ ) = Ev v ⊤ AA⊤ v = Ev ∥A⊤ v∥22 , for any random vector v satisfying E[vv ⊤ ] = I, the squared Frobenius norms in J(weff,B ′ , SB ′ ) and H(weff,B ′ , SB ′ ) can be estimated using random matrix-vector products. In practice, this only requires Jacobian-vector and Hessian-vector products, and avoids explicitly forming or storing the full Jacobian or Hessian matrices. To estimate the Jacobian term, we sample M independent random vectors v1 , . . . , vM in the output space of the minibatch score vector hweff,B′ (x1 ), . . . , hweff,B′ (xB ′ ) , and compute

∇weff,B′

E 1 D √ vm , hweff,B′ (x1 ), . . . , hweff,B′ (xB ′ ) , B′

m = 1, . . . , M.

The average of the squared norms of these quantities gives a stochastic estimate of the corresponding squared Frobenius norm. To estimate the Hessian term, for each m, we additionally sample an independent random vector um in parameter space and differentiate, with respect to weff,B ′ , the scalar product between the vector-Jacobian product above and um . This yields the required Hessian-vector product without explicitly forming the Hessian. During training, these stochastic estimates are kept in the computational graph, so PyTorch autograd can differentiate through the vector-Jacobian and Hessian-vector products and optimize the resulting regularized objective. We train an eight-layer convolutional neural network on CIFAR-10, where the eight layers consist of six convolutional layers and two fully connected layers. Each convolutional layer and the first fully connected layer are followed by a BatchNorm layer and a centered Softplus activation. The loss function is the cross-entropy and training is performed with Adam, using a cosine annealing learning-rate schedule preceded by a linear warm-up phase of 3 epochs. The total number of epochs is set to 40, except in the experiments that adjust the training time as a function of the batch size. In that case, for a batch size B ∈ {256, 512, 1024, 2048, 4096}, we use q 40 B/256

epochs. For each batch size, we first tune the learning rate for the baseline model. We then keep this learning rate fixed and tune only the regularization coefficient for the JH-regularized model. The learning rate grid consists of 10 logarithmically spaced values between 10−3 and 10−1 , generated using np.geomspace. The regularization grid consists of 10 logarithmically spaced values between 10−5 and 5 × 10−4 , except for the JH(w/∥w∥; SB ′ ) method in the first experiment. For this method, the appropriate search grid consisted of 10 logarithmically spaced values between 10−7 and 5 × 10−6 . Hyperparameters are selected using validation accuracy on 5000 examples and the final selected configurations are rerun over three seeds. In all experiments, the regularizer is computed on a subset minibatch of size B ′ = 50 with M = 4 random vectors except for the experiments reported in Table 1. In the first experiment, we compare four parametrizations of the JH regularizer with the unregularized cross-entropy baseline. The first version computes JH with respect to the effective weights weff,B ′ , as described in this section. The second computes JH with respect to the original weights w, while the third also includes the affine parameters of the BatchNorm layers. The fourth computes JH with respect to layerwise normalized weights, where the weights of every layer of the network are replaced by Wt /∥Wt ∥F . We denote 37

this method by JH(w/∥w∥; SB ′ ), where w/∥w∥ is used as shorthand for the collection {Wt /∥Wt ∥F }t . Figure 5 shows the results across batch sizes. Only the effective-weight version, JH(weff,B ′ ; SB ′ ), and the layerwise normalized-weight version, JH(w/∥w∥; SB ′ ), meaningfully improve over the baseline. This highlights the importance of choosing a parametrization that is compatible with the effective function implemented by networks with BatchNorm layers. Remark 9.1. Jacobian and Hessian regularizers have been studied as training objectives, including regularization in input space [Sokolić et al., 2017, Varga et al., 2017, Cui et al., 2022] and Hessian trace regularization with respect to the model parameters [Liu et al., 2022]. To our knowledge, previous approaches based on curvature or sharpness for BatchNorm networks define these quantities with respect to the original weights or to normalized or scale invariant parameterizations of these weights [Rangamani et al., 2021, Tsuzuku et al., 2020, Yi et al., 2019, Lyu et al., 2022]. In contrast, we compute the regularizer with respect to the BatchNorm effective weights weff,B ′ . Such folding of the BatchNorm layer into the adjacent affine weights is used in the quantization and inference literature [Jacob et al., 2018, Nagel et al., 2021], where the goal is to deploy the same trained function more efficiently. In our case, the folding is used for a different purpose: it defines the coordinate system in which the regularizer is computed during training. Moreover, the effective weights are batch dependent because they are constructed using the current regularizer minibatch statistics rather than fixed test time BatchNorm statistics. In the second experiment, we further investigate whether JH(weff,B ′ ; SB ′ ) can mitigate the degradation in performance sometimes observed when increasing the batch size. We compare the baseline and the JH-regularized model under two training-time protocols: the fixed 40-epoch protocol and the variable-epoch p protocol described above, in which the number of epochs is scaled by B/256. We perform this comparison both on clean CIFAR-10 and under 20% uniform label noise (with probability 0.2, each label is replaced by a uniformly sampled incorrect class). The results are shown in Figure 3 for the clean-label setting and in Figure 4 for the label-noise setting. We first observe that the regularizer leads to larger absolute gains over the baseline in the label-noise setting than in the clean-label setting. This is expected since label noise exacerbates overfitting, thereby creating more room for the regularizer to improve generalization. In most cases, increasing the number of epochs benefits both the baseline and the JH-regularized model. The main exception occurs under label noise at batch size 4096, where the fixed-epoch JH run performs unusually well. We conjecture that this corresponds to an early-stopping-like regime, which may prevent excessive adaptation to the corrupted labels. Under label noise, when the number of epochs is increased according to the variable-epoch protocol, the larger batch sizes even outperform batch size 256. On clean data, the baseline performance deteriorates more rapidly as the batch size increases compared to the JH-regularized model. Overall, these results suggest that JH(weff,B ′ ; SB ′ ) is especially beneficial in regimes where large batch training or noisy labels deteriorate performance. Finally, we investigate the effect of the regularizer minibatch size B ′ and the number M of random vectors used to estimate the Jacobian and Hessian terms. Table 1 reports the results under the variable-epoch protocol with B = 4096. Increasing B ′ led to a small improvement in test accuracy, while increasing M beyond 4 did not provide a clear additional benefit. Remark 9.2. A natural idea suggested by the generalization bounds would be to combine the JH regularizer with a norm penalty on the effective weights weff,B . However, based on our preliminary experiments, this did not meaningfully improve performance compared with using only the JH regularizer in our experimental setting. In some sense, the effective parameters weff,B are not arbitrary because of the BatchNorm layers. Indeed, BatchNorm induces some control over the scale of the inputs fed to the nonlinearities, although this control is data-dependent and comes with the caveat that the affine BatchNorm parameters can partially undo it. This type of control may already be sufficient in some practical settings to make additional norm control unnecessary. We leave a more thorough investigation of these considerations to future work. 38

Table 1: CIFAR-10 test accuracy under the variable-epoch protocol with batch size B = 4096. We compare the baseline with JH-regularized models using different regularizer minibatch sizes B ′ and different numbers M of random vectors. Results are reported as mean ± standard deviation over three seeds. Method

B′

Test accuracy (%)

Baseline JH(weff,B ′ ; SB ′ ) JH(weff,B ′ ; SB ′ ) JH(weff,B ′ ; SB ′ ) JH(weff,B ′ ; SB ′ ) JH(weff,B ′ ; SB ′ )

– 50 50 50 256 1024

– 1 4 16 4 4

78.84 ± 0.21 81.19 ± 0.43 81.46 ± 0.46 81.40 ± 0.18 81.68 ± 0.37 81.73 ± 0.11

Remark 9.3. Unlike a regularizer built from the Hessian of the labeled loss, the JH regularizer is label-free: it is computed from the Jacobian and Hessian of the score map with respect to the (effective) parameters. Consequently, JH can also be evaluated on unlabeled inputs, making it potentially suitable as an auxiliary regularizer in settings where unlabeled data are available, such as semi-supervised or unsupervised learning. Future research could investigate this direction.

Figure 3: CIFAR-10 test accuracy as a function of the batch size for the baseline and the JH-regularized model. The fixed 40-epoch protocol is compared with the variable-epoch protocol where the number of p epochs is scaled by B/256. Error bars indicate the standard deviation over three seeds.

Figure 4: Clean CIFAR-10 test accuracy under 20% uniform label noise in the training and validation labels. The JH-regularized model is compared with the baseline under p both the fixed 40-epoch protocol and the variable-epoch protocol where the number of epochs is scaled by B/256. Error bars indicate the standard deviation over three seeds. 40

Figure 5: CIFAR-10 test accuracy as a function of the training batch size B for the baseline and four variants of the JH regularizer, estimated using a regularizer minibatch of size B ′ = 50. Among the tested variants, only when the regularizer is computed with respect to the effective weights or with respect to the normalized weights does the performance consistently and meaningfully improve over the baseline. Error bars indicate the standard deviation over three seeds.

Conclusion

We introduced a smoothness based approach to PAC-Bayes derandomization. The main message is that the passage from a randomized Gibbs predictor to the deterministic predictor at the posterior mean can be isolated as a separate generalization problem, namely bounding the generalization gap of the Jensen gap class. This viewpoint makes it possible to combine PAC-Bayes control of the randomized predictor with data dependent control of the derandomization penalty. Controlling this derandomization term through Rademacher complexity naturally brings in Jacobian and Hessian quantities of the score map. An important direction for future work is to obtain sharper high probability bounds for the Jensen gap class. In particular, local Rademacher complexity bounds could lead to tighter bounds than those obtained here. Another promising direction is an algorithmic stability analysis of the Jensen gap class, which could provide a different route to controlling the derandomization penalty and clarify its behavior under a given optimization algorithm.

Acknowledgements The authors thank Mathieu Bazinet and Pascal Germain for helpful discussions on PAC-Bayes theory. This research was enabled in part by support provided by Calcul Québec and the Digital Research Alliance of Canada.

References Pierre Alquier, James Ridgway, and Nicolas Chopin. On the properties of variational approximations of gibbs posteriors. Journal of Machine Learning Research, 17(239):1–41, 2016. Arindam Banerjee, Tiancong Chen, and Yingxue Zhou. De-randomized pac-bayes margin bounds: Applications to non-convex and non-smooth predictors. CoRR, abs/2002.09956, 2020. URL https: //arxiv.org/abs/2002.09956. Fergus Immanuel Biggs and Benjamin Guedj. On margins and derandomization in pac-bayes. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics (AISTATS), 2022. Ioar Casado, Luis A. Ortega, Aritz Pérez, and Andrés R. Masegosa. PAC-Bayes-Chernoff bounds for unbounded losses. In Advances in Neural Information Processing Systems, volume 37, 2024. URL https://openreview.net/forum?id=CyzZeND3LB. Olivier Catoni. PAC-Bayesian Supervised Classification: The Thermodynamics of Statistical Learning, volume 56 of IMS Lecture Notes–Monograph Series. Institute of Mathematical Statistics, Beachwood, Ohio, 2007. doi: 10.1214/074921707000000391. Eugenio Clerico, Tyler Farghly, George Deligiannidis, Benjamin Guedj, and Arnaud Doucet. Generalisation under gradient descent via deterministic PAC-Bayes. In Gautam Kamath and Po-Ling Loh, editors, Proceedings of The 36th International Conference on Algorithmic Learning Theory, volume 272 of Proceedings of Machine Learning Research, pages 349–389. PMLR, 24–27 Feb 2025. URL https: //proceedings.mlr.press/v272/clerico25a.html. Chenwei Cui, Zehao Yan, Guangshen Liu, and Liangfu Lu. Generalizing and improving Jacobian and Hessian regularization. arXiv preprint arXiv:2212.00311, 2022. URL https://arxiv.org/abs/ 2212.00311. Gintare Karolina Dziugaite, Alexandre Drouin, Brady Neal, Nitarshan Rajkumar, Ethan Caballero, Linbo Wang, Ioannis Mitliagkas, and Daniel M. Roy. In search of robust measures of generalization. In Advances in Neural Information Processing Systems, volume 33, pages 11723–11733. Curran Associates, Inc., 2020. 42

Pascal Germain, Alexandre Lacasse, François Laviolette, Mario Marchand, and Jean-Francis Roy. Risk bounds for the majority vote: From a pac-bayesian analysis to a learning algorithm. Journal of Machine Learning Research, 16:787–860, 2015. Pascal Germain, Francis Bach, Alexandre Lacoste, and Simon Lacoste-Julien. Pac-bayesian theory meets bayesian inference. In Advances in Neural Information Processing Systems 29 (NeurIPS 2016), pages 1–9, 2016. URL https://papers.nips.cc/paper/ 6569-pac-bayesian-theory-meets-bayesian-inference. Aritra Ghosh, Naresh Manwani, and P.S. Sastry. Making risk minimization tolerant to label noise. Neurocomput., 160(C):93–107, jul 2015. ISSN 0925-2312. doi: 10.1016/j.neucom.2014.09.081. URL https://doi.org/10.1016/j.neucom.2014.09.081. Maxime Haddouche, Benjamin Guedj, Omar Rivasplata, and John Shawe-Taylor. Pac-bayes unleashed: Generalisation bounds with unbounded losses. arXiv preprint arXiv:2006.07279, 2020. Maxime Haddouche, Paul Viallard, Umut Simsekli, and Benjamin Guedj. A PAC-Bayesian link between generalisation and flat minima. In Gautam Kamath and Po-Ling Loh, editors, Proceedings of The 36th International Conference on Algorithmic Learning Theory, volume 272 of Proceedings of Machine Learning Research, pages 481–511. PMLR, 24–27 Feb 2025. URL https://proceedings.mlr. press/v272/haddouche25a.html. Benoit Jacob, Skirmantas Kligys, Bo Chen, Menglong Zhu, Matthew Tang, Andrew Howard, Hartwig Adam, and Dmitry Kalenichenko. Quantization and training of neural networks for efficient integer-arithmeticonly inference. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2704–2713, 2018. Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic generalization measures and where to find them. In International Conference on Learning Representations, 2020. URL https://openreview.net/forum?id=SJgIPJBFvH. Alexandre Lacasse, François Laviolette, Mario Marchand, Pascal Germain, and Jean-Francis Roy. Pac-bayes bounds for the risk of the majority vote and the variance of the gibbs classifier. In Advances in Neural Information Processing Systems (NeurIPS), volume 19, 2007. John Langford and John Shawe-Taylor. Pac-bayes & margins. In Advances in Neural Information Processing Systems (NeurIPS), volume 15, 2002. Benjamin Leblanc and Pascal Germain. A framework for bounding deterministic risk with PAC-Bayes: Applications to majority votes. arXiv preprint arXiv:2510.25569, 2025. URL https://arxiv.org/ abs/2510.25569. Alexandre Lemire Paquin, Brahim Chaib-Draa, and Philippe Giguère. Symmetrization of loss functions for robust training of neural networks in the presence of noisy labels, 2026. URL https://arxiv.org/ abs/2605.20347. Yucong Liu, Shixing Yu, and Tong Lin. Regularizing deep neural networks with stochastic estimators of Hessian trace. arXiv preprint arXiv:2208.05924, 2022. URL https://arxiv.org/abs/2208. 05924. Kaifeng Lyu, Zhiyuan Li, and Sanjeev Arora. Understanding the generalization benefit of normalization layers: Sharpness reduction. In Advances in Neural Information Processing Systems, volume 35, 2022. 43

Andrés R. Masegosa, Serafín Moral, and Manuel Cebrián. Second-order pac-bayesian bounds for weighted majority votes. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, 2020. Andreas Maurer. A note on the PAC-Bayesian theorem, 2004. URL https://arxiv.org/abs/cs/ 0411099. Andreas Maurer. A vector-contraction inequality for rademacher complexities. CoRR, abs/1605.00251, 2016. URL http://arxiv.org/abs/1605.00251. David A. McAllester. Some PAC-bayesian theorems. In Proceedings of the Eleventh Annual Conference on Computational Learning Theory, pages 230–234. Association for Computing Machinery, 1998. doi: 10.1145/279943.279989. David A. McAllester. Pac-bayesian model averaging. In Proceedings of the 12th Annual Conference on Computational Learning Theory (COLT), pages 164–170. ACM, 1999. Markus Nagel, Marios Fournarakis, Rana Ali Amjad, Yelysei Bondarenko, Mart van Baalen, and Tijmen Blankevoort. A white paper on neural network quantization. arXiv preprint arXiv:2106.08295, 2021. Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nathan Srebro. A pac-bayesian approach to spectrally-normalized margin bounds for neural networks. In International Conference on Learning Representations (ICLR), 2018. Akshay Rangamani, Nam H. Nguyen, Abhishek Kumar, Dzung Phan, Sang H. Chin, and Trac D. Tran. A scale invariant measure of flatness for deep network minima. In 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1680–1684. IEEE, 2021. doi: 10.1109/ ICASSP39728.2021.9413771. Omar Rivasplata, Ilja Kuzborskij, Csaba Szepesvári, and John Shawe-Taylor. PAC-Bayes analysis beyond the usual bounds. In Advances in Neural Information Processing Systems, volume 33, 2020. URL https://arxiv.org/abs/2006.13057. Matthias Seeger. PAC-bayesian generalisation error bounds for gaussian process classification. Journal of Machine Learning Research, 3:233–269, October 2002. URL https://www.jmlr.org/papers/ v3/seeger02a.html. Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, Cambridge, UK, 2014. ISBN 9781107057135. Neta Shoham, Tomer Avidor, and Nadav Israel. An exploration into why output regularization mitigates label noise. arXiv preprint arXiv:2104.12477, 2021. Jure Sokolić, Raja Giryes, Guillermo Sapiro, and Miguel R. D. Rodrigues. Robust large margin deep neural networks. IEEE Transactions on Signal Processing, 65(16):4265–4280, 2017. doi: 10.1109/TSP.2017. 2708039. Michel Talagrand. The Generic Chaining: Upper and Lower Bounds of Stochastic Processes. Springer Monographs in Mathematics. Springer, Berlin, Heidelberg, 2005. Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Normalized flat minima: Exploring scale invariant definition of flat minima for neural networks using PAC-bayesian analysis. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 9636–9647. PMLR, 2020. URL https: //proceedings.mlr.press/v119/tsuzuku20a.html. 44

Dániel Varga, Adrián Csiszárik, and Zsolt Zombori. Gradient regularization improves accuracy of discriminative models. arXiv preprint arXiv:1712.09936, 2017. Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press, Cambridge, 2018. ISBN 9781108415194. URL https://www.math.uci. edu/~rvershyn/papers/HDP-book/HDP-2.pdf. See Corollary 8.5.6 (Talagrand comparison inequality). Paul Viallard, Pascal Germain, Amaury Habrard, and Emilie Morvant. A general framework for the practical disintegration of pac-bayesian bounds. CoRR, abs/2102.08649, 2021. URL https://arxiv.org/ abs/2102.08649. Mingyang Yi, Huishuai Zhang, Wei Chen, Zhi-Ming Ma, and Tie-Yan Liu. BN-invariant sharpness regularizes the training model to better generalization. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, pages 4164–4170. International Joint Conferences on Artificial Intelligence Organization, 2019. Xiong Zhou, Xianming Liu, Hanzhang Wang, Deming Zhai, Jiangjunjun, and Xiangyang Ji. On the dynamics under the unhinged loss and beyond. Journal of Machine Learning Research, 24:1–62, 2023. URL https://jmlr.org/papers/v24/23-0771.html.

Record · ID 287151 · SHA-256 b2c0d37392fd62a8
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.