Sample-efficient Bayesian Optimisation Using Known Invariances
Authors: Theodore Brown
Alexandru Cioba
Ilija Bogunovic
Venue: NeurIPS 2024 poster (2024)
Keywords: Bayesian optimisation
bandit optimisation
Gaussian processes
kernel methods
groups
invariance
transformations
sample efficiency
Primary area: bandits
TL;DR: We derive sample complexity bounds for BayesOpt algorithms with kernels that incorporate known invariance of the target function, and demonstrate their application to the design of a fusion reactor.

Abstract: Bayesian optimisation (BO) is a powerful framework for global optimisation of costly functions, using predictions from Gaussian process models (GPs). In this work, we apply BO to functions that exhibit invariance to a known group of transformations.  We show that vanilla and constrained BO algorithms are inefficient when optimising such invariant objectives, and provide a method for incorporating group invariances into the kernel of the GP to produce invariance-aware algorithms that achieve significant improvements in sample efficiency. We derive a bound on the maximum information gain of these invariant kernels, and provide novel upper and lower bounds on the number of observations required for invariance-aware BO algorithms to achieve $\epsilon$-optimality. We demonstrate our method's improved performance on a range of synthetic invariant and quasi-invariant functions. We also apply our method in the case where only some of the invariance is incorporated into the kernel, and find that these kernels achieve similar gains in sample efficiency at significantly reduced computational cost. Finally, we use invariant BO to design a current drive system for a nuclear fusion reactor, finding a high-performance solution where non-invariant methods failed.

Sample-efficient Bayesian Optimisation Using Known Invariances
Theodore Brown" 1,2 1,2
Alexandru Cioba +3
Iija Bogunovic'
Equal contribution
'University College London
United Kingdom Atomic Energy Authority
3MediaTek Research
(theodore brown. 23, i bogunovic/@ucl.. ac.uk
alexandru. cioba@mtkreeeeacch com
Abstract
Bayesian optimisation (BO) is a powerful framework for global optimisation of costly functions, using predictions from Gaussian process models (GPs). In this work, we apply BO to functions that exhibit invariance to known group transformations. We show that vanilla and constrained BO algorithms inefficient when optimising such invariant objectives, and provide a method for incorporating group invariances into the kernel of the GP produce invariance-awan algorithms that achieve significant improvements in sample efficiency. We derive a bound on the maximum information gain of these invariant kernels, and provide novel upper and lower bounds on the number of observations required for invariance-awart BO algorithms achieve e-optimality, We demonstrate our method's improved performance on range of synthetic invariant and quasi-invariant functions. We also apply our method in the case where only some of the invariance is incorporated into the kernel, and find that these kernels achieve similar gains in sample efficiency at significantly reduced computational cost. Finally, we use invariant BO design a current drive system for a nuclear fusion reactor, finding nigh-performance solution where non-invariant methods failed.
Introduction
Bayesian optimisation (BO) has been applied to many global optimisation tasks science and engineering, such improving the performance of web servers [30], reducing the losses in particle accelerators [26], or maximising the potency of a drug [1]. The most challenging real-world tasks tend to have large or continuous input domains, well as target functions that costly evaluate.
One particular example of interest is the design and operation of nuclear fusion reactors, which promise to deliver huge amounts of energy with zero greenhouse gas emissions. However, the devel- opment of high-pus -eghfrerformaec fusion power plant scenarios is a difficult optimisation task, involving expensive simulations and physical experiments [39, 11]. For tasks like this, is desirable develop sample efficient algorithms that only require a small number evaluations to find the optimal solution.
Crucially, the physical world is characterized by underlying structures that can be leveraged to significantly improve sample efficiency. The concept of invariance, which describes properties that remain constant under various transformations, is one of the most fundamental structures in nature. A prime example of invariance found in image classification tasks: a classifier should consistently identify cat cat, regardless of its orientation, position, size. The central question answer the extent to which the sample efficiency of BO can be improved by exploiting these invariances.
We study general approach for incorporating invariances into any BO algorithm. We represent invariant objective functions as elements of a reproducing kernel Hilbert space (RKHS), and produce invariance aware versions of existing Gaussian process (GP) bandit optimisation algorithms by using the kernel of this RKHS. We apply these algorithms synthetic and nuclear fusion optimisation
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

0.50
10
1.0
0.5
0.0
6.5
0.25
-5
-1.0
(a) Permutation group, S3
(b) Cyclic group, C33
(c) Dihedral group, Ds
Figure 1: Examples of group-in coouu-invariint functions, sampled from Gaussian process with the corre- sponding invariant kernel. Note that observing a point (red) provides information about transformed locations (o(x) G} (white).
tasks, and show that incorporating the underlying invariance into the kernel significantly improves the sample efficiency. We also investigate the behaviour of the algorithms when the full invariant kernel known, and provide an empirical study of the performance of invariance-awan BO on target functions that are "quasi-im iuvaii-nvvrrian'' (modelled as sum of invariant and non-invariant components). Our main contribution the derivation of novel upper and lower bounds on the regret achieved by invariance-aware BO algorithms.
1.1 Related work
Invariance in deep learning. The role of invariance in deep learning has been extensively explored in the literature. Invariance, particularly to geometric transformations like rotation, scaling, and translation, is crucial for the robust performance of deep learning models. Many deep learning methods incorporate invariance via data augmentation, in which additional training examples are generated by transforming the input data [28, 29]. However, the of kernelised learning methods often scales poorly with the number of training points Gaussian process inference, for example, incurs (n²)) time and Onn") memory cost [47] - which means that data augmentation prohibitively expensive. In this work, we adopt an alternative approach by directly embedding invariance properties into the model's structure, which effectively reduces computational complexity [44, 15].
Structure-informed BO. There an extensive body of empirical BO literature that exploits known patterns present in the behaviour of system. In [24], BO is applied after variety of physics informed physics-informed
feature transformations to the state; in [48] the authors employ BO to handle optimization over crystal configurations with symmetries found using [40]. However, in these works, only empirical results given and asymptotic rates on sample complexity are not estimated.
Invariant kernel methods. The theory of group invariant kernels was introduced in [18, 27]. Using these ideas, [46] developed efficient variational methods for learning hyperparameters in invariant Gaussian processes. Invariant kernel ridge regression (KRR) for finite groups has been studied for translation- and
kernels [33, 4]. [38] quantify the gain in sample complexity for kernels invariant to the actions of Lie groups arbitrary manifolds and tie the sample complexity bounds to the dimensions the group. Motivated by the invariance properties of convolutional neural networks. [27, 33, 4] focus kernelised regression with the Neural Tangent Kernel; instead consider the kernelised bandit optimisation setting with the more general Matérn family of kernels. These methods be readily extended less strict notions of so-called quasi- invariicev [18, 46, 4).
Matérn kernels on manifolds. The previous studies of invariant kernel algorithms rely on the spectral properties of kernels the hypersphere [33, 4]; the relevant spectral theory for Matérn kernels on Riemannian manifolds (including the hypersphere) was developed in [9]. These geometry- kemels were applied to optimisation tasks in [20]; however, the structure they include is restricted to the geometry the domain only, rather than invariance to a set of transformations.
Regret bounds for Bayesian optimisation. The techniques for upper-bounding the regret of Bayesian optimisation algorithms using the kernel-dependent quantity known as maximum information gain were developed in [37]. Subsequent studies [43, 8, 14, 36, 19, 41] have focused on improving regret bounds in both cumulative and simple regret settings. [22] provided an upper
bound for regret in BO using the convolutional NTK, which exhibits invariance only to the cyclic

---

