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.

Response to weaknesses and questions

"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."

We 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.

"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."

The 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.

"Is there more intuition into why the bounds for maximal information gain are independent of the bandit strategy chosen?"

This 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.

"How do you do the batching of the acquisition function in the nuclear fusion experiment?"

We use the default quasi-Monte Carlo method from BoTorch for batching (see [2] and the BoTorch documentation for details). As 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:

... we use a quasi Monte Carlo batched version of UCB from BoTorch [X],...

Summary

We 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.

References:

[1] On the Sublinear Regret of GP-UCB, Justin Whitehouse et. al.

[2] BoTorch: A Framework for Efficient Monte-Carlo Bayesian Optimization; Balandat et al. (2020)

We thank the reviewer for their comments, and for their close reading that brought to our attention minor typographical errors.

Response to weaknesses

Limited applicability

We respectfully disagree with the reviewer's comment on the limited applicability of our work. Some examples:

• Molecular optimization, where the invariance is in the permutation of the molecule as a list of atoms / functional groups [1].
• 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].
• 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].
• 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].

Feasibility of listing invariances

We 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.

Clarity in the experimental section

We 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:

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.

Lack of simpler baselines

We appreciate that the reviewer has considered the setting carefully, and agree that baselines like constrained BO (CBO) make sense to investigate. We 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).

• CBO vs. ours

  • 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. Constraining 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.
  • 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.

• Other methods

  • 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. The 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. The latter represent a subset of our problem, in which case a "periodic" kernel is the "invariant" kernel with respect to the cyclic group.

Summary

We would like to thank the reviewer again for engaging with our work. We 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. We have addressed all the questions raised in the review, with a particular focus towards the empirical comparisons, explanations and improvements proposed by the reviewer. Based on our changes, we hope that the reviewer would consider that the empirical part of the paper has improved as well.

We kindly request that the reviewer reconsider the decision in light of our responses and update their score accordingly. We are also eager to address any additional concerns.

References:

[1] Learning Invariant Representations of Molecules for Atomization Energy Prediction; Montavon et al. (2012)

[2] Optimal Data Placement for Heterogeneous Cache, Memory, and Storage Systems; Zhang et al. (2020)

[3] Engineering a Compiler; Cooper et al. (2011)

[4] Algorithms for VLSI Design Automation; Gerez (1999)

We thank the reviewer for their engagement with our paper and recognition of its "novel approach" to a popular problem.

Response to weaknesses

Critique of literature review

We cannot hope to provide an exhaustive survey of the literature in this setting. We 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.

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. In [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. In [2] the authors employ BO to handle optimization over crystal configurations with symmetries found using [3]. The objective is a surrogate for the physical target of system energy, computed via a GNN architecture. Both 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. Asymptotic rates on sample complexity are not estimated. In [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.

References:

[1] A physics informed Bayesian optimization approach for material design: application to NiTi shape memory alloys; Khatamsaz et al. (2023)

[2] Accelerating Materials Discovery with Bayesian Optimization and Graph Deep Learning; Zuoa et al. (2021)

[3] Spglib: a software library for crystal symmetry search; Togo et al. (2018)

[4] Bayesian optimization with approximate set kernels; Kim et al. (2021)

Critique of methods

We are grateful to the reviewer for the praise of our exposition and novelty of our approach. We respond below to their criticism.

"...for example the upper bound largely seems to follow Joan Bruna's existing work on this which tackles a very similar problem."

The 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. Beyond 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. The analysis in this case, and for these particular bounds, is, to the best of our knowledge, novel, and so is the derived result. Finally, 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.

"...which makes no attempt to engage with alternative approaches"

As 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).

"The theory, while nice, again seems a moderate modification of existing work..."

In our paper, we have taken care to acknowledge papers that follow a similar method or contributed to our thought process. Therefore, 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.

Answers to questions

"Could the authors help distinguish their work from other approaches [...] -- certainly not all as nice as this paper."

Please see the additional discussion of the literature and the PDF. We primarily provide comparisons of our method with data augmentation and constrained BO.

"[...] quasi-invariances. Could the authors demonstrate that this method still yields better sample complexity [...]?"

This 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. 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.

Summary

We have addressed all the questions raised by the reviewer. We believe that our theoretical results, combined with our practical experiments, provide strong evidence of the utility of our approach. We 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". We are also eager to address any additional concerns the reviewer may have.

We thank the reviewer for their appreciation of our work, and their positive comments regarding its importance, thoroughness and empirical performance.

Response to weaknesses and questions

Concerning the plots in Figure 3: Currently, we plot the cumulative regret for UCB and the simple regret for MVR, which we suggest is standard practice for these algorithms. In 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]. We chose to follow this convention for our bounds and experiments. This makes it easy to identify the performance improvement that can be achieved by incorporating invariance compared to existing regret bounds. Finally, we would highlight that it is fairly trivial to convert the simple regret to cumulative regret, if that is interesting for the reader.

Concerning the performance in high dimensions: We 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. In 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. Our 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.

On 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].

We 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.

References:

[1] Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design; Srinivas et al. (2009)

[2] On Information Gain and Regret Bounds in Gaussian Process Bandits; Vakili et al. (2021)

[3] Optimal order simple regret for Gaussian process bandits; Vakili et al. (2021)

[4] High-Dimensional Bayesian Optimisation and Bandits via Additive Models; Kandasamy et al. (2016)

[5] High-Dimensional Bayesian Optimization via Additive Models with Overlapping Groups; Rolland et al. (2018)