Symmetries as an inductive bias
When a function has symmetries, every observation yields information about multiple locations in the search space. How to tell a Bayesian optimizer about it?
Some functions are invariant according to some symmetries. The energy of a molecule does not change when you rotate it, and a mixture of three powders is the same whatever order you list them in. When a function is unchanged by a group of transformations, a single evaluation tells you its value at several places at once. When evaluations are expensive, that is a powerful way to increase sample efficiency.
Take a wireless network. Below, two identical antennas serve sixteen people working along a corridor, and the goal is to place them so as to maximize the total throughput. A design of the wireless network is a pair of numbers, \(x = (x_1, x_2)\): the position of antenna 1 and the position of antenna 2. But the ordering of the antennas is arbitrary. Change it and you get another design, \((x_2, x_1)\), which describes the very same network.
Every network appears twice in the search space, once on each side of the diagonal, and the landscape is a mirror image of itself. That is worth exploiting. And the more antennas, the more worth it is: with \(n\) antennas, each network has \(n!\) labelings, and an optimizer that does not know it may pay for the same network up to \(n!\) times.
Now, the easiest way to grasp how useful symmetries could be is to play the optimizer yourself. Below is a hidden landscape with a few mirror symmetries. You have six evaluations to find its highest point. Then switch the symmetry on and play again.
This note is about incorporating these symmetries as an inductive bias for a Bayesian algorithm. It is based on our ICLR 2026 paper with Antoine Gonon, Aryan Ahadinia and Patrick Thiran, in which we revisit a simple idea from kernel methods, and show that it makes Bayesian optimization significantly more sample-efficient on symmetric problems.
Paying twice for the same information
Bayesian optimization looks for the maximum of a function that is expensive to evaluate and that offers no gradients: all you can do is query it and observe a (noisy) value. It maintains a probabilistic model of the function, usually a Gaussian process. After each evaluation, the model provides two things at every point \(x\): a best guess \(\mu(x)\), the posterior mean, and an uncertainty \(\sigma(x)\). The next query goes where the function could plausibly be highest,
\[x_{t+1} = \arg\max_x \; \mu_t(x) + \beta\,\sigma_t(x),\]where a large \(\beta\) favors exploring uncertain regions and a small one favors refining the best region found so far. Everything the model believes comes from a single object, its kernel \(k(x, x') = \mathrm{Cov}(f(x), f(x'))\), which quantifies how similar the values of the function at \(x\) and \(x'\) should be. Here, as in the rest of this note, it is the Gaussian kernel \(k(x,x') = \exp\left(-\lVert x - x' \rVert^2 / 2\ell^2\right)\): nearby points are similar, distant ones are not.
The function below is symmetric: for any \(x\), \(f(x) = f(-x)\), but the model does not know it. Let the algorithm choose a few points and watch where it goes. Then tell the model about the mirror.
The symmetry-blind model sees an unexplored half and pays to evaluate it again, point by point. Once it knows the mirror, its uncertainty collapses on both sides at once and every evaluation lands somewhere new. With a single mirror, ignoring the symmetry roughly doubles the work. In real-world problems, a point can have thousands of copies.
Two ways to make a kernel invariant
Suppose that \(f\) is invariant under a group \(G\) of transformations: \(f(gx) = f(x)\) for every \(g \in G\) and every \(x\). Then \(x\) and \(gx\) are not merely similar, they are interchangeable. A Gaussian process whose sample paths all share this invariance must have an invariant kernel, with \(k(gx, g'x') = k(x, x')\) for all \(g, g' \in G\).1 Starting from a base kernel \(k\), there are two natural ways to build one:
\[k_{\mathrm{avg}}(x,x') = \frac{1}{\lvert G \rvert^2}\sum_{g,g'\in G} k(gx, g'x'), \qquad k_{\max}(x,x') = \max_{g,g'\in G}\, k(gx, g'x').\]Both compare the copies of \(x\) with the copies of \(x'\). The first averages these similarities. It is the standard choice for Bayesian optimization, with a clean interpretation: the functions it can represent are exactly the invariant functions of the base kernel.2 The second keeps only the best alignment. Below, a group with \(n\) mirror lines gives \(x'\) its \(2n\) copies, and each segment links \(x\) to one of them, darker when they are more similar.
One thing becomes immediately clear: only one copy is well aligned with \(x\), and the average dilutes it among all \(2n\) of them, so the averaged similarity is roughly \(1/(2n)\) of the true one. Unlike the average, taking the max keeps the closest alignment. The exception is instructive: drag \(x'\) onto a mirror line, or to the center, and several copies merge. There, several alignments are right at once, and the average recovers part of its strength. Its opinion of how similar two points are depends on where they are relative to the mirrors.
The same contrast, for all points of the disc at once: each panel shows how similar every point is to the dot.
The base kernel knows nothing of the symmetry and shows a single bump. Both invariant kernels light up every copy of the dot, but the average lights them at a fraction of full strength, while under the max kernel every copy is exactly as similar to the dot as the dot is to itself (as it should be).
Folding the search space
We just found something interesting. Why is \(k_\mathrm{max}\) so good at capturing symmetries?
The answer is geometric, and can easily be visualized. Fold the disc along its mirror lines, like a paper fan, until all the copies of a point land on top of one another. What remains is a single wedge in which each point stands for a whole family of equivalent points. More formally, this is the quotient of the disc by the group, the space of equivalence classes, also called an orbifold. There is a natural distance function in this space: the distance between two points of the wedge is the length of the shortest path from one to any copy of the other, \(\min_{g \in G} \lVert x - gx' \rVert\).
The last option, ∞, takes every rotation of the disc. The copies of a point now form a whole circle, the wedge narrows to a single line, and the fold sends each point \(x\) to its distance from the center, \(\lVert x \rVert_2\). The orbifold is a segment, and the distance between two points is the difference of their radii.
Fold first, then draw
Now put an ordinary Gaussian process on the folded space, with the base kernel and these distances, and unfold it. The result is a Gaussian process on the disc whose covariance is exactly \(k_{\max}\)!3 The max kernel is not an ad hoc trick: it is what you get by modeling the function where it actually lives, on the space of equivalence classes, with the base kernel you would have used anyway.
The averaged kernel has a construction too. Draw a function \(h\) from the base Gaussian process on the whole disc, then average it over all its copies, \(\frac{1}{\lvert G \rvert}\sum_{g} h(gx)\). The result is invariant, and its covariance is exactly \(k_{\mathrm{avg}}\); it is also what you obtain by conditioning \(h\) on being invariant to \(G\).4 Both routes can start from the same random draw. Here they are, side by side.
Same draw, two invariant functions. Folding keeps \(h\) intact on every copy of the wedge: the result looks like an ordinary draw from the base prior, repeated by the symmetry. Averaging washes \(h\) out, because \(\lvert G \rvert\) unrelated values mostly cancel, except near the mirrors and the center, where some copies coincide. The averaged prior is not only fainter, it is uneven: it expects the function to vary much more near the symmetry axes than anywhere else, for no reason other than the way the kernel was built. Formally, the Gaussian process built with the average kernel is not stationary. Conversely, the Gaussian process built from \(k_\max\) is a vanilla stationary process in the wedge, which the mirrors copy across the whole disc.
A race
Time to see the kernels at work. Below, three optimizers chase the peak of the same symmetric landscape from the same five random starting points, using the upper-confidence rule from above. They differ only in their kernel. Each panel shows what the model currently believes, its posterior mean, along with every point it has evaluated; faint circles mark the true peaks. The chart tracks the cumulative regret \(R_T = \sum_{i = 1}^T (f(x^*) - f(x_i))\), the total optimization error of all evaluations so far with respect to the maximum of \(f\).
Run it a few times. With four mirrors, both invariant kernels leave the base kernel far behind and stay fairly close. With eight mirrors, \(\lvert G \rvert = 16\), the gap opens. To fit the data, the averaged model inflates its signal variance, to about five times that of the max model, and its uncertainty is then largest where copies merge: on the mirrors and at the center. That is where it spends its evaluations, more than half of them against a fifth for the max kernel.
Coda: when the max is not a kernel
Everything above relied on folding: mirror lines fold the disc flat into a wedge, and all rotations together collapse it onto a segment. Unfortunately, some groups cannot be folded that way. Take the four rotations by multiples of 90°, without mirrors. A quarter of the disc contains one copy of every point, but its two straight edges are copies of each other according to \(G\), and to measure distances between orbits they must be glued together.
A cone cannot be laid flat without tearing or stretching, so no fold turns orbit distances into ordinary distances, and \(k_{\max}\) indeed fails to be positive semi-definite here. A Gaussian process cannot use it as it is.
The fix is pragmatic. Given the points \(D\) evaluated so far, form the matrix \(K = k_{\max}(D, D)\), set its negative eigenvalues to zero to obtain \(K_+\), and extend it to new points with the Nyström formula
\[k_+(x, x') = k_{\max}(x, D)\, K_+^{\dagger}\, k_{\max}(D, x').\]The result is a valid invariant kernel that agrees with \(k_{\max}\) on \(D\) whenever \(K\) was already positive semi-definite, at the same asymptotic cost per iteration as the averaged kernel. Here are the two kernels side by side. Drag the reference point \(x_0\), change the number of data points, or switch groups.
With rotations by 90°, about a third of the eigenvalues of \(K\) are negative and set to zero. The two kernels then differ by a few hundredths, even at the data points, and the gap shrinks only slowly as data accumulate: it comes from the negative part of \(k_{\max}\) itself, not from a lack of data. Add the mirrors and nothing is clipped: once the data cover the disc, \(k_+\) and \(k_{\max}\) coincide.
This is the off-the-shelf version of the \(k_\max\) we propose in our paper, and our benchmarks show its advantage over the averaged kernel, which grows with the size of the group.
If you are eager for more technical details, the paper is on OpenReview, and the code is on GitHub.
Thanks for reading, and see you on the next note!
-
D. Ginsbourger, X. Bay, O. Roustant and L. Carraro, Argumentwise invariant kernels for the approximation of invariant functions, Annales de la Faculté des Sciences de Toulouse, 2012. ↩
-
R. Kondor, Group theoretical methods in machine learning, PhD thesis, Columbia University, 2008; T. Brown, A. Cioba and I. Bogunovic, Sample-efficient Bayesian optimisation using known invariances, NeurIPS 2024. ↩
-
Proposition 1 in the paper. It requires a folding map that turns the distance between orbits into an ordinary Euclidean distance: folding along mirrors provides one, and so does \(x \mapsto \lVert x \rVert\) for all rotations. ↩
-
Brown, Cioba and Bogunovic (2024), for a base kernel that is unchanged when both of its arguments are transformed together, as the Gaussian kernel is under rotations and reflections. ↩