group. [23] explored graph neural network bandits, offering maximum information gain rates by embedding permutation invariance using additive kernels. In [25], a permutation-invarre -nvariiat kernel is constructed in the same way ours, and a regret analysis provided. Our work expands upon these approaches by considering more general (non-additive) kernels and broader transformation groups, demonstrating that the regret bounds from [22] can be shown to be a specialisation of ours. Lower bounds for kernelised bandits, including their robust variants ([7, 6]), have been examined in [35] and [12]. In this paper, we derive novel lower bounds on regret for the setting with invariant kernels.
1.2 Contributions
Our main contributions are:
We develop new upper bounds on sample complexity in Bayesian optimisation with invariant kernels, which explicitly quantify the gain in sample complexity due to the number of symmetries.
We extend several results from the literature, as our statement applies to a wide class of groups.
This is, our knowledge, the first time such bounds are given in this degree of generality. We show how results from the literature (e.g. [12]) can be extended to obtain lower bounds on the sample complexity of invariant BO, using a novel construction and quantification of members of the RKHS of invariant functions. We extend the methods in the literature to the hyperspherical domain, giving a blueprint for similar constructions on other Riemannian manifolds.
We conduct experiments that support our theoretical findings. We demonstrate that incorporating invariance some subgroup of transformations is sufficient to achieve good performance, a result of key importance when the full invariance is not known or is too expensive to compute. We also demonstrate the robustness of the invariant kernel method, in the case where the target function deviates from true invariance.
We apply these methods to solve real-world design problem from nuclear fusion engineering that is known to exhibit invariance; our invariance-awer method finds better solutions in fewer samples compared to standard approaches.
2 Problem statement
We begin by providing an overview of invariant function spaces. Consider finite subgroup of isometries, G, on a compact manifold, X, embedded in Rd. A function f + R is invariant to the action of G if, for all a E G.
foo=f i.c. f(x) ((rxx) Vx E X.
(I)
We provide some examples of invariant functions for different groups G in Figure 1.
In this paper, we study the optimisation of invariant functions that belong to a reproducing kernel Hilbert space (RKHS). The invariance of the RKHS elements translates to invariance properties of the kernel. For ls X' X - R. we say that is simultaneously invariant the action of G if, for all E G and x. y E X.
k(((x), a (y)) k(xx y), and is totally invariant to the action of G if, for all a, r E G and x, E X,
(2)
(((x))((()) = 6(x.v).
(3)
as introduced in [18]. Note that both inner product kernels k(x,, y) = k. ((x,, v)) and stationary kernels k(x,)) = <(Il vll satisfy simultaneous invariance, as Gi consists of isometries (which preserve distances and inner products).
Next, we outline the relationship between the invariance of the kernel and the invariance of the functions in the associated RKHS. In particular, the following proposition (Proposition 1) identifies the space of invariant functions Moreover, it turns out that this subspace is an RKHS in its own right, with a corresponding kernel that is totally invariant. For proof of these properties, see Appendix A. Propasition 1 (RKHS of invariant functions), Let X and G be as defined above. Consider a positive definite and simultaneously invariant kernel : X X + R. The kernel defines reproducing kernel Hilbert space H., whose elements are functions f X + R. and a corresponding Hilbert space norm
subspace of the RKHS of a simultaneously invariant kernel.
H Define the symmetrization operator SG Hi + Ht. such that
Sc(f)
G Σ foo.
1
(4)
3

---

Standard kernel
Invariant kernel
0.50
Figure 2: UCB run with standard & and invariant kernel lig applied to an invariant objective: queried points in white. UCB with the invariant kernel requires signifi- cantly fewer samples to find the optimum.
8
-0 3
-025
Then, SG is a self-adjoint projection operator, whose image [m[Sc] is the subspace of Hy that contains G- G-invariant functions. Moreoever, Im Im[Sc] is an RKHS in its own right, Hhg For I, X, the reproducing kernel of Hka
kc 9)
Σ k(a(z).)).
(5)
G
We consider a kernelised optimisation setup with bandit feedback, which the goal is to find the maximum of an unknown function f X -> R that is invariant to known group of transformations G. We model f as belonging to the invariant RKHS Hike from Proposition Without further smoothness assumptions, this task is intractable; similarly to the common non-invariant setting, we make the regularity assumption that f has bounded RKHS norm, |l < B. The learner is given and G. In Section 3.2, we explore setting k in kg to common kernels, such as those from the Matérn family.
At each round I, the learner selects a point #t E X' and receives noisy function observation
f(t) +
(6)
where is drawn independently from or -u.- Sub-Gaussian noise distribution. The agent reports point of and incurs a corresponding simple regret, defined
Tt arg max fxx f(x2).
xEX
After T rounds, the cumulative regret given by
RT
Σ
arg max f(x) - f(x;))
(8)
ZEX
In the next section, quantify the impact of invariance the number of function samples required to achieve a given regret, known as the sample complexity.
Sample complexity bounds for invariance-aware Bayesian optimisation
The bandit problem outlined in the previous section can be tackled using Bayesian optimisation (BO) [17]. Intuitively, expect BO algorithms that utilize the G-invariance of the target function to achieve improvements in sample complexity, as each observed simultancously provides information about additional transformed locations or (z) for each a E (see Figure
In this section, we quantify the performance improvements by deriving bounds on the sample complex- ity of BO with totally invariant kernels (Equation (3)). We begin with outline of the BO framework.
3.1 Bayesian optimisation of invariant functions
In Bayesian optimisation, predictions from Gaussian process (GP) used in conjunction with an acquisition function to select points to query [17]. After collecting a sequence of input-observatinn pairs, D {(#1, vi).... (I,, }. the learner models the invariant target function f Hsc using GP with a totally invariant kernel, GP(O, kg). The posterior predictive distribution the function value at specified input location will be Gaussian with mean and variance given by
[x(x) = k K x -1)-'y
(9)
of (z) kz( - ko K + XI) -
(10)

---

Algorithm Max. variance reduction [42]
Algorithm 2 Upper confidence bound [37]
Input: kg.
Input: kg, A'
1: initialize D ()
1: initialize D [
2: for t= 1....., ,....,To T do
2: for tort=10 1,.... 7 do
3: Select It arg max xE (x)
3: Select ii; arg max Z Mt- (x:) (o)
4: Observe y/ = f(x,)= + T
4: Observe - f f(x;)) ) + 7)t
5: Append (Ir, M/1) D
5: Append (æi, 31) to D
6: Update Pe; from Eqs. 9, 10
6: Update Me, from Eqs. 9, 10
7: end for
7: end for
8: return 2ap = arg & (r)
8: return sUCB = FT
where ka = (2),,1)). (a( xx)) E [R K is the kernel matrix with elements [K akly = ka x,, 224) Vi,j E 1,...,f, f, [yl..... yel". and À is regularising term. Note that as this GP has a totally G-invariant kernel, kG, can be interpreted as a distribution over G-invariant functions.
We consider two common acquisition functions. The tightest simple regret bounds in the literature for the Maximum Variance Reduction algorithm (MVR), in which the learner iteratively queries the points with highest uncertainty before reporting the point with highest posterior mean [42]. Another algorithm that has been widely studied is Upper Confidence Bound (UCB), which balances exploration and exploitation by behaving optimistically in the face of uncertainty [37]. Pseudocode for MVR and UCB is provided in Algorithm I and Algorithm 2, respectively. Our analysis framed in terms of MVR and simple regret, although in Section 4.1 we also investigate empirically the cumulative regret performance of UCB.
A popular family of kernels used in BO is the Matérn kernel. On R the Matérn kernel with parameters 1, given by
k(xz x') 2 21 ['v]
22 || -01-x K, (121 -'1)
<22 (
(11)
where K2 is the modified Bessel function of the second kind. The parameter v controls the differen- tiability of the corresponding GP, which enables Matérn kernels to define a diverse range of function spaces. As the Matérn kernel is simultaneously invariant (Equation (2)), we can construct a totally invariant ko and corresponding RKHS following Proposition 1. The bounds that derive both hold for the Matérn family; our upper bound also extends to any kernel that exhibits polynomial eigendecay.
In Figure 2, we provide visual example of the impact of using ke in Bayesian optimisation. We run UCB on a group-invariant objective with the standard and invariant kernels. With the non-invariant kernel k, the algorithm spends many samples querying suboptimal points with similar objective values. In contrast, using the invariant kernel Kg allows the algorithm to identify suboptimal regions across the parameter space with only handful of samples, resulting in significantly faster convergence.
3.2 Upper bounds on sample complexity
In this section, X' = gd-1 C IRdd and let G be a finite subgroup of the orthogonal group, (dd), equipped with its natural action on X. Let be simultaneously invariant kernel gd-1, and assume that the eigenvalues of the associated integral operator decay at a polynomial rate μı O(k-²)) for some constant 3/ > 1. Many common kernels exhibit this property, such as the standard Matérn kernel on Rdd. For GPs defined intrinsically on Riemannian manifolds [45], the corresponding Matérn kernel also exhibits polynomial eigendecay [9]. We impose the following assumption on the spectra of elements in the group G, which is in line with the assumptions and spectral decay rates in [4]. Assumption 1. All elements a E G satisfy the following spectral property:
mi <d- if X +1,
(12)
for all X E Spec(o), where my is the multiplicity of X.
This assumption excludes certain groups in low dimensions, but we expect can be relaxed through tighter analysis. In fact, our experiments for d = 2,3 show is essential as a theoretical artefact only.
5

---

Nevertheless, Equation (12) holds for all finite orthogonal groups in dimension 2 10 (see Lemma as well as for many groups of lower dimension; for example, groups for which my 1, so that only distinct eigenvalues are present in the spectra. Under this assumption, we have the following upper bound on sample complexity.
Theorem (Upper bound on sample complexity of invariance-aware BO). Let k. be a polynomial eigendecay kernel on Sd-1 which is simultaneously invariant w.r.t. the orthogonal group O(d), and let G S (d)) be subgroup of O(d) satisfying Assumption I. Let lig be the totally invariant kernel, as defined in Proposition 1. Consider noisy bandit optimisation of f E Hko where Iifll < B and f gd-1 - R. Then, the maximum information gain (MIG) for the totally invariant kernel after G. rounds, TT' is bounded by
G TT
Ö [G|
%
(13)
where O()) hides logarithmic factors. Moreover, for the MVR algorithm with invariant kernel kg to achieve expected simple regret B((r] < e, must hold that
= ((tt)
P5
297 17
-4+1
(14)
For the Matérn kernel, this corresponds to
2u
T =
20 4-1
17
(15)
Proof. See Appendix A.2.
Our upper bound demonstrates that incorporating the group invariance into the kernel is guaranteed to result in sample efficiency improvements that increase with the size of the group, due to the [ factor. Our result for the MIG of invariant kernels is of independent interest, as it is applicable to wide range of scenarios. Notably, the linear [ improvement the information gain from Equation (13)
resembles the linear [ि] improvement in generalisation error in the invariant kernel ridge regression setting [3]. Intuitively, this reflects how the MIG criterion is determined solely by the ability of the kernel to approximate the objective function, and is agnostic to the algorithm used in optimisation.
In our proof, we begin with kernels on gd-1 that are simultancously invariant w.r.t. the full orthogonal group (d). and use Proposition to construct kernels that totally invariant kernels w.r.t finite subgroups S (dd. Simultaneously Odd)-invariant kernels on Sd-1 are fact dot-product kernels, which allows us to use standard versions of Mercer's theorem in terms of known spectral decompositions. If an alternative decomposition is known for a particular k; then it is sufficient that instead satisfies the weaker condition of simultaneous invariance w.r.t. G only.
3.3 Lower bounds on sample complexity
In the next theorem, we present lower bound on sample complexity which nearly matches the upper bound in its dependence on |G].
Theorem 2 (Lower bound on sample complexity of invariance-an -waree aware BO with Matérn kernels). Let X be one of [0, 1]6 Sd.
f Let k be the standard Matérn kernel on Rdd with smoothness v, and G be finite group of isometries acting on X. Let kG be the totally invariant kernel constructed from k and G according to Proposition 1. Consider noisy bandit optimisation of Hx f
RR where the observations are corrupted by o-sub- Saahh-Gussiann noise. Then, for sufficiently small there exists function family Fx(c, B) such that the number of samples required for an algorithm to achieve simple regret less than e for all functions in Fx with probability at least 8 is bounded by:
T= ((1)
11d-1
2rid-1
o² BB* d-1 log 1 !)
(16)
Proof. See Appendix A.3.

---

Our lower bound guarantees that algorithms that are run for number of sample less than T fail to be e-optimal with high probability. At fixed T, there a trade-off between this probability and the order of the group. However, when combined with the upper bound our results imply that as the order of the group increases, the probability that an algorithm is e-optimal after a fixed number of iterations also increases.
We recover the previously known lower and upper bounds on sample complexity for non-invariant
optimisation from [12] and [42] respectively by setting G| = 1. We also note that there is a gap between our bounds, as the exponent of [ in Equation (15) is 1 + d-1 but is 1+ d-1 in Equation (16). A likely reason for this gap is in the lower bound, which uses a packing argument for the support sets of functions in the RKHS. While in the absence of the group action, the lower bound and upper bound agree, it is not clear priori how to achieve the tightest packing of invariant functions.
2v
To achieve the largest improvement in sample complexity, one would like to choose the largest possible G when constructing kg. However, as we will see in our experimental section, there is computational tradeoff between the sample complexity and the computation of Sg, as in the case of very large groups the sums over the group elements becomes computational bottleneck.
4 Experiments
We demonstrate the performance gains from incorporating known invariances in a number of synthetic and real-world optimisation tasks. Previous work has demonstrated the sample efficiency improve- ments from upplying invariance-awar algorithms to regression tasks [3. 33, 38]: our experiments complement the literature by observing the corresponding improvements in optimisation tasks. Code for our experiments and implementations of invariant kernels can be found on GitHubl.
4.1 Synthetic experiments
For each of our synthetic experiments, our goal is to find the maximum of function drawn from an RKHS with group-invariant isotropic Matérn-5/2 kernel. The groups we consider act by permutation of the coordinate axes, and therefore include reflections and discrete rotations. For PermInv-2D (Figure la) and PermInv-6D, the kernel of the GP is invariant to the full permutation group which acts on R and IR respectively by permuting the coordinates. For CyclInv-31 it is invariant to the cyclic group acting R2 by permuting the axes cyclically (Figure lb). We provide the learner with the true kernel and observation noise variance to eliminate the effect of online hyperparameter learning. For more detail on experiments, see Appendix B.
In Figure 3, we show that the algorithm's 's performance on invariant functions is improved by using an invariant kernel. In all cases, the performance of the invariance-awan algorithm significantly outperforms the baselines, converging to the optimum with many fewer samples. Notably, in the PermInv-60 task, the baseline algorithms fail to find the true optimum, whereas the permutation- invariant versions do so without difficulty. We also note that the performance improvement increases with increasing dimension and group size, as predicted by our regret bounds.
For the PermInv tasks, we provide an additional baseline: constrained Bayesian optimisation (CBO, [16]). In this case, we constrain the search space of the acquisition function optimiser to the fundamental region of the group's 's action. For arbitrary groups, finding an analytical formula for this region can be difficult, particularly when the dimension of the domain is high and the group is complicated; however, it straightforward in the case of the full permutation group. We find that constrained BO performs worse than our method, and in high dimensions is identical to standard (non-invariant) BO. Intuitively, this matches our expectations, as in CBO the kernel not aware of all of the structure that the RKHS elements possess that is, while the domain of exploration restricted, the function class is not. Observations CBO contribute no information across the boundaries of the region, unlike in the invariant kernel case, and so the performance improvement of CBO is upper bounded by [
For the PermInv-60 6D task, we also consider the case where the full invariance is not fully known to the learner; that is, the kernel is not totally invariant w.r.t. the full group, but only subgroup. Our results show that incorporating any amount of the true invariance results in performance improvements. In this case, the true function is invariant to the full permutation group in 6D (720 elements). We evaluate
gi thub. http:/thhoobbooomnneeeeeee
and githhbcco//teeeeee www/theo-brroteeoooo htt///thheobbrrm//aaasspp.pppp with invariances
7

---

Perminv-20
Cycllnv-3D
Perminv-6D
50
800
Standard
Standard
Standard
Cumulative regret
40
Constrained
regret
Invariant
Cumulative regret
Constrained
600
(a) UCB
Invariant
100
3-black inv.
2-block inv.
400
Fully inv.
200
10
25
50
100
125
100
150
200
250
200
400
600
Number of evaluations
Number of evaluations
Number of evaluations
Perminv-2D
Cyclinv-3D
Permlnv60D
Standard
Standard Invariant
Standard -2-block Inv.
Simple regret
1.00
Constrained
1.00
Simple regret
Constrained
- Fully Inv.
(b) MVR
Invariant
3-block inv.
1.0
0.50
0.50
0.5
0.25
0.25
0.00
0.00
25
100
100
150
200
250
200 400
600
evaluations
Number evaluations
Number evaluations
Figure 3: Regret performance of invariant UCB and MVR algorithms across 3 different tasks; lower is better. Non-invariant kernels (blue) are outperformed by the full group invariant kernel (red) as well as partially specified (subgroup-invarin
kernels (green and yellow). For the permutation invariant function, the search space of standard BO can be constrained by the fundamental domain of the group (purple), but this performs worse than the invariant kernel. Mean + s.d., 32 seeds.
the performance of the full invariant kernel, the non-invariant kernel, and two subgroup invariant kernels. The subgroups we consider consist of "block' permutations, which involve reordering the coordinate indices in chunks of length 2 and 3 (leading to groups with 6 and 2 elements respectively). For both algorithms, we see that all kernels that incorporate invariance outperform the non-invariant kernel, even when the difference in the group size considered is large.
4.2 Extension: quasi-invariance using additive kernels
In real-world scenarios, is possible that the underlying function only exhibits approximate symmetry. For example, in the fusion application from Section 4.3, the launchers may have slightly different properties and are no longer interchangeable. A 2D example this 'quasi-invarianc""
given the first column of Figure 4. Although the large-scale features (such as the layout of the peaks) remain ap- proximately symmetric, invariance is not maintained in the detail (the values and shapes of the peaks).
We model quasi-invarie insarincveeeeeee by introducing an additive non-invariant disturbance to the target function. The function can then be considered as belonging to the RKHS H((-e)Mo++ek' where ke is G- invariant kernel, k' is non-invariant kernel, and sets the degree of deviation from invariance. In our experiments, we observe that performing BO with the fully invariant kernel still results in significant performance improvements over the non-invariant kernel when is small, achieving performance com- parable to BO with the kernel of the function's 's RKHS. As this is a kind of model misspecification, we refer the reader [5] for theoretical discussion on the performance of BO with misspecified kernels.
4.3 Real-world application: nuclear fusion scenario design
In this section, we use invariance-aware BO to efficiently solve a design task from fusion engineering.
The leading concept for controlled fusion power plant is the tokamak, device that confines high- temperature plasma using powerful magnetic fields. Finding steady-state configurations for tokamak plasma that are simultaneously robustly stable and high-performance is challenging task. Moreover, evaluating the plasma operating point requires high-fidelin multi-physics simulations, which take several hours to evaluate configuration due to the complexity and characteristic timescales of the physics involved [34]. Iterating on design requires many such simulations, which has led to an in- creased focus on highly sample-efficient algorithms for tokamak design optimisation [13, 32, 10, 31].
We consider a scalarised version of the multi-objective optimisation task presented in [10], which the goal is to shape the output of plasma current actuator maximise various performance and ro-

---

Objective
MVR
1.2
2.0
Standard
invariant Quasi invariant (truth)
Cumullativ regret
60
Permutation
(8) II 0.01
0.6
0.3
13
Quas -invariant (truth)
2
-0.3
Simple
1.0
0.2
-0.9
0.6
0.5
20
1.2
0.0
0.00
0.25
0.50
0.75
1.00
75
100
125
25
50
75
100
125
Number of evaluations
Number of evaluations
Objective
MVR
0.05
0.8
1.2
0.6
1.25
1:00
Permutation invariant
Standard
Quasi-nnarraat
Curmulaatvve regret
60
Quas -nnaarint (truth)
Permutation invariant
Standard
0.6
II
0.0
0.75
0.50
(b)
-066
20
0.2
-1.2
0.00
0.00
0.25
0.50
0.75
1.00
25
50
75
100
125
ber evallattions
Number of evaluations
Figure 4: Performance of MVR and UCB quasi-invariant functions. Regret shown for the noninvariant kernel k' (standard, blue), the invariant kernel kg (invariant, green), and the quasi-invariant kernel kg + =k' (additive, red). In all cases, the invariant kernel performs almost as well as the true quasi-invariin kernel.
bustness criteria based on the so-called safety factor profile. Using a weighted sum, we reduce the vec- objective to [0, 1]. with component weights selected represent the proposed SPR45 design of the STEP tokamak [39, 31J. J. As the objective components are in direct competition, the highest achievable scores are around 0.7 0.8, while the lowest-scoring converged solutions achieve around 0.4 0.5.
In previous work, the actuator output was represented by arbitrary 1D functions (piecewise linear [31] and Bézier curves [10]). However, in practice the actuator will have finite number of 'launchers' that drive current a localised region, and so will be unable to accurately recreate arbitrary profiles. In contrast to previous work, directly optimise a parameterisation that reflects the actuator's 's real capabilities: sum 12 Gaussians, where each models a launcher targeted at a different point the plasma cross-section (Figure 5a). In this setting, the objective function is ʃ R212 - IR, where the input is the normalised radial coordinate of the 12 launchers. As all of the launchers have identical behaviour, the objective is invariant permutations. However, the full invariant kernel is too costly to compute (G' = 12! = 479 x 10%), so we instead use partially specified kernel (3-block invariant, |G| = 4! 24).
An additional challenge of this task is that large regions of parameter space are infeasible, corresponding to simulations that will not converge steady-state solution and will therefore be
Safety factor optimisation
Total
Noraaisedd power
Launcher
Objective value
deposition
Launcher
Launcher
0.65
1.0
Launcher
Launcher
0.5
0.60
Standard
Invariant
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
2
8
10
12
14
16
Normalised position
Optimisation step
(a) Example current drive actuator profile, shown for launchers
(b) Performance comparison (mean of seeds)
Figure 5: Nuclear fusion application: optimising safety factor by adjusting current drive actuator. In (a), observe that the order of launchers can be permuted without changing the total profile. Incorporating this invariance into the kernel of the UCB algorithm achieves improved performance (b).

---

GPU memory (GiB)
Time to fit (ms)
30
40
20
10
Standard
3-block Inv.
3-black aug.
2-block inv.
2-block aug.
Fully inv.
Standard
3-block Inv.
3-block aug.
2-block inv.
2-block aug.
Fully Inv.
(a) Memory cost
(b) Time cost
Figure 6: Effect of group size on cost of data augmentation and invariant kemee methods. Benchmark task to fit a 6D GP with the given kernel to 100 random datapoints from PermInv-6D. Shown are results from 100 seeds, 64 repeats per seed, performed on one NVIDIA V100-32GB GPU using BoTorch. Invariant kernels are (a) more memory efficient than data augmentation, and (b) can be computed faster. Incorporating full invariance via data augmentation exceeds the GPU memory.
impossible to observe. Selecting an appropriate method of dealing with this situation can impact the optimiser's performance, and is an open area of research. In this work, we choose to assign fixed low score to failed observations for simplicity. As MVR is purely exploratory it has no mechanism that discourages querying points from infeasible regions, leading to many failed observations. UCB a more natural choice in this setting, as the parameter introduces balance between querying unknown regions (that could be infeasible) and exploiting known high-scoring regions.
In Figure 5b, we see that the invariant version of UCB achieves significantly improved performance compared to the non-invariant version. In fact, the non non-invariant algorithm totally fails to find the small region of -egrfoerfrmmece solutions, and instead queries many suboptimal profiles that are similar under the action of permutations. The high sample efficiency of the invariant kernel method will enable tokamak designers iterate on designs faster, with fewer calls to expensive simulations.
5 Limitations
Although the number of terms involved in computing the totally invariant kernel only scales linearly with the group size (Equation (5)), this cost can still become a bottleneck for very large groups; for example, the size of the permutation group scales with the factorial of the dimension, leading to |G| = 24 for d = 4, but |G| = 179 x 10 for d = 12. In Figure we compare the compute and memory costs of performing a marginal log likelihood fit of the GP hyperparameters for each of the kernels in the previous section, given 100 observations from the PermInv-6D function. The standard, 3-block invariant, and blok invariant kernel are faster than the fully invariant kernel by a factor of 2. As we observed that the 2- and 3-block invariant kernels still achieve significantly improved sample efficiency over the standard kernel (Figure 3), we propose that subgroup approximations of the full invariance group can be used low-cost alternative when the group size is large, reducing computational cost while maintaining improved performance. Finally, we note that our invariant kernel method scales significantly more favourably than data augmentation, both in terms of memory and compute.
Conclusion
We have developed new upper bounds the sample complexity in Bayesian optimization with invariant kernels, highlighting the advantages gained from symmetries that hold for a broad range of practical groups. We also derived novel lower bounds by constructing and quantifying members of the RKHS of invariant functions, extending this approach to the hyperspherical domain and providing a framework for other Riemannian manifolds. Empirically, our experiments show that even partial invariance can effectively improve performance, which is crucial when full invariance is unavailable or computationally intensive. Additionally, we applied these methods real-world problem in nuclear fusion engineering, achieving superior outcomes with fewer samples compared to standard methods.
Broader Impact. The incorporation of symmetries in Bayesian optimization can have a profound impact on science and engineering. By exploiting symmetrical properties in various applications, such as nuclear engineering, material and drug design, and robotic control, it can reduce the number of sam- ples needed to achieve (near) optimal solutions, thus accelerating research and development processes.
10

---

Acknowledgments
TB was supported by the Engineering and Physical Sciences Research Council (EPSRC) grants EP/T517793/1 and EP/W524335/L. IB was supported by the EPSRC New Investigator Award EP/X03917X/1; EPSRC grant 15/S021566/1; and Google Research Scholar award.
References
[1] Mohsen Ahmadi et al. "Predicting potent compounds via model-based global optimization". In: Journal of Chemical Information and Modeling 53.3 (2013), pp. 553-559,
[2] Maximilian Balandat et al. "BoTorch; a framework for efficient Monte-Carbl Bayesian opti- mization". In: Advances in Neural Information Processing Systems. Vol. 33. 2020.
[3] Alberto Bietti and Francis Bach. "Deep equals shallow for ReLU networks in kernel regimes".
In: International Conference on Learning Reprexentations. 2021.
[4] Alberto Bietti, Luca Venturi, and Joan Bruna. "On the sample complexity of learning under geometric stability". In: Advances Neural Information Processing Systems. Vol. 34. 2021, pp. 18673-18684.
[5] Iliaa Bogunovic and Andreas Krause. "Misspecified Gaussian process bandit optimization". In: Advances in Neural Information Processing Systems. Vol. 34. 2021, pp. 3004-3015. [6] Ilia Bogunovic et al. "A robust phased elimination algorithm for corruption-tolerant Gaussian process bandits". In: Advances Neural Information Processing Systems. Vol. 35. 2022,
Pp. 23951-23966
[7] Iijaa Bogunovic et al. "Adversarially robust optimization with Gaussian processes". In: Ad- vances in Neural Information Processing Systems. Vol. 31. 2018, pp. 5765-5775.
[8] Ilija Bogunovic et al. "Truncated variance reduction: unified approach to Bayesian optimiza- tion and level-set estimation". In: Advances in Neural Information Processing Systems. Vol. 29.
2016, pp. 1515-1523.
[9] Viacheslav Borovitskiy, Alexander Terenin, Peter Mostowsky, et al. "Matérn Gaussian pro- cesses on Riemannian manifolds". In: Advances in Neural Information Processing Syslems.
Vol. 33. 2020, pp. 12426-12437.
[10] Theodore Brown et al. "Multi-objective Bayesian optimization for design of Pareto-optimal current drive profiles in STEP". In: IEEE Transactions on Plasma Science 99 (2024), pp. 1-6.
[11] RJ Buttery et al. "DIII-D research to prepare for steady state advanced tokamak power plants". In: Journal of Fusion Energy 38 (2019), pp- 72-111.
[12] Xu Cai and Jonathan Scarlett. "On lower bounds for standard and robust Gaussian process bandit optimization". In: Proceedings of the 38th International Conference on Machine Learning. Vol. 139. 2021, pp. 1216-1226.
[13] Ian Char et al. "Offline contextual Bayesian optimization". In: Advances in Neural Information Processing Systems. Vol. 32. 2019, pp. 4627-4638.
[14] Sayak Ray Chowdhury and Aditya Gopalan. "On kernelized multi-armed bandits". In: Pro- ceedings of the 34th International Conference Machine Learning- 2017, pp. 844-853. [15] Taco Cohen and Max Welling. "Group equivariant convolutional networks" ".."""""". In: Proceedings of the 33rd International Conference on Machine Learning. Vol. 48. 2016, pp. 2990-299999 2999.
[16] Jacob R Gardner et al. "Bayesian optimization with inequality constraints" In: Proceedings of the 31st International Conference on Machine Learning. Vol. 32. 2014. pp. 937-945. Roman Garnett. Bayesian optimization. Cambridge University Press, 2023.
[17]
[18] Bernard Haasdonk and Hans Burkhardt. "Invariant kernel functions for pattern analysis and machine learning".. In: Machine Learning 68 (2007), pp. 35-61.
[19] David Janz, David Burt, and Javier González. "Bandit optimisation functions in the Matém kernel RKHS". In: Internationaal Conference on Artificial Intelligence and Statistics. Vol. 108. 2020, pp. 2486-2495.
[20] Noémie Jaquier et al. "Geometry-awann Bayesian optimization in robotics using Riemannian Matérn kemels". In: Conference on Robot Learning. 2022, pp. 794 805.
[21] Michael Kapovich. note on properly discontinuous actions. 2023. eprint: arxiv 2301.
05325.

---

[22] Parnian Kassraie and Andreas Krause. "Neural contextual bandits without regret". In: Proceed- ings of the 25th International Conference on Artificial Intelligence and Statistics. Vol. 151. 2022, pp. 240-278.
[23] Parnian Kassraie, Andreas Krause, and Iiija Bogunovic. "Graph neural network bandits". In: Advances in Neural Information Processing Systems. Vol. 35. 2022, pp. 34519-34531.
[24] Danial Khatamsaz et al. "A physics- informed Bayesian optimization approach for material design: application to NiTi shape memory alloys". In: npj Computaaional Materials 9.1 (2023), p. 221.
[25] Jungtaek Kim et al. "Bayesian optimization with approximate set kernels". In: Machine Learning 110 (2021), pp. 857-879.
[26] Johannes Kirschner et al. "Tuning particle accelerators with safety constraints using Bayesian optimization". In: Physical Review Accelerators and Beams 25 (6 2022), 062802.
[27] Imre Risi Kondor. "Group theoretical methods in machine learning". PhD thesis. Columbia University, 2008.
[28] Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. "ImageNet Classification with deep convolutional neural networks". In: Advances in Neural Information Processing Systems.
Ed. by F. Pereira et al. Vol. 25. 2012.
[29] Yann Lecun et al. "Learning algorithms for classification; a comparison on handwritten digit recognition". In: Neural networks: The statistical mechanics perspective. World Scientific, 1995, pp. 261-276.
[30] Benjamin Letham et al. "Constrained Bayesian Optimization with noisy experiments". In:
Bayesian Analysis 14.2 (2019), pp. 495-519.
[31] S. Marsden et al. "Using genetic algorithms to optimise current drive in STEP". Europhysics Conference Abstracts. Vol. 46A. 2022, P2b.
[32] Viraj Mehta al. "Exploration via planning for information about the optimal trajectory". In: Advances in Neural Information Processing Systems. Vol. 35. 2022. pp. 28761-28775.
[33] Song Mei, Theodor Misiakiewicz, and Andrea Montanari. "Learning with invariances in random features and kernel models". In: Conference on Learning Theory. 2021, pp. 3351- 3418.
[34] Michele Romanelli et al. "JINTRAC: system of codes for integrated simulation of tokamak scenarios". In: Plasma and Fusion Research 9 (2014), pp. 0003023-3403023.
[35] Jonathan Scarlett, Ilija Bogunovic, and Volkan Cevher. "Lower bounds on regret for noisy Gaussian process bandit optimization". In: Proceedings of the 2017 Conference on Learning Theory. Vol. 65. 2017.
[36]
Shubhanshu Shekhar and Tara Javidi. "Gaussian process bandits with adaptive discretization". In: Electronic Journal of Statistics 12 (2018), pp. 3829-3874.
[37] Niranjan Srinivas et al. "Gaussian process optimization in the bandit setting: regret and experimental design". In: Proceedings of the 27th International Conference on Machine Learning. 2010, pp. 1015-1022.
[38] Behrooz Tahmasebi and Stefanie Jegelka. "The exact sample complexity gain from invariances for kernel tegression". In: Advances in Neural Information Processing Systems. Vol. 36. 2023, pp. 55616-556446.
[39] Emmi Tholerus al. "Flat-top plasma operational space of the STEP power plant". In: Nuclear Fusion 64 (Aug. 2024).
[40] Atsushi Togo and Isao Tanaka. Spglid: software library for crystal symmetry search. wwt.////////////// coom/spglib/sgglib 2018. eprint: arXiv: 1808. 01590.
betps://githrn
[41] Sattar Vakili, Kia Khezeli, and Victor Picheny. "On information gain and regret bounds in Gaussian process bandits". In: International Conference Artificial Intelligence and Statistics.
Vol. 130. 2021, pp. 82-90.
[42] Sattar Vakili et al. "Optimal order simple regret for Gaussian process bandits". In: Advances in Neural Information Processing Systems 34 (2021), pp. 21202-21215.
[43] Michal Valko et al. "Finite-time analysis of kernelised contextual bandits". In: 3096691 (2013).
[44] Elise Van der Pol et al. "MDP homomorphic networks: group symmetries in reinforcement learning". In: Advances Neural Information Processing Systems. Vol. 33. 2020, pp. 4199- 4210.
12

---

[45] Peter Whittle. "Stochastic processes in several dimensions". In: Bulletin of the International Statistical Institute 40.2 (1963), pp. 974-994.
[46] Mark van der Wilk al. "Learning invariances using the marginal likelihood".. In: Advances in Neural Information Processing Systems. Vol. 31. 2018, pp.
[47] Christopher KI Williams and Carl Edward Rasmussen. Gaussian processes for machine
learming. 3. MIT Press Cambridge, MA, 2006.
[48] Yunxing Zuo et al. "Accelerating materials discovery with Bayesian optimization and graph deep learning". " In: Muterials Today 51 (2021), pp. 126-135.
13

---

A Proofs
A.1 Proof of Proposition (RKHS of invariant functions)
The kernel & defines reproducing kernel Hilbert space, Hy. with inner product (1, H,, and norm Il/ V'.. for Hy.
Recall from Equation (4) that Sa(f)
क Eoea
We begin by showing that SG is continuous and bounded. Observe that simultancous invariance determines the following property of the representer elements kz)()) = k(z,)) :) = k(.,z):
kg oo- (x))(x) Ao E G.
(17)
Now observe that: 1 o a112 = (ke oo = (k)- Ko 1o)) = (() = k(xx x) = ||/x||
(18)
f = Eisl hz,, we have, similarly:
11
n
[|ʃ o1f = ti (a)ll
ΣΣ k(o (x.) ==
Σ
- 11/111 (19)
i=1
Now, let fn be Cauchy sequence, where each fn lies in the span of the k2 elements. We have ||ʃ o oll
|| oal
lim [1 o oll
lim ||
|ISlI|
(20)
Therefore,
1
||affll S
Ilf o oll
$ IIfll|
(21)
G
FEG
so SG is continuous, with ||Sc|| <
We now verify that the image of Sc, denoted as Im(Sc), contains precisely the G-invariant functions (Equation (I)). For f Hk, a E G. we have
Solf)oo=
1
Σ
(foT)oo
(22)
G
FEG
1
Σ
f
(TOO)
(23)
G
FEG
1
Σ
foo
(24)
G
d'EG
Sc()),
(25)
where Equation (23) follows by associativity of G, and Equation (24) follows by letting o' :- T and using the fact that G is closed under the o operator. Hence, Sa(f) is invariant to E G (Equation (1)).
Next, we show that the image of Sg a reproducing kernel Hilbert space with kernel kg (Equa- tion (5)). First note that SG projection, applying SG twice gives
Sa(Sc())
So(f) oa
(26)
DEG
1
Σ Sc(f)
(27)
Gl
oEG
So(f),
(28)
where Equation (27) follows by applying Equation (25).
14

---

Moreover, Sg is self-adjoint. Let f E H& be an element in the span of the representer elements kz. such that f()) Di=1 arka, (.), and let g E Hy. Then,
(Sa(f) =
Σ
foo,g
(29)
Gl
BEG
(as ( 9) Hh.
(30)
GEG
anglo (xxi)
(31)
im OEG
(asken 9 o n
(32)
G
G EiSgoo'
(33)
(c())
(34)
where Equation (30) follows by expanding f and recalling that for simultaneously invariant kernels kg 0 k(or (x),)(x),.) Equation (31) follows by using the reproducing property of kr(z)) Equa- tion (32) uses the decomposition of g in terms of the reproducing element kr,, and Equation (33) uses the definition of f-
Now, as before, let fn >> be Cauchy sequence, where fn lies in the span of the h2 elements. We have
(lim fn. (g())) lim (im(So (lim Sa(fa), (So(lim (x).9)94 Hu: (35)
by continuity of the inner product. Hence, Sg self-adjoint for all Sig H4.
As Sc is projection (Equation (28)) and self-adjoint Im (SG) is a closed subspace of Hg. Now, denoting the evaluation functional L2 H& + R. (f) f(z). note that since Im(Sc) is closed, then if Ly was bounded on H4. it remains bounded on (m().). Hence Im(Sc) is itself RKHS, which we'll ll denote as H'.
We will now relate kw. the kernel associated with H', and G. Note that, for f E H'.
f(x) k2) (Se(f), km) (J,
(36)
So Sa(ka) is the reproducing element for H', giving
ke (z, y) = (Sc(k,), = (Sc(k,,, = |G|
Σ k(a(z),))
(37)
OEG
which recovers the formula for the kernel in Equation 5.
Finally, note that (ky(, So (kz)) recovers the more general "double sum" formula for producing a totally invariant kernel out of kernel which is not necessarily simultaneously invariant [18, 33]:
ko(x,v)
Σ k(o(x),
(38)
GG
a.TEG
15

---

A.2 Proof of Theorem 1: upper bound on sample complexity
In this section we derive Theorem 1, the upper bound on regret for Bayesian optimisation algorithms that incorporate invariance. The main elements of this proof were introduced in [41]. Our derivation similar to the one section C.I of [22], but extends that work to more general groups and kernels.
In Appendix 1.2.1, we present a concise summary of already known bounds on the information gain of dot-product kernels with polynomial eigendecay on the hypersphere. Appendix A.2.2, we will adapt this argument for information gain of totally invariant versions of these kernels. We then use the bounds on information gain to bound the regret in Appendix A.2.3.
We begin with the following remark which we use throughout this section. Namely, with the assumptions of Theorem I, kernel & on Sa-1 which is simultaneously invariant with respect to the whole of (d)) is a dot-product kernel. To see this, choose r E [-1,1] 1] and pick Ir, such that (Frr yr) and define x(r) k(arr )r). Observe that is well defined, as for any other choice of
(1',, n/.) there is a (non-unique) isometry M (( such that
</ (a
(2r.2r) Fr
(39)
5/4 M(ee (Er:3t.) yr
(40)
(41)
and therefore k( Ur) = k( v.)). Hence, throughout this section we can consider dot-product kernels only.
A.2.1 Information gain for kernels the hypersphere
Consider the hyperspherical domain gd-1 {ar E IRd s.t. ||]||| = 13. The Mercer decomposition of a dot-product kernel on the hypersphere is
N(d.K)
k(x x')
Pk Σ
Yaxl))Y,ua')),
(42)
km
where Yi.p is the i-th spherical harmonic polynomial of degree k and N (dd, is the number of spherical harmonics of degree h on Sd-1 given by
2k d - 2 k + d - 3) N(d, k)
(43)
d - 2
Asymptotically in terms of k we have
N(d, k)) θ (k=-
(44)
In this representation, μI can be interpreted as an eigenvalue that is repeated (d,,)) times, with corresponding eigenfunctions Yi, YN(d,)).. We let v be the maximum absolute value of the eigenfunctions, such that (Yr, S vb Vor gd-1
We project onto a subspace of eigenfunctions corresponding to the first D eigenvalues. Let be the number of distinct values in the first D eigenvalues. It follows that
K
D
(dd
(45)
k=0
K
<D 02
Ld-2
(46)
k=0
k=0
C Kd-1
Kd-1
< D
C2
(47)
d-1
d d-1
D= (K
(48)
16

---

where Equation (46) follows by substituting Equation (44), and Equation (47) follows by bounding the sum with an integral, and C₁ C2 are constants that ensure the asymptotic equalities hold. Truncating the eigenvalues at D leaves a tail with mass
åD
Appe 2
(dN(d,
(49)
D=++1
k=
01 Σ
Hkhd-2
(50)
km k
S 5 C2
h
(51)
K=K
S C3 K K -p +
(52)
3.+d +d-1
2 C4D
d-1
(53)
where Equation (50) follows by substituting Equation (44), Equation (51) follows if the distinct
eigenvalues have polynomial decay rate, 14 = = );² Equation (52) follows by bounding the sum with an integral; Equation (53) follows because D ((K-11), and hence K @(Da.).
Theorem [41] states that
D log
kT TD
T8D 2T
TI S 2
1+
(54)
where [k(2x,))) S Te Vo and is the observation noise variance. Substituting in Equation (53) gives
D log
KT
Tw
---4-1
YT S
1+
D
(55)
2
7D
2T
We have freedom in setting D. We choose so that the first term dominates, by setting
D
KT
TV
-d-
log
1
D
d-1
(56)
2
2T
This is satisfied by
1-1
Triics
D
(57)
Flog
1 +
KT
which gives:
d-1
Tob
KT
rr S
+1 1
log
1
(58)
(log [1 KT.
where we have used the fact that
[x]] I x. + Hence,
YT = O T 3 log
op T
(59)
A.2.2 Information gain for symmetrised kernels on the hypersphere
Our upper bound involves comparing the corresponding reduction in maximal information across the invariant vs the standard kernel. In this section we will use overbars refer properties of the symmetrised (invariant) kernel. We remind the reader that G < (dd) is a finite subgroup of
Matérn kemels gd-1 satisfy this property with 87 = 2v + 1 19].
17

---

isometries of the sphere gd-1, Our aim will be to provide bounds on the asymptotics of the eigenspace
dimensions ((d.k) where N (d, k) defined in A.2.1 and N (d, k) is the corresponding eigenspace
[dd.k)
dimension for the symmetrized kernel kg.
We will follow the exposition from [4], where asymptotic bounds on r(d, k) == (dd
N(d.) are given
with two minor differences: 1. our treatment will handle any finite group of isometries and 2. we pay the price for generalizing to arbitrary groups by obtaining less strict decay rates, which will not trouble us for our analysis.
We will show the following:
Lemma 1. With the notations described in this section, assume G S O(d) for d 2 10 is a finite group. Then, if -f- E G:
C
5 <d, 5
for odd,
(60)
2
2 C
S (dd k) -
for k even,
(61)
G
G
(62)
and, otherwise:
C
(63)
|G|
Gl
where a constant that depends on k d and the spectra of elements G.
Proof. Recall from [4], the formula:
rd, = G
Σ Tddkko) = Σ Ep [Pa 2))1, GEG
(64)
OEG
where 1 is the uniform measure on the sphere 5 and Pa. is the corresponding Gegenbauer polynomial. To demystify the conditional statement in the Lemma, notice first that Pa, ((z, Pa.x(1)= = 1, and Pa, ((-xr, .t) = Pa,x(-1 = if & even and if k: is odd. For all other E G, we'll follow the argument in [4] to show that yd, k o) - O with asymptotics at least O (t)
We don't make significant contributions to the method in [4], here, other than to remark on the fact that many
arguments they present follow through for finite subgroups of (d).
First remark that for E G < (d) there is a matrix representation A,, which admits a canonical basis in which the matrix elements are:
R1
0
Rs
(65)
#1
0
#1
where each R2 is a 2 matrix of the form () with eigenvalues À and X.
Moreover, notice that since A!Gi = I. all eigenvalues are roots of unity À = 2nix
with q G). The the eigenvalues such matrices are the same as the allowable eigenvalues of permutation matrices considered in [4], from which Proposition 6 gives:
rd, k. a) S Ck-d++ + o(k -dts
(66)
where s = mmaxxeSpe(AA)) {mx + 4 1([1 < 1)}. Now assume + =l. We have mi 5 d
2,
m_1 < d d-3 2 and ms < if * +1. Collectively this implies -d + < -f > 10.
0
18

---

In the following assume that -I g G. The corresponding argument for -1 E G' is similar. In view of Lemma 1
k) k)
1 C G k
G -
(67)
We take the same number of distinct cigenvalues for the invariant and noninvariant kernels, K. However, there will be different multiplicities for the eigenvalues, leading different number of eigenvalues D. The corresponding tail has mass
8D S 2
Σ im D+1
A =
2/?
P (d,
(68)
1 + C)
2/2
(
(69)
G
k
k=K
1
C"
2/2
Σ
(d,
(70)
G
K
k=K
1
C"
ÖD
(71)
G
K
1
C"
6D
(72)
GG|
Da-1
1+6
8D
(73)
G
where Equation (69) follows by substituting Equation (67), Equation (70) follows because 1 < K
k
for 1 K, Equation (72) follows because K @(D=tr), and for D De where D. satisfies
dl <E D.
Now, Theorem 3 in [41] gives:
D fr S
kT
TôD 2T
log
1
+
(74)
2
TD
Proposition 2. af,, > O, 6n > O, with lim an lim bn = xc and lim bn/ aa, = X >> 0, then Ve > 0, EN such that VN' > N we have Enex, bn (1 c) Ener' On-
Proof. From the definition of the limit, noting that the 1 gives slack bound À Enen a₂ above by ENenen bn.
Using this proposition on the sequences N(d, k) and [d, k) we have further:
D(1 + c)
KT|
1 c T8p
log
1
(75)
2|G
7D(1 +e)
G 27
1 +e c
D
KTIGI
TOD
log
1 1
(76)
|G|
2
TD(1 +0)
2T
1+c
TD(1+0) )
KT|G|
T
-d-+d-1
log
1/
CDD
d-1
(77)
|G|
2
2T
As previously we'll choose Dr as a function of T such that the logarithmic term dominates (notice that since the first term is increasing in any choice of Dr greater than this will also satisfy), i.e
Dr log (1
KTG ) 7(1 (1)+))
T
+d-1
CDD
d-1
(78)
19

---

Or
7 4280 C4
DT 2
log 11 Lola
(79)
7(1+0) ((1tt)
With this choice:
2-1
48 2.
1+E (T
KTGGI
C
log
1+
(80)
Gl 7
7(1 +c)
Hence,
T
(81)
G
A.2.3 From information gain to sample complexity
Under the assumption of sub-Gaussian noise, is shown in [42, Remark 2] that the maximum variance reduction algorithm presented in Algorithm incurs simple regret satisfying
TT =0 =0=
yr (oog(T/////
(82)
T
with probability at least 1, where (0, 1).
Note that we are able to use this result without modification, as our approach only incorporates G-invariance through the kernel; hence, any changes the regret due the G-invariance will only appear in the " term. Substituting "r from Equation (80) into Equation (82) gives
26 dil
26
211 (TI T/8
=
T
log
(83)
|G|
log (T) T/6)
=
T
(84)
G
02-d+1
where we have absorbed factors that do not depend on T or G, and let a
233
Our goal is for FT (e)) This can be achieved by setting
1 log
2
1
log TF
(85)
G
G
with appropriate implied constants. Substitution of T from Equation (85) into Equation (84) makes it evident that for this T we have
FT O(e) + O(log log T log log [G|).
(86)
Substituting a into Equation (85) gives the final upper bound sample complexity, which is
((t)
285
200
2.5
88-241
T=O
log
log
(87)
G p
GG #p 1--441
89
For the Matérn kernel on the hypersphere, [9] showed that
B 2v + 1
(88)
and hence, the MVR algorithm with an invariant Matern GP defined on gd-1 will achieve simple regret with probability 1 - 8 if
2014--1
==Ö Ô
2rid-1
where δ hides logarithmic factors in and |G].
20

---

Figure 7: Examples of invariant func- tions on the sphere. The construction for our lower bound consists of func- tions invariant to finite rotations, as in Figure 7a, but does not include functions like Figure 7b (which produce different packings).
(a) Function invariant to 10-fold rotations
(b) Function invariant rotations along an axis
A.3 Proof of Theorem 2: lower bound on sample complexity
In this section, we derive Theorem 2, the lower bound on regret for the invariant Matérn kernel under permutation groups. The main elements of this proof were introduced in [12], which extended the method [35]. This constructive method serves to demonstrate the tightness the upper bound. As in [12] and [42], our method involves building up set of candidate optimization targets in Nka However, unlike these papers, it is no longer clear in this setting that such constructions are optimal in terms of the resulting dependence of the lower bound on |G] (the current gap the upper bound potentially measures this failure rate). Our methods will produce elements in (FF S Hik for be
partieular set of functions F, and it's the object of further research if these constructions improved.In Figure 7a, we have an example of the types of functions we construct, by applying the operator Sg to a simple bump function. In this example, G' is group of rotations along the vertical axis. In Figure 7b is an example of function we cannot retrieve through our method. This function is similarly invariant (also to all other rotations along the axis). Our method relies packing argument for the supports of such functions and it is a priori unclear how the tightest packing can be obtained.
We identify bounded subset of the RKHS of invariant functions that contains functions with the property that each point in X' is e-optimal for at most one function. We then construct a set of noisy bandit problems using functions from this class, before applying [12, Lemma 1] lower-bound the number of samples that a learner requires in order to distinguish between them, and hence the best-case regret for this configuration.
A.3.1 An explicit construction
The proof for our lower bound will be constructive. We will exhibit a family of functions for which there is computable lower bound of samples needed to distinguish their maxima. The challenge comes from constructing these functions natively in the RKHS of invariant functions. The strategy employ here is to construct functions by symmetrization of simple bump functions. For the benefit of the reader, we'll show an explicit version of this construction first, on the hypercube X' = [0. 1]d equipped with the action of G Sa and subsequently extend to general actions of subgroups of (d) on the sphere gd-1,
Lemma 2 (Bounded support function construction [12, Lemma 4)). Let h(x)
exp 1- 1f] < 1) be the d-dimensional bump function, and define g(x, w. c)
2e h +t b(0)
for some w > 0 and e 0. Then, g satisfies the following properties:
1. g(2, w, E) for all x outside the ball of radius w centred at the origin;
2. g(z, w. e) E [0, for all x. and g(0) = 22:
3. |lgll < ci kCO)
(1) [|blll when & the Matérn-v kernel on Rdd, where e₁ is constant. In particular, we have I| S B when
2e
2ecc Alle K(0)B
Let e Ed be the canonical basis vectors in IRd Then, the set
2A
2A -
I(a)= = 2 a61 + ....
aea : A E
(90)
2
21

---

forms lattice of points on Ie with spacing a. Equivalently, L(a) defines partitioning of R into disjoint regions or 'lattice cells' {R(xo) : zo E L(a)), where (zo) is d-dimensional hypercube of side length a centred on Zo.
Define the function class Flw,,) (g(x: zo, w. xo E [(w)). By property (1) of Lemma 2, g(x - 20, w, e) is zero outside of R(ro). Hence, the support of functions f E F(w, e) are pairwise disjoint. In addition, as F(w, E) consists only of translates of g(z w, e), we retain max f = 2e and I|A x B Vf E F(w, E) for appropriate w from properties 2 and 3 of Lemma 2 respectively.
The hypercube [0, 11 contains N of these functions, where
d
h()) 2ec ||b|l
d/v
N =
(91)
Now, we construct set G-invariant bump functions with disjoint support on the hypercube [o, 1]4. centred the lattice cells for a class of groups G' equipped with action which we define below.
Lemma 3 (Set of invariant functions). Let G be a subset of Sa. the permutation group d elements. G acts on Red (and on any invariant subset X) by permutation of the coordinate axes. Let F(w, c) {g(x= - In, w. c) : Do E L.w)}. Then, F(w, c, G) {Sa(f): F(IG))/ w. (G][) where Sg is defined as in Proposition 1, satisfies the following properties:
1. F(w,e, G) is a set of G-invariant functions I&d with pairwise disjoint support;
2. max, f((z) 2|G
where f((z) Scle(1 Is, (Gle)) F(w,,,G);
[G-ll
3. |lfIl S B vf e F(.,c,
Proof. First, we show that Flw. e, G) is indeed Sg-invariant set of G-invariant functions with disjoint support. As all translates g(x: zo) are symmetric around zo. it holds that g( ro) g(x o (xx)). ). From Equation (90), it is evident that the lattice [(aa) is invariant to permutations; that is, (30) L(w) for all 20 I(w), G. Hence, F(w, e) itself invariant under Se, and fortiori F(w, C, G) SG (F(IG)//w, (.)e)))
Next, we show that functions in F(w, G) have maximum value 2/c [G-zal Let fi E F(I)) w. |G]() be the function centred z₁- From Lemma 2, property 2, fo has maximum value 2 Gle.. Let Gz, = (o (x,) = x4} denote the stabilizer group of G at zi.
Since the lattice itself is invariant, the image G-z; of the centre will have size
IG|
I-aall
(92)
|Ga
The preimage of any element in G- consists of exactly GGa, elements. Therefore,
Sc(f)
Σ Σ foo
(93)
G
HEG/G.,, dCH
|Gagl
ROON
(94)
G G
HEG/G..
(95)
where σн is a representative of the coset H and f. oh is the unique value of on this coset,
regardless of its representative.
Note that for any cosets H and K, fooo and fooo have disjoint supports from the same arguments as before, and thus,
|Gagl
G.,
2|
max Sc(fi) =
max fo oo = 2|G|e
(96)
G
G
G-
22

---

Finally, we show that functions in F(w, e, G) have norm bounded by B. Let f E F(w, e, G) and f F( G|e).. From property (3) in Lemma 2,
2
Il - h())
||b||a
11 S B,
where w is the same before. From Proposition 1, recall that Sg is projection; hence, ||f S B implies [|So()) & B, and so |f S l S B.
F7
We now restrict the function set to the unit hypercube. The number of functions from F(G F(GG [G]e) (the set of rescaled non-invariant functions) that fit in the unit hypercube is given by N', where
N'
(97)
G /
N,
(98)
where N is defined in Equation (91).
Clearly, the number of orbits in F[[G)// |Gle). i.c the number of elements in F(w, G) is equal the number of orbits of G on L(w), by Lemma We would like count the number of orbits, or at least bound it from below. For specific groups G one can do this explicitly, however, in general it is impossible to give a count of the orbits, without further assumption. What we can, however say is that the number of orbits of size exactly |G| represents almost the total number of orbits when w is small.
Proposition 3. Let M [Fw, e, - = (L(IG))/' Nio, 174) /GI. Let K | Then
and this bound is asymptotically tight in the limit ofw w + 0. M N G
Proof. Let W(s) be the of points in L[[G) 1/2)) w) noo 11d with exactly s I d repeated indices.
Assume is such that K == Liqut/! > + 1. Then, W(0) + 0 under the action of G, such points
(ww) will have GG = G).
Points in U._1 W(s), i.. points with repeated indices lie in a union of manifolds of dimension 1 or below within the hypercube [0, 1]d. As such, w decreases,
W
+1
(99)
N
This is easy see as
[W(O]] K (K - 1) ... (K-d) -d).
(100)
Hence, we have that F(w, e, G)I approaches
M/ w. [Ge]]
from above the width tends to 0:
[G|
[F e, G)l 1
lim a-+0
(101)
[[[G G
|G|
Note that M is also the number of functions from F(w, G) that are supported in [0, 1]d. Then, we can rewrite the above inequality as:
N
M
(102)
G
2
Gj++d/v N,
(103)
23

---

where N is the number of functions from F(w, e) that fit in [o, 1]", as defined in Equation (91). Equation (103) gives a direct relationship between the packing of invariant and non-invariant bump functions with bounded norm that fit in the unit hypercube.
Note that the above analysis shows that this bound is tight for small enough which depends only on d and y/ since GG < d!. If one is interested only in Equation (103), this is easy to obtain as M, the number of orbits is greater than N' divided by the size of the largest orbit.
Note also that in the case of noiseless observations any optimisation algorithm will have to query at least . (resp. N) points to be able to distinguish between functions in F(w, c, G) (resp. F(w,,) defined on [0, I] hence, Equation (103) (resp. Equation (91)) can also be interpreted as lower bound on the sample complexity of finding the maximum of these functions.
A.3.2 Distinguishing between bandit instances
The subsequent section of the proof mirrors the approach used to derive simple regret lower bound in the standard monniinvriiant) setting, as detailed in [12, Section 4.2]. The primary distinction lies in the construction of the representative functions that exhibit group invariance, as outlined in Equation (104) and Equation (105).
Recall the definition of region R(-)) from the discussion following Equation (90). Define R, as the center of the region. Note that these regions are self-contained under G, so that x E R2 = a(x) E R2 and are pairwise disjoint. Therefore, we define set of M such regions (R, 1i which partition our domain. The value of M is lower bounded in Equation (103).
R, = Urec (xx)), where I2 E L( L(GG)
We replace B with B/3 in the construction of F(IG)//w, |Gle) (see Lemma 3).² Let fi and fa (**)) j) be shifted bump functions from the set F(|G) // |G|e), centered at some fixed x; and zy respectively, where Ti, 2 E L[GG) 1' w). Furthermore, these are selected such that the sizes of the orbits, |G xz| and |G - æzl. are both equal to [G]. Then, we construct the pair
f = Sc(fi),
(104)
8 = Sc(f)) + (f)(
(105)
The following holds || S B/3 and ||f'|KK S B (from Lemma 3 and triangle inequality). We observe that f and f' coincide outside R, i.e., I f f is only non-zero in region R,, Moreover, we have maxzeR, [(x)) 2. and max ['(x) = 4e. It follows that only points from R2 and R, can be c-optimal for f' and f, respectively.
In the subsequent steps, let P/|-] and E-I-] denote probabilities and expectations with respect the random noise, given suitably chosen underlying function f. Additionally, we define (V( as the conditional distribution N (ff()), consistent with the Gaussian noise model.
We fix T E Zt, 8 (0, 1/3), B 0 and (0, 1/2), and assume the existence of an algorithm such that for any f E FR (B), it achieves average simple regret r(2(2)) S with probability of at least 1 8. Here, .T)) represents the final point reported by the algorithm. Note that an algorithm that achieves simple regret less than e for all f E Fi (B) automatically solves the decision problem of distinguishing between f and f' above. If no such algorithm exists, the sample complexity necessary to achieve this bound on regret must be higher than T. Next, we establish a lower bound on the number of samples required for such an algorithm to differentiate between two bandit environments (with reward functions f and f' and the same Gaussian noise model) that share the same input domain but have distinct optimal regions.
Let A denote the event that the returned point (T) falls within the region R., Assume that an algorithm achieves a simple regret of most for both functions ff and f' (both f.f e FRa (B) as established before) each with probability of at least 1 - 8. Under our assumption on simple regret, this implies [y[A] 2 under f. and only points within R, can be o-ptmmal under ft
and Py. < 8 since only points within R, can be coptimal
We note that this modification affects only the constant factors (also in the bound on M from Equation (103)), which are not important for our analysis.
24

---

We are now in position to apply [12, Lemma 1]. We apply this lemma using the previously defined f. f', and A. It therefore holds that, for (0, 3):
1 Σ Ey [Cm] max KL (1 2 log 2.46 R.R....
(106)
where Cm the number of queried points in R. up to time T.
For the two bandit instances and any input x, the observation distributions are (ff(a), o²) and (x), o²). Utilising the standard result for the KL divergence between two Gaussian distributions with the same variance, we obtain:
max KL (Py(12)) Py = (max,eR... f(x) - max, {()))² RERm
(107)
20²
Sc jj
a²
(108)
otherwise,
fxx) (x) for x & Rj. and for R2 we have that f(x) and max (x))) 4c.
Hence, Equation (106) becomes
8E² σ² B [111) 2 log 1
(109)
2.48
Let J (j E Mr, W(0) be the of indices j such that ʃj centred around a point with no repeated indices such as in Proposition 3. Let Pee = G M be the fraction of all orbits of size exactly |G). By Proposition 3, for any small 6w.. there is correspondingly small enough such that Pro 2 8u- Since the previous inequality holds for an arbitrary j. we sum over over j E (J G(i)) /G arrive at:
S
1
F
[C
2 log 2.48
(110)
J
J
By rearranging and noting that En F [C,] = T we obtain
T2 (Mp - 1) 86
log 2.48
(111)
Substituting in M from Equation (103) gives
6 log
σ²
T
log
(112)
G
822
2.48
822
2.48"
and using N from Equation (91) gives the final bound
B
d/v
1
T= Ω
log
(113)
|0|
2
5
where the implied constants can depend on d, I, and v.
A.4 Lower bounds on different underlying spaces.
In this section we'll investigate how to raise the lower bounds on sample complexity to embedded submanifolds + ddd. The full treatment below is valid only for the hypersphere, X' S but many of the ingredients required are valid on other manifolds as well. When specific statements about the sphere are made in the treatment below, we will explicitly refer Sd instead of X.
FFollowing the approach [12]. we deterministically set the stopping time in Lemma I to 7' corresponding to the fixed-length setting in which the time horizon is pre-specified. For an adaptation to scenarios where the algorithm may determine its stopping time, refer Remark I in [12].
25

---

In the proof in A.3, we used the existence of a G-invariant lattice to underpin our bump function construction. Moreover, we've used the fact that the RKHS norm B := |1gl|x wa the underlying function class construction for F(w, c, G) here.
We will replicate
We will recover the same property for bump functions on X' but under a different notion of rescaling.
Pick point p U X' and consider (v'... ...., "'.."""""" system of coordinates on U so that x,, (o'''...... .... yn") represent the standard coordinates the ambient space T2d. Let Sp.w.c Rdd - IR, be bump function around p which is O outside B (p: Rd) and supported in /2 Rd) with height as in section A.3. Let Op.w. fp.w.elx
If X 34, then the intersection Br (pi X) == (p; ( X' is a geodesic neighbourhood with geodesic radius Tw arccos 2~ For small enough w,
w Twn S w
(114)
by computing the Taylor expansion.
We will Iso need to compute the RKHS norm for dp.w,e for some suitably defined kernel. Let ky : Fd Rd be the standard Matérn kernel, and consider ky its restriction to X.
Next, we recall the existence of fundamental domain for the action of finite groups on X. Following the definition of fundamental domain from [21], say F C 2' is fundamental domain for the action of G if:
F is a domain.
* F-F
gFF NF - g = e, the identity.
For any compact K X, the transporter set (FIK). finite.
Note that the last condition is trivial if G is finite. The construction of F is simple given that G acts by isometries of the underlying space Rdd and 9x =" Igd.
Indeed, let x be point such that |Gx| |G| (such a point trivially exists, as each member of G other than the identity fixes a subspace of dimension at most - 1) on the X gd-1, Then, |Gz| = |G], and the Dirichlet domain:
Fg = fy E X(dx(1x))) < dx(gx, v), Ag E G {e}}
(115)
is fundamental domain for the action (see [21] for proof). One can see this set of points as the interior of the points in which are closest to x rather than any of its other translates under G. For example, for the action of Sa on the positive orthant sd-1, it is any of the simplices in the barycentric subdivision.
Equipped with this definition, we construct the lattice of bump function centres on X' as follows. First construct 2r wP-nee L(Twi on Fz as the set of centres of optimal geodesic ball packing F.. Then define
L(rw) == L(r:: G L(r fx)
(116)
We will need to compare the cardinalities of [.(ww) and [trr.) for some scaling factor > 0. Let 11(rw) be the packing number of F C Sd-1 by geodesic balls of radius Tw.
We have trivially that
Vol(F)
Vol(F)
Vol B2r, (p: S IT(r.)) Vol(Br. X))
(117)
where the first inequality comes trivially from noticing that maximal rw packing is 2r,, covering. Moreover, since the exponential map is diffeomorphism on small enough neighbourhoods (with derivative at the origin), we have that:
K V ol Br.. (p: Rd- < Vol X2)) < K2Vol(B,,. (p: Rd:))11))
(118)
26

---

for some 0 < Ki < K2. Combining equations 117 and 118 gives:
c II((T)) I1(ttw) S c2t"=!1l((w))
(119)
Following this discussion, we have the following lemma which is an extension to Lemma 3. Denote by w, the inverse mapping of w Two defined small enough geodesic balls on Sd-1, We write F(w,c) = (Sp...c E [rr)) for a set of functions on the ambient space and Fx(rw. c) = {óp,ue = fp.w,exx {Sc(f) f F(GG) (G'ee) [G'e)] and Fx(w, (,W,,,),,,...., F(w, E, G)
[(rw)] for the restriction F(w, x) Similarly, we write F(w, G)
Lemma 4 (Invariant functions on the sphere). The sets Fx(Tws e, G) and F(w, e, G) satisfy the following properties.
1. Flw,e, ew,,e,G) G) is a set of G-invariant functions on Sd-1 with pairwise disjoint support;
2. max, Sa (n = ppp
k
3. [ff| SB vf Fx(
Proof. The key ingredient for 1. is to note that each fp.w,e(x) = p( and thus, each f is G-invariant around the point p, namely, for G, fp.w.e o fo) Then, since L(rw) is G-invariant by construction, 1. follows. For 2. the proof is identical to Lemma 2. For 3. notice that
11 Ils. S inf 1l I Illp,,eellkk = pll
(120)
qr
where the second inequality follows from the restriction and df is any extension of to the underlying space, since the norm of a restriction less than that of all extensions.
Let N = IFW, e)), M = F(w, e, G). Recall that these functions are defined terms of the packing numbers of F, so that N [r] and M = [[]])))))) Pick 8. >> O. For all small enough w, we have that:
M> (1 Z ei G (1 )d
c3/G/|/ G|
(121)
where the first inequality comes from equation 114 and the fact that the packing number is decreasing function of the radius, the second inequality comes from equation 119 and 03 a constant which depends on the ambient dimension and the curvature of the space X'
Following the arguments of section A.3.2 see, that by construction, L(rw) admits only orbits of size [G), end hence in Equation 1 100 the sum is over all elements (x c, G). Hence we recover the same lower bound on sample complexity:
B
1 0
T = Ω
log
(122)
2
This concludes the proof Theorem 2.
The key element is the original construction of the functions (x)) which are of the form g(x: - p) for some bump function constructed around the origin which itself symmetric with respect the action of (d) (and hence its subgroups).
27

---

B Experimental details
B.1 Synthetic experiments
We use an isotropic Matérn-9t kernel as the base kernel k, and compute kG according to Equation (5). To generate the objective functions, we first generate large number n of sample pairs (æ f f(x) from zero-mean GP prior with kernel lengthscale / = 0.12. We scale with the dimensionality of the problem d, so that n 64 for d 2, 256 for d 3, and 512 for d = 6, mitigate sparsity. We then use BoTorch to fit the noise parameter of noisy invariant GP with fixed lengthscale = 0.12 that data, and treat the mean of the trained GP as our objective function. In this way, we ensure that the objective function belongs to the desired RKHS.
During the BO loop, the learner provided the true lengthscale, magnitude, and noise variance of the trained kernel, to avoid the impact of online hyperparameter learning. For UCB, we use / = 2.0, except in the quasi-invariant case with ε 0.05 where we found that increasing 33 was necessary to achieve good performance (B 3.0). MVR has no algorithm hyperparameters.
For the constrained BO baseline, replaced BoTorch's 's default initialisation heuristic with rejection sampling in order to generate multiple random restarts that lie within the fundamental domain. We found that this improved the diversity of the initial conditions, and hence boosted the performance of the acquisition function optimiser.
In all other cases Bo' BoTooc defaults were used.
B.2 Fusion experiment
We consider the 3-block permutation group, with |G| are learned offline, based on 256 runs of the fusion simulator with parameters generated by low- discrepancy Sobol sampling. Due the cost of evaluating the objective function we use batched version of the acquisition function as implemented by BoTorch, querying points in batches of 10. We use the multi-start optimisation routine from BoTorch for finding the maximum acquisition function value.
24. The kernel hyperparameters
28

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our theoretical results have been listed with all accompanying conditions and assumptions. Equally, our empirical results have the appropriate limitations and special settings described. Both match what listed the abstract.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors? Answer: [Yes]
Justification: In our 'Limitations' section (Section 5), we outline the computational cost of our method; this is the main drawback of our approach. Importantly, provide an alternative low-cost approximation for use when the full technique is too costly. In our theoretical results, we clearly state the group actions, kernels, and other assumptions for which our theorems hold (Proposition 1, Theorem 2, Theorem 1). Following the literature, we do not include the impact of online hyperparameter learning our theory or experiments.
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 out any strong assumptions and how robust the results 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 the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect 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 of 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 acknowledged 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.
29

---

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]
We provide formal proofs of all theorems and propositions in the main text in the appendix: Proposition has proof in Appendix A.1, Theorem 2 has proof in Appendix A.3, Theorem has proof in Appendix A.2. These are correct and complete to the best of knowledge. Where our work depends on lemmas and theorems from other papers they are clearly cited and their use in our case explained in words (e.g. Lemma 2).
Justification:
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 in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch 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.
Thcorems 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 of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All resources needed to reproduce our results have been provided in the code itself. The paper merely summarizes and describes the experimental settings, and all results are available directly from our code. Aside from the code, the experimental section clearly describes how the synthetic test functions are generated, and the tools used perform BO. A complete explanation of the fusion setting is provided, and additional resources cited for more detailed information on the experiental configuration.
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 is a specific model and empirical evaluation, it may be necessary to either make 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.
30

---

(c) If the contribution is a 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-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 the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide a running codebase with scripted experiment files. All will be made available online upon acceptance. We provide access to the relevant simulation environments where needed, otherwise, as our algorithms fundamentally deal with data acquisition, open access to data is not applicable. In particular, depends on proprictary code and models that belong to the United Kingdom Atomic Energy Authority, the full fusion experiment cannot be made public. We do, however, provide the optimisation script, with the calls to the proprietary models censored, so that reviewers can view our exact methodology.
the fusion experiment
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/ Seapii/ggudeee/Coeeeee
wwmmiiissioooooooo oniioiippyyy MiPoollyy) for more details.
While 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 NeurlPS code and data submission guidelines (https: / //nips. cc/ aec//ublic//gee wwtccc//giiee/eeeeeeeeee (odeee/mmm aassonnollll onPolicyy for more details.
The authors should provide instructions 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.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code 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: All the special experimental settings needed to understand, appraise and judge the usefulness of our results have been provided, and connections to our theoretical setting have been drawn. Details needed for the implementation only are part of the code we supply; this includes exact hyperparameters and seeds used to generate each of the plots.
Guidelines:
The answer NA means that the paper does not include experiments.
31

---

The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, 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: In all our experiments we provide adequate statistics except where appli- cable. This includes sample sizes for experimental runs, sources of randomness and the appropriate error bars where applicable. the fusion experiment, providing estimates the standard deviation is not meaningful due to the presence of failed simulations, as discussed in the text.
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 or the standard error of the mean.
OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error 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 to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in 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: We make special mention of the hardware we use, the computational trade-offs in various applications of our method, with quantitative data summarized in a graph.
Guidelines:
The answer NA means that the paper does not include experiments.
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 compute required for each of the individual experimental runs as well 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 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https : ht///nuurippp http://////pp/ieeiiiiiiiieeeeeee
32

---

Answer: [Yes]
Justification:
We conform in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: In our conclusion we include a separate set of comments on broader impact. Our work more broadly falls into the category of foundational and theoretical research.
Guidelines:
The answer NA means that there is 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 (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 that a 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 as 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.
there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML...
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: Our work poses no 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.
33

---

We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: 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?
Answer: [Yes]
Justification: We cite the papers for the code we use ((2, 10]), which are both available under open-source licenses.
Guidelines:
The answer NA means that the paper does not 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 is used and, if possible, include URL.
The name of the license (c.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.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged to reach out the asset's '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: We provide commented Python code with informative doestrings. Upon publication, we will share the full code repository under a permissive open-source license.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl 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 is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
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: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
34

---

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 Ethies, 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
Question: 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 on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
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.
35


Reviews:
[{"review_id": "y9ptxEAqCk", "reviewer": "Reviewer_8csK", "summary": "The paper targets the Bayesian optimization problem for a class of invariant functions, which is useful in many fields including machine learning and physics. Specifically, the paper proposes to incorporate the invariances into the kernel of the GP to produce invariance-aware algorithms, either fully or partially. The paper presents theoretical analysis regarding the lower bound on sample complexity when using invariant kernels in BO. Several experiments are shown to support the findings.", "questions": "I don’t have many questions regarding the submission. I think my main question is on the performance of the algorithms for higher-dimensional problems. Will the methods work well in high-dim regime? And if not, are there anything we can do to make it work better in the high-dim setting?", "limitations": "I agree with the author’s limitations regarding the computational expense of fully invariant kernel on large group of transformation.\n\nNo negative societal impact needs to be addressed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "•\tThe target problems (invariant functions) are important yet has not been focused on much.\n\n•\tThe ideas of invariant kernels are interesting and worth investigating.\n\n•\tThe theoretical analysis is thorough by providing both upper and lower bound for sample complexity.\n\n•\tThe empirical performance is good in all cases.", "weaknesses": "•\tIn Figure 3, the plots should be consistent, i.e., either use cumulative regret or simple regret. \n•\tThe experiments are only conducted on low-dim problems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their appreciation of our work, and their positive comments regarding its importance, thoroughness and empirical performance.\n\n### Response to weaknesses and questions \n\n**Concerning the plots in Figure 3:**\nCurrently, we plot the cumulative regret for UCB and the simple regret for MVR, which we suggest is standard practice for these algorithms.\nIn the literature, the regret bounds for UCB are reported in terms of cumulative regret **[1, 2]** and those for MVR in terms of simple regret **[3]**.\nWe chose to follow this convention for our bounds and experiments.\nThis makes it easy to identify the performance improvement that can be achieved by incorporating invariance compared to existing regret bounds.\nFinally, we would highlight that it is fairly trivial to convert the simple regret to cumulative regret, if that is interesting for the reader.\n\n**Concerning the performance in high dimensions:**\nWe agree that the performance of any algorithm in high dimensions is important for real-world applications; however, BO in high dimensions is a domain in its own right and often necessitates special treatment.\nIn our work, we do evaluate performance on medium dimensional problems (6 and 12 dimensions), which are already bordering on the point at which traditional BO breaks down.\nOur method does show improved performance with increasing dimension, but beyond 10-15 dimensions it is likely that the factors that limit the performance of standard methods will also start to hamper ours.\n\nOn the other hand, our kernel is an additive kernel, which is an established method for improved performance in high dimensions (see, e.g., [4]). With this in mind, **we will add a reference to the literature on additive methods for high-dimensional BO, namely [4] and [5]**.\n\nWe wholeheartedly agree with the author that this is certainly an interesting topic, but given the additional scope involved we suggest that investigating methods for high-dimensional invariant functions might be better suited to a dedicated paper.\n\n\n**References:** \n\n[1] Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design; Srinivas et al. (2009)\n\n[2] On Information Gain and Regret Bounds in Gaussian Process Bandits; Vakili et al. (2021)\n\n[3] Optimal order simple regret for Gaussian process bandits; Vakili et al. (2021)\n\n[4] High-Dimensional Bayesian Optimisation and Bandits via Additive Models; Kandasamy et al. (2016)\n\n[5] High-Dimensional Bayesian Optimization via Additive Models with Overlapping Groups; Rolland et al. (2018)", "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": "uynMF8qjKS", "reviewer": "Reviewer_5kTb", "summary": "The paper introduces an Bayesian Optimisation method which is able to take into account known invariances of the objective function.  Specifically, it is assumed that the objective function remains invariant under a finite group action $G$.     \n\nThe approach is straightforward, one does standard Bayesian optimisation using a $G$-invariant kernel, following the approach of [Haasdonk et al, 2007] and others.    The authors then propose using standard BO with UCB or Maximum variance acquisition function. \n  The paper provides theoretical bounds on the regret for this invariance aware approach -- in the special case where the domain is a sphere.    The authors demonstrate the sample efficiency of the method empirically, on some synthetic experiments, and then a nice tokamak optimisation example.", "questions": "1. Could the authors help distinguish their work from other approaches in this field.   I strongly urge the authors to engage a bit more with other proposed methodology (some of which might not be very rigorous).  Understandably this is a fairly common issue, and many resolutions exist -- certainly not all as nice as this paper.\n\n2. In particular, it would be good if the authors could identify strong advantages of this method over others, and maybe even provide other methods as a useful benchmark.\n\n3. One possible advantage of this approach over others is situations where the invariance is not strongly constrained, e.g. quasi-invariances.  Could the authors demonstrate that this method still yields better sample complexity when the objective is nearly invariant?\n\nI am v happy to adjust my score of the authors can provide a stronger case for the novelty and/or value-add of this work over other approaches.", "limitations": "The limitations addressed are around the complexity of computing the invariant kernel -- this has been addressed and some guidelines for mitigating this are discussed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The specific approach of using a G-invariant kernel in the context of Bayesian optimisation seems new to me.  \n\nThe biggest contribution of the paper is the very nice sample complexity bounds,  both lower and upper -- albeit in a simplified setting, but really demonstrate the mechanisms from which the efficiency gain arises in this setting.  \n\n The tokamak numerical experiment is quite interesting and a challenging example.", "weaknesses": "Dealing with invariances in optimisation (Bayesian / black-box / otherwise) is certainly not a new problem, and there are typically well-established methods to deal with this, through symmetry breaking constraints etc.   This is particularly common in the context of computational chemistry and materials design properties where molecules have a wide range of symmetries.   One noteworthy example is Bayesian Optimization With Symmetry Relaxation Algorithm from [Zuo, Yunxing, et al. \"Accelerating materials discovery with Bayesian optimization and graph deep learning.\" Materials Today 51 (2021): 126-135].     So while the approach is novel, it is far from unique, and I feel that the authors have not really engaged with existing methods at all.   The literature review seems to go from \"Invariances in DL\" -> \"Invariant Kernels\" -> \"Kernels on Manifolds\" (again missing a lot of important works there too) -> \"regret bounds for BO\". \n\nThe sample complexity bounds are certainly novel, but for example the upper bound largely seems to follow Joan Bruna's existing work on this which tackles a very similar problem.    \n\nSo to summarise:\n(+) I think this is nice work.\n(+) I think its a novel approach.\n(+) The theory is nice.\n(-) However, it feels like a quite incremental contribution, which makes no attempt to engage with alternative approaches to the same problem.\n(-) The theory, while nice, again seems a moderate modification of existing work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their engagement with our paper and recognition of its \"novel approach\" to a popular problem.\n\n## Response to weaknesses\n### Critique of literature review\nWe cannot hope to provide an exhaustive survey of the literature in this setting.\nWe acknowledge, however, that the reviewer is right in requesting a broader coverage of the field in the literature review. **We will include the following paragraph to engage with the literature on empirical methods.**\n\n> **Physics informed BO.** There is an extensive body of literature where symmetries come from physical information present in the system states, which is well known to the experiment designer. Our own example (Figure 4) benefits from such a description.\nIn **[1]** authors apply BO after a variety of physics-informed feature transformations to the state, and engineer product kernels with factors acting on these individual representations.\nIn **[2]** the authors employ BO to handle optimization over crystal configurations with symmetries found using **[3]**.\nThe objective is a surrogate for the physical target of system energy, computed via a GNN architecture.\nBoth the symmetries and the invariance of the objective lack theoretical guarantees, but empirical results show that constraining the symmetry by separating the dependent and independent parameters provides significant gains in terms of regret versus non-constrained ablations.\nAsymptotic rates on sample complexity are not estimated. \nIn **[4]** a set-invariant kernel is constructed in the same way as ours (see Eq 38, and references [16, 29] from the original manuscript) to optimize functions over sets, incorporating the permutation invariance of the set elements.\n>\n> **References:**\n>\n> [1] A physics informed Bayesian optimization approach for material design: application to NiTi shape memory alloys;\nKhatamsaz et al. (2023)\n>\n> [2] Accelerating Materials Discovery with Bayesian Optimization and Graph Deep Learning; Zuoa et al. (2021)\n>\n> [3] Spglib: a software library for crystal symmetry search; Togo et al. (2018)\n>\n> [4] Bayesian optimization with approximate set kernels; Kim et al. (2021)\n\n### Critique of methods\nWe are grateful to the reviewer for the praise of our exposition and novelty of our approach. We respond below to their criticism.\n\n> \"...for example the upper bound largely seems to follow Joan Bruna's existing work on this which tackles a very similar problem.\"\n\nThe upper bound is dependent on results involving the ratio of the dimensions of invariant RKHS eigenspaces vs. their non-invariant counterparts. We quote Bruna et al. (reference [3] in our manuscript), for these results; however, it is important to note that their paper is concerned with Kernel Ridge Regression (KRR) alone, which has fundamental differences in both theory and algorithms compared to BO.\nBeyond quoting the above result, our proofs proceed largely independently. A careful computation of how these ratios factor into the bound for maximal information gain is performed. Then we turn the bounds on information gain into a bound on sample complexity.\nThe analysis in this case, and for these particular bounds, is, to the best of our knowledge, novel, and so is the derived result.\nFinally, a significant portion of our paper is devoted to finding a lower bound for this setting (analysis which is not present in Bruna et al.), which we feel deserves more acknowledgment.\n\n> \"...which makes no attempt to engage with alternative approaches\"\n\nAs above, we feel this remark is somewhat uncharitable, as the main contribution of the paper is fundamentally a theoretical novelty, not an empirical one. However, we acknowledge that a stronger comparison with existing methods is valuable for members of the research community. *As such we will include additional baselines in our empirical results section, comparing with data augmentation and constrained BO (see the attached PDF and responses to other reviewers).*\n\n> \"The theory, while nice, again seems a moderate modification of existing work...\"\n\nIn our paper, we have taken care to acknowledge papers that follow a similar method or contributed to our thought process.\nTherefore, while we would agree that some of the steps in the proofs may be familiar to a well-versed practitioner, we would like to argue the analysis for the incorporation of *symmetries* in particular is novel and showcases the phenomenon under study (that of sample complexity decrease due to symmetry) well. \n\n## Answers to questions\n> \"Could the authors help distinguish their work from other approaches [...] -- certainly not all as nice as this paper.\"\n\nPlease see the additional discussion of the literature and the PDF. We primarily **provide comparisons of our method with data augmentation and constrained BO.**\n\n> \"[...] quasi-invariances. Could the authors demonstrate that this method still yields better sample complexity [...]?\"\n\nThis is indeed a very pertinent question and one that we do not neglect in our paper, as we present the relative gains in sample complexity by progressively incorporating more knowledge of the underlying symmetry group in Figure 3.\n**In the attached PDF, we demonstrate an example of a quasi-invariant function**, and demonstrate that MVR achieves good performance even as the function becomes less strongly invariant. **We will incorporate this in a new subsection of our experimental results.**\n\n## Summary \nWe have addressed all the questions raised by the reviewer.\nWe believe that our theoretical results, combined with our practical experiments, provide strong evidence of the utility of our approach.\nWe kindly request that the reviewer reconsider their decision in light of our responses and their comments that this is \"nice work\" and \"a novel approach\".\nWe are also eager to address any additional concerns the reviewer may have.", "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": "W9SHsoGxgQ", "reviewer": "Reviewer_pMXJ", "summary": "The authors proposed a new setting where the invariance is either known or partially known. They theoretically examined the upper and lower bounds of convergence rates concerning sample complexity. Their findings demonstrated both theoretical and empirical superior performance over the standard UCB approach in cases with known invariance. Additionally, they explored more practical settings with partially known invariance using synthetic tasks and a real-world example from tokamak optimization.", "questions": "The questions are detailed in the weakness section above.", "limitations": "Limitations are well discussed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The theoretical section is well-written, but the experimental part is difficult to follow.\n- The convergence rate is provably better than vanilla UCB and has shown empirical success in both synthetic tasks and one real-world example.", "weaknesses": "**Limited Applicability:**\nI am not convinced that this new setting is widely applicable to real-world scenarios. Aside from the specific tokamak application, it is challenging to identify other examples where this setting would be useful. While regression tasks in previous work have broad applicability, is the same true for optimization? Can you provide more intuitive examples of invariance-aware BO? For instance, in classification tasks, such as translation invariance in cat images in the introduction section, the concept is clear. However, does this example apply to BO? Beyond the tokamak example, the authors mention material science, but it is difficult to envision practical situations in this domain where the search space has known invariance. For example, while crystal lattice invariance is known, is this relevant to the search space? This is merely one feature characterizing materials, and it is hard to imagine a scenario where we aim to maximize something within this symmetric lattice space. While band gap optimization can be the one (finding minimum and maximum of electronic energy), it is computationally simple and not computationally demanding.\n\n**Feasibility of Listing Possible Invariances:**\nIt is hard to imagine users being able to list possible invariances. This raises concerns about the motivation behind the work.\n\n**Lack of Simpler Baselines:**\nThe work lacks comparisons with simpler baselines, such as periodic kernels or constrained BO. For example, in Figure 2, if the search space is known to be symmetric for 10 cycles, why not constrain the search space to 1/10 as in typical constrained BO approaches? Finding all peaks in Figure 2 seems wasteful since we know they are repetitive. The same applies to permutation invariance; why not algorithmically reject repetitive candidates?\n\n**Clarity in Experimental Section:**\nThe experimental section is difficult to follow. The tasks in Figure 3 are unclear, making it hard for readers to reproduce the results.\n\n**Minor Points**\n- Numerous typos (e.g., lines 102-103, 116-117, repeating the RKHS acronym definition).\n- Limited baseline comparisons (e.g., permutation kernel, periodic kernel, and constrained BO).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments, and for their close reading that brought to our attention minor typographical errors.\n\n## Response to weaknesses\n### Limited applicability\nWe respectfully disagree with the reviewer's comment on the limited applicability of our work.\nSome examples: \n- Molecular optimization, where the invariance is in the permutation of the molecule as a list of atoms / functional groups **[1]**.\n- Cache memory placement in computer architectures. In a fully associative two-level cache with LRU eviction, the permutation of function symbols in tightly coupled memory (TCM) is invariant and does not impact hard real-time (HRT) performance. This invariance is well-known to system designers **[2]**.\n- Compiler optimization operates on intermediate representations (IR) of code and performs passes to create the most efficient IR for back-end translation. Some of these passes operate on the IR through permutation of basic blocks only, rearranging the state in the hope that further passes will benefit **[3]**.\n- Placement and floorplanning is a 2D graph embedding problem where a graph of components must be embedded in 2D under a series of geometric constraints with geometric symmetries in the arrangement (i.e. 4-fold rotations and 2 fold reflections) **[4]**.\n\n### Feasibility of listing invariances\nWe don’t believe this is a flaw in our approach, as seen in the examples above. Moreover, in Figure 3 (last column), we demonstrate that having partial knowledge of the invariances in the system can still lead to significant gains.\n\n### Clarity in the experimental section\nWe would appreciate it if the reviewer could specify which paragraph is unclear so that we can improve the exposition. By default **we will modify the opening paragraph to read**:\n\n> For each of our synthetic experiments, our objective function is drawn from an RKHS with a group-invariant isotropic Matern-5/2 kernel. To generate the function, we first sample $n$ points from a GP prior with the target kernel. Then, we fit a GP to those samples and use the posterior mean function of the fitted GP as the objective function. The groups we consider act by permutation of the coordinate axes, and therefore include reflections and discrete rotations. For *PermInv-2D* and *PermInv-6D*, the kernel of the GP is invariant to the full permutation group which acts on $R^2$ and $R^6$ respectively by permuting the coordinates. For *CyclInv-3D* it is invariant to the cyclic group acting on $R^3$ by permuting the axes cyclically. The observations of the objective values are corrupted with Gaussian noise of known variance. In our examples, we provide the learner with the true kernel and noise variance to eliminate the effect of online hyperparameter learning. The values of the GP hyperparameters are provided in the appendix. The objective functions *PermInv-2D* and *CyclInv-3D* are visualised in Figures 1a and 1b respectively.\n\n### Lack of simpler baselines\nWe appreciate that the reviewer has considered the setting carefully, and agree that baselines like constrained BO (CBO) make sense to investigate.\nWe also hope that as the reviewer has included this section in \"minor points\", it will be sufficient to improve this section of the manuscript by **adding a comparison section which we summarise below (see the PDF for appropriate figures)**.\n\n- CBO vs. ours\n    - While constraining the domain to the fundamental region of the action is a valid choice of experimental design, characterizing the region analytically can be difficult when the dimension of the domain is high and the group is complicated. Moreover, optimizing an acquisition function using global optimizers in such complex input spaces is non-trivial.\nConstraining by rejection sampling may lead to inefficient use of computational resources and in practice could significantly slow down acquisition function optimisation. In contrast, our approach is both efficient and elegant in handling these challenges. \n    - In terms of sample complexity, CBO is expected to achieve only a $\\frac{1}{|G|}$ reduction. The intuition is that in CBO the kernel is not aware of all of the added structure that the RKHS elements possess, i.e. while we have restricted the _domain of exploration_, we have not restricted the _function class_. We will add a theoretical justification in the appendix.\n\n- Other methods\n    - For periodic kernels, our knowledge is that they are used to model data repeating at regular intervals, such as time-series data or spatial patterns with cyclic behavior.\nThe former are out of scope for this paper, as we deal with finite groups of transformations (discrete groups on compact domains), which are not applicable to time-series.\nThe latter represent a subset of our problem, in which case a \"periodic\" kernel is the \"invariant\" kernel with respect to the cyclic group. \n\n## Summary\nWe would like to thank the reviewer again for engaging with our work. \nWe hope, however, that the reviewer would consider re-evaluating the paper for its intended purpose, i.e. mainly making a theoretical contribution rather than an empirical one. \nWe have addressed all the questions raised in the review, with a particular focus towards the empirical comparisons, explanations and improvements proposed by the reviewer.\nBased on our changes, we hope that the reviewer would consider that the empirical part of the paper has improved as well.\n\nWe kindly request that the reviewer reconsider the decision in light of our responses and update their score accordingly. \nWe are also eager to address any additional concerns.\n\n**References:**\n\n[1] Learning Invariant Representations of Molecules for Atomization Energy Prediction; Montavon et al. (2012)\n\n[2] Optimal Data Placement for Heterogeneous Cache, Memory, and Storage Systems; Zhang et al. (2020)\n\n[3] Engineering a Compiler; Cooper et al. (2011)\n\n[4] Algorithms for VLSI Design Automation; Gerez (1999)", "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": "Rol4ke3WCM", "reviewer": "Reviewer_eKC1", "summary": "This paper provides sample complexity bounds for Bayesian optimization under settings with invariant kernels. Invariant kernels are able to model functions which are invariant under transformation families. Such models allow us to carry out Bayesian optimization efficiently due to having to being able to obtain far much information with a single query than if we used standard kernels (as we obtain information over the whole group of invariances with a single observations, while standard BayesOpt will carry out redundant sampling). The theoretical effect of invariances is investigated in this paper.\n\nA simultaneously invariant kernel satisfies the property that $k(\\sigma(x), \\sigma(y)) = k(x, y) \\forall \\sigma \\in G$. Where $G$ is the group of invariance. The paper focuses on finite subgroups of isometries, which maintain distances and dot products and therefore any stationary kernel will be simultaneously invariant for any group in question. The paper shows in Proposition 1 how a simultaneously invariant kernel can be used to build an RKHS with the invariances translated to the function space as well. We can then use this space of functions with their corresponding kernel to model the black-box functions for Bayesian Optimization. \n\nThe analysis is carried out for two standard BayesOpt algorithms: (a) maximum variance reduction, which selects as the next query the point with maximal variance, and (b) the standard upper confidence bound acquisition function. The first main result is shown in Theorem 1, where the authors obtain an upper bound on the maximal information gain of any bandit algorithm, and of particular importance is a factor of $O(1 / |G|)$. They then show this translates to a $O(1 / |G|)^{(2v + d - 1) / 2v}$ dependency on the sample complexity of the maximum variance reduction algorithm under a Matern kernel. A lower bound is then shown, with complexity $O(1 / |G|)^{(2v + d - 1) / v}$. This shows the upper bound is relatively tight, and that algorithms are likely to fail when run for anything lower than the sample complexity.\n\nTwo main experiments are ran:\n\n1. The first experiment looks at the optimization of Matern function samples under different invariance groups. This results in significant speed-ups for optimization in all three benchmarks. In the PermInv6D benchmark, further analysis is carried out where only certain subgroups of the invariances are included in the known invariance group; these result in the expected outcome and the regret improves as more invariances are added.\n\n2. A real-world example is then introduced, where a simulated nuclear reactor configuration is optimized. A subgroup of the invariances is used for computational efficiency, and the results show a very significant improvement from using invariant kernels.", "questions": "- How do you do the batching of the acquisition function in the nuclear fusion experiment? \n\n- Is there anything that can be said about the sample complexity of the UCB acquisition function? From L195 I am under the impression that the upper bound only holds for MVR.\n\n- Is there more intuition into why the bounds for maximal information gain are independent of the bandit strategy chosen?", "limitations": "Limitations are addressed in Section 5.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- (Originality and Significance) I am not too familiar with the literature around regret bounds in BayesOpt, however, the regret bounds provided in the paper appear to be novel and of significance to the Bayesian optimization community. They can help understand the trade-offs when choosing invariances for kernels. In addition, the empirical study highlights some important properties of using invariances in kernels which are of practical importance in potentially many applications, as highlighted by the nuclear fusion example. \n\n- (Quality) The ideas in the paper seem sound, and follow natural intuition. The method is described and investigated in depth through the theoretical contributions.\n\n- (Clarity) The paper is very well written, and the ideas are expressed clearly. I found it easy to follow, even though I am not well acquainted with the literature around regret bounds.", "weaknesses": "- The modeling comes from previous literature, and the bandit strategies followed are standard. The paper's contributions are strictly the theoretical additions, and the convincing, yet somewhat short, empirical study.\n\n- From my understanding, sample complexity upper bounds are only given for the maximum variance reduction algorithm, which could be argued is less important for many optimization applications than UCB.\n\n- Perhaps more applications of the algorithm could be showcased or discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the close attention paid to our methods and results and for the relevant comments. Below we provide answers to the questions and the remark on the weaknesses identified.\n\n### Response to weaknesses and questions \n> \"The modeling comes from previous literature, and the bandit strategies followed are standard. The paper's contributions are strictly the theoretical additions, and the convincing, yet somewhat short, empirical study. [...] Perhaps more applications of the algorithm could be showcased or discussed.\"\n\nWe would like to suggest that the fact that we rely on previous literature for the core definitions and prerequisite results is not a weakness in of itself. We take great care not to overclaim our contributions, but believe they make sufficient advancement into the field of BO and learning with symmetries, that they present a benchmark of interest to the community. With respect to the empirical study, while we cannot extend our fusion study with further settings at this time, we have chosen to **extend the range of examples and provide other synthetic baselines**, as requested by other reviewers as well. **Please see the attached PDF.**\n\n> \"From my understanding, sample complexity upper bounds are only given for the maximum variance reduction algorithm, which could be argued is less important for many optimization applications than UCB. [...] Is there anything that can be said about the sample complexity of the UCB acquisition function? From L195 I am under the impression that the upper bound only holds for MVR.\"\n\nThe sample complexity of UCB is a topic of active research in the frequentist setting (where the target function lives in the RKHS) of BO. Only recently have state-of-the-art (SOTA) upper bounds on regret have been established, e.g. $O (T^\\frac{\\nu+2d}{2\\nu +2d})$ ([1]) which are not order optimal. The motivation for selecting MVR is that, in this setting at least one can show order-optimal upper bounds which align to the *a priori* (algorithm independent) ones of Scarlett et. al. (reference 31 in our text). We agree that a thorough analysis of UCB making use of the SOTA methodology would be of interest. \n\n> \"Is there more intuition into why the bounds for maximal information gain are independent of the bandit strategy chosen?\"\n\nThis is an artefact of the definition of maximal information gain, and holds for all acquisition functions, independent of symmetry. In particular, UCB, MVR, TS, MEI (maximal expected improvement), all benefit from the same definition of $\\gamma_T$ (see e.g. reference 33 in our text).  The information gain depends on the choice of samples (not the sampling strategy, but merely its output at time $T$), whereas the _maximal_ information gain is a supremum over all sets of samples and is this a function of the kernel and $T$ alone.\n\n> \"How do you do the batching of the acquisition function in the nuclear fusion experiment?\"\n\nWe use the default quasi-Monte Carlo method from BoTorch for batching (see **[2]** and the BoTorch documentation for details).\nAs this is a very standard tool and technique, we did not deem it necessary to comment further. **We will, however, update the relevant sentence to read:**\n> ... we use a quasi Monte Carlo batched version of UCB from BoTorch [X],...\n\n### Summary \n\nWe feel we have addressed the reviewer's main concerns, and would be eager to engage in further discussion. If any of our answers served to clarify and remove the reviewer's doubts, we would be grateful to receive an even firmer acknowledgement of our paper from the reviewer.\n\n\n**References:**\n\n[1] On the Sublinear Regret of GP-UCB, Justin Whitehouse et. al.\n\n[2] BoTorch: A Framework for Efficient Monte-Carlo Bayesian Optimization; Balandat et al. (2020)", "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:
# Global rebuttal

The authors thank the reviewers collectively for engaging with the work, and providing both positive feedback and actionable critique of our manuscript. 
We believe we have provided satisfactory answers, and produced a further body of evidence that strengthens the cause for our paper. 
The following is a (reductive) summary of the 4 reviewer's concerns, and the work we have done to address them (highlighted in **bold**).

## Outline of main reviewer concerns
- Comments were made about the breadth and scope of our empirical results. 
- Comments were made about the literature review, requesting us to engage with a broader body of literature (especially applied works that may have employed similar methods).
- A request for clarification was made about our experimental section.

## Outline of our actions
- In the attached PDF, we have added **details of several additional experiments**:
  - Figure 1 details a **new example of quasi-invariant optimisation**.
  - Figure 2 adds **comparisons with constrained BO** to our regret plots.
  - Figure 3 adds **comparisons with data augmentation** to our performance plots.
- We have **extended the scope** of our literature review.

### Quasi-invariance
Reviewer 5kTB requested an exploration of quasi-invariance. The notion of 'almost'-invariance has been mentioned in previous literature, but has not been considered in BO. However, one of the strengths of the invariant kernel method is the ease of applicability to the quasi-invariant setting, by considering a kernel that is comprised of a sum of invariant and non-invariant components.

In response to the reviewer's comment, we have **included plots showing the performance of our algorithm in this setting**, comparing the performance of a non-invariant kernel, an invariant kernel, and the aforementioned sum kernel. The plots show that as long as the objective does not deviate too much from being invariant, the invariant kernel significantly surpasses the non-invariant kernel and is comparable in performance to the sum kernel.

### Constrained BO and data augmentation
Reviewer pMXJ requested more baseline comparisons. In response, we have **added plots to compare our method against constrained BO and data augmentation**. In doing so, we have also responded to reviewer eKC1's request to extend the scope of our empirical study.

We show that using data augmentation leads to exploding memory requirements while our method remains effective and lightweight. 

We use the built-in functionality of BoTorch to implement a constrained BO benchmark on our test problems, ensuring that the acquisition function optimisation step remains as similar as possible to the unconstrained case. We are happy to discuss more details of our implementation if the reviewer is interested. We would like to highlight two key takeaways from this new benchmark:
1. As this method requires hand-writing an analytic description of the the fundamental domain's boundary, setting up the constrained BO problem becomes very difficult for groups with a more complicated action. Although we were able to implement it for the full permutation group, this is a specific example where the fundamental region can be computed with ease; it is not as straightforward to implement even for subgroups of the permutation group (e.g. the cyclic group from our experimental section).
2. Our invariant kernel method significantly outperforms constrained BO. In the reply to reviewer pMXJ and the caption of Figure 2 in the PDF, we have provided intuition as to why it is expected that constrained BO achieves worse sample complexity than our method. **We will add a detailed proof of this fact in the appendix.**

### Literature review and scope
To address reviewer 5kTB's concerns about engaging with previous literature, we will **add the given paragraph and references to the literature review** (see reply to 5kTB) concerning existing methods for incorporating structure into BO. We gratefully acknowledge the reviewer's contribution in encouraging us to include this section, as we believe it strengthens our paper. Nonetheless, we would like to remind the reviewers that many of these methods are purely empirical, whereas our work is primarily concerned with providing an algorithm with performance guarantees that are grounded in theory.

We will also **add references to high-dimensional BO**, following comments from reviewer 8csK. 

We hope that our additional benchmarks and new quasi-invariance experiment, alongside the additional examples we list in our reply, will address reviewer pMXJ's question about the limited applicability of our methods.

### Experimental section
To add clarity to the experimental section, we've included a paragraph with further details and explanations at reviewer pMXJ's request.

We will also include the hyperparameters of the GPs used in a table in the appendix.

Meta-review: The reviewers discuss the incorporation of invariance under a group action into a standard UCB-based BO loop, and show that this leads to improvements both empirically and theoretically.  Coming out from the discussion period the reviewers were unanimously positive about the paper.  This seems like a clear case for acceptance.
Decision: Accept (poster)