Sample-efficient Bayesian Optimisation Using Known Invariances

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. A 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. The 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. Two main experiments are ran: 1. 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. 2. 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.

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. - (Quality) The ideas in the paper seem sound, and follow natural intuition. The method is described and investigated in depth through the theoretical contributions. - (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. - 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. - Perhaps more applications of the algorithm could be showcased or discussed.

Questions

- How do you do the batching of the acquisition function in the nuclear fusion experiment? - 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. - Is there more intuition into why the bounds for maximal information gain are independent of the bandit strategy chosen?

Rating

6

Confidence

2

Soundness

3

Presentation

3

Contribution

2

Limitations

Limitations are addressed in Section 5.

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.

Strengths

- The theoretical section is well-written, but the experimental part is difficult to follow. - 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:** I 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. **Feasibility of Listing Possible Invariances:** It is hard to imagine users being able to list possible invariances. This raises concerns about the motivation behind the work. **Lack of Simpler Baselines:** The 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? **Clarity in Experimental Section:** The experimental section is difficult to follow. The tasks in Figure 3 are unclear, making it hard for readers to reproduce the results. **Minor Points** - Numerous typos (e.g., lines 102-103, 116-117, repeating the RKHS acronym definition). - Limited baseline comparisons (e.g., permutation kernel, periodic kernel, and constrained BO).

Questions

The questions are detailed in the weakness section above.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Limitations are well discussed.

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

Strengths

The specific approach of using a G-invariant kernel in the context of Bayesian optimisation seems new to me. The 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. 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". The 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. So to summarise: (+) I think this is nice work. (+) I think its a novel approach. (+) The theory is nice. (-) However, it feels like a quite incremental contribution, which makes no attempt to engage with alternative approaches to the same problem. (-) The theory, while nice, again seems a moderate modification of existing work.

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. 2. 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. 3. 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? I 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.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

2

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.

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.

Strengths

• The target problems (invariant functions) are important yet has not been focused on much. • The ideas of invariant kernels are interesting and worth investigating. • The theoretical analysis is thorough by providing both upper and lower bound for sample complexity. • The empirical performance is good in all cases.

Weaknesses

• In Figure 3, the plots should be consistent, i.e., either use cumulative regret or simple regret. • The experiments are only conducted on low-dim problems.

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?

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

I agree with the author’s limitations regarding the computational expense of fully invariant kernel on large group of transformation. No negative societal impact needs to be addressed.

Request for response

We thank all the reviewers again for their time taken to review our work. **As the author-reviewer discussion period is nearing its end, we would appreciate it if the reviewers would respond to our rebuttals.** If there any further questions, we are more than happy to clarify and discuss further.

Response

I thank the authors for their rebuttal and for their suggested updates. I feel that I understand a bit better the authors contributions on the theoretical aspects of this work, which are the main contribution of this paper, in particular how they distinguish with other works in this area. I think this is broadly a well written paper, but I do agree with the other reviewers that perhaps some other applications should have been showcased to demonstrate the feasibility of identifying (partial or otherwise) invariance. I will update my score.

Rebuttal summary and acknowledgements

To all reviewers and area chairs, As the rebuttal period it nearing its end, we would like to thank all the reviewers again for taking the time to read our manuscript, to provide constructive criticism and raise many important points that have helped improve both our understanding and the write-up. We would like to doubly thank reviewers for engaging in the rebuttal discussion and for providing _unanimous approval for our paper_. We will improve the manuscript according to the discussion below to ensure that it passes the high quality standards expected from a NeurIPS publication.