Learning via Surrogate PAC-Bayes

Summary

The paper introduces a novel strategy for building iterative learning algorithms via the optimisation of a sequence of surrogate training objectives derived from PAC-Bayes generalization bounds. It also theoretical estabilishes that iteratively optimising our surrogates implies the optimisation of the original generalisation bounds and showcase the algorithm in a meta-learning context, and demonstrate that the algorithm works practically.

Strengths

Firstly, my expertise within the area is unfortunately almost nonexistent. My apologies to the authors. With that said, the paper appears to be very nicely written, and its contributions appear substantial. I am left with a very positive impression, although I cannot assess the technical contributions with any credibility.

Weaknesses

No comment.

Questions

Unfortunately, the paper is too far outside my field to even start assessing where things can be clarified.

Rating

7

Confidence

1

Soundness

3

Presentation

3

Contribution

3

Limitations

Limitations have been properly addressed.

Summary

- This paper tackles the issue that model training based on PAC-Bayes bounds can become computationally burdensome in certain applications, such as calibration tasks for biochemical models. - To overcome this issue, the authors propose replacing the empirical risk in the standard PAC-Bayes bound with a surrogate loss, which is the projection of the empirical risk onto a low-dimensional function space. - The authors also provide a theoretical guarantee, showing that minimizing their bound also minimizes the original PAC-Bayes bound. - They applied their framework to meta-learning, deriving an optimization scheme based on a closed-form gradient. - The authors validated the performance of their method using an anaerobic model in the biochemical setting.

Strengths

- Practical motivation inspired by applications to biochemical settings - The authors identify the computational burden associated with PAC-Bayes generalization in commonly used models within this setting and propose a solution, which is a significant practical contribution. - Theoretical guarantee of the proposed method - The proposed method is theoretically guaranteed to minimize the original PAC-Bayes generalization error bound. This indicates that the method can enhance generalization while mitigating the aforementioned issue, making it a valuable practical property.

Weaknesses

- Lack of discussion on computational bottlenecks and ambiguity in the definition of computational burden - If I understand correctly, the main motivation of this paper is the computational burden of PAC-Bayes learning for specific problems. However, there is insufficient detailed discussion on how much this issue is resolved by the proposed method compared to traditional methods. - There is neither a theoretical evaluation of complexity nor empirical discussion based on physical time metrics like wall-clock time. The definition of “computational burden” is vague. Therefore, it is unclear what the paper resolves and what advantages the proposed method has overall. - Unclear presentation - The proofs feel somewhat informal (e.g., Corollary 1. and Theorem 2.). Understanding the techniques used to derive the theory is crucial for future research development, but the lack of detailed explanation makes it difficult to understand. - Insufficient experimental evaluation - All experiments are compared only by the value of the objective, and the theoretical results are not fully validated. The claim that the proposed method also minimizes the original PAC-Bayes bound could be verified by illustrating the PAC-Bayes bound, but such experiments are not reported, reducing the persuasiveness. - If high computational burden is a concern and there is no theoretical discussion on computational load, it is crucial to compare the proposed method with existing methods in terms of various time units. However, these discussions are lacking, making the support for the proposed method’s advantages insufficient. While comparisons are made based on the number of empirical risk queries, this alone is not sufficient to support the claim of reduced computational burden. For instance, a method that is efficient in terms of the number of queries but takes more physical time would be counterproductive. It is necessary to empirically compare whether the computation time for the closed-form gradient derived in Lemma 1, including the evaluation of the inverse Fisher information matrix, is indeed more efficient than traditional methods.

Questions

- Discussion on Computational Bottlenecks and Definition of Computational Burden - What is the precise definition of “computational burden” as used in this paper? - Can you provide a theoretical evaluation of the complexity of the proposed method? If it's impossible, are there empirical discussions or evaluations based on physical time metrics like wall-clock time to support the claims? If these comparison or discussion is unnecessary, I'm happy if you could give me the concrete reason. - Presentation Clarity - The proofs, such as those in Corollary 1 and Theorem 2, feel somewhat informal. Can you provide more detailed explanations of the techniques used to derive these theories? - Experimental Evaluation - Why are the experiments only compared by the value of the objective? Can you provide additional metrics for comparison or the concrete reason about why such a comparison is unnecessary? - Why is the empirical validation about the theoretical claim that the proposed method minimizes the original PAC-Bayes bound absent? Straightforwardly, it can validate your claim by evaluating the original PAC-Bayes bound; but, is it impossible? - Is there a comparison of the proposed method with existing methods in terms of various time units to address computational burden concerns? If no, I'm happy that if you could give the reason why such a comparison is absent. - How does the proposed method perform in terms of physical time compared to existing methods, considering both efficiency in the number of queries and the actual computation time? - What is the theoretical (or empirical) computational complexity for the closed-form gradient derived in Lemma 1, including the evaluation of the inverse Fisher information matrix, and how does it compare to traditional methods? - Why does considering your surrogate risk reduce computational burden? Is the projection onto a lower-dimensional space the most effective factor? A discussion on the intuition behind this would be appreciated. - Regarding Hypothesis (Assumption) 4: the authors assume bounded losses as a condition for the theoretical results. Is this not a concern in the context of Meta-learning? For instance, Rothfuss et al. (2021) address the issue that PAC-Bayes bounds for many meta-learners are only valid under bounded losses, and they derive PAC-Bayes bounds that hold even under unbounded losses. Personally, I believe that the theoretical guarantees under the assumption of bounded losses might limit the contribution of this paper. - Is there any rationale behind the settings of hyperparameters such as the learning rate? It appears that the criteria for these selections have not been provided, which raises concerns about the potential arbitrariness of the evaluations. - MISC: Is “Hypotheses” here used as the mean of assumptions? CItation: Rothfuss et al. (2021): Rothfuss et al. PACOH: Bayes-Optimal Meta-Learning with PAC-Guarantees. ICML2021. https://arxiv.org/pdf/2002.05551

Rating

5

Confidence

4

Soundness

2

Presentation

1

Contribution

2

Limitations

This study is foundational research aimed at improving the computational burden of PAC-Bayes in specific problems, and these aspects are discussed in the Broader Impact paragraph. The datasets used are synthetic one, which suggests that there are no significant concerns regarding potential negative social impacts.

Summary

This paper provides novel tools to construct surrogate minimization objectives based on PAC-Bayes bounds, where the empirical risk is replaced by a proxy. This approach has the advantage of efficiency in scenarios where querying the empirical risk is expensive. The proxy is constructed by projecting the empirical risk on a finite-dimensional function space, and theoretical guarantees are provided for the resulting surrogate minimization problem. The strategy is instantiated in meta-learning problems and a real-life biochemical modeling problem, where surrogate loss minimization outperforms gradient descent.

Strengths

1- The paper is clearly written and readable. 2- The theory behind the surrogate loss construction is solid, and the assumptions seem reasonable. 3- The efficiency and performance gains with respect to simple gradient descent look impressive.

Weaknesses

1- It seems that the only motivating problem for the paper is (Picard-Weibel et al., 2024), it would be nice to discuss more examples where evaluating the empirical risk is the main bottleneck in PAC-Bayes learning. Some extra discussion on the difficulty of querying the empirical risk in models based on solving differential equations would help appreciate the scope of the contribution. 2- Related to the previous point, it would be nice to provide concrete examples of "physics, biology or medical inspired problems" for which your approach applies, because otherwise, the scope of the contribution might be unclear.

Questions

1- I don't understand Hypothesis 5, what does substituting $\pi_\theta$ by $\theta$ mean?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

The limitations are well discussed in Section 7.

Summary

The paper explores the problem of optimization where estimating the empirical loss is computationally expensive. By optimizing the PAC-Bayes posterior distribution on an appropriate surrogate function, the paper derives an optimization strategy that minimizes the PAC-Bayes upper bound on the expected loss with potentially fewer empirical risk queries, as they provide an approximation that may be valid further away compared to linear approximations. The paper proves the validity of this optimization process, applies it for exponential families, and discusses an extension of this strategy for the meta-learning setting. Finally, the paper provides empirical experiments for both the single task and meta-learning settings.

Strengths

* The paper is both interesting and a promising avenue for future research. * The overall originality is **very high**. To the best of my knowledge, the topic of optimizing PAC-Bayes while trying to minimize queries to the risk function is entirely novel. While the techniques themselves may not be new, they are combined in a novel manner and setting. This work clearly differs from previous work on PAC-Bayes optimization. * The submission is *well-organized* and mostly *clear*. Theoretical results are discussed and clarified, and the overall flow of the paper is good. There are several minor issues and missing details in the theoretical results and formulae, but they are easily fixable. * Theoretical claims are proven, and empirical claims are supported by simple experiments. The authors are honest regarding the strengths and limitations of their results.

Weaknesses

* The overall technical quality of the paper is **medium**. There are minor errors and missing definitions in a few of the proofs (see questions), and the empirical experiments are quite lacking (see questions for specific issues and some suggestions). * The significance of the results is **medium**. The potential impact of this paper is somewhat limited, as it is focused on learning problems where risk estimates are computationally expensive (e.g. model requires solving ODEs/PDEs), and is therefore mostly relevant to domains in Physics, Biology, and medicine. Furthermore, the framework presented in the paper is only relevant to settings where the parameter space for the predictor is low-dimension, meaning that this framework is (by the authors’ own honest admission) not effective for optimizing deep learning models with few risk queries. *The theoretical results only provide a guarantee on the validity of the approach, and offers nothing with regards to the number of risk queries (in either the average or worst case), and the numerical experiments are not sufficient for inductive reasoning in the absence of such theoretical results.

Questions

* Typos, grammatical errors and minor technical issues: * In section 3 line 119, "A few hypothesis”->"A few hypotheses” * In section 3 line 130, "$\infty$ PAC-Bayes bound”->"unbounded PAC-Bayes bound” (this is also dependent on how the KL-divergence is defined for missing support in the prior, and as such may actually be undefined rather than unbounded) * In section 3 line 132, "for adequate parametrization”-> "for any adequate parametrization”/"for adequate parametrizations” * In section 3 line 133, "of PAC-Bayes bound”->"of PAC-Bayes bounds”, and same for the next line. * In the proof of Theorem 1 line 145, the term $\partial_3 \tilde{PB}(\theta,\pi_\theta[R],\pi_p,\gamma)$ should be $\partial_2$. * In section 3 line 159, "paves the way for heterogeneous proxy”->rephrase. * In section 6 line 323, "this could be explained to the”->"this could be attributed to the”. * In corollary 1 line 170, $M(\pi,\theta,f,\gamma)$ is undefined. * In theorem 3 line 493, $\mathcal{C}^2$ is undefined (presumably, this means twice continuously differentiable) * The caption in figure 2 (page 14) incorrectly attributes the images: the weighted predictors should be the lower right figure (and not lower left picture) and the linear regression should be the lower left figure (and not lower left picture). You should also be consistent in your terminology and refer to all of them either as figures or pictures. * In section 4.1 line 200, the closed-form solution for the optimum of Catoni’s bound given that both prior and posterior are from an exponential family should be attributed to a source. * Why are your assumptions ($h_1-h_7$) called hypotheses? * In figure 1 detailing the experimental results, the achieved (expected) risk for the learned posterior is not reported or shown, only the PB upper bounds. Are the final bounds tight? How do they compare to the results reported in [2]? * The stability of SuPAC-CE is attributed in section 6 to the "generation agnostic” weighting scheme. This could serve as an interesting ablation: would i.i.d. weights from the posterior (or the corrected sampling discussed in 4.2.1) serve as a less stable but still effective predictor weighting scheme for SuPAC-CE? Would this method require significantly more risk queries? * The statement made in section 5 lines 292 to 296 is slightly problematic. The meta-training objective defined in section 5 only provides guarantees on the training tasks, not on unknown test tasks. Adding test tasks to the objective and optimizing over them would indeed extend this guarantee to each new task, but does not offer a valid upper bound on unknown tasks, which is commonly the objective of PAC-Bayes meta-learning as mentioned in lines 271-273. This is admittedly a fairly minor point, but these statements can be misinterpreted as currently written. * Empirical experiment observations and recommendations: * Figure 1a (and figures 3,4 in the appendix) only compare the achieved PB objective for gradient descent and your method. As gradient descent is well-known for slow convergence rates, and since your approach makes use of additional inductive bias in the choice of the parametric family and the closed form solution, it makes sense to include additional, more informed reference points to better emphasize the benefits of SuPAC-CE. Namely, Nesterov momentum GD is easy to add as one such reference point (the included code already allows for it). * The meta-learning experiments are wholly synthetic, and contain no external reference points, so it is unclear whether SuPAC-CE is actually effective for this setting. The experimental set-up described B.3 appears to be highly fine-tuned, and it would be interesting to see how well it can generalize to other problems. * The setting of optimization with expensive risk queries does seem to lend itself naturally to few-shot meta-learning as a solution, and there are likely advances in PAC-Bayes meta-learning for the few-shot setting that are applicable here. A good starting point to consider would be [1]. In addition, since this setting naturally lends itself to few-shot learning, it would be interesting to see whether the rapid improvement rate of SuPAC-CE allows it to achieve better test generalization. This is especially interesting since the bound optimized by SuPAC-CE is not a "mean task” bound but rather a training task bound. * Comparing and contrasting the difference between your setting and settings that seek to minimize sample draws such as Active learning may help emphasize the novelty of the discussed problem. In similar essence, comparisons to research on differentiable physics can further emphasize that the optimum values achieved are exact despite optimizing a surrogate of the risk.

Rating

5

Confidence

4

Soundness

2

Presentation

3

Contribution

2

Limitations

The authors have sufficiently addressed both the limitations of their work and any potential negative societal impact of their work.

Rebuttal comments and rating change given revisions

Your rebuttal is good and addresses several of the key issues highlighted in the reviews in my opinion. (Empirical validation) The additional plots on Nesterov momentum GD help show that the benefit of SuPAC-CE in terms of risk queries to convergence is not just a product of efficient optimization or good hyper-parameter tuning (though naturally, that plays a role in overall performance). Explicitly stating the expected risk achieved by your approach compared to previous results as well as the PB objective is important to the empirical validation. I would also suggest calculating the full PB bound for a confidence of $\delta=0.05$. Regarding the point raised in the global rebuttal regarding measuring the optimization over a PB objective in terms of that objective: while this is correct, it is important to note that this is almost always accompanied by comparing the final expected risk and/or the PB bounds. You have done so in your rebuttal, and I expect this to be in your revision. (Meta-learning) At the current point, the segment on meta-learning offers no theoretical results, and the empirical validation is too preliminary to provide significant insight beyond SuPAC-CE being well-behaved on a synthetic meta-learning problem. The topic of meta-learning with a low budget on empirical risk access can likely be a full paper on its own merit. The current section on meta-learning with its validation do little justice to this topic and it is my opinion that this paper would be better served by extending the empirical validation of its main results instead and including the discussion regarding actual computational costs from your rebuttal of reviewer 7ntj. **Assuming the revisions are added, I would like to change my score to 5: borderline accept**, as the revised empirical section would be sufficient to outweigh reasons to reject. While the paper deals with an original concept with high potential impact, the empirical evaluation is too limited for me to be comfortable with a higher score. PS: Theoretical results on the gap in convergence speeds (vs. number of risk queries) would also be sufficient instead of more comprehensive empirical results, but I suspect that would be very difficult to achieve, and require different theoretical tools.

Aknowledgements

First and foremost, I would like to express my gratitude to the authors for their detailed feedback. Assuming the authors' answer for my review, along with the revisions suggested to Reviewer ku1E and those indicated in the global rebuttal, are reflected in the text, I believe this paper would warrant a score of 5 or 6. I suggest offering one major revision opportunity to fully incorporate these changes and revise the presentation. For these reasons, I intend to keep my score as it is at this stage. The content of this paper is very interesting, and I expect that a revised submission will receive better scores in the future conference.