# How does removal of symmetry (e.g. via constraints) in a Bayesian optimization search space affect search efficiency?

There are many examples of search space symmetry in real-world optimization problems in the physical sciences. To motivate this, here are some that come to mind:

1. When optimizing a formulation such as a chemical formula or a mixture of chemicals for a target application, the target property doesn't change if you switch the order in which the elements appear (i.e., $$SiO_2$$ is equivalent to $$O_2Si$$, 80% $$H_2O$$+20% $$HCl$$ is the same as 20% $$HCl$$+80% $$H_2O$$)$$^1$$.
2. When optimizing a formulation, there is often a compositional (linear equality) constraint $$^2$$ such that the fractional contributions sum to $$1$$ (e.g. $$x_1+x_2+x_3=1$$). A degenerate dimension can be removed (retaining only the $$n-1$$ degrees of freedom) by representing it as a linear inequality constraint (e.g. $$x_1+x_2\le1$$ where $$x_3=1-x_1-x_2$$).
3. Similarly, there are "unitless" physics-based simulations where scaling certain inputs related to size (e.g. multiplying everything by 10) results in the same output. e.g. $$[x_1, x_2, x_3]$$ can be reparameterized to $$[r_1=\frac{x_1}{x_3}, r_2=\frac{x_2}{x_3}]$$ where $$x_3$$ is some constant (e.g. $$1$$).

1. Except perhaps in the case where you're trying to model "steps" (e.g. first add 80% $$H_2O$$ then add 20% $$HCl$$)
2. There are also cases where magnitude affects the objective rather than being solely dependent on fractional contribution.

In the first case, an ordering constraint can be applied (i.e., impose constraints that elements have to appear in a certain order). When dataset scaling isn't an issue, a better solution might be to perform data augmentation where you give it all symmetric representations. In the second case, you can reparameterize a linear equality constraint as a linear inequality constraint. In the third case, you can reparameterize by setting one variable as a constant and dividing the other variables by the constant.

Intuitively and in general, I would expect each of these to have a non-negligible benefit to the search space efficiency. In the last two cases, there is less "hay" relative to the "number of needles" (EDIT: which become "beads" in the lower dimension). For the first case using data augmentation, when you search in one spot, you get to search in a few other specific places at "no-cost" for a fixed amount of hay.

I tried to pose the title question in a way that targets the intended audience within the character limit. If I were to ask it again:

What examples (analytical, physical, computational, etc.) are you aware of that either corroborate or contradict the assumption that addressing search space symmetry will have a non-negligible benefit to Bayesian optimization search efficiency?

### Related

UPDATE: I am actively working on a manuscript related to this, and it's still really important for me to know what prior work has been done. Planning to update this with an arXiv link to the manuscript when available.

• Notice that while symmetries increase the search space they also increase the solution space (or number of solutions) by exactly the same amount, so the intuition about "less hay relative to needles" is not necessarily correct. Neural networks for example have huge combinatorial symmetries, but therefore also huge number of equivalent global minima (see e.g.). In the context of Bayesian optimization, the critical question seems to be whether or not one can account for the symmetries by using an appropriate prior. Commented Apr 22, 2022 at 19:45
• @J.Delaney definitely agreed about "less hay relative to needles" being incorrect for symmetry - as I mentioned the first constraint is a fixed amount of hay. For the other constraints, the "needle" becomes a "bead" in the lower dimension (updated), which as you mention means increasing the solution space. While technically there are more solutions when a point becomes a line, from a Brownian motion perspective one is likely to take a far greater number of steps in happening upon a line in a cube than happening upon (the reduced representation of) a point in a square. Commented Apr 23, 2022 at 2:38
• I think you bring up a good point about manipulating the prior. One example related to this for which I am a co-author is Section 2.6 Designing the covariance (kernel) function from DOI: 10.1016/j.actamat.2021.116967. While a useful technique, it's probably not one I can implement easily given my preferences - which is to use the Ax platform. Maybe I need to give that one some more thought. Thanks also very much for the REF on neural network combinatorial symmetry. Commented Apr 23, 2022 at 2:50
• I have a hard time seeing why there should be any correct answer to this question. Generally, searching within a space for a problem with a symmetry group ought to be mathematically equivalent to searching within the quotient (modulo the group of symmetries); but there can be complications (or simplifications) in the implementation of algorithms related to the creation of boundaries in the quotient, depending on the search algorithm.
– whuber
Commented Apr 23, 2022 at 14:32
• @whuber In terms of answers, I'm interested in examples of implementations that include a "before and after" so to speak in the mathematical representation / imposition of constraints. I mentioned that the title question was meant to target the audience within the character limit and be more searchable. I put a longer/contextualized/rephrased question at the end asking explicitly for examples, but I realize that may not sit well. Happy to hear suggestions for an alternative title. Note also the "references" tag. Let me know if I misunderstood something from what you described. Commented Apr 23, 2022 at 21:44