- 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
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 and approach it as approaches . 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 , and approaches CP as approaches . 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 . When the tolerance is tightened to , the optimal width tends to approximately . 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 , 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.
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 S consists of independent and identically distributed observations. The prior P and posterior Q 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 1 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 1. 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.