acceptodds
Under review as a conference paper at ICLR 2027

Common Formulas and Calibration Frontiers in PAC–Bayes Bounds

Abstract

PAC–Bayes bounds certify predictors selected from data, but their tightness can be limited by the need to use one formula across sample outcomes or recover classical confidence bounds when posterior equals prior. We characterize when one normalized convex comparator attains every statewise optimum and derive matching excess bounds in two regimes for fixed finite interior targets with positive weights. A fixed task using empirical risk minimization has low risk and bounded Kullback–Leibler (KL) complexity, yet its optimal expected excess is of the same order as the benchmark width above empirical risk. For finite binary-loss libraries, our construction combines Clopper–Pearson (CP) exactness at a shared point mass with simultaneous posterior coverage, continuity and KL learning, whereas exact recovery at a mixed prior can obstruct learning. Under the specified randomized evaluation, every rule with CP recovery at the original confidence level and simultaneous coverage throughout the full model gives a perfect predictor a bound tending to one in probability on a common fixed task. Allowing pathwise one-sided calibration tolerance yields matching asymptotic limits for width quantiles under each distribution and in the worst case, with the finite model, positive prior and KL budget fixed. The worst-case width can vanish when the tolerance decays subexponentially, whereas exponential decay can leave a positive limit. One explicit rule uses joint losses to attain each distribution’s optimal limit without knowing the distribution. This attainment is uniform over growing finite libraries and all positive priors and data laws at specified confidence levels with a fixed positive precision exponent and KL budget.

Primary area:
learning theory
Keywords:
PAC-Bayes bounds, generalization bounds, confidence bounds, post-selection inference

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_Pq5NOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The authors claim to partially solve two Open Problems stated in Foong at al (2021) on the behavior and optimization (in terms of tightness) of PAC-Bayes bounds.

Critical strengths

Solving the Open Problems in Foong et al. (2021) could potentially be of value, however, this potential strength is severely overshadowed by the paper's many weaknesses.

Critical weaknesses

W1) The paper does not properly introduce and define its core terminology. For instance, in the very beginning of Section 2, there is no mention of what S is and what spaces the distributions P and Q are over. While these things might be reasonably easy to guess for an expert in the field, there is also a lot of vague terminology beyond that which the authors don't bother to define. Examples are "finite libraries", "optimal width", "exact compatibility", "sensitivity-weighted entropy", and "informative guarantees". I stress that this is a problem throughout the paper with almost every technical term used, and I am only naming a few examples.

W2) Due to the lack of clear technical definitions and the extraordinary length of the apper including appendices of over 80 pages, I cannot form an opinion as to whether the proofs are technically sound. Extrapolating from the poor technical writing of the main part of the paper, however, I would be very surprised if they were. In any case, due to the insufficiently clear writing and the poor use of technical vocabulary, it isn't even reasonably possible for me to verify that the statements support the authors' claim that they have partially solved the two referenced Open Problems.

W3) Even beyond my concerns about the quality of the technical writing, I am not sure that a paper of over 80 pages, almost all of which is dense mathematical/technical material, is of value for a venue whose publications are primarily intended for human reading. There is no discussion of why such an unusual amount of technical material is necessary to establish the technical results, and what value publishing it would bring to the theoretical understanding of the topic. If the value is just establishing the technical validity itself with no insight into methodology or technique (at least for humans), it stands to reason that the proofs should also be published in a machine-friendly form (e.g., a theorem checker language). In any case, the 2.5 weeks review process of ICLR is in my view not remotely suitable to determine if a paper of this length should be published.

W4) From reading the paper, it seems that it may be (at best) lightly edited LLM output, and if that was indeed the case, it would be unclear what value to readers publishing such a paper at a conference would have. Of course, it is not possible for me to cite definitive evidence for this, but I do want to highlight a potential contradiction within the authors' AI use statement on page 10. The first part of it claims that the use of AI was limited to "language editing, manuscript organization, presentation refinement, figure preparation, (...) LATEX preparation [and] to stress-test proofs already developed by the authors and to help identify potential gaps, hidden assumptions, edge cases, or inconsistencies". On the other hand, the authors write also that "(a)ll mathematical claims and proofs were independently verified, revised where necessary, and finalized by the authors". To me, this strongly hints at mathematical claims and proofs being written by AI, in direct contradiction with the first part of the statement.

Questions for authors

Q1) What is the learning problem considered in Section 6?

Q2) Have other authors tried to approach or partially solved Open Problem 1 or Open Problem 2 in Foong et al. (2021)? The authors neither mention any papers nor say explicitly that this hasn't happened.

Q3) What are the (potential) practical implications of solving these Open Problems?

2 comments

Thank you for pointing out where the terminology was unclear and the proofs were difficult to verify. We revised the explanations in Sections 2–5. The proof guide on page 14 now directs readers from each main result to its complete proof.


W1. Problem setup and terminology

Section 2 now defines the observation and hypothesis spaces and explains how the sample is drawn and how predictors are selected. The training sample SS consists of independent and identically distributed observations. The prior PP and posterior QQ are both distributions over predictors. The prior is fixed before sampling, while the posterior may be chosen after observing the sample. Empirical risk is the average loss on the training sample, and population risk is the expected loss on a new observation drawn from the same distribution. We also updated the AI use statement to specify how generative AI was used.

Section 3 explains how a comparator, a convex function that relates empirical risk to possible values of population risk, is used to compute a risk upper bound. A finite library is a finite collection of candidate comparators. For each pair of empirical risk and complexity values, one can optimize the formula separately to obtain the smallest upper bound. Exact compatibility asks whether a single formula can attain all of those individual optima. The sensitivity-weighted entropy in Equation (6) quantifies the cost of using one formula across several such pairs. The same change in the comparator’s value can raise the risk upper bound by different amounts at different pairs, and the weights reflect those differences.

Section 5.2 defines the width of a posterior’s bound as the amount by which the upper bound exceeds its empirical risk, taking this amount to be zero if the bound is lower. We take the maximum width over posteriors within the complexity budget. The optimal width describes how small a valid rule can make this maximum at the prescribed probability level while meeting the calibration requirement. For example, an error-rate upper bound of 11 rules out no possible error rate, even when the predictor makes no errors.


W2–W3. Proof structure and what the arguments establish

Section 3 starts from the observation that different samples can favor different formulas. For a formula to attain the optimum for a given pair of empirical risk and complexity values, its comparator must satisfy a corresponding supporting-plane constraint. To determine whether one formula can attain several optima at once, we take the pointwise maximum of these planes and check whether it satisfies the common normalization condition. Appendix B.2 proves this criterion. Theorem 1 then shows the cost of using one formula on a fixed low-risk classification task. Its full proof is in Appendix B.1.

Section 4 constructs a confidence set for the vector of population risks. To bound a posterior’s risk, we weight the predictors’ risks by their probabilities under that posterior and maximize the resulting average over the confidence set. Whenever the set contains the true risk vector, this argument gives a valid bound for every posterior on the same event, including posteriors chosen after seeing the sample. When the prior and posterior both concentrate on the same predictor, the construction recovers the classical Clopper–Pearson (CP) bound exactly. The proofs are in Appendices C.2–C.4.

Section 5 explains the difficulty that arises when the prior assigns weight to several predictors. Under some data distributions, requiring exact recovery of the original-confidence CP bound at the prior uses nearly all of the allowed failure probability. The same guarantee must also cover the learned posteriors, leaving very little room for coverage failures elsewhere. Theorem 5 shows that this can force the upper bound for a zero-risk predictor to approach 11. The proof is in Appendix D.1. When some calibration error is allowed, Appendices D.2–D.3 give lower bounds on the achievable width and constructions that match them under the stated conditions. Together, they determine how much the bounds can improve when the calibration requirement is relaxed.

Q2. Prior work and our answers to the two open problems

We answer Open Problem 1 in the negative within the normalized convex-comparator class studied by Foong et al. (2021). Their benchmark minimizes the upper bound separately for each sample. They ask whether a single formula chosen before sampling can attain that benchmark on average. Theorem 1 gives a fixed low-risk task on which even the best formula chosen in advance for that task yields a strictly larger average upper bound. The original problem also asks how closely a common formula can approach the benchmark. We characterize when one formula attains all the individual optima and give matching lower bounds and constructions in two regimes for the finite target sets specified in the paper.

Related work provides other ways to tighten PAC–Bayes bounds. Hellström and Guedj (2024) study Cramér comparators and obtain near-optimal guarantees under their criterion. Rodríguez-Gálvez et al. (2024) derive bounds that are simultaneously valid over a family of temperatures, allowing the temperature to be chosen after seeing the sample once the corresponding normalization term is included. We use Foong et al.’s benchmark and the same threshold for computing the risk bound to determine how tight a formula fixed before sampling can be.

Open Problem 2 asks whether a PAC–Bayes risk upper bound can recover the classical CP bound at Q=PQ=P and approach it as QQ approaches PP. We give an affirmative answer for finite hypothesis sets with binary losses under the specified randomized Gibbs evaluation. Foong et al. (2021, Appendix I.2) explain how to obtain a binomial count by randomization and use it to compute a CP bound for the prior risk. In Section 5.1, we use that CP bound to constrain the prior-weighted average of the predictors’ population risks. We then use this constraint to compute a risk upper bound for each posterior. The resulting rule covers all posteriors simultaneously at the original confidence level, equals CP at Q=PQ=P, and approaches CP as QQ approaches PP. Theorem 5 and the subsequent results establish when exact recovery can lead to wide bounds for learned posteriors and how much those bounds can tighten when some calibration error is allowed. Section 1.1 and Appendix F.1 discuss the relationship to prior work.


Q3. Practical implications

Optimizing a formula separately for each sample gives a benchmark for how much room there is to tighten a bound. When comparing PAC–Bayes methods, the relevant quantity is how tight a bound each method can report at the same confidence level. If a method chooses its formula after seeing the data, its coverage proof must account for that choice. Theorem 1 shows that the average cost of using one common formula can be of the same order as the gap between the separately optimized upper bounds and the empirical risk. Section 4 gives a concrete example of what a different construction can achieve. When the prior and posterior concentrate on the same predictor and the sample contains both correct and incorrect predictions, the confidence-set construction recovers CP exactly and gives a strictly tighter bound than the formulas studied in Section 3.

Figure 2(c) illustrates why the rate at which the calibration tolerance decreases matters. On the same task, the optimal width tends to zero when the tolerance is 1/N1/N. When the tolerance is tightened to e−N/2e^{-N/2}, the optimal width tends to approximately 0.3930.393. Both tolerances tend to zero, and both settings retain simultaneous coverage at the same confidence level. The rate at which the tolerance vanishes can therefore determine how tight a risk bound one can report after learning. These optimal-width results are proved for finite hypothesis spaces, and Theorem 7 allows the number of predictors to grow with the sample size.


Q1. Learning tasks in Section 6

Figure 2(a) measures the cost of using the same formula across samples. The classification task has three possible inputs. Both classifiers have a population error rate of 10%10\%, and they make errors on different inputs. For each training sample, empirical risk minimization selects a classifier. The figure measures the average gap between the bound from a formula fixed before sampling and the benchmark obtained by optimizing the formula separately for each sample. Figure 2(b) shows how close our construction is to the best possible common formula. We specify two pairs of empirical risk and complexity values and require one formula to serve both. The figure gives lower and upper bounds on the smallest additional width this requirement entails. Figure 2(c) shows how calibration affects the bounds for learned posteriors. The task has two classifiers, one always correct and one always wrong. We vary the calibration tolerance at the prior and examine how small a valid rule can make the maximum width over posteriors within the complexity budget.

Reviewer_ZhncOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The first part of the paper studies how tight PAC-Bayes bounds can be, under the derivation framework of PAC-Bayes bounds through a convex function ff. Previous works suggested that the tightness of a PAC-Bayes bound can differ for different (empirical error, complexity term) pairs. This paper provides a negative answer to the Open Problem 1 proposed by Foong et al.: whether there is one function ff that can be good regardless of the pairs observed after seeing the data, through Theorem 1.

The second part studies whether a PAC-Bayes bound can recover the Clopper–Pearson bound when the posterior equals the prior, while remaining valid. For finite hypothesis spaces with binary losses and point mass priors and posteriors, they provide a positive construction (Theorem 4). However, for a mixed prior under the paper's randomized evaluation scheme, exact recovery at the original confidence level can push the bound to nearly one (Theorem 5).

Critical strengths

As mentioned in the summary, the paper provides partial answers to the open questions raised by Foong et al., under the frameworks and assumptions considered. The counterexamples make concrete some limitations of using one fixed convex function and of requiring exact recovery of the Clopper–Pearson bound. However, I find the number of formal statements way too many to check the arguments supporting the main contributions within the review time available.

Critical weaknesses

For me, the amount and way LLMs are used in writing to overcomplicate the presentation is concerning, making it unclear how much the community can benefit from the current version of the work. I am familiar with this field and with the literature that the paper mainly builds on. However, I still find it overwhelming to understand and keep track of what the authors are trying to achieve and how they are trying to achieve it.

Across the 83 pages, there are, I believe, unnecessarily overwhelming amount of notations and statements (81 numbered formal statements). It would be much better to make clear which contributions and results the authors want readers to take away, and to simplify things further. Some connecting explanations would also help readers navigate the logic and arguments throughout the paper, but they are largely missing. From Sections 3–5 through the appendix, I see more and more results being stuffed, without a clear explanation of how they fit together or move the argument forward. I strongly believe that this work does not need 81 numbered statements.

In addition to the overwhelming amount of notations, some more common notations also seem to rely on assumed shared conventions. For example, even in the first paragraph of the preliminaries, the sample space of DD and the roles of hh and zz are not explicitly laid out. These are also not consistently taken forward to even the first theorem, Theorem 1. The authors could have used formulas to define L(Q)L(Q) and L^S(Q)\widehat L_S(Q), and explicitly stated the spaces on which the prior and posterior are defined. I am used to seeing these standard objects explicitly defined in most of the learning-theory and PAC-Bayes literature. For readers who already know these definitions, this may not be big obstacles, but it is still annoying. For readers who are not familiar with them, I doubt it’s possible to understand what is going on. Right after Eq. (1), the introduction of the comparator Δ\Delta and the shift to a normalized f‘f` adds more elements before the motivation is made clear. I recognize the ingredients, but I still have to slow down and reconstruct why they are being introduced and what role they play. It takes extra work to put these elements together, even though they could have been presented much more directly and made much easier for readers to follow.

As far as I understand, the second part (Sections 4–5) studies whether, and at what cost, a PAC-Bayes bound can recover the Clopper–Pearson bound when the posterior equals the prior, while remaining valid. However, I honestly find the constructions and the statements hard to follow, despite being familiar with PAC-Bayes and its literature.

Questions for authors
  1. There are indeed many PAC-Bayes bounds can be derived by designing a convex function ff, but there are also a few that are not done through this path. I wonder what the results in Section 3 imply in a more general sense?

  2. The results in Sections 4–5 seemed to be only for finite hypothesis spaces. It is not clear whether or how these constructions extend to continuous hypothesis spaces.

1 comment

Thank you for reading the paper carefully and pointing out where the exposition and proofs were difficult to follow. The original draft did not explain clearly how the results fit together, and readers had to look across several appendices to find the proofs. We revised the explanations in Sections 2–5 and reorganized the 17 appendix sections into six groups. We consolidated repeated arguments and moved extensions that the main results do not rely on out of the submission. The revised manuscript is 75 pages and contains 70 numbered statements, down from 81. The proof guide on page 14 gives the location of each main proof. For example, Theorems 1, 4, and 5 are proved in Appendices B.1, C.2–C.4, and D.1, respectively. We also updated the AI use statement to describe how the tools were used.


Problem setup and constructions in Sections 4–5. Section 2 now defines the observation and hypothesis spaces, explains how the sample is drawn and when the prior PP and posterior QQ are chosen, and gives formulas for empirical and population risk. We first show how a convex function gives a risk upper bound, then explain how normalization lets us compare formulas at the same complexity threshold. Section 4 starts from a confidence set for the risk vector. Whenever this set contains the true risk vector, maximizing a posterior’s risk over the set gives a valid bound. The same event therefore covers all posteriors, including those chosen from the data. Section 5 explains the difficulty at a mixed prior. Under the stated randomized evaluation, the prior’s original-confidence Clopper–Pearson (CP) bound can use nearly all of the allowed failure probability under some data laws. This leaves little room for coverage failures at other posteriors. On a fixed task, the requirement can force the bound for a zero-risk predictor to approach one. We then characterize how much tighter the bounds can become when some calibration error is allowed.


Implications for other PAC–Bayes methods. We suggest comparing the bounds that different methods can actually report at the same confidence level. Optimizing a formula separately for each sample gives a useful benchmark. A method that chooses its formula after seeing the sample needs a guarantee that remains valid after that choice. Theorem 1 shows why this distinction matters. On a fixed task with low risk and bounded posterior KL divergence, even the smallest average cost of using one normalized convex comparator can be of the same order as the gap between the separately optimized bounds and the training error. This lower bound applies to the comparator class studied in Section 3. Section 4 shows what a different construction can achieve. When prior and posterior concentrate on the same predictor and the error count is strictly between zero and the sample size, the confidence set recovers CP exactly, while every bound in the comparator class is strictly above it.


Continuous hypothesis spaces. The randomized count extends by taking the prior average of the loss on each observation and using it as the success probability of an independent Bernoulli draw. If cc is the resulting CP bound for the prior risk, then min⁡{1,c+TV⁡(P,Q)}\min\{1,c+\operatorname{TV}(P,Q)\} bounds every posterior risk on the same event and equals cc at Q=PQ=P. This extension can still give loose bounds because increasing the sample size need not reduce the distance between prior and posterior. The stronger results in Sections 4–5 are proved for finite hypothesis sets. These include combining exact recovery at a shared point mass with bounds that tighten as the sample grows at fixed KL divergence, and characterizing the best attainable width under approximate calibration. Section 5.3 now states explicitly that Theorem 7 allows the number of predictors to grow with the sample size, with a finite set at each sample size.

Reviewer_DjHNOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies the cost of using one PAC-Bayes bound formula across sampled datasets and requiring recovery of the classical Clopper–Pearson bound. It characterizes when one formula can attain individually optimal bounds and derives limitations and matching constructions under exact and approximate recovery requirements.

Critical strengths
  • This paper characterizes when one normalized convex comparator attains every statewise optimum and derives matching excess bounds in two regimes for fixed finite interior targets with positive weights.
Critical weaknesses
  • The paper is really hard to read. Many terminologies are not common but are used without definition, e.g., comparator, benchmark width, library, state, endpoint, and interior targets/interior state, etc.. I think the authors need to rewrite the paper before publishing it at any conference.
Questions for authors
  • Can you explain what a comparator, benchmark width, library, state, endpoint, and interior targets/interior state are? Are they commonly used in this research area?
1 comment

Thank you for reading the paper carefully and identifying the terms that made it difficult to follow. The original draft introduced several of these terms before explaining which risk bounds we were comparing. We have revised the abstract and introduction to state the questions more directly. Section 2 now defines the sample, prior, posterior, empirical risk, and population risk before explaining how a convex function gives a risk upper bound.

We call a convex function f(q,r)f(q,r) relating empirical risk qq to population risk rr a comparator. For a normalized comparator fixed before sampling, the PAC–Bayes theorem gives f(q,r)≤cf(q,r)\le c on a single high-probability event for all posteriors with finite KL divergence. The complexity level cc depends on the sample size, confidence level, and KL divergence from the prior. We call (q,c)(q,c) a sample state. The endpoint Uf(q,c)U_f(q,c) is the supremum of the risks allowed by this inequality. If F(q,c)F(q,c) is the tightest bound obtained by optimizing the comparator separately for that pair, the benchmark width F(q,c)−qF(q,c)-q is how far that bound lies above empirical risk. Our first question is how much higher the bound is on average when one formula must serve all samples.

We use “convex comparator” as in Hellström and Guedj (2024) and “endpoint” in its usual mathematical sense. “Sample state” and “benchmark width” are terms we define for this paper. A sample state is interior when 0<q<F(q,c)<10 < q < F(q,c) < 1. In Section 3.2, an interior target specifies an empirical risk qq, an individually optimal upper bound pp with 0<q<p<10 < q < p < 1, and a positive weight ww used to average the gaps. In the calibration results, a finite hypothesis set is a finite collection of candidate predictors. This is the term we now use in the introduction. In the formula-selection discussion, a comparator library is a collection of candidate convex functions used to construct risk bounds. Section 3.1 illustrates why different samples can favor different formulas even in a fixed learning task. The two classifiers have the same population risk but different prior weights. Empirical risk minimization can select either classifier, depending on the sample. That choice changes the KL penalty and can change which formula gives the tightest bound. The proof guide on page 14 directs readers from the main results to their proofs.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.