Learning via Surrogate PAC-Bayes
Authors: Antoine Picard
Roman Moscoviz
Benjamin Guedj
Venue: NeurIPS 2024 poster (2024)
Keywords: PAC-Bayes
Generalisation
Optimisation
Learning Theory
Primary area: learning_theory
TL;DR: We introduce a novel approach for learning via surrogate training objectives inherited from PAC-Bayes generalisation bounds, offering computational efficiency and theoretical support, with applications to meta-learning.

Abstract: PAC-Bayes learning is a comprehensive setting for (i) studying the generalisation ability of learning algorithms and (ii) deriving new learning algorithms by optimising a generalisation bound. However, optimising generalisation bounds might not always be viable for tractable or computational reasons, or both. For example, iteratively querying the empirical risk might prove computationally expensive.
In response, we introduce a novel principled strategy for building an iterative learning algorithm via the optimisation of a sequence of surrogate training objectives, inherited from PAC-Bayes generalisation bounds. The key argument is to replace the empirical risk (seen as a function of hypotheses) in the generalisation bound by its projection onto a constructible low dimensional functional space: these projections can be queried much more efficiently than the initial risk. On top of providing that generic recipe for learning via surrogate PAC-Bayes bounds, we (i) contribute theoretical results establishing that iteratively optimising our surrogates implies the optimisation of the original generalisation bounds, (ii) instantiate this strategy to the framework of meta-learning, introducing a meta-objective offering a closed form expression for meta-gradient, (iii) illustrate our approach with numerical experiments inspired by an industrial biochemical problem.

Learning via Surrogate PAC-Bayes
Antoine Picard-Weibe Inria & SUEZ; France
Roman Moscoviz SUEZ, France roman comaa.mosccrizzauuezccom
antoine. aettone.picard... ext@suez.com
Benjamin Guedj
Inria and University College London, France and United Kingdom
benj amin
Abstract
PAC-Bayes learning is a comprehensive setting for (i) studying the generalisation ability of learning algorithms and (ii) deriving new learning algorithms by opti- mising a generalisation bound. However, optimising generalisation bounds might not always be viable for tractable or computational reasons, or both. For example, iteratively querying the empirical risk might prove computationally expensive. response, introduce novel principled strategy for building iterative learning algorithm via the optimisation a sequence of surrogate training objectives, inher- ited from PAC- Bayes generalisation bounds. The key argument is replace the empirical risk (seen as a function of hypotheses) in the generalisation bound by its projection onto constructible low dimensional functional space: these projections can be queried much more efficiently than the initial risk. On top of providing that generic recipe for learning via surrogate PAC-Bayes bounds, (i) contribute theoretical results establishing that iteratively optimising our surrogates implies the optimisation of the original generalisation bounds, (ii) instantiate this strategy to the framework of meta-learning, introducing a meta-objective offering a closed form expression for meta- geea-ggaddent, (iii) illustrate our approach with numerical experiments inspired by an industrial biochemical problem.
Introduction
Generalisation arguably one of the central problems in machine learning. Among the different techniques to study generalisation, PAC-Bayes has gained considerable traction over the past decade, as evidenced by the surge in publications. We refer to the seminal works of Shawe-Taylle and Williamson [1997], McAllester [1999], Catoni [2004, 2007] and to the recent surveys and monographs from Guedj [2019], Hellström et al. [2023], Alquier [2024] for a thorough overview the field.
One appealing feature is that PAC-Bayes learning is comprehensive setting for (i) studying the generalisation ability of learning algorithms and (ii) deriving new learning algorithms by optimising PAC-Bayes generalisation bound. This is the strategy pursued in number of recent works, among which Germain al. [2009], Biggs and Guedj [2021], Germain et al. [2015], Viallard al. [2023], Zantedeschi et al. [2021]. J]. Rivasplata et al. [2019], Pérez-Ortiz et al. [2021] 1], Zhou et al. [2019].
We now regard this strategy of substituting generalisation bound more classical training objectives as established, and we focus here on the computational aspect of this strategy. Indeed, optimising generalisation bounds might not always be viable for tractable or computational reasons, or both.
"Centre International de Recherche Sur l'Eau et I'Environnement. Depaarmeet of Computer Science and Centre for Artificial Intelligence.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Most PAC-Bayes bounds do not admit a close form minima formulation; moreover, such bounds involve expectations and divergence terms which in general settings can not be evaluated in closed form and thus require the use of approximation methods such as Monte-Carlo sampling (see amongst others Seldin and Tishby [2010], Dziugaite and Roy [2017]. Neyshabur et al. [2017]. Mhammedi et al. [2019]). Such approximation methods can prove computationally intensive, notably if the empirical risk, whose expectation is optimised in the bound, is hard to query. Ficard-Weibed et al. [2024] reports that such queries proved to be the main computational bottleneck when optimising PAC-Bayes bound in bio-chemical model calibration task. More generally, models whose predictions require solving stiff ordinary differential equations (ODE) or partial differential equations (PDE), such as naturally occurs in physics or biology inspired problems, result in empirical risks whose query can be computationally expensive, in practice all but making numerous iterative computations of PAC-Bayes objective's 's gradients impracticable.
In response to the aforementioned difficulties for optimising PAC-Bayes generalisation bounds in practice, we introduce a novel principled strategy designed to mitigate the computational cost of querying the empirical risk, Surrogate PAC-Bayes Learning (SuPAC, see algorithm 1). We build a learning algorithm which iteratively optimises a sequence of surrogate training objectives in which the empirical risk is replaced by proxy. This proxy is built as the orthogonal projection of the true empirical risk on a functional vector space of finite dimension, which we conjecture can be queried much more efficiently than the initial risk. A key motivation is that such surrogate objectives can offer adequate approximations of the true objective valid much further away than the linear approximation offered by the gradient, and enable larger optimisation steps. This effectively decouples the complexity of querying the empirical risk and optimising PAC-Bayes objectives.
Our contributions. We list below our four main contributions, spanning theory, algorithmic, application to meta-learning and numerical experiments.
1. We provide a generic recipe for learning via surrogate PAC-Bayes bounds, which we believe is of practical interest for machine learning tasks involving computationally intensive models with moderate dimension (e.g. physics models with less than few hundred parameters),
2. contribute theoretical results establishing that iteratively optimising our surrogates implics the optimisation of the original generalisation bounds. This is established by Theorem and further developed in Corollary and Theorem 2,
3. instantiate this strategy to the framework of meta-learning, introducing a meta-objective with closed form expression for meta-gradient
4. illustrate our approach with numerical experiments inspired by an industrial biochemical setting using an anaerobic digestion model.
The paper is organised follows: in Section 2 set the stage and introduce generic framework. In Section 3, we construct functional approximation spaces and establish generic guarantees for framework. In Section 4, we focus Catoni's bound [Catoni, 2007] and describe a practical implementation of our framework. In Section 5, we investigate how our surrogate PAC- Bayes minimisation strategy can be used in meta-learning settings. Numerical experiments described in Section Future prospects are discussed in Section 7. The manuscript closes with an appendix in which gather (i) technical proofs in Appendix A, (ii) implementation details in Appendix B.
Outline.
2 A generic surrogate framework
Consider a measurable space H of predictors, denote P the set of all probability distributions on H. and M(H) the set of measurable real valued functions. For probability distribution E P. let (T) (resp. (T)( denote the set of integrable (resp. square integrable) functions with respect to For a f E (T),,, =[f] denotes the mean of f with respect to (the notation is extended for functions outputting vectors), while for functions in (T). [xl denotes the variance of f (resp. covariance).
A PAC-Bayes bound, denoted PB, can generically be summarised as a real valued function of four variables: a generic distribution w E P, prior distribution Tp E P. an empirical risk function P. and other factors which regroup y (e.g. the confidence level, the PAC-Bayes temperature, the

---

size of the dataset). A PAC-Bayer theorem states that, under given assumptions on the data generation mechanisms and risk, the average risk function R = E R satisfies for some function !
P P E P, π T S PB (T,, R, pp, 7)] 2 7(7))
where the probability is taken the data generation mechanism. Due to the bound holding simul- taneously for all distributions with high probability, it notably holds with high probability on the minimiser of the bound, hence the PAC-Bayes minimisation task
arg inf PB (T, R, Tp: 7) TEP
We consider restriction of this minimisation task on a subset II P of all probability distributions. Such a restriction might be justified by various considerations, including storage of the calibrated distribution, simplification of the minimisation task or even expert knowledge [Alquier et al., 2016, Dziugaite and Roy, 2017, Picard- Weibel et al., 2024]. However, even this simplified minimisation problem might prove computationally difficult for Gradient Descent (GD) based algorithm. This is especially the case when evaluating the empirical risk is costly, e.g. when the prediction model involves solving stiff ODEs or PDEs. As PAC-Bayes bounds depend on the T-mean of the empirical risk, each gradient estimation rely on numerous new evaluations of the empirical risk. For ODEs S S F(S, f, f) where F is very sensitive with respect to S, numerous evaluations of F are required to obtain adequate numerical solutions in given range [fo,4]] These evaluations must moreover be performed iteratively, and hence can not be parallelized. Moreover, implementing the ODE solver in way to benefit from GPU speed up when simulating for multiple parameters rs simultaneously might not be practicable, since most ODE solver use a varying step size which will depend This will result in typically long model calls which can not be massively parallelised. To overcome this difficulty, we introduce the Surrogate PAC-Bayes bound learning framework (SuPAC), which is based on alternatively building and solving surrogate problems. It is designed to reduce the number of calls to the risk and consequently, in ODE example, the ODE solver.
Formally, we consider an approximation algorithm F : II x M(H) + M(H) in conjunction with an approximate solving algorithm Solve : P x II x M(H) + II. Informally, F constructs proxy of the empirical risk valid for the current posterior estimation m:; while Solve updates the posterior estimation by solving the resulting surrogate objective (Algorithm 1).
Algorithm offers a lot of leeway for building surrogates (e.g., iteratively refining an ODE or PDE solver, tailor-made surrogates for phys- ical models, polynomial approximations) as well as solving the surrogate problem. For such framework to be practicable, two con- ditions should apply: the construction of the surrogate and approximate solving should be faster than solving the initial problem, and the algorithm's 's result should tend to diminish the PAC- PAC-Bayes bound. Intuitively, the choice of the approximation mechanisms plays critical role; indeed, the more precise the approxima- tion, the more likely is the minima of the surrogate task to be close to the true minimiser, but the harder the approximation task and the surrogate construction task.
Algorithm 1 Surrogate PAC-Bayes Learning framework (SuPAC)
Require: PB, To E II, Tp E P, R M(H)
+ To
while not converged do f F(T, R)
+ ---SoolleeTpp IJ)
end while
3 Constructing surrogate function spaces
A core contribution of the present work is to show that for generic PAC-Bayes bounds and generic probability families II of dimension d, (T) orthogonal projection of the true score on a functional vector space of dimension d 1 is sufficient to obtain convergence guarantees.
few assumptions on the PAC-Bayes bounds, the risk R and the probability family II are required. Assumptions.
(A1) II {mg. 0 E θ) is parametric set indexed by an open subset θ C Rd;
dep (A2) v0 E O, ne is absolutely continuous with respect to up and dra (x) = exp(E(O,,x)) with
0 + f(0, x) differentiable for all x;
3

---

(As) A0 E θ, 3N a neighbourhood of f such that z + MMPOEN,10be(CA E (moo)
(A4) Decel
(As) There exists PB such that (T R, Tp: ( Ty Ry) the empirical risk is limited to the posterior average of the empirical risk), Moreover, PB is differentiable with respect its two first arguments.
Tp: (i.e. PB's dependence
We emphasise that these assumptions are valid for essentially all PAC-Bayes bounds, most risks, and for a wide variety of probability distributions, and are thus rather more technical than restrictive. Although the second assumption rules out probability distributions whose support is not included in the prior support, we remark that such distributions usually yield vacuous PAC-Bayes bounds due to penalisation termss (e.g., vacuous Kullback-Leibe Most standard family distributions, including Gaussian and Gaussian mixtures, satisfy (A₁) (As) for adequate parameterizations. The fourth assumption is automatically satisfied for all bounded risks, which is a typical assumption of PAC-Bayes bounds, but also allows for unbounded risks provided that they are square integrable (e.g. polynomials if II span Gaussian would satisfy (A4)). The last assumption is satisfied by most PAC-Bayes bound, e.g. those of McAllester [1999], Maurer [2004].
divergence), and as such are already ruled out.
Since II is parameterized by θ, we will abuse notations for functions of II and write G(0) == G(TT): For given 0, the functional vector space Fe := [fn.c æ + 17 0gL(0, x) + C 1 E R C R] provides natural upproximation space of dimension d + 1. We now in position to state main approximation result.
I
Theorem 1. Under assumptions (A1) to (As), replacing the empirical risk R by the proxy risk
f == arg inf Tol(R - f)
FEFo
leaves the gradient of the objective PB invariant, i.
3 (0,,, R2 np. 7) = PB(, [ RR. Tp; mp: 7)-
This result also holds if the approximation space Fo is replaced by Fo + := -f + Fo, for any set G C (TT).
Proof. Assumptions (Aa) and (A4) allow differentiating 0 - no
| R under the integral
sign (see Theorem 6.28 in Klenke [2020]), yielding Vx [R] nh [ā . As such, the derivative of (B, No R Tp. 7) with respect 0 equals 0 (B, (, RR. Tp. 7) + a,PB(8 No R), Tp. m) [Rōbe].
As the only dependence on the gradient with respect to is on the value of [ at which the derivative is evaluated and on the vector no [R0 it follows that OB is not modified by replacing R by function (TT))) satisfying the following linear system:
To [R0ge] [o]
no [f]fe [o]s]-
By construction of Fo, the linear system (3) is satisfied if and only if ( R) E Ft. where A+ denotes the orthogonal complement of A in L.2 (TT)) Hence for any set G c (.) the orthogonal projection of R on f Fo + G satisfies the linear system (3). Noticing that the orthogonal projection fR.0 of R on space JE satisfies fn. arg inf se fe mo
f) ends the proof.
Informally, Theorem 1 guarantees that if searching for PAC-Baye posterior in space of size d, adcquately projecting the score on a space of dimension at most + 1 preserves the immediate surrounding of the PAC-Bayes objective. If the approximation built at 0 maintains performance for a large neighbourhood of 0, this surrogate task provides a valid approximation the true task for a wide range of distributions, and offers approximate solutions Ø much further away than the range of validity of the objective's gradient.
optimal
The extension of the result for Fo + G implies that proxy score functions combining a known, simplified model with learnt correction term can be used. For G {h}, it implies that the result

---

holds if the approximation space consists of a fixed user defined proxy and correction term. This can have direct practical implications in settings where efficient, natural proxy are available; the learnt corrective term would presumably be smaller, and hence the approximation's validity larger.
A direct consequence of Theorem 1 is fixed point characterisation of the minima of the PAC-Bayes objective for instances of Algorithm 1 using GD based surrogate solver (see proof in Appendix A.1):
Corollary 1. Under assumptions (A1) (As), the minimiser 0 of the original PAC-Bayes bound is fixed point of any instance of Algorithm 1 such that:
* the approximation function is F(TT, R) == arg inf fEF, Tol(R f)²
the surrogate solving Solve strategy is any (corrected) gradient descent strategy starting at the current 0, using update steps of form Upd = M(x, 0, I; (: (.)))) J.Tp: ?). where M stands for any function returning an endomorphism, for any number of steps, any convergence criteria.
It should be stressed that Corollary 1 does not imply that Algorithm improves on GD. Corollary 1 only guarantees that replacing the score by a low dimensional approximation is harmless locally. Informally, if the approximation built at 0 maintains near optimal performance for large neighbour- hood of 0, this surrogate task provides a valid approximation of the objective for this wide radius, and can construct approximate solutions 0 much further away than the range of validity of the gradient. SuPAC decouples the variations of the bound due to the evolution of 0 and fa,R; such a decoupling is particularly interesting the approximation f is stable.
Exponential family and Catoni's bound
4.1 Closed form surrogate solution and fixed point property
Theorem involves approximation of the empirical risk through orthogonal projection on a local functional vector space Fg of dimension at most d + 1. A setting of particular interest concerns families of probabilities such that the space F8 does not depend on A. Exponential families, i.e. family of distributions of the form
dxg doTect
= cxp(0.T T g(f) + h)) m
11 TT
well studied class of probability family which satisfy this property (and essentially the only such class if θ is connected and the likelihood smooth, see Theorem 3 in Appendix A.3). The approximation space can be written F = {fc. 0 T C). Without loss of generality, assume that functions (1,Ti..... T2) are linearly independent.
Exponential families define tractable, yet flexible class of probability families, spanning from simple, fixed variance distributions to multimodal distributions [Cobb et al., 1983J. They englobe most familiar distribution families such as multivariate Gaussians, Beta and Gamma [Brown, 1986). The approximation space they generate can equally vary. For Gaussian distributions, we remark that F covers quadratic forms.
We now focus on the celebrated PAC-Bayes bound from Catoni [Catoni, 2007, Alquier, 2024],
C2
PB (T, Tp. R, (2,8, C)) T T[ + AKL mp) + 8An
Alog(6),
(4)
where (L( v
is the Kullback-Leibhe divergence and is the PAC-Bayes temperature. Catoni's bound holds with probability 1 5 if 0 < R < C. Due to its particular form, minimising the bound amounts to minimising the simpler objective ObjeanA == x R + XKL mp)
dz) de
For simplicity, we will assume that Tp = Ta, E e. In this setting, (A1), (A2) and (A4) are automatically verified. A key incentive to use Catoni's bound is that the surrogate objective can be solved in closed form; for risks of form fn.c, if the prior belongs to the exponential family, the minimiser of Catoni's bound on belongs II, and it follows that
arg inf PBca To, no, S0,c) Ö(n) = 0, x x=
5

---

provided that Bg - - 1 E θ (if not, Catoni's bound does not admit a minima) (see Lemma 2.2, and Corollary 2.3 in Alquier [2024]). Since the posterior distribution does not depend on the constant term C we will note Jn for any Jn,C E F..
We here the exact solution of the surrogate PAC-Bayes bound rather than have minimise the bound through GD. The following lemma (proved in Appendix A.2) bridges the gap by showing that the update rule using the closed form solution can be interpreted as a corrected GD step:
Lemma 1. Consider an exponential family II {To | 0 E Q} with sufficient statistic T. Noting = Usg x x 1I (x) + C v E R. C E R., let fn E Then for any prior parameter Op- E e
for any parameter 0, the mapping ((1) = 0g x 1 satisfies:
= - - PB (0, pp fu 1
where I(0) denotes Fisher's 's information matrix.
direct consequence of Lemma 1 is that Corollary 1 applies when using the exact solver for the
surrogate Catoni task. Since Fisher's s information is positive, follows that the update direction 0 always diminishes the bound locally. We summarise these results in the following theorem.
Theorem 2. The minimiser of Catoni's 's PAC-Bayes objective on exponential family is fixed point of Algorithm with approximation functiooo
F(TTE R) = arg inf To(( f)²],
FEF
and surrogate solver
Solve(Tp; 0, --- arg inf PBça (0, Tp: Jn: 7)- dee
Moreover, for all 0,
PPCaa (Solve(Tp:: F(O, R)) 0) S.
As noted above, the solution of the surrogate task must belong to θ to define a probability distribution. There however no guarantee that such is the case for any approximated risk. For instance, if the risk is estimated close to local maxima by a quadratic function, the resulting surrogate task might not have a minima, and hence the resulting ((n) might fail be probability distribution, causing the algorithm to break. Another difficulty lies in solving the approximation task. Involving an integral of a function the risk, the objective theoretically requires evaluations of the risk all predictors. We show in the next section how both these issues can be solved in practice.
4.2 Framework implementation: SuPAC-CE
Following Theorem 2, we propose an algorithm, SuPAC-CE (uttps://githus t/gt com/ APicardWeibell /srrbbbyssss designed to efficiently find the minimiser of Catoni's bound on Exponential families.
4.2.1 Implementing the approximation
As the surrogate PAC-Bayes bound is solved using closed form expression, the computational bottleneck of Algorithm is the approximation task of computing 17(0) arg inf Tol(S, R [f - 2. Due to the form of fy, this formally a least square weighted linear approximation problem with infinite number of observations, whose solution can be explicitly written as
V V=[71-1 π [R[T π [TT]]. This solution can be approximated using a finite number of function evaluations R(x;), replacing the probability by an empirical counterpart Temp = Σ wydr..
Different choices of (Ir; can be considered. A first approach consists in drawing i.i.d. samples from Fe and considering uniform weights. This guarantees that the approximated objective is unbiased. A main shortcoming of this approach, however, is that it disregards all previous risk evaluations at each step. Corrections of the form dite dag can be used salvage samples drawn from Tz. all the while guaranteeing unbiased approximated objective. This however can drastically increase the variance, and thus might not be practical.

---

We advocate a generation agnostic approach for the weighing process, which treats all available risk evaluations like manner. We assume that H. is a metric space. For all predictors (2i) whose risk R(x;) known, target weights W; are defined as the probability given the Voronoi cell I; by distribution ne. This target weight can be approximated using Monte Carlo simulations and solving nearest neighbour in (Zt)aE(L.N]) tasks, The distance used for the Voronoi cell can depend on the distribution xe -'e... Mahalanobis distance for Gaussian exponential families). This approach requires. if the empirical distribution Σ wx, is to form an adequate approximation of the distribution TT. some queries from to Ty. The stack of function evaluation is hence appended at each approximation step by evaluating samples from mT. As this weight computation can bring some overhead, it is only appropriate when risk queries are the main computational bottleneck.
4.2.2 Boundary issues
PAC-Bayes bounds typically hold for empirical risk functions satisfying moment bounds (with respect to the data generation mechanism) or boundedness conditions (the latter being usually required for Catoni's ' bound). Such assumptions might no longer be met for the approximated risks. A consequence is that the minimiser of the surrogate task might not exist. For instance, a local quadratic approximation of the score near a local maxima can induce a surrogate task whose minima is inf.
To ensure that for any score approximation fn,c, c. the surrogate solver always define probability distribution, two regularisation hyperparameters klmax and O'max are introduced. klmax E R_. U +00 determines the maximum step size allowed between two successive posterior estimation, measured in Kullback-Leibler divergence. m'max Ej0, 1] acts as dampening hyperparameter. The corrected update rule is changed to (f)
a(f(n) 0) + with the highest a I mmax such that (0. 0) S klmax- Such á can be easily obtained through a Newton scheme or dichotomy, noticing that it is defined through (ā) C' for a non decreasing function
This modification does not impact the fixed point property of Theorem Moreover, if the empirical risk A belongs to F, choosing klmax < 00, Q'ax = 1 results in convergence in finite number of steps (resp. exponential convergence for Quux < 1) (see Appendix A.4).
Remark 4.1. While SuPAC-CE is designed to optimize Catoni's PAC-Bayes bound (4), it can serve as a work engine for the minimisation of other PAC-Bayes bounds. For instance, Proposition 2.1 from Germain et al. [2015] implies that Maurcer-Langford seeegerr--'-'''ss 's bound (MLS bound, Maurer [2004], Langford and Seeger [2001] can be rewritten as
Obieu.
(5()))))
exp
PB = inf X=0
An
22
exp (-1/(Xn))
As such, the minimisation of MLS bound could be performed by alternatively minimizing Catoni's s objective at fixed temperature using SuPAC-CE and solving on the temperature at fixed posterior. The generation agnostic weighing approach moreover implies that re-optimising Catoni's objective after a small change of temperature can be done with few new risk queries (see the strategy developed in Section 5). This strategy is further detailed in Appendix C.
Surrogate Catoni in a Meta-Learning framework
Both the Bayes and PAC-Bayes framework offer a natural connection with Meta-Learning. both involve a natural inductive bias in the form of the prior. Previous work which studied Meta-Learning for PAC-Bayes include Pentina and Lampert [2014], Amit and Meir [2018], Rothfuss et al. [2023], Zakerinia et al. [2024]. The aim of PAC-Bayes Meta-Learning is the construction, from a sample of independent train tasks, of a prior yielding optimal generalisation bounds new unknown test tasks. Such optimisation of the prior brings two benefits: tighter generalisation bounds (smaller penalisation); and simplified PAC-Bayes learning task (better initial guess). For PAC-Bayes meta learning, a natural training objective can be derived from the minimised PAC-Bayes bounds obtained for each task. This defines the following meta training objective, analogue to empirical risk the meta level:
M(Tp)
Σ inf PB Ra, Tp: rlll
(5)
7

---

where tH denotes the task posterior and is a function of Rg, Tp and Ti- The objective defined in Equation (5) departs from previous formulations which typically involve a further penalisation term at the meta level. We advance two justificcations for this simplification. First, the extra penalisation term involves divergence terms between a meta prior and meta posterior (hoth distributions on probability distributions) which in practice make the bound vacuous and thus of limited practical interest. Second, PAC-Bayes theory already offers guarantees on the generalisation performances of each test task, limiting the need to assess the generalisation performance at the meta level. Arguably, the task specific bound provided by using PAC-Bayes as inner algorithm is more informative than the "mean" task bound offered by meta PAC-Bayes algorithm (when PAC-Bayes learning is used both as inner algorithm and meta training algorithm).
We consider that assumptions (A,) to (As) hold, and also these further mild assumptions: the prior is looked for in II, i. R the PAC-Bayes bound PB is differentiable w.r.t. 0z- Then, noting 0, the posterior parameter for each task, a simplification of the meta gradient occurs:
VO,,,) = Ôo, (0,) Rs, Pp. n)) a,,,, R2, Op.0p.77. 7:).
(6)
Remarkably, the knowledge of the derivative of Ô, with respect to Op is not required to compute the meta gradient. This is due 8 PB being when evaluated for the prior posterior. We stress that such a simplification is specific to our meta-learning objective. It does not occur in meta- meaanneg strategies such as MAML [Finn et al., 2017], where the performance of each task is assessed on a test set. In the context of PAC-Bayes, such reliance on test sets can be optimistically replaced by the PAC-Bayes bounds, which give test guarantees with high probability. is unclear whether such a simplification occurs in previous PAC-Bayes Meta Learning objectives from the literature, as these involve distributions on priors rather than a single prior.
A key consequence is that training the meta learning algorithm is as hard as cycling all the Bayesian optimisation tasks. In a nutshell, meta learning as hard as re optimising the bound for new prior.
SuPAC-CE brings two main benefits when used in conjunction with meta-learming First, by improving the optimisation efficiency for given prior, SuPAC-CE speeds up the meta-learning procedure. Second, the "generation agnostic" weighing approach implics that risk revaluations from previous optimisation procedures can be reused. As consequence, optimisation of PAC-Bayes bound for a new prior can conceivably be performed with few risk queries, bringing an additional speed-up. Moreover, the setting considered for SuPAC-CE enjoys an analytical expression for meta- veta-graddents, (0,)) (Vv((0))) Vg((p)) which can be efficiently evaluated.
6 Experiments
SuPAC-CE was assessed on the learning task described by Picard-Weibel et al. [2024]. A PAC-Bayes bound is minimised on Gaussian distributions with block diagonal covariance in order to calibrate 30 parameters of a biological inspired numerical model describing anaerobic digestion processes, ADMI [Batstone et al.. 2002]. This model relies on solving a stiff ODE to predict the evolution of the states, and is therefore quite computationally intensive (about 3 seconds per model query in our experiments).
We compared SuPAC-CE to standard GD on a synthetic dataset from Picard- Weibel et al. [2024], using the same family of distributions and risk function. For SuPAC-CE, 160 risk queries where performed for the initial step, and 32 for all further step. A maximal budget of 9600 empirical risk queries was fixed; hyperparameters for the GD were selected after evaluating a grid on the first 1600 queries. Mean risks were assessed at test time by resampling new predictors from the posterior. The PAC-Bayes temperature was set to 0.002. Training procedures were repeated 20 times.
The performance of the sequence of posteriors were compared by aligning the number of empirical risk queries. Indeed, the main motivation of SuPAC-CE is the setting when querying the empirical risk is computationally expensive, and can be assumed to be the computational bottleneck. This is indeed the case for the anaerobic digestion example considered here. At equal number of risk queries, SuPAC-CE required an extra 3.5% processing time compared to gradient descent, mainly caused by the weighing process.
SuPAC-CB proved significantly more efficient at minimising the bound than GD (see Figure la). The average performance of our algorithm proved better after 1800 queries than the best performance
8

---

0.6
Gradient Descent SuPAC
Meta Objy M = 0.011
0.6
Train meta-score
Tast meta-score
0.5
Tast score flact
0.5
Objective
0.4
0.2
50
100
150
Training iterations
0.3
Meta Obj (t =.1)
Train meta-score
0.125
Test meta-score
0.2
0.100
Test score fluct
0.075
0.1
0.050
2000
4000 Number of emp. risk queries
6000
8000
10000
100
150
Training Iterations
(a) Optim. perf.
(b) Meta Learning
Figure 1: Experiments results. Figure la compares the optimisation performance of our algorithm SuPAC-CE with gradient descent approaches on an biochemical calibration task. Optimisation procedures were repeated 20 times; median performance and quantiles 0.2 and 0.8 are represented. Figure 1b investigates train and test performance of the meta-learning approach of Section 5. Mean test performance, as well quantiles 0.2 and 0.8 for the sequence of built prior is assessed on 40 tasks and compared to the train performance. SuPAC-CE reduced the PAC-Bayes objective to 0.121 + 0.004 (avg. risk of posterior of 0.102 0.003).
obtained after the full 9600 queries for GD. The experiments also indicate that our procedure offers much higher stability compared to GD, both during training and between the training duplicates. This could be attributed the "generation agnostic" weighing approach, which relies on all previous risk evaluations at each step and is thus more stable. On the other hand, the noisy gradients estimates have some probability of leading to problematic steps during GD, leading to sharp increase in the objective. In our experiments, out of 20 GD procedures thus led to a worse performance than the one obtained by a single optimisation step of SuPAC-CE. The posterior distributions constructed through SuPAC-CE obtained an average empirical risk of 0.102 + 0.003, similar to the 0.101 value reported in Picard- Weibel et al. [2024]. The resulting PAC- PAC-Bayes bound proved also similar (0.121 0.004 vs. 0.122). Thus SuPAC-CE constructed good posterior as Picard- Weiibel al. [2024], but twenty times faster.
Further assessments of SuPAC-CE's performance for other hyperparameters values and comparison to Nesterov accelerated GD were also conducted. SuPAC-CE proved have a stable behaviour for wide range of hyperparameters value (0.25 < Qmax 0.75, 0.5 < klmax < 2), with instabilities starting to appear for kimax > 5, and speed decrease for klmax < 0.1. Nesterov accelcration, requiring some iterations to build up momentum, proved unable to compete with SuPAC-CE's almost instantaneous optimisation. Results for these experiments can be found in Appendix B.
Preliminary experiments were also performed for the meta-learning objective described in Section 5. To facilitate the evaluation of the learnt meta priors, wholly synthetic risk functions were used in this case, and PAC-Bayes objective minimised on Gaussian distributions. The risk functions considered were bounded, smooth functions of IR$ achieving their global minima at zip N(ão, Eo). To was chosen so that || 2, and Eo such that only two of its eigenvalues are higher than 0.052 (drawn at random between exp(-1) and exp(1)). Such choices ensure that the original prior distribution, (0, Is), be improved upon both by shifting its mass centre and adjusting its covariance. The performance of the meta-learning algorithm was assessed for two temperatures, X 0.1 and x 0.01. Meta training was performed using stochastic gradient descent. The sequence of prior thus constructed was evaluated on a further 40 test tasks, each time restarting the optimisation procedure from scratch, and evaluating the final score 10 draws from the posterior.
The meta- learning algorithm was able to satisfactorily reduce the objective, from an initial average generalisation bound of 0.61 (resp. 0.14) to 0.24 (resp. 0.050) after 1 150 gradient steps for À = 0.1 (resp. 0.01). Most of the meta-objective reduction takes place during the early phase of training, with the first 15 steps amounting to more than 80 % of the objective decrease. For both temperatures

---

tested, the average performance on the test tasks followed the objective decrease throughout training, even though the number of queries per optimisation was minimal after the first meta step (less than 40), supporting both our meta-learning objective and the use of SuPAC-CE.
Full implementation details the experiments can be found in Appendix B and in the source code ()-
7 Discussion
The present work shows that it is possible to locally decouple the complexity related to querying the empirical risk and the minimisation of a PAC-Bayes bound. A main motivation for such decoupling is that the approximated risk function defines non linear surrogate objective which might be valid (i.e. close to the original objective) for wider range of probabilities than the linear approximations offered by the gradients. As a consequence, the surrogate bound solution can be reasonably allowed to be much further away from the current posterior estimation than is the case for GD. key implementation difficulty remains picking the range of validity, i.e. how far away from the current posterior the surrogate solver can be allowed to choose a distribution. Such a choice, formalised in the selection of an adequate surrogate solving algorithm, is analogue to the choice of step size in gradient descent procedures, and balances the stability and speed of the procedure. Automating the selection of the surrogate validity range offers an exciting prospect for the framework.
The Voronoi cell weighing approach used solve the approximation problem is equivalent to replacing the empirical risk function by a I-nearest neighbour trained predictor, and approximating this predictor. Variants following this two step approximation approach could be worth investigating. Notably, an interesting perspective would be to approximate the empirical risk through Gaussian processes, taking inspiration from Gaussian Optimisation. This would notably track the uncertainty on the approximate risk on extrapolated values, which could drive the choice of new predictors to evaluate and improve on the current random draws.
A key restriction of the present work is that our surrogate PAC-Bayes framework is only practicable when the dimension of the predictor space and of the probability family are small (i.e. less than a few hundreds). This is due to two factors; first of all, the larger the dimension of the probability family, the larger becomes the upproximation space, and hence the more empirical risk evaluations are required. Notably, at least d + 1 evaluations of the empirical risk are required for probability families of dimension d. The second factor that the "generation agnostic" weighing approach described in Section 4.2.1 is unlikely to give adequate performances if H is high dimensional. This effectively rules out deep learning settings, which have been recently the main focus of the PAC- Bayes community. Still, we believe that PAC-Bayes learning offers meaningful prospects for wide range of physics, biology or medical inspired problems which involve few parameters and expensive model computations, and therefore can be efficiently trained using framework. Concrete fields of application of SuPAC-CE include, but are not limited to, fluid dynamics simulations with dimension reduction [Callaham et al., 2021]. metabolic models for microbial communities [Cerk et al., 2024] and greenhouse gas emission inverse problems [Nalini et al., 2022]. We remark that, as of now, PAC-Bayes has not been much used outside of the learning community. While this be vastly attributed to lack of awareness of PAC-Bayes theory outside of the learning community, the use of PAC-Bayes was also hampered by the fact that previous PAC-Bayes algorithm required a prohibitive number of simulations and hence computation time. We believe SuPAC-CE is game changer in that respect, due to its focus on limiting the number of risk queries, and readily usable implementation. and we hope that this can be leveraged in different disciplines.
Conclusion. We introduced generic framework for minimising PAC- bounds designed to tackle computationally intensive empirical risks for low to moderate dimensional problems such as naturally arise in physical models. We established that our optimisation strategy was theoretically well supported. We instantiated this framework for the optimisation of bounds on exponential family, and considered how this implementation could interact with meta-learning. Preliminary experiments showed that our framework could significantly reduce the number of empirical risks queries when calibrating a biochemical model, thus opening exciting new fields of applications for PAC-Bayes.
10

---

Acknowledgments and Disclosure of Funding
We warmly thank reviewers and the Area Chair who provided insigthful comments and suggestions which greatl helped us improve our manuscript. A.P. acknowledges support by ANRT CIFRE grant 2021/1894, B.G. acknowledges partial support by the U.S. Army Research Laboratory and the U.S. Army Research Office, and by the U.K. Ministry of Defence and the U.K. Engineering and Physical Sciences Research Council (EPSRC) under grant number EP/R013616/1 B.G. acknowledges partial support from the French National Agency for Research, through grants ANR- 1-R18--0 18--188--- CE40-0016 and ANR-18- CE23-0015-02 and through the programme "France 2030" and PEPR IA on grant SHARP ANR-23-PEIA-0008.
References
Pierre Alquier. User-friendly introduction to PAC-Bayes Bounds. Foundations and Trends@ in
Machine Learning, 17(2):174-3033 2024. ISSN 1935-8237. doi: 10.1561/22000000000.. URL
http:// //tp:///xx..a doi. oro.o/gg///// 1ttp:/....111222000000 1561/2200000000.
Pierre Alquier, James Ridgway, and Nicolas Chopin. On the properties of variational approximations of Gibbs posteriors. Journal of Machine Learning Research (JMLR), 17(236)11-41, 12 2016. URL http:// jmlr. httg//apers/vv1/111 290. html.
Ron Amit and Ron Meir. Meta-leaming by adjusting priors based on extended PAC-Bayes theory. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 205-214. PMLR, 10-15 Jul 2018. URL https::/proceeddiiee
mlr. www.ppressseeeee hw0//mmtttttmmmeeemmeem//meeaaaa amammmiiii mimit18a.. html.
Damien J. Batstone, J. Keller, Trini Angelidaki, Sergey V. Kalyuzhnyi, Spyros G. Pavlostathis, A. Rozzi, W.T.M. Sanders, H. Siegrist, and Vasily A. Vavilin. The IWA Anaerobic Digestion Model No I (ADMI). Water Science and Technology, 45(10):65-73, May 2002. ISSN 1996-9732. doi: 0..1166/wst20002.0239 URL http: / dx doi. org/ 1aoeg///...00 w1t.:/st.....e.. 2002. 0292.
Felix Biggs and Benjamin Guedj. Differentiable PAC-Bayes objectives with partially aggregated neural networks. Entropy, 23(10), 2021. doi: 10.3390/e231012880 URL https:t////// / /ww.//wwww..... www...
com/1099-433 0019999-330/200 /3/0//3/0011133 22////33///2222 10/0.
Lawrence D. Brown. Fundamentals of statistical exponential families: with applications in statistical decision theory. In Statistics. Ims, 1986. ISBN 0940600102.
Jared I.. Callaham, Chrrsttst Loiseau, Georgios Rigas, and Steve L.. Brunton. Nonlinear stochastic modelling with Langevin regression. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 477(2250), June 2021. ISSN 1471-2946. doi: 10. 1099//p/ss... 2021.0092. URL http: /xx doi org/10 10 1098/1spe. 2021.0092
Olivier Catoni. Statistical learning theory and stochastic optimization. In Jean Picard, editor, Lecture Notes in Mathematics: Saint-Flout Summer School on Probability Theory XXXI 2001. 2004. doi: 10.1007/b99352. URL. https: //doi. org/ 10. 10070000//0 /b99352.
Olivier Catoni. PAC-Bayesian supervised classification: The thermodynamics of statistical learning. IMS Lecture Notes Monograph Series, 2007.
Klara Cerk, Pablo Ugalde-Salas, Chabname Ghassemi Nedjad, Maxime Lecomte, Coralie Muller, David J. Sherman, Falk Hildebrand, Simon Labarthe, and Clémence Frioux. Community models of microbiomes: Articulating metabolic modelling and metagenome sequencing. Microbial Biotechnology, 17(1), Jamuary 2024. ISSN 1751-7915. doi: 10.1111/1751-7915.1 14396. URL http://dx.doi dow. www.::/ooo..ogg////// 1 11111111111119911 14396.
Loren Cobb, Peter Koppstein, and Neng Hsin Chen. Estimation and moment recursion relations for multimodal distributions of the exponential family. Journal of the American Statistical Association, 78(381):124 130, 1983. doi: 10.2307/2287118. URL httpstts:///oi.ooot org/ 10. 2307 22///122777111
Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Peeree-Emmauul Mazaré, Maria Lomeli, Lueas Hosseini, and Hervé Jégou. The Faiss library, 2024. URL. https: // /arxivv. org/ abs/2401.11....///////////////// 08281.

---

Gintare K. Dziugaite and Daniel M. Roy, Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Proc. Conf. Uncertainty in Artif. Intell. (UAI), Sydney, Australia, 8 2017. URL. https://doi. org/10. 48550/ arxiv. 1703. 11008.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In Doina Precup and Yee Whye Teh, editors. Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 11 1126-1133 PMLR, 06-11 Aug 2017. URL. httttp::/ppoceedinng mlr. www.ssmw........./...... finn17a. html.
Pascal Germain, Alexandre Lacasse, François Laviolette, and Mario Marchand. PAC-Bayesian learning of linear classifiers. In Proc. Int. Conf. Mach. Learning (ICML), Montreal, Canada, 06 2009. doi: 15511444/53333415534411 URL https:///doi... org/ 10. 1111 1555/45 1553419.
Pascal Germain, Alexandre Lacasse, Francois Laviolette, Mario March, and Jean- Cean-Francis Roy. Risk bounds for the majority vote: From a (PAC-Bayesiee analysis to learning algorithm. Journal of Machine Learning Research (JMLR), 16(26):787 860, 2015. URL http:/ /jmrr.r....... org.ooooo/ooo papers/
v16/ 1/6/germain15a. html.
Benjamin Guedj. A primer on PAC-Bo AAC-Bayesian learning. Proceedings of the Second Congress of the French Mathematical Society, 2019.
Fredrik Hellström, Giuseppe Durisi, Benjamin Guedj, and Maxim Raginsky. Generalization bounds: Perspectives from information theory and PAC-Bayes, 2023, URL 2309. 04381.
org. abs/
Achim Klenke. Probability theory: a comprehensive course. Springer, 2020, doi: 10.1007/
978-3-030-56402-5. URL https:://oi.oooottt 101.///0.0.0000970--333333
Serge Lang. Fundamentals of Differential Geometry. Springer New York, 1999. ISBN
9781461205418. doi: 10.1007/978-1-4412-053.
URL http://dx.de/ ort....r/100000..
978-1-4612- 0541-88.
John Langford and Matthias Seeger. Bounds for averaging classifiers. 2001. URL http://www.c.. jttp///pecppppes//////// cmu. cmu.edu/" edw/"jcullcci//"e/// jttp/"jcc////// papers/ wwtprr//aveaaannn/eeee www.ggggiiaaaagggng.... tech. tech.pdf.
Andreas Maurer. A note on the PAC-Bayesian theorem, 2004. URL https::/aaxxi..rg///////
cs/0411099.
David A. McAllester. PAC-Bayesian model averaging. In Proceedings of the Twelfth Annual Conference Computational Learning Theory, COLT '99, page 164-170, New York, NY, USA. 1999. Association for Computing Machinery. ISBN 1581131674, doi: 10. 10.1145/374400.37745. URL https: :/dp::///d.... org/10. 10. 1145/307400.. 307435.
Zakaria Mhammedi, Peter Grünwald, and Benjamin Guedj. PAC-Bayes un-expected Bernstein inequality. In Proc. Conf. Neural Inf. Process. Syst. (NeurIPS), volume 32, Vancouver, Canada, 12 2019. URL https: //tiriaii.../////// hal secieencchhaa-0241222222
K. Nalini, Thomas Lauvaux, C. Abdallah, Jinghui Lian, Philippe Ciais, Hervé Utard, Olivier Laurent, and Michel Ramonet. High-resolution Lagrangian inverse modeling of CO2 emissions over the Paris region during the first 2020 lockdown period. Journal of Geophysical Research: Atmospheres, 127(14), July 2022. ISSN 2169-8996. doi: 10.1029/2021j80036032. URL http: doi org/ 10.
Behnam Neyshabur, Srinadh Bhojanapalli, David A. McAllester, and Nati Srebro. Exploring gen- eralization in deep learning. In Proc. Conf. Neural Inf. Process. Syst. (NeurIPS), Long Beach, CA, 12 2017. httpthtttts//occeeeeee www.kinnnn...niiineeeeeeee. neurips.e.. cccppps....ppppppppeepeeecpeppee ftwppaapllele////eeepppppaaeeeel (Dee0aaaee0..07eeee2993555533323 Pappee
Seaper_fleesspppe///01///// http/ppppe//2////1/eee/
Anastasia Pentina and Christoph Lampert. A PAC-Bayesian bound for lifelong learning. In Eric P. Xing and Tony Jebara, editors, Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 991 19999 Bejing, China, 22-24 Jun 2014, PMLR. URL https: /ttp://///ccee.s..../// mlr. wwwsssevseee2 wttp///i/pppenaa..//////m/ html.
12

---

María Pérez-Oriee Ortiz, Omar Rivasplata, John Shawe- Taylor, and Csaba Szepesvári. Tighter risk cer- tificates for neural networks. Journal of Machine Learning Research (JMLR), 22((27):1-40. 2021.
Antoine -eirrd,,,,el,, Gabriel Capson-Tope Tojoo Benjamin Guedj, and Roman Moscoviz. Bayesian uncertainty quantification for anaerobic digestion models. Bioresource Technology, 394:130147, February 2024. ISSN 0960-8524. doi: 10. b0016/..iortccch.223...... 130147.. URL http://da doi.
org/10. 1016/j biortech. 2023. 130147.
Omar Rivasplata, Vikram M Tankasali, and Csaba Szepesvari. PAC-Bayes with backprop. arXiv, 10 2019. doi: 1885500arxii.1908.77333 URL https://doi org/ 10. 48550/ (01/550/arxv.1111 arxiv.1908. 07380.
Jonas Rothfuss, Martin Josifoski, Vincent Fortuin, and Andreas Krause. Scalable PAC-Bayesial meta-learning via the PAC-optimal hyper-posterior: From theory to practice. Journal of Machine Learning Research, 24(386):1-62 2023. URL bttpps//jjmt
pwppes///4//ee/ppppaappppppp/pea 22 1254.
html.
Yevgeny Seldin and Naftali Tishby. PAC-Bayesian analysis of co-clustering and beyond. Journal of Machine Learning Research (JMLR), 11(117:3395-3646, 12 2010. URL http: //jmrr/mmrrrrr/ org/
papers/v11/ /eli//eeldnnnaammm html.
John Shawe-Taylor and Robert C. Williamson. A PAC analysis Bayesian estimator. Proc. Conf. Learn. Theory (COLT), 7 1997. doi: 10. 10.1145/264400.267466 URL https:/ddoii org/
10. 1041//6674600.... 2tt.5/222776..276666.6. 267466.
Paul Viallard, Maxime Haddouche, Umut Şimşekli, and Benjamin Guedj. Learning via Wasserstein- based high probability generalisation bounds. arXiv, 2023. doi: 10.46550/rrxiw22000.43337
URL https: //1///1///// 48550/ 48550/arXiv arxiv. 2306. 04375.
Hossein Zakerinia, Amin Behjati, and Christoph H Lampert. More flexible PAC-bayesian Meta- Learning by learning learning algorithms. arXiv preprint arXiv:2402.04054, 2024.
Valentina Zantedeschi, Paul Viallard, Emilie Morvant, Rémi Emonet, Amaury Habrard, Pascal Germain, and Benjamin Guedj. Learning stochastic majority votes by minimizing PAC-bayes generalization bound. In A. Beygelzimer, Y. Dauphin, Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021. URL https: //pp///eeee//eeee//////e net/ forum?id= Dorum?idd22L5mmmVWBd..
Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P. Adams, and Peter Orbanz. Non- vacuous generalization bounds the ImageNet scale: PAC-Bayesian compression approach. In Proc. Iut. Conf. Learn. Representations (ICLR), New Orleans, LA, 5 2019. URL htLttts://opperreee //wpereeeee....../// net//poffideBBBgsscctt.
13

---

A Technical proofs
A.1 Proof of Corollary
As assumptions (A1) to (As) hold, Theorem 3 can be used. It implies that replacing R by fR.
does not change the gradient of PB. Hence, starting from 0 0r, since O O,PB( R, mT 7) o P0"",0 f p, 7) = O, the update step in the solving strategy satisfies Updi(0") = 0"
M 0, f, 7) x = 0 Hence, by recursion, follows that Solve(Tp: f assume that F(TTO. R) f this implies that T² is fixed step of π - Solve( F(T, R))), and hence that the posterior fixed point of SuPAC for the specified F and Solve strategies, concluding the proof.
T0- Since we
A.2 Proof of Lemma
We consider the broader problem where the prior тp might not belong to the exponential family, but any probability satisfying the following assumptions:
Assumptions.
(As) Tp is absolutely continuous with respect Trffi
(A7) 40 E O, h = log
dip.. diti
E (TT)
Note that when Fp II, one can use Tιi = Tp for which assumptions (Ag) and (Az) are automatically fulfilled. The generalisation of the approximation space becomes
Un = 0- C Ah),
which fits into the framework described in Theorem For any fn E F, the solver of Catoni's bound on all distributions is given by 0 - provided this defines a probability distribution (else Catoni's bound does reach its minima on II or P). Note that the choice of is coherent with the formula given in Lemma 1 when the prior belongs to II, since in that case h = 0p T, leading to change of coordinate in the definition of F.
Under the assumptions, Catoni's bound is differentiable and its gradient with respect to 9 can be computed under the integral. Thus, for score fup
PBCaa
=T Vg(())) + Amo (0 T g(0) h)(T - Vo(O)) Tol(f X0 - -00) AT Vg)i
Tol(Jn, X0 T AT) - [T)]
-T C) no [T]] AV (
Vx,,TT + 20)
where use the well known identity Te (7) Vg (see Brown [1986]). For exponential families,
the variance V., [T) coincides with Fisher's information, and hence the previous equality reads
<PBca (I ((n)), which implies Lemma 1.
A.3 Probability families with constant approximation space
Theorem considers projections of the risk local vector space of functions Fo. A special case of interest concerns families of distributions such that the approximation set is constant. Exponential families offer such characteristic. We show here that exponential families (and its restrictions) the only smoothly parameterised distributions with this characteristic:
Theorem 3. For family of distributions satisfying the first three hypotheses of Section such that, moreover:
② a connected,
f ((0, x) is twice continuously differentiable for all x.
If there exists a vector space of finite dimension F such that Fg C F for all 0 E O then there exists an exponential family 11T defined on & and connected, open set On such that II {np 0 E On).
14

---

Proof. For F of dimension d + 1, choose 71, ..... Ta. T4t1 = 1 a basis of F. Then, for all 8, there exists a unique matrix A(0) E IRd.d, and unique vector E Rd.1 such that
Ti Ta+1
Oge (A(0) c(0))
Assume that A(0) and c(f) are differentiable (this is proved afterwards). Since is twice continuously differentiable, it follows 0s, de, f = 0o, 0e f, and therefore that 0g, Aj. = 0g Ai, and that de C, This, in conjunction with the hypothesis that θ is connected, implies that A(0) a gradient (see Lang [1999]). Hence, (()) = 3(0) T(x) - ((0) + h for a solution of 0gh = 0. Since @ is connected, this implies that can not be function of 0. Hence II the restriction of an exponential family on O.
of some 3 Rd Rdd while is the gradient of some -g R
remains to show that A()) and c(0) are differentiable. First of all, we remark that for all finite collection of linearly independent real valued functions (f1,..., fn)) there exists d points (#1.-..,44 Fn such that (f(z)))).sss is inversible. Indeed, this result holds for a single function, since fi must be non zero. Then if the result holds for 21.-... Jkk Le. D (E) o 0 then consider the with ă 2j if S k. . = z. Then the determinant matrix m Df (z) Eisk Cif((z). Since /1,... fa++1 linearly independent and since D is not zero, there must exist z such that det(mn()) + 0, which we can pick as 2k+1- This proves the result by recursion.
matrix (2) = (f.())).sss
Since Ti.... T are linearly independent, of A(0) and c(O). it follows that for all 8,
therefore pick such ................................ zd+t By definition
0o, ((0,21)
Oo, ((0,
(i(1))
Ti(aan)
(A(0) c(0))
(111
T241 (24t))))))
Oo 21)
Oog ((0, xz41)/
This implics that A and e are linear combinations of the differentiable functions (0e(, s:))),d.) and hence that they are differentiable.
A.4 Regularisation and convergence for Catoni's bound
If R = fn E F. the uncorrected step direction results one step convergence, implying that the update direction at 0 is 0. This implies that all successive estimation 0, belongs to the segment 10o, 0). Note A0 = - 0o. Since the normalisation function is strictly convex, follows that the function A0 Vg(0, + (A0) is non decreasing, and hence, for all 1,
AO (g( AO Vg(0, + +10) < A0- Vg(().
Using the convexity of g. this implies that for f < 12, (+o + 1 1,))) g(00 + t2) S ((1 Do gg((p) while (t2 t, Ao Vg(0 + tz (t2 t1) (g(
follows that for all l < 12,
KL + 1 A0, O. + 1 A0) S (12 4)40 (Vg(0) Vg(Oo))
This implies that for 0; = 0g + t, A, 0.11 = 0o + 1++1 A0, if the condition KL(0,+1, 0.) < klmax
is active, then 4+1 - 4 2 (V -v(())) Since 4,-1 - 4; > 0 and for all i, 4 < 1, this
kl klaan
this implies convergence in a finite number of steps. For 0 S Qmax < 1, this implies that after some K,
implies that the condition is active finite number of time at most. In the case amax
t+ = (1 )max)' ) tx), and hence exponential convergence of (0.) to 0.
15

---

B Implementation details
The code described in this section can be found in the publication repo: https:///ittub..om APi walcaaeeebellsurbbaaaa.a..
B.1 Further notes on SuPAC-CE
SuPAC-CE can be summarised in the following pseudo-code:
Algorithm 2 Surrogate Catoni solver for exponential families (SuPAC-CE)
Require: À > 0, 0g E O, Op E O, Re M(H), (mi, R(x)))==+ 0 < Omax S 1, klmax
< 0o
while not converged do
Draw i..d. Tn+1,..... Tntk ne
Ev,n + Ev ((In+1, R(Zn+1))..... (In+R) R(In+x))) n
Wi 4 -
> Solving nearest neighbour problems
7¹ C = arg inf ing R.C. Eisn wi (T(:). - -R(x;) - C)2
50 0o- - -x-1n1
f
< sup a < Omax: KI. + ad0, 0) S klma
0 + 0 + ad0
end while
Our implementation is based the pre-existing code source provided by Picard-Werr al [2024]. Part the original code was reworked to our new setting. New classes for exponential families of distributions were introduced, and implementation of the Gaussian family classes modified accordingly. A modular and generic solver class for the minimisation of Catoni's PAC-Bayes bound on exponential families introduced, well families outputting Gaussian distributions, using the Mahalanobis distance when approximating the weights. These solvers rely on closed form expressions for the Kullback-Leible divergence and its derivative, inferred from the normalisation function and its derivatives.
specific implementations for probability
The default weighing approach for the score approximation uses exact 1-NN for user specified number of samples ("n estim weights" argument), performed using Faiss library [Douze et al., 2024]. Another weight approximation method, relying approximate k-NN solving, is also provided.
The corrected update rule parameter â is estimated by dichotomy, using the fact that for all 0, 50, the function - KI.(# a50, 0) is not decreasing. The resulting ă is guaranteed to result in Kullback-Leibler step of less than klmax-
B.2
Experiments
B.2.1
Catoni's bound minimisation
The implementation of ADMI from Picard-Weibel et al. [2024] was used to perform the experiments, and slightly modified benefit from just-in-time compilation. The dataset used was the training part of dataset "LFF.. The probability family (Gaussian with block diagonal covariance with fixed blocks) and prior distribution considered in the original paper was used. For SuPAC-CE, the regularisation hyperparameters were set to klmax = 1 and Obmax 0.5, while the number of samples generated to evaluate the weights was set to 40 000. The optimisation algorithm was trained on 296 steps; for the initial step. 160 risk queries were performed, while for all the remaining steps, 32 risk queries were performed. This larger number of queries for the initial step is due to the necessity of having a least more evaluations than the dimension of the family of probability.
Hyperparameters for GD were selected after assessing the grid per step E {80. 160), step_ size x (0.025, 0.05, 0.07) on preliminary 1600 score queries budget, with 20 repeats. The larger step size 0.07 was rejected due to erratic behaviour between repeats, obtaining both optimal and worse GD performance. This erratic behaviour was also observed for step size 0.05 when estimating gradients from 80 risk queries. On the other hand, for per_step set to 160, the step size of 0.025 clearly under- performed compared to the step size of 0.05, although slightly more stable. This led to the selection of
16

---

Draw predictors Evaluate score
SuPAC
Update Posterior
Weigh predictors
Linear least
square
Figure 2: Overview of SuPAC-CE. At each step, some new predictors are drawn from the current posterior approximation and evaluated (top right figure). All evaluated predictors are then weighted according to the weight of their Voronoi cell (bottom right figure). These weighted evaluations are used to construct an optimal approximation left figure). The approximated score is used to update the posterior using closed form expression (top left figure). This procedure is looped until convergence (center).
the score through a linear least square task (bottom
0r0.26 per tip-16 p-i.i e4c
(ri pM 010 PNLRRRN
GR (HEA) PRLIRI-OR
popiip-10
04-
64
0.5-
03
63-
07x
20
466
900
1003
120
3408 200
201
466
800
1003
1200 5406 2000
200
400
680
689
2000 12:0 1400 1069
ofume
(a) 17 0.025
(b) 1y= 0.05
(c) 0.07
Figure 3: Preliminary GD optimisation procedures for different choices of hyperparameters. The evaluations of each optimisation procedure was repeated 20 times; the median performance and 0.2 and 0.8 quantiles represented. The performance of SuPAC-CE is given for comparison.
the two sets of hyperparameters, ste_=st, which had similar performances. Both were assessed, and the set of hyperparameters obtaining the lowest score, (per_step=160, step size=0..z... was kept for comparison (see Appendix B.2.1).
and pper_step=160, step_sizeed sippsiize0005)
SuPAC-CE was further compared to Nesterov accelerated gradient descent (implementation in the publication repo). Starting from the two sets of hyperparameters preselected for GD, optimisation procedures using momentum of 0.5, 0.9 and 0.95, and either the original step size or twice the step size were assessed. Each of these new optimisation procedures was repeated 8 times, and compared to SuPAC-CE (see Appendix B.2. For choice of hyperparameter values did Nesterov
17

---

0.6
GD, n=0.025, per per_step=80
GD, n=0.00 per_step=160
0.5
SuPAC
Objective
0.4
0.3
0.2
0.1
2000
4000
6000
8000
10000
Number of emp. risk queries
Figure Comparison of the optimisation procedures as performed by SuPAC-CE and gradient descent (GD) for the two selected sets of hyperparameters. Each optimisation procedure was repeated 20 times; the median performance and 0.2 and 0.8 quantiles are represented. SuPAC-CE was performed with hyperparameters Omax 0.5 and klmax
accelerated GD proved more efficient than SuPAC-CE (Appendix B.2.1). The increase of step size conjunction with the moderate momentum improved the speed of the optimisation procedure, but at the cost of higher risk of optimisation failure, leading to 3 out of 8 runs (resp. 2 out of runs) for 160 simulations per step (resp. 80 simulations per step) with final objective higher than the initial objective. Higher momentum led to major instabilities, with less than 3 runs out of 8 managing to reduce objective below 0.2 (compared to 0.121 obtained by SuPAC-CE) for all hyperparameter combinations. For the original step size, momentum appeared to improve the stability of the procedures for all setting except moderate momentum for a per step hyperparameter of 80. Higher momentum procedures led speed decrease, caused by the larger number of steps necessary for momentum to build up.
The impact of SuPAC-CE's hyperparameters was investigated by running further optimisation pro- cedures with different choices of hyperparameters. A grid was assessed, with values of klmax in (0.5, 1, 2} and Qmax in (0.25, 0.5, 0.75), with each optimisation process repeated ten times (see Appendix B.2.1). The resulting optimisation procedures proved all have similar performances, with only slight decrease in speed in the early phase between the most regularized and less regularized hy- perparameters which was below the noise level after the fourth optimisation step (see Appendix B.2. Two further sets of slow hyperparameters values ([k)max; Ommax) E {0.11 0.9), (0.01, 0.9))) and fast peerparraeteess values ((klmax = 5, Q'ax = 0.1). (klmax = 10, amax = 0)) were also assessed, with 8 repeats (sce Appendix 1).. The slow hyperparameters led to more stable and reproducible optimisation procedures. For the small maximum step size of klmax = 0.01, the average performance of the optimisation process was similar (i.e. difference below the noise level) to the performance of the optimisation process with standard hyperparameters after 2000 risk queries. The highest maximal step size assessed of kl,max 10 resulted in final average PAC-Bayes bound of 0.147 + 0.022, with a standard deviation between runs of 0.061, significantly higher than the standard deviation for the standard hyperparameters (0.0032, p-value of 1.95e 09).
Computations were performed using Azure Machine Learning compute clusters with cores and Intel Xcon Platinum 8272CL processors.
18

---

momentum 0.5
momentum 0,9
momentum 0.95
stop 80
! RGD
(AGD 0,025)
33
G2
322
160
Ablo
4693
a830
10000
3230
<662
6930
10.03
14600
2865
+290
6648
kble
3948
IrGD 0.06)
77
SuPAC-CE
2 RGD
022
32
3000
6000
2006
6030
10300
3000
4003
6300
0003
10090
2003
4000
0003
8000
33008
Figure Comparison of the optimisation procedures as performed by SuPAC-CE and Nesterov accelerated gradient descent (x axis: number of empirical risk queries). Each optimisation procedure was repeated times; median performance and 0.2 and 0.8 quantiles are represented. SuPAC-CE was performed with hyperparameters maa = 0.5 and kl mm 1. Momentum of 0.5, 0.9 and 0.95 were assessed for Nesterov gradient descent. Both the original step size (77) parameter as well as twice the step size parameter for gradient descent comparisons were investigated. At twice the step size, all momentum accelerated procedures proved unstable. At the original step size, the momentum tended to increase the stability of the procedure at the cost of speed. All Nesterov accelerated gradient descent procedures assessed were slower than SuPAC-CE
SUPAC-CE Nesterov Gradient Descent
NestGD
0.5,
NestGD In. 0.025, mom: 0.9, per step: 80)
0.6
NestGD
NestGD In: 0.05, mom: 5, per stop: 160)
NestGD
per_step: 160)
PAC- CCC-Bayes objective
0.5-
NestGD In. 0.05, mom: 95, per per_step: 1601
0.05,
per_step:
NestGD In: 0505, mom: 9. per step: 80)
0.4
0.05, mom: per_step:
NestGD 0.1. mom: 0.5, per stop: 160)
mom: 0.9, por stop: 160)
0.3-
NestGD 0.1, mam: 0.85, stap: 160)
SUPAC (elem 0.5, deax: 0.751
SLPAC (dieai
0.5)
SUPMC (8lmes 0.5, Deeci 0.251
SUPAC
SUPAC DMrua 1.0, Seaci 0.5)
0.1
SUPAC
0.25)
0
2000
4000
6000
8000
10000
SLPAC (diaw: 2.0. draci 0.75)
Number of risk queries
SuPAC (elewi 2.0, Geaxi 0.25]
Figure 6: Comparison of SuPAC-CE with Nesterov accelerated gradient descent for variety of hyperparameters choices. Each optimisation procedure was repeated 8 times; the median performance and 0.2 and 0.8 quantiles are represented. SuPAC-CE proved to be consistently more efficient for all hyperparameters values tested. The hyperparameter for SuPAC-CE assessed in the main part of the publication is highlighted.
19

---

"Fast" hyperparameters
0.6
PAC- Et-Bayes objective
klmax "nax klmax 5, Oau
0.5
"Standard" hyperparameters
PAC-Bayes
0.4
kmmax 1.0, "nn 0.5
0.3
"Slow" hyperparameters
klmax 0.1, Gua 0.9 klmax 0.01, Aax 0.9
0.2
0.1
2000
4000
6000
8000
10000
Number of risk queries
Figure 7: Performance of SuPAC-CE with extreme hyperparameters values. Each optimisation procedure was repeated times; the median performance and 0.2 and 0.8 quantiles are represented. SuPAC-CE exhibited noticeable instabilities and speed loss for hyperparameters leading insufficient regularization (blue curve). Too much regularisation lead to speed decrease in the early phase of the optimisation procedure (purple curve)
B.3 Meta-Learning experiments
For the meta-learning experiments, the tasks were generated as follow. Empirical risk functions of form
A x tanh(h(w]] zo)il z=)01²)/10))
with h(z) = cos(2) + considered. These such that zy is the only global minima of R,,A,s while all ins such that w|| A(x xo) ]| = 7/2 /2 + 2kT are local minima. The distributions of the risk parameters are as follow: Zi ~ (ão, En), w (3 5x) and A,,; ~ ( x² 0.052). The mean parameter Zo was initiated at random on the sphere of radius 2, while the covariance Eg was initiated at random as
Σ. O diag(o? o 0',
where JI...., 0--2 orthonormal matrices. The dimension of the predictor space is fixed 8.
02-2 = 0.05, da-1, ~ exp(U(-0055 0.5)) and O drawn at random amongst
The meta training process was performed follow. The initial calibration phase for each task was performed in 15 steps. with 100 score queries for the first five steps and 50 score queries for the remaining steps. The hyperparameters were set to klmax = 0.5, Qmax = 0.3 and 10* samples are used to estimate weights. This initial meta step used mini batch size of 10, maximum meta kl step of 0.2 and step size of X -1 After all tasks have been trained once, the hyperparameters for and O'ax set to 0.7. 20 risk queries
SuPAC-CE were modified: the number of steps are performed on the first and third step, and none on the second and fourth. This accounts for the fact that the posterior distribution updates are expected be small at this stage. The mini batch size is increased to 20. After 19 epochs, the step size is reduced to 0.5A and the maximum meta kl step to 0.1. After 30 more epochs, the step size reduced 0.4A-1 and trained for further 100 epochs.
reduced
The performance of sequence of priors was assessed in the following way. 40 test tasks were drawn. For each prior, full independent calibration of SuPAC-CE (100 risk queries for the first 5 steps, 50 for the remaining steps). The resulting posterior performance is assessed by computing the bound using 10 fresh evaluations of the risk. The mean of these performance over the task defines the meta test score. The dispersion these test performance between different test task is assessed by computing the quantiles 0.2 and 0.8 of the test performances at a given prior. This procedure being quite computationally intensive, only the first ten priors constructed and afterwards prior out of five were assessed.
performed on each task, using 20 steps
Computations were performed using Azure Machine Learning compute clusters with 16 cores and Intel Xcon Platinum 8272CL processors.
20

---

C SuPAC for Maureer-Laggorr--eeee''' bound
We here provide details for the use of SuPAC-CE for the minimisation of Maureer-Langford- -eeggrr's objective, as mentionned in Remark 1.1. Maurer-Langford Laae-----rrrrreeeeerss bound [Maurer, 2004, Langford and Seeger, 2001] states that, for i.i.. observations 2,, risks R 22 -i=1 lzz with 0 I c. S 1, for any 0 < 5 < 1, with probability at least 5, for any posterior distribution π < Tp.
1 [KL(TT, Tp) log (E(m)
kl( [
R
-
(8)
where E(n) n and kl(g, is the Kullback-Leibler divergence between two Bernoulli distribu- tions with means g and p. respectively. Germain et al. [2009] noted that kl(g, p) satisfies
kl p) max C20
log (1 - p(1 (sp(-c))-Cop CC)
(9)
Equation (9) can be plugged in the MLS bound (8), and, after the change of variable X = C-1, ttis implies that with probability at least 6,
- exp( Am (T [ + AKL(TT, lug(E(n)/6)
PB (T[R) n. T. A)
holds simultaneously for any measures
< pp and any temperature À 0.
At fixed temperature À > 0, minimising the right hand side equivalent minimising [[R] (KL(mT, Tp). which is the objective defined by Catoni's bound. At fixed posterior the right hand side smooth function of the temperature, and derivatives of arbitrary orders can computed (L(T, Tp) and л Ft] are known. Searching for the minimiser of Seeger's bound in an exponential family leads to Algorithm relying on SuPAC-CE for optimisation a given temperature.
Algorithm 3 Surrogate May-Bayes Learning for MLS (SuPAC-MLSE)
Require: PB, To E I1, Tp E P, R M(H), Ao E Rt.
+ To - Ag
Ev =
No evaluations
while not converged do
n, Fy <- SuPAC-CE(RR p. n, A,,, Ev)
Evaluate [R]
Use Ev Closed form
Evaluate KL,(m, mp)
À + arg infAso PBMLS R] A)
e.g. Newton, Houscholder
end while
In practical implementations of Algorithm 3, the hyperparameters of SuPAC-CE should be modified after the first optimisation procedure lower the number of risk queries. Indeed, the risk queries from previous optimisation procedure (conducted at other temperature) are used in new optimisation procedures through the generation agnostic weighing process. As noted section 7, this limits the applicability of SuPAC-CE, and hence of SuPAC-MLSE, to the low to moderate dimension setting.
We remark that the two level optimisation strategy pursued by Algorithm 3 relies on greedy optimisation the PAC-Bayes temperature. While this might lead to convergence to a local minima, it has the benefit of guaranteeing that the objective can only decrease during the optimisation procedure (as long as proper safeguards are put into place when using SuPAC-CE, e.g., by adapting the step size).
21

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and precede the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
All claims made in the abstract and introduction reflect the paper's contribu-
tions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
22

---

Justification: The main limits of the work are discussed in the section dedicated to discus- sions.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "I "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All theoretical results are given with the full set of assumptions and proof. These are provided both in the core of the paper and in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: link to the code executed for the experiments is provided. Moreover high level description of the code given in the main part of the submission, with additional details provided in the appendix.
23

---

Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: data and code are available in open access. Scripts enabling the reproduction of the main experimental results are provided.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ /nips. fisisscoo wttpccccppccccceeeocccecccccccet gutcc//g/////////ee /Codeeuumisssiooooool wwwssssssiioooooso for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
24

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Implementation details are specified in the appendix. The code also available. Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: uncertainty quantification is provided for the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The specifications of the compute used for the experiments are specified in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
25

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't It make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: / nnurips.....p// cc htpppli//ttiisuuuiiiiepe ines?
Answer: [Yes]
Justification:
The research did not involve human subjects participants. The data used is synthetic and therefore concern free. The authors do not anticipate any harmful consequence to their research.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics. If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: No societal impact of the paper is performed. The current paper introduces a generic methodology for optimisation of PAC-Bayes generalisation bounds. As such, specific applications and societal impacts are beyond the scope of the paper.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
26

---

Answer: [NA]
Justification:
The paper does not pose any such risk.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging. and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The creators of the assets are cited and referenced the code.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The code released with the paper is thoroughly commented and comes with demo notebooks.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
27

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "uBueckamKl", "reviewer": "Reviewer_ku1E", "summary": "The paper explores the problem of optimization where estimating the empirical loss is computationally expensive. \n\nBy 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. \n\nThe 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. \nFinally, the paper provides empirical experiments for both the single task and meta-learning settings.", "questions": "*\tTypos, grammatical errors and minor technical issues:\n    *\tIn section 3 line 119, \"A few hypothesis”->\"A few hypotheses”\n    *\tIn 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)\n    *\tIn section 3 line 132, \"for adequate parametrization”-> \"for any adequate parametrization”/\"for adequate parametrizations”\n    *\tIn section 3 line 133, \"of PAC-Bayes bound”->\"of PAC-Bayes bounds”, and same for the next line.\n    *\tIn the proof of Theorem 1 line 145, the term $\\partial_3 \\tilde{PB}(\\theta,\\pi_\\theta[R],\\pi_p,\\gamma)$ should be $\\partial_2$. \n    *\tIn section 3 line 159, \"paves the way for heterogeneous proxy”->rephrase.\n    *\tIn section 6 line 323, \"this could be explained to the”->\"this could be attributed to the”.\n    *\tIn corollary 1 line 170, $M(\\pi,\\theta,f,\\gamma)$ is undefined.\n    *\tIn theorem 3 line 493, $\\mathcal{C}^2$ is undefined (presumably, this means twice continuously differentiable) \n    *\tThe 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.\n\n* 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.\n* Why are your assumptions ($h_1-h_7$) called hypotheses?\n* 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]?\n* 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? \n\n* 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.\n\n* Empirical experiment observations and recommendations:\n    * 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).\n    * 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.\n    * 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.\n\n* 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.", "limitations": "The authors have sufficiently addressed both the limitations of their work and any potential negative societal impact of their work.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "* The paper is both interesting and a promising avenue for future research.\n* 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.\n* 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. \n* 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).\n* 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. \nFurthermore, 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. \n*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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for carefully examining our submission, and for stressing its highly original character.\n\nTypos\n- \"In corollary 1 line 170, M(π,θ,f,γ) is undefined.\"\n\nThank you for raising this. The notation M stood for any function of π, θ, f and y outputting a matrix.\n\n- \"In section 3 line 159, \"paves the way for heterogeneous proxy”->rephrase.\"\n\nThis has been rephrased as “implies that proxy score functions combining a known, simplified model with a learnt correction term can be used.”\n\n- \"In theorem 3 line 493, C2 is undefined (presumably, this means twice continuously differentiable)\"\n\nThe notation C2 does indeed stand for twice continuously differentiable. This has been clarified.\n\n\nMain remarks\n\n- Reference for the closed form optimum of Catoni's bound\n\nThis is a direct consequence of the equality case of Donsker and Varadhan’s variational formula, a proof of which is given in Pierre Alquier’s “User-friendly introduction to PAC-Bayes bounds” (Lemma 2.2, and Corollary 2.3). We have added this in the revised manuscript.\n\n- \"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?\"\n\nYour intuition is correct. It is possible to use an i.i.d. sample from the posterior at each step. In this case, there is a trade-off between the number of risk queries and convergence stability. The i.i.d. strategy would forget all information from the previous step, which in our application case is costly (3s per query). This would therefore likely work but require significantly more queries. On the other hand, SuPAC-CE has access to a growing number of risk queries at each step. We note that the extra steps involved in the generation agnostic strategy added only a negligible computation time (about 3.5%).\n\n- On the meta learning objective\n\nWe agree the original text is not explicit enough and this is now revised in the manuscript. The mention of standard meta learning in line 291, concerns non-PAC-Bayes meta learning strategies, such as MAML. These define their meta learning objective in terms of test performance of the learnt model (for each train task). Since PAC-Bayes gives upper bounds on these test performances (with high probability), our meta learning objective is constructed by replacing the test evaluation by the PAC-Bayes bounds. Clearly, there is no guarantee that the learnt meta prior will perform well on future test tasks. However, as discussed in lines 271-273, for a given test task, since the learnt meta prior and the test task data are independent, the PAC-Bayes guarantee holds for the posterior learnt from the meta prior. Such a task specific guarantee might arguably be more informative than the guarantee obtained on an average test task (which are moreover hampered by a further penalisation term at the meta level).\n\n- Comparison of SuPAC with Nesterov accelerated GD\n\nThe experiment minimizes the same PAC-Bayes bound on the same parametric family as in Picard-Weibel et al 2024. That it is an exponential family rather illustrates the prevalence and flexibility of this class rather than inductive bias on our part.\nWe had initially considered Nesterov accelerated GD for the submission. It was set aside for two reasons: first, the additional momentum hyperparameter made it harder to thoroughly explore hyperparameter combinations. Second, momentum techniques affect the optimisation procedure only once momentum has had time to build up. SuPAC-CE converging extremely fast, it appeared unlikely that the momentum accelerated GD would be much more competitive than GD. To illustrate this point, please find attached a figure comparing the performance of Nesterov GD with SuPAC-CE (Figure 1 and 2 in the pdf). We reused the best hyperparameters evaluated for GD (those of Figure 4 in the submission) and assessed: momentums of 0.5, 0.9 and 0.95, the original step size reported in Figure 4 as well as a step size twice as large. Larger step size resulted in increased instabilities. For the original step size, Nesterov GD improved on standard GD in terms of stability, but was not competitive compared to SuPAC-CE.\n\n- On the meta learning experiments\n\nThe meta-learning experiments are indeed preliminary work, requiring further insights for efficient hyperparameter tuning and adaptation – however, we felt this would be relevant to include in our submission as an illustrative example of our approach. The PAC-Bayes meta learning community focuses on deep learning settings on which SuPAC-CE cannot be used, hence the absence of benchmark. The focus of this section is to investigate whether the “empirical risk minimisation” meta-objective would positively impact the test PAC-Bayes bound, which appears to be corroborated by our preliminary experiments.\n\n- \"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.\"\n\nWe indeed believe that linking our SuPAC approach with topics such as active learning and Bayesian Optimisation offers exciting prospects for improvements, notably in improving the generation mechanism of new samples to evaluate.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GZHIKghPWe", "reviewer": "Reviewer_2FBD", "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.\nThe strategy is instantiated in meta-learning problems and a real-life biochemical modeling problem, where surrogate loss minimization outperforms gradient descent.", "questions": "1- I don't understand Hypothesis 5, what does substituting $\\pi_\\theta$ by $\\theta$ mean?", "limitations": "The limitations are well discussed in Section 7.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1- The paper is clearly written and readable.\n\n2- The theory behind the surrogate loss construction is solid, and the assumptions seem reasonable.\n\n3- 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.\n\n2- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for carefully examining our submission, and for your positive evaluation.\n\n- On the difficulty of querying the empirical risk for differential equations based models\n\nStiff ordinary differential equations (ODE) of form $\\dot X = F(X, t, parameter)$ require numerous evaluations of the function $F$, when the function $F$ might be very sensitive to the parameter $X$; in that case, the step size is necessarily small. These evaluations of $F$ must be performed iteratively, and hence can not be parallelized. Moreover, implementing in the ODE solver in a way to benefit for GPU when evaluating multiple parameters might be simple, since most ODE solver rely on a varying step size, which will depend on the parameter. This will result in typically slow simulation code. \n\n- Other use cases of SuPAC-CE\n\nHere are some examples of problems arising in different topics where calibration of low dimensional, intensive score queries naturally occur:\n\n- Metabolic models for microbial communities (Cerk et al. 2024)\n- Emission related inverse problems (Nalini et al. 2022)\n- Fluid dynamics problems with dimension reduction (Callaham et al. 2021) \n\nWe remark that, as of now, PAC-Bayes has not been much used outside of the learning/deep learning community. While this can be partly attributed to a lack of awareness of PAC-Bayes theory outside of the learning community, the use of PAC-Bayes was also hampered by the fact that previous PAC-Bayes algorithm required a prohibitive number of simulations and hence computation time. We believe SuPAC-CE is a game changer in that respect, due to its focus on limiting the number of risk queries, and readily usable implementation.\n\nQuestions\n- I don't understand Hypothesis 5, what does substituting \\pi_\\theta by \\theta mean?\n\nThe substitution of $\\pi_\\theta$ by $\\theta$ in Hypothesis 5 is used to simplify notation; while the function defining the PAC-Bayes bound takes as input a posterior distribution ($\\pi_\\theta$), we reformulate the PAC-Bayes bound as a function taking as input the parameter defining the posterior distribution ($\\theta$). We stress that this is always possible. The main point of hypothesis 5 (renamed Assumption 5 in the revised manuscript) is that the PAC-Bayes bound only dependence on the empirical risk function is in the form of the posterior average of the empirical risk (the function R is replaced by $\\pi_\\theta[R]$), which can be done for almost all PAC-Bayes bounds).\n\nReferences:\n\n- Callaham J. L., Loiseau J.-C., Rigas G. and Brunton S. L. (2021) Nonlinear stochastic modelling with Langevin regression. Proc. R. Soc. A.47720210092\n\n- Cerk, K., Ugalde-Salas, P., Nedjad, C.G., Lecomte, M., Muller, C., Sherman, D.J. et al. (2024) Community-scale models of microbiomes: Articulating metabolic modelling and metagenome sequencing. Microbial Biotechnology, 17, e14396.\n\n- Nalini, K., Lauvaux, T., Abdallah, C., Lian, J., Ciais, P., Utard, H., et al. (2022). High-resolution Lagrangian inverse modeling of CO2 emissions over the Paris region during the first 2020 lockdown period. Journal of Geophysical Research: Atmospheres, 127, e2021JD036032", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0EaNWkBknm", "reviewer": "Reviewer_7ntj", "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.\n- 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.\n- The authors also provide a theoretical guarantee, showing that minimizing their bound also minimizes the original PAC-Bayes bound.\n- They applied their framework to meta-learning, deriving an optimization scheme based on a closed-form gradient.\n- The authors validated the performance of their method using an anaerobic model in the biochemical setting.", "questions": "- Discussion on Computational Bottlenecks and Definition of Computational Burden\n  - What is the precise definition of “computational burden” as used in this paper?\n  - 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.\n\n- Presentation Clarity\n  - 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?\n- Experimental Evaluation\n  - 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?\n  - 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?\n  - 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.\n  - 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?\n- 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?\n- 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.\n- 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.\n- 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.\n- MISC: Is “Hypotheses” here used as the mean of assumptions?\n\nCItation:\nRothfuss et al. (2021): Rothfuss et al. PACOH: Bayes-Optimal Meta-Learning with PAC-Guarantees. ICML2021. https://arxiv.org/pdf/2002.05551", "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.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "- Practical motivation inspired by applications to biochemical settings\n  - 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.\n- Theoretical guarantee of the proposed method\n  - 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\n  - 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.\n  - 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.\n- Unclear presentation\n  - 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.\n- Insufficient experimental evaluation\n  - 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.\n  - 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- Computational burden and measure of the time\n\nThe main motivation for the SuPAC algorithm is to tackle settings when querying the empirical risk is computationally expensive. This covers cases when a risk query takes more than 10 ms. In the real-world example of Anaerobic Digestion model, each risk query took about 3 s. The time spent in the optimisation procedure in tasks other than querying the risk can then be deemed negligible. This was verified for the Anaerobic Digestion task considered: at equal number of queries, SuPAC-CE took about 3.5% more time than Gradient Descent, which can be taken as a good estimation of the extra processing time. Meanwhile, SuPAC-CE reduced the PAC-Bayes objective below 0.125 in 176 seconds on average, while the GD procedure managed to reduce the objective below that target in only half of the runs, and on average after 1645 seconds (more than 9 times longer). The time spent in extra processing was more than compensated.\n\nWe argue that normalising the time in our experiments results by the number of risk queries is the best option because:\n\n-\tRisk queries are assumed to be the main computational bottleneck,\n-\tThe actual computation time of the risk query and extra processing depends on implementation details and actual compute,\n-\tThe computation time of risk queries depends on the ability to parallelize risk queries (and on number of cores)\n\nThe extra processing steps in SuPAC-CE consist in: 1. solving many one nearest neighbour problems (to compute Voronoi cell weights), 2. inverting a matrix of size the dimension of the probability family considered for optimisation, 3. multiple evaluations of Kullback-Leibler divergences. The first step proved the most intensive in the case studied. If needed, it could be sped up by using approximative nearest neighbour searches.\n\nFor the general SuPAC strategy, the use of a surrogate risk to reduce computational burden follows from the assumption that the original risk is expensive (time wise) to query. As discussed in the paper, surrogate risks constructed depend on the family of probability distributions considered. Hence the cost of querying the empirical risk is determined by the user’s choice of probability distributions and will typically be orders of magnitude smaller (e.g. quadratic form vs ODE solving for the Anaerobic Digestion problem tested).\n\nFor the computational complexity for the closed form gradient in Lemma 1, we remark that the formula mentioned is not used to compute the update rule in SuPAC-CE algorithm (the update can be computed in a simpler fashion, see section 4.2 for implementation details of SuPAC-CE). Lemma 1 shows that our new approach is related to the more established Gradient Descent strategy. This helps in the theoretical analysis of our algorithm. However, neither the actual gradient, nor Fisher’s information are computed in our algorithm.\n\n- On the proofs of Corollary 1 and Theorem 2\n\nWe regret that you feel the proofs to be somewhat informal. Corollary 1 follows from Theorem 1 by remarking that if $\\theta^*$ minimizes the PAC Bayesian bound, then the gradient term is null and therefore the update rule is simplified to $Updt(\\theta^*) = \\theta^*$ (hence $\\theta^*$ is a fixed point). As mentioned in line 210, the first part of Theorem 2 is a consequence of Lemma 1 and Corollary 1, since Lemma 1 implies that the update rule is of the form described in Corollary 1, while the second part of Theorem 2 is a direct consequence of Lemma 1 and the positivity of Fisher’s information (mentioned line 211). We stress that the proof of Lemma 1 is detailed in Appendix A.1.\n\n- On the empirical validation \n\nThe theoretical claim for SuPAC-CE (Theorem 2) is that all local minima (including global minimum) of the PAC-Bayes objective are a fixed point of algorithm SuPAC-CE. Therefore, we do not claim that the algorithm will automatically converge to the global minimum, but that if our algorithm converges, it is likely that the resulting parameter is a local minima (exactly as for gradient descent). For the general case, corollary 1 shows that the SuPAC strategy has the same theoretical guarantees as gradient descent.\nThe PAC-Bayes objective is a function of a parameter defining the probability distribution. In the task considered, the parameter lives in a space of dimension 84. It is all but impossible to perform an exhaustive search to evaluate the PAC-Bayes objective. Hence it is virtually impossible to compute the PAC-Bayes bound, if by that term you mean the minima of the PAC-Bayes objective.\n\n- On the boundedness of the risk functions\n\nAssumption 4 does not imply that the losses must be bounded (but if the loss is bounded, then it satisfies Assumption 4). It only requires that all losses should be square integrable with respect to all the probability distributions considered for the optimisation of the PAC-Bayes bound. To give an example, if the probability family is the Gaussian distributions family, any quadratic form satisfies Assumption 4. Therefore, the risk functions are allowed to be unbounded.\n\n- On the choice of hyperparameters for SuPAC-CE\n\nAll hyperparameter values used for the experiments are specified in appendix 2. For SuPAC-CE, the hyperparameters were not optimised, and set to medium values (maximum kl step of 1, dampening factor of 0.5, the middle of the possible values). For the GD procedure, multiple choice of hyperparameters were assessed (see appendix 2).\nTo answer the reviewer’s concerns, a grid of hyperparameter values was assessed for SuPAC-CE (max kl step of 0.5, 1.0 or 2.0, dampen of 0.25, 0.5, 0.75, see results in the pdf file, figure 1). SuPAC-CE’s behavior proved to be not much sensitive to the choice of hyperparameter in the range assessed. Further evaluations of “fast” hyperparameters choice hinted that instabilities appeared for max kl step higher than 5, while the optimisation speed start to decrease for a max kl step lower than 0.1 (extra figure 3)", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lG3k4DyN4V", "reviewer": "Reviewer_GVtZ", "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.", "questions": "Unfortunately, the paper is too far outside my field to even start assessing where things can be clarified.", "limitations": "Limitations have been properly addressed.", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Firstly, my expertise within the area is unfortunately almost nonexistent. My apologies to the authors.\n\nWith 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their careful reading of our work. We address all relevant points in individual rebuttals below each review. We hope our answers will clarify the concerns expressed in reviews, and hopefully encourage reviewers to revise their assessment of our submission.

We address here some points raised by more than one reviewer:

-	The term “hypothesis” was meant as a synonym for “assumption.” To avoid confusion, we are now using “assumption” in the updated version of the submission.
-	Reviewers ku1E and 7ntj note that the empirical risk of the posterior is not reported. We stress that our submission focuses on the task of minimising a PAC-Bayes objective, as it is a common strategy for many PAC-Bayes learning algorithms. As such, it is reasonable to measure the performance of the optimisation algorithm in terms of the resulting PAC-Bayes objective, rather than in the empirical risk which constitutes only part of this objective. This being said, the empirical risk obtained during the numerical experiments is 0.102 $\pm$ 0.003 (average on the 20 replicates performed). This should be compared to the reported value of 0.101 in Picard-Weibel et al. 2024 (single value reported). We remark that the resulting PAC-Bayes objective are similar (0.121 $\pm$ 0.004 against 0.122 reported in Picard-Weibel et al. 2024), which indicates that SuPAC-CE constructs a posterior which is as good as the one previously reported, while being about twenty time faster. 
-	In response to reviewers ku1E and 7ntj, we conducted further optimisation procedures to assess 1. how SuPAC-CE fared against Nesterov accelerated gradient descent (GD), 2. how SuPAC-CE performed for other choices of hyperparameters. Summary graphs for these optimisation procedures are included in the pdf file. SuPAC-CE outperformed both standard GD and Nesterov accelerated GD for a broad variety of hyperparameters in the Anaerobic Digestion task studied here. A more detailed analysis is joined to specific rebuttals.

Reference:

- Antoine Picard-Weibel, Gabriel Capson-Tojo, Benjamin Guedj, Roman Moscoviz, (2024) Bayesian uncertainty quantification for Anaerobic Digestion models, Bioresource Technology, Volume 394, ISSN 0960-8524

Meta-review: The work is interesting and benefits the community. Optimizing PAC-Bayesian bounds is a successful framework for empirical risk minimization and this work advances this area of research. Specifically, the work explores the idea of approximating the bound to achieve simpler optimization settings. The application of this framework to exponential family and Catoni's bound admits a novel and interesting relation to Fisher's information and emphasize the originality and the power of this approach.  

Involuntarily, the work emphasizes the cons in the current review process, both in term of diverse community and the open review interaction. To be transparent with the authors I kindly want to point out: (i) the non-confident review was discarded in the process. (ii) the authors' discussion was insightful and starts to resemble to a fast-journal review without the benefit of "major revision". Being immersed in the community, and to help the process be honest, I urge the authors to take the reviewers comments into account for the final submission.
Decision: Accept (poster)