PAC-Bayes is a popular and efficient framework for obtaining generalization guarantees in situations involving uncountable hypothesis spaces. Unfortunately, in its classical formulation, it only provides guarantees on the expected risk of a randomly sampled hypothesis. This requires stochastic predictions at test time, making PAC-Bayes unusable in many practical situations where a single deterministic hypothesis must be deployed. We propose a unified framework for extracting guarantees for a single hypothesis from PAC-Bayesian guarantees. We present a general derandomization framework, and derive from it a numerical bound for majority votes and for three different probability distributions over the posterior space. We study the empirical behaviour of our approach, showing that it consistently outperforms popular baselines in terms of generalization bounds for single classifiers (by up to a factor of 2), but sometimes requires a sacrifice in accuracy.
Figures & tables
k
Distribution
First Order
Second Order
Binomial Bound
C-Bound
Partition Bound
k=2
Categorical
✓
✓
✓
✓
⋆
Dirichlet
×
×
×
×
⋆
Gaussian
✓
✓
✓
×
⋆
k>2
Categorical
✓
✓
✓
×
⋆
Dirichlet
×
×
×
×
⋆
Gaussian
⋆
⋆
⋆
×
×
Table 1: Applicability of the true risk bounding method to derandomized majority vote, for binary ( k=2 ) and multi-class ( k>2 ) classification problems. Green ( ⋆ ): applicable, contribution; lime ( ✓ ): applicable, literature result; red ( × ): non-applicable.
Task
First Order
Second Order
Binomial Bound
C-Bound
VC-dimension
Partition Bound
Bound
Test error
Bound
Test error
Bound
Test error
Bound
Test error
Bound
Test error
Bound
Test error
ADULT
46.9 ± 0.0
22.2 ± 0.1
52.9 ± 0.1
15.8 ± 0.2
51.4 ± 0.0
24.1 ± 0.0
74.5 ± 0.4
21.0 ± 1.6
78.9 ± 0.0
17.2 ± 0.3
23.2 ± 2.4
21.7 ± 2.5
CODRNA
40.2 ± 0.1
12.0 ± 0.1
47.4 ± 0.1
11.7 ± 0.1
42.8 ± 5.2
15.2 ± 4.5
63.7 ± 1.0
23.1 ± 1.3
38.8 ± 1.6
23.1 ± 1.5
24.7 ± 0.3
23.6 ± 0.3
HABER
75.2 ± 0.9
26.5 ± 1.8
110.5 ± 1.1
26.1 ± 2.1
84.7 ± 0.8
26.1 ± 0.7
100.0 ± 0.0
27.1 ± 1.8
112.0 ± 1.0
28.4 ± 1.8
37.8 ± 0.5
26.5 ± 1.8
MUSH
12.2 ± 0.3
4.8 ± 0.5
20.6 ± 1.2
0.5 ± 0.3
12.6 ± 0.4
1.1 ± 0.1
22.0 ± 0.5
4.8 ± 0.5
59.1 ± 0.1
4.8 ± 0.5
6.1 ± 0.1
4.8 ± 0.5
PHIS
25.8 ± 0.3
11.1 ± 0.6
33.6 ± 0.2
6.4 ± 0.5
27.5 ± 0.2
6.8 ± 0.5
37.1 ± 0.5
10.4 ± 1.3
85.2 ± 0.2
11.1 ± 0.6
24.9 ± 1.0
11.1 ± 0.6
Table 2: Comparison of our proposed approach and a few baselines for different types of predictors. Bolded and underlined values are respectively within one standard deviation of the best bound and test error values (%). Average and standard deviations computed over 5 random seeds.
Task
Categorical Distribution
Dirichlet Distribution
Gaussian Distribution
Partition Bound
Test error
Partition Bound
Test error
Partition Bound
Test error
ADULT
46.4 ± 0.4
22.2 ± 0.1
23.2 ± 2.4
21.7 ± 2.5
51.0 ± 0.0
24.1 ± 0.0
CODRNA
24.7 ± 0.3
23.6 ± 0.3
29.4 ± 4.8
28.4 ± 4.6
39.1 ± 1.4
17.1 ± 7.2
HABER
37.8 ± 0.5
26.5 ± 1.8
73.6 ± 7.9
34.2 ± 7.2
71.7 ± 4.2
25.8 ± 3.0
MUSH
6.1 ± 0.1
4.8 ± 0.5
8.0 ± 1.0
4.1 ± 1.8
19.0 ± 0.5
2.6 ± 0.6
PHIS
24.9 ± 1.0
11.1 ± 0.6
26.8 ± 0.2
6.7 ± 0.4
27.5 ± 0.2
6.6 ± 0.5
Table 3: Proposed approach’s bound and test error (%) for every distribution. Bolded and underlined values are respectively within one standard deviation of the best bound and test error values. Average and standard deviations computed over 5 random seeds.
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
#
Dataset
Full name
Source
d
k
m
1
ADULT
Adult
LIBSVM
123
2
32 561
2
CODRNA
CodRNA
LIBSVM
8
2
59 535
3
HABER
Haberman
UCI
3
2
306
4
MUSH
Mushroom
UCI
22
2
8124
5
PHIS
Phishing
LIBSVM
68
2
2456
6
SVMG
Svmguide1
LIBSVM
4
2
7089
Appendix
Table 4: Details of the datasets used in the experimental section coming from either the UCI datasets repository ( Dua and Graff, 2017 ) , the LIBSVM library ( Chang and Lin, 2011 ) , or Zalando ( Xiao et al., 2017 ) . d is the number of features, k the number of classes and m the total number of examples.
#
Dataset
Partition problem solving (ms)
Heuristic #1 (s)
Heuristic #2 (s)
Heuristic #3 (s)
1
ADULT
124.4 ± 11.2
12.3 ± 2.3
67.1 ± 20.8
16.7 ± 1.0
2
CODRNA
23.7 ± 7.5
14.2 ± 4.6
1.9 ± 0.2
10.2 ± 1.8
3
HABER
17.3 ± 4.3
2.3 ± 0.1
0.4 ± 0.1
1.9 ± 0.3
4
MUSH
42.1 ± 8.8
2.9 ± 0.4
1.1 ± 0.2
3.1 ± 0.3
5
PHIS
12.3 ± 4.0
4.1 ± 1.0
6.2 ± 1.1
3.4 ± 0.7
6
SVMG
16.0 ± 4.6
2.8 ± 0.1
0.4 ± 0.0
2.1 ± 0.4
Appendix
Table 5: Average and standard deviation of running time of the partition problem algorithm and the computations of every heuristic for the selected models (over five random seeds).
Figure 1: Average running time of the considered partition problem-solving algorithm throughout a complete optimization using our proposed method for various numbers of base classifiers (over five random seeds).
Task
First Order
Second Order
Binomial Bound
C-Bound
VC-dimension
Partition Bound
C , or G
C , or G
C , or G
C
C
C , D , or G
ADULT
Categorical
Gaussian
Categorical
Categorical
Categorical
Dirichlet
CODRNA
Gaussian
Gaussian
Categorical
Categorical
Categorical
Categorical
HABER
Categorical
Categorical
Categorical
Categorical
Categorical
Categorical
MUSH
Categorical
Categorical
Categorical
Categorical
Categorical
Categorical
PHIS
Categorical
Gaussian
Categorical
Categorical
Categorical
Categorical
Appendix
Table 6: Selected distributions for our approach and a few baselines across different types of predictors.
Figure 2: Evolution of the selected model bound and test error for the Categorical distribution as the various heuristics are applied.
Figure 3: Evolution of the selected model bound and test error for the Dirichlet distribution as the various heuristics are applied.
Figure 4: Evolution of the selected model bound and test error for the Gaussian distribution as the various heuristics are applied.
Weighted majority votes are central to many successful ensemble methods. PAC-Bayesian theory provides tight generalization guarantees for such models by analyzing the expected risk of stochastic classifiers, while analyzing the risk of deterministic majority votes relies on surrogate bounds. To avoid these surrogates, Zantedeschi et al. ( 2021) introduced guarantees for stochastic majority votes, but the resulting models remain randomized. In this paper, we propose a derandomization framework for stochastic majority votes. To do so, we apply recent advances in disintegrated PAC-Bayesian theory directly to the space of majority vote weight vectors, transforming stochastic guarantees into certificates for a single deterministic majority vote. We derive two families of high-probability generalization bounds, covering both data-independent and data-dependent constructions of the ensemble, which naturally lead to a self-bounding learning algorithm optimizing deterministic majority vote guarantees.
Julien Bastian, Benjamin Leblanc, Pascal Germain +4
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.
Alexandre Lemire Paquin, Brahim Chaib-Draa, Philippe Giguère
Department of Computer Science and Software Engineering Université Laval, Québec, Canada
Generalization bounds for deep learning models are typically vacuous, not computable or restricted to specific model classes. In this paper, we tackle these issues by providing new disagreement-based certificates for the gap between the true risk of any two predictors. We then bound the true risk of the predictor of interest via a surrogate model that enjoys tight generalization guarantees, and by evaluating our disagreement bound on an unlabeled dataset.We empirically demonstrate the tightness of the obtained certificates and showcase the versatility of the approach by training surrogate models leveraging three different frameworks: sample compression, model compression and PAC-Bayes theory. Importantly, such guarantees are achieved without modifying the target model, nor adapting the training procedure to the generalization framework.