Symmetry-Aware Bayesian Optimization via Max Kernels

## Abstract

Abstract Bayesian Optimization (BO) is a powerful framework for optimizing noisy, expensive-to-evaluate black-box functions. When the objective exhibits invariances under a group action, exploiting these symmetries can substantially improve BO efficiency. While using maximum similarity across group orbits has long been considered in other domains, the fact that the max kernel is not positive semidefinite (PSD) has prevented its use in BO. In this work, we revisit this idea by considering a PSD projection of the max kernel. Compared to existing invariant (and non-invariant) kernels, we show it achieves significantly lower regret on both synthetic and real-world BO benchmarks, without increasing computational complexity.

## 1 Introduction

Bayesian optimization (BO) tackles the maximization of a noisy, expensive-to-evaluate black-box ${f^{\star}}:\mathcal{S}\subset\mathbb{R}^{d}\to\mathbb{R}$ using a Gaussian process (GP) surrogate. When prior knowledge says that ${f^{\star}}$ is invariant on orbits $[\bm{x}]=\{{g\bm{x}}:g\in\mathcal{G}\}$ of a group $\mathcal{G}$, that is,

$$ ${f^{\star}}(\bm{x})={f^{\star}}({g\bm{x}})\quad(\forall g\in\mathcal{G}),$ $$

embedding this invariance into the kernel can significantly improve sample efficiency.
A classical and principled approach is to average a base kernel $k_{\mathrm{b}}$ over group orbits
(e.g., Kondor (2008); Glielmo et al. (2017); Brown et al. (2024)). Averaging yields a $\mathcal{G}$-invariant kernel with a clean RKHS interpretation
(as discussed in [Section 2.2](https://arxiv.org/html/2509.25051v1#S2.SS2)), but as $|\mathcal{G}|$ grows it can dilute high-similarity alignments across orbits.

From averaging to max-alignment.
We revisit a simple idea—*retain the strongest orbitwise alignment*—and adapt it to BO. Given a base kernel $k_{\mathrm{b}}$ and a symmetry group $\mathcal{G}$, define

$$ $k_{\mathrm{max}}(\bm{x},\bm{x}^{\prime})=\max_{g,g^{\prime}\in\mathcal{G}}\,k_{\mathrm{b}}\!\big({g\bm{x}},\,{g^{\prime}\bm{x}^{\prime}}\big),$ (1) $$

so that the similarity between $\bm{x}$ and $\bm{x}^{\prime}$ is the best alignment over their orbits. While $k_{\mathrm{max}}$ is symmetric and $\mathcal{G}$-invariant, it is not positive semidefinite (PSD) in general and thus cannot serve directly as a GP covariance.

A PSD, invariant surrogate via projection + Nyström.
On a finite design set $\mathcal{D}$, we form the Gram matrix of $k_{\mathrm{max}}$ and project it onto the PSD cone (eigenvalue clipping), obtaining ${\bm{K}}_{+}$. Denoting by ${\bm{K}}_{+}^{\dagger}$ the Moore-Penrose pseudo-inverse of ${\bm{K}}_{+}$, we then define the $\mathcal{G}$-invariant, PSD kernel

$$ $k_{+}^{(\mathcal{D})}(\bm{x},\bm{x}^{\prime})\;=\;k_{\mathrm{max}}(\bm{x},\mathcal{D})\,{\bm{K}}_{+}^{\dagger}\,k_{\mathrm{max}}(\mathcal{D},\bm{x}^{\prime}).$ (2) $$

Equivalently, $k_{+}^{(\mathcal{D})}(\bm{x},\bm{x}^{\prime})=\phi(\bm{x})^{\top}\phi(\bm{x}^{\prime})$ with features $\phi(\bm{x})={\bm{K}}_{+}^{\dagger/2}\,k_{\mathrm{max}}(\mathcal{D},\bm{x})$, which makes positive semidefiniteness immediate. By construction, $k_{+}^{(\mathcal{D})}$ (i) coincides with $k_{\mathrm{max}}$ on $\mathcal{D}$ whenever $k_{\mathrm{max}}$ is already PSD, and (ii) has per-iteration asymptotic cost comparable to orbit-averaged kernels; details in [Section 3.2](https://arxiv.org/html/2509.25051v1#S3.SS2).

Why can max-alignment help?
Averaging mixes all orbit pairings and can shrink contrasts as $|\mathcal{G}|$ increases. In contrast, ([1](https://arxiv.org/html/2509.25051v1#S1.E1)) preserves high-contrast alignments that drive exploration, while the projection step ([2](https://arxiv.org/html/2509.25051v1#S1.E2)) produces a valid GP kernel without introducing new algorithmic complexity (BO iterations already perform a Singular Value Decomposition (SVD) of the Gram matrix for GP inference, so the extra-computation of ${\bm{K}}_{+}^{\dagger}$ does not change the asymptotic cost as we will see later in [Table 1](https://arxiv.org/html/2509.25051v1#S3.T1)).

Empirics and spectra.
Across synthetic benchmarks with finite and continuous groups and a wireless-network design task, we show that $k_{+}^{(\mathcal{D})}$ consistently attains lower cumulative and simple regret than both the base kernel and the orbit-averaged alternative, with gains increasing with $|\mathcal{G}|$. Our spectral analyses reveal that $k_{+}^{(\mathcal{D})}$ does not necessarily enjoy faster eigendecay than averaging-based kernels; thus, eigendecay-based regret bounds would predict similar or weaker rates, yet we observe the opposite in practice. We hypothesize that search-geometry effects (e.g., preserving high-contrast orbit alignments), approximation hardness and misspecification are key factors to take into account to fill this gap between theory and practice; see [Section 5](https://arxiv.org/html/2509.25051v1#S5).

Summary of the contributions.
We propose $k_{\mathrm{max}}$ as a *max-alignment* route to $\mathcal{G}$-invariance, turn it into a valid GP kernel for BO via PSD projection and Nyström, and show $k_{+}^{(\mathcal{D})}$ is $\mathcal{G}$-invariant, equals $k_{\mathrm{max}}$ on $\mathcal{D}$ when $k_{\mathrm{max}}$ is PSD, and matches the asymptotic cost of orbit-averaged kernels ([Section 3](https://arxiv.org/html/2509.25051v1#S3)). We demonstrate consistent BO gains over orbit averaging across BO benchmarks ([Section 4](https://arxiv.org/html/2509.25051v1#S4)), and we analyze why eigendecay alone does not explain these gains ([Section 5](https://arxiv.org/html/2509.25051v1#S5)).

## 2 Background

### 2.1 Bayesian Optimization in a Nutshell

Problem.
We seek to maximize an expensive-to-evaluate, black-box objective ${f^{\star}}:\mathcal{S}\!\to\!\mathbb{R}$ under the assumption that ${f^{\star}}$ is in the RKHS $\mathcal{H}_{k}$ of a kernel $k:\mathcal{S}\times\mathcal{S}\to\mathbb{R}$.
Each query $\bm{x}\in\mathcal{S}$ returns a noisy observation
$y={f^{\star}}(\bm{x})+\varepsilon$, where $\varepsilon\sim\mathcal{N}(0,\sigma_{0}^{2})$.
Let $\mathcal{Z}_{t}=\{(\bm{x}_{i},y_{i})\}_{i=1}^{t}$ denote the dataset after $t$ evaluations, and write
$\mathcal{D}_{t}=(\bm{x}_{1},\ldots,\bm{x}_{t})$ and $\bm{y}_{t}=(y_{1},\ldots,y_{t})^{\top}$.

Surrogate model: the GP prior.
BO maintains a probabilistic surrogate ${f}$ over functions in $\mathcal{H}_{k}$ to guide sampling of new queries $\bm{x}\in\mathcal{S}$ with the goal of converging to $\operatorname*{arg\,max}_{x\in\mathcal{S}}{f^{\star}}(\bm{x})$.
A common choice is a zero-mean Gaussian process (GP) (Rasmussen and Williams, 2006),

$$ ${f}\sim\mathcal{GP}(0,k),$ $$

Conditionally on $\mathcal{Z}_{t}$, the posterior ${f}\mid\mathcal{Z}_{t}$ is still a GP with posterior mean and covariance

$$ $\displaystyle\mu_{t}(\bm{x})$ $\displaystyle=k(\bm{x},\mathcal{D}_{t})\,\big({\bm{K}}_{t}+\sigma_{0}^{2}\bm{I}_{t}\big)^{-1}\bm{y}_{t},$ (3) $\displaystyle\mathrm{Cov}_{t}(\bm{x},\bm{x}^{\prime})$ $\displaystyle=k(\bm{x},\bm{x}^{\prime})-k(\bm{x},\mathcal{D}_{t})\,\big({\bm{K}}_{t}+\sigma_{0}^{2}\bm{I}_{t}\big)^{-1}k(\mathcal{D}_{t},\bm{x}^{\prime}),$ (4) $$

where ${\bm{K}}_{t}=k(\mathcal{D}_{t},\mathcal{D}_{t})\in\mathbb{R}^{t\times t}$, $\bm{I}_{t}$ is the $t\times t$ identity, and
$k(\bm{x},\mathcal{D}_{t})=[k(\bm{x},\bm{x}_{1}),\ldots,k(\bm{x},\bm{x}_{t})]$.

BO Iteration.
At step $t$, BO trades off *exploration* (learning ${f^{\star}}$) and *exploitation*
(sampling near current optima) via an acquisition function $\alpha_{t}:\mathcal{S}\to\mathbb{R}$ computed from
$(\mu_{t},\mathrm{Cov}_{t})$ (e.g., GP-UCB (Srinivas et al., 2012) or
Expected Improvement (Jones et al., 1998)). The next point is

$$ $\bm{x}_{t+1}\in\operatorname*{arg\,max}_{\bm{x}\in\mathcal{S}}\,\alpha_{t}(\bm{x}),\qquad y_{t+1}={f^{\star}}(\bm{x}_{t+1})+\varepsilon_{t+1}.$ $$

Measuring performance with regret. We follow the common practice in BO: for experiments where ${f^{\star}}$ is known, we measure the regret on the deterministic ${f^{\star}}\in\mathcal{H}_{k}$, and when discussing theoretical regret bounds we refer to the regret on ${f}\sim\mathcal{GP}(0,k)$ (Garnett, 2023). In both cases, for $h={f}$ or $h={f^{\star}}$, the *instantaneous regret* at timestep $t$ is $r_{t}=\max_{\bm{x}\in\mathcal{S}}h(\bm{x})-h(\bm{x}_{t})$, the
*cumulative regret* at horizon $T$ is $R_{T}=\sum_{t=1}^{T}r_{t}$, and the
*simple regret* is $s_{T}=\max_{\bm{x}\in\mathcal{S}}h(\bm{x})-\max_{1\leq t\leq T}h(\bm{x}_{t})$. A BO algorithm with a sublinear regret (i.e., $R_{T}\in o(T)$) is called *no-regret* and offers asymptotic global optimization guarantees on ${f^{\star}}$. Most standard cumulative regret upper bounds are established in terms of the eigendecay of the operator spectrum of the kernel $k$ (Srinivas et al., 2012; Valko et al., 2013; Scarlett et al., 2017; Whitehouse et al., 2023).

### 2.2 Invariance in Bayesian Optimization

In many applications, the objective function ${f^{\star}}$ is invariant under the action of a known symmetry group $\mathcal{G}$ on $\mathcal{S}$, i.e., ${f^{\star}}(\bm{x})={f^{\star}}({g\bm{x}})$ for all $g\in\mathcal{G}$. When such invariances are ignored, BO algorithms may waste evaluations by treating all points within the same $|\mathcal{G}|$-orbit as distinct. Given a non-invariant base kernel $k_{\mathrm{b}}$ and an arbitrary symmetry group $\mathcal{G}$, both provided by the user, this section reviews existing strategies for incorporating group invariance into BO and positions our contribution within this literature.

Data augmentation. A popular way to enforce symmetry is to expand the dataset $\mathcal{Z}$ itself, as it is often done in computer vision (Krizhevsky et al., 2012). For each acquired observation $(\bm{x}_{t},y_{t})$, one augments $\mathcal{Z}$ with all transformed copies $\{({g\bm{x}_{t}},y_{t})\}_{g\in\mathcal{G}}$, while leaving the base kernel $k_{\mathrm{b}}$ unchanged. However, since BO scales as $\mathcal{O}(|\mathcal{Z}|^{3})$, this approach quickly becomes computationally prohibitive and is inapplicable to continuous symmetry groups.

Search space restriction. A second strategy is to restrict the optimization domain to the smallest subset $\mathcal{S}_{\mathcal{G}}\subseteq\mathcal{S}$ such that $\bigcup_{g\in\mathcal{G}}g\mathcal{S}_{\mathcal{G}}=\mathcal{S}$ (e.g., Baird et al. (2023)). For instance, if $\mathcal{S}=[-1,1]^{2}$ and $\mathcal{G}$ is the group of planar rotations by angle $\pi/2$, then it suffices to optimize over $\mathcal{S}_{\mathcal{G}}=[0,1]^{2}$ while keeping the base kernel $k_{\mathrm{b}}$ unchanged. In general, however, identifying a suitable fundamental domain $\mathcal{S}_{\mathcal{G}}$ can be challenging, and enforcing optimization within it may be impractical.

Invariant kernels. A principled way to incorporate prior $\mathcal{G}$-invariance of ${f^{\star}}$ is to consider a $\mathcal{G}$-invariant GP prior ${f}$, i.e., a GP whose sample paths $\bm{x}\in\mathcal{S}\mapsto{f}(\bm{x},\omega)$ obtained by fixing one outcome $\omega$ in the probability space are themselves invariant under $\mathcal{G}$. Ginsbourger et al. (2012) established that such GPs necessarily admit a $\mathcal{G}$-invariant covariance function(^1^11Up to modification, i.e., there is another GP ${f}^{\prime}$ such that for every $x\in\mathcal{S}$, $\mathbb{P}({f}(\bm{x})={f}^{\prime}(\bm{x}))=1$ and ${f}^{\prime}$ has invariant paths and invariant covariance, see Property 3.3 in Ginsbourger et al. (2012).), meaning $k(g\bm{x},g^{\prime}\bm{x}^{\prime})=k(\bm{x},\bm{x}^{\prime})$ for all $\bm{x},\bm{x}^{\prime}\in\mathcal{S}$ and $g,g^{\prime}\in\mathcal{G}$. The central question then becomes: how can one construct an invariant kernel $k$ from an arbitrary base kernel $k_{\mathrm{b}}$ and symmetry group $\mathcal{G}$? An elegant solution, dating back to Kondor (2008) and recently advocated for BO by Brown et al. (2024), is to average $k_{\mathrm{b}}$ over $\mathcal{G}$-orbits:

$$ $k_{\mathrm{avg}}(\bm{x},\bm{x}^{\prime})=\frac{1}{|\mathcal{G}|^{2}}\sum_{g,g^{\prime}\in\mathcal{G}}k_{\mathrm{b}}(g\bm{x},g^{\prime}\bm{x}^{\prime}).$ (5) $$

This construction is not only guaranteed to be $\mathcal{G}$-invariant, but also admits a clean functional interpretation: if $\mathcal{H}_{k_{\mathrm{b}}}$ and $\mathcal{H}_{k_{\mathrm{avg}}}$ denote the RKHS induced by $k_{\mathrm{b}}$ and $k_{\mathrm{avg}}$ respectively, then $\mathcal{H}_{k_{\mathrm{avg}}}$ coincides exactly with the subspace of $\mathcal{G}$-invariant functions in $\mathcal{H}_{k_{\mathrm{b}}}$ (Theorem 4.4.3 in Kondor (2008)). Consequently, $k_{\mathrm{avg}}$ (up to normalization) has gained popularity as the standard off-the-shelf kernel for BO in symmetric settings (Glielmo et al., 2017; Kim et al., 2021; Brown et al., 2024).

A complementary idea in kernel methods is to retain the *best* latent alignment between two orbits via a maximum, as in convolution/best-match kernels for structured data (Gärtner, 2003; Vishwanathan et al., 2003) and follow-up work across domains (Fröhlich et al., 2005; Zhang, 2010; Curtin et al., 2013). Max-alignment kernels, however, are not PSD in general, leading to indefinite Gram matrices. This has motivated two families of remedies: (i) explicit Kreĭn-space formulations (Ong et al., 2004; Oglic and Gärtner, 2018), and (ii) simple PSD corrections such as eigenvalue clipping/flipping in SVMs (Luss and D' aspremont, 2007; Chen et al., 2009), which are empirically effective.

Our adaptation to BO.
Guided by the above, we adopt the max-alignment view for BO. To ensure positive definiteness, we project $k_{\mathrm{max}}$ (see ([1](https://arxiv.org/html/2509.25051v1#S1.E1))) onto a PSD kernel $k_{+}^{(\mathcal{D})}$, which coincides with $k_{\mathrm{max}}$ whenever the latter is already PSD. This preserves the sharp, high-contrast orbit alignments of $k_{\mathrm{max}}$ while ensuring compatibility with the BO framework and it keeps per-iteration BO complexity on par with orbit-averaged kernels (see complexity details later in [Section 2.2](https://arxiv.org/html/2509.25051v1#S2.SS2)). In our experiments, $k_{+}^{(\mathcal{D})}$ better reflects the intended symmetries of standard synthetic objectives and achieves substantially lower cumulative regret; interestingly, these empirical gains are not mirrored by existing eigendecay-based upper bounds, a point we return to in [Section 5](https://arxiv.org/html/2509.25051v1#S5).

## 3 The Max Kernel

We have introduced the max-alignment kernel $k_{\mathrm{max}}$ and its PSD surrogate $k_{+}^{(\mathcal{D})}$ in ([2](https://arxiv.org/html/2509.25051v1#S1.E2)). This section explains *why* $k_{\mathrm{max}}$ is a natural $\mathcal{G}$-invariant covariance, clarifies how it differs from orbit averaging through examples, and records the practical PSD construction we use in BO.

### 3.1 Motivation: k max k_{\mathrm{max}} as a valid covariance

A natural way to motivate $k_{\mathrm{max}}$ is to exhibit $\mathcal{G}$-invariant GPs whose covariance equals $k_{\mathrm{max}}$.

Construction.
Let $h\sim\mathcal{GP}(0,k_{\mathrm{b}})$ with an isotropic base kernel $k_{\mathrm{b}}(\bm{x},\bm{x}^{\prime})=\kappa(\|\bm{x}-\bm{x}^{\prime}\|_{2})$ with $\kappa$ nonincreasing (e.g., popular ones such as RBF, Matérn).
Consider a map $\phi_{\mathcal{G}}$ such that (i) $\phi_{\mathcal{G}}(\bm{x})=\phi_{\mathcal{G}}({g\bm{x}})$ for all $g\in\mathcal{G}$ and
(ii) $\|\phi_{\mathcal{G}}(\bm{x})-\phi_{\mathcal{G}}(\bm{x}^{\prime})\|_{2}=\min_{g,g^{\prime}}\|{g\bm{x}}-{g^{\prime}\bm{x}^{\prime}}\|_{2}$.
Define ${f}(\bm{x})=h(\phi_{\mathcal{G}}(\bm{x}))$. Then ${f}$ is $\mathcal{G}$-invariant and:

###### Proposition 1 .

Under the construction above, ${f}\sim\mathcal{GP}(0,k_{\mathrm{max}})$ with $k_{\mathrm{max}}$ given by ([1](https://arxiv.org/html/2509.25051v1#S1.E1)).

*Proof sketch, details in [Appendix A](https://arxiv.org/html/2509.25051v1#A1).* $\mathrm{Cov}({f}(\bm{x}),{f}(\bm{x}^{\prime}))\overset{\text{def}{f}}{=}k_{\mathrm{b}}(\phi_{\mathcal{G}}(\bm{x}),\phi_{\mathcal{G}}(\bm{x}^{\prime}))\overset{\text{(ii)}}{=}\kappa(\min_{g,g^{\prime}}\|{g\bm{x}}-{g^{\prime}\bm{x}^{\prime}}\|_{2})$, and
monotonicity of $\kappa$ converts the min-distance into $\max_{g,g^{\prime}}k_{\mathrm{b}}({g\bm{x}},{g^{\prime}\bm{x}^{\prime}})$.∎

This shows that $k_{\mathrm{max}}$ naturally arises as the covariance of valid $\mathcal{G}$-invariant GPs.
In contrast, the common approach to invariance in BO is to build $k_{\mathrm{avg}}$ by averaging a base kernel as in ([5](https://arxiv.org/html/2509.25051v1#S2.E5)).
But averaging and maximization induce fundamentally different geometries:

###### Lemma 2 .

For any base kernel $k_{\mathrm{b}}$ and any (double) orbit $\mathcal{O}(\bm{x},\bm{x}^{\prime}):=\{({g\bm{x}},{g^{\prime}\bm{x}^{\prime}}),g,g^{\prime}\in\mathcal{G}\}$,
$k_{\mathrm{avg}}=k_{\mathrm{max}}$ on $\mathcal{O}(\bm{x},\bm{x}^{\prime})$ if and only if $k_{\mathrm{b}}=k_{\mathrm{max}}$ on that orbit.

Indeed, an average reaches the maximum only when every term is maximal. Thus $k_{\mathrm{avg}}$ can never reproduce the geometry of $k_{\mathrm{max}}$, except in the degenerate case where the base kernel is already $k_{\mathrm{max}}$, making averaging redundant. One might wonder whether this limitation of $k_{\mathrm{avg}}$ could be circumvented by building it from a *different* base kernel than the one used for $k_{\mathrm{max}}$. In [Section A.2](https://arxiv.org/html/2509.25051v1#A1.SS2) we show that, under mild assumptions satisfied by standard kernels (upper-bounded by $1$, with equality $k(\bm{x},\bm{x})=1$ along the diagonal), $k_{\mathrm{avg}}$ and $k_{\mathrm{max}}$ can coincide only in the trivial case where the base kernel of $k_{\mathrm{avg}}$ is already invariant when its arguments belong to the same orbit.
Thus, even in this more general setting, averaging does not reproduce the geometry of maximization (except if the base kernel already had invariances).

To make this contrast concrete, we now examine a simple example
(radial invariance with an RBF base kernel) where $k_{\mathrm{max}}$ and $k_{\mathrm{avg}}$
can be computed in closed form.

###### Example 3 (Radial invariance with $k_{\mathrm{max}}$ ) .

Let $\mathcal{G}$ be the group of planar rotations and $k_{\mathrm{b}}(\bm{x},\bm{x}^{\prime})=\exp\!\left(-\|\bm{x}-\bm{x}^{\prime}\|_{2}^{2}/2l^{2}\right)$ be an RBF kernel. With $\phi_{\mathcal{G}}(\bm{x})=\|\bm{x}\|_{2}$,

$$ $k_{\mathrm{max}}(\bm{x},\bm{x}^{\prime})=\exp\!\left(-(\|\bm{x}\|_{2}-\|\bm{x}^{\prime}\|_{2})^{2}/2l^{2}\right),\quad k_{\mathrm{avg}}(\bm{x},\bm{x}^{\prime})=\exp\!\Big(-\tfrac{\|\bm{x}\|_{2}^{2}+\|\bm{x}^{\prime}\|_{2}^{2}}{2l^{2}}\Big)I_{0}\!\Big(\tfrac{\|\bm{x}\|_{2}\|\bm{x}^{\prime}\|_{2}}{l^{2}}\Big),$ $$

with $I_{0}$ the modified Bessel function (derivation in [Appendix B](https://arxiv.org/html/2509.25051v1#A2)). As illustrated in [Figure 1](https://arxiv.org/html/2509.25051v1#S3.F1), the two kernels $k_{\mathrm{max}}$ and $k_{\mathrm{avg}}$ induce qualitatively different similarity structures.
By construction, $k_{\mathrm{max}}$ assigns large similarity whenever $\|\bm{x}\|_{2}\approx\|\bm{x}^{\prime}\|_{2}$. If $\|\bm{x}\|_{2}=\|\bm{x}^{\prime}\|_{2}$, the function ${f^{\star}}$ satisfies ${f^{\star}}(\bm{x})={f^{\star}}(\bm{x}^{\prime})$ since it is invariant under rotations, and $k_{\mathrm{max}}$ exactly recovers this invariance by assigning maximal similarity $k_{\mathrm{max}}(\bm{x},\bm{x}^{\prime})=1$.
In contrast, $k_{\mathrm{avg}}$ only approximates this behavior: its iso-similarity curves as a function of $(\|\bm{x}\|_{2},\|\bm{x}^{\prime}\|_{2})$ correspond to distorted balls, and two points with identical norms may be ranked as highly dissimilar (see the diagonal $\|\bm{x}\|_{2}=\|\bm{x}^{\prime}\|_{2}$ of the right plot in [Figure 1](https://arxiv.org/html/2509.25051v1#S3.F1)).
This mismatch highlights that while both constructions enforce rotation invariance, only $k_{\mathrm{max}}$ preserves the correct notion of similarity.

Figure: Figure 1: (Left) A two-dimensional function ${f^{\star}}(\bm{x})$ invariant under planar rotations (see ([16](https://arxiv.org/html/2509.25051v1#A5.E16))): if $\|\bm{x}\|_{2}=\|\bm{x}^{\prime}\|_{2}$, then ${f^{\star}}(\bm{x})={f^{\star}}(\bm{x}^{\prime})$. (Center/Right) Rotation-invariant kernels derived from an RBF base kernel (lengthscale $1/2$), visualized as a function of $(\|\bm{x}\|_{2},\|\bm{x}^{\prime}\|_{2})$. $k_{\mathrm{max}}$ (center) captures the correct invariance, while $k_{\mathrm{avg}}$ (right) only approximates it.
Refer to caption: rsc/Radial_Invariance.png

###### Proposition 1 .

###### Lemma 2 .

###### Example 3 (Radial invariance with k max k_{\mathrm{max}} ) .

### 3.2 A PSD Extension of k max k_{\mathrm{max}} : What We Use in Practice

Because $k_{\mathrm{max}}$ is not PSD in general, we apply a standard projection step on the finite design set $\mathcal{D}=\{\bm{x}_{1},\dots,\bm{x}_{n}\}$. Let ${\bm{K}}=k_{\mathrm{max}}(\mathcal{D},\mathcal{D})$ with eigendecomposition ${\bm{K}}=\bm{Q}\bm{\Lambda}\bm{Q}^{\top}$ and define(^2^22${\bm{K}}_{+}$ does not depend on the choice of the eigendecomposition, see [Lemma 7](https://arxiv.org/html/2509.25051v1#Thmtheorem7) in the appendix.) (with the max applied elementwise)

$$ ${\bm{K}}_{+}\;=\;\bm{Q}\,\max(0,\bm{\Lambda})\,\bm{Q}^{\top}.$ (6) $$

We then use the Nyström extension(^3^33It indeed extends ${\bm{K}}_{+}$ since $k_{+}^{(\mathcal{D})}(\bm{x}_{i},\bm{x}_{j})\;=\;{\bm{K}}_{i,:}\,{\bm{K}}_{+}^{\dagger}\,{\bm{K}}_{:,j}\;=\;({\bm{K}}{\bm{K}}_{+}^{\dagger}{\bm{K}})_{ij}\;=\;({\bm{K}}_{+})_{ij}$.) (Williams and Seeger, 2000) to evaluate cross-covariances with new points, yielding the PSD, $\mathcal{G}$-invariant surrogate $k_{+}^{(\mathcal{D})}$ given in ([2](https://arxiv.org/html/2509.25051v1#S1.E2)) and that we reproduce here:

$$ $k_{+}^{(\mathcal{D})}(\bm{x},\bm{x}^{\prime})\;:=\;k_{\mathrm{max}}(\bm{x},\mathcal{D})\,{\bm{K}}_{+}^{\dagger}\,k_{\mathrm{max}}(\mathcal{D},\bm{x}^{\prime}).$ (7) $$

**Table 1: Complexity per BO iteration. Here $|G|^{\!*}$ denotes either $|G|$ or $|G|^{2}$ depending on whether the orbit terms reduce to a single sum (when $k_{\mathrm{b}}({g\bm{x}},\bm{x}^{\prime})$ suffices) or require a double sum over $(g,g^{\prime})$; $m$ is the number of candidate points used in acquisition optimization.**
|  | Base kernel $k_{\mathrm{b}}$ | Averaged $k_{\mathrm{avg}}$ | Projected $k_{+}^{(\mathcal{D})}$ |
| --- | --- | --- | --- |
| Gram matrix ($n\times n$) | $\mathcal{O}(n^{2})$ | $\mathcal{O}(n^{2}|G|^{\!*})$ | $\mathcal{O}(n^{2}|G|^{\!*})$ |
| SVD / inversion | $\mathcal{O}(n^{3})$ | $\mathcal{O}(n^{3})$ | $\mathcal{O}(n^{3})$ |
| PSD projection | – | – | $\mathcal{O}(n^{3})$(^4^44One SVD of ${\bm{K}}$ suffices to obtain both ${\bm{K}}_{+}$ and ${\bm{K}}_{+}^{\dagger}$, so the extra PSD projection does not increase asymptotic cost.) |
| Per-query evaluation | $\mathcal{O}(1)$ | $\mathcal{O}(|G|^{\!*})$ | $\mathcal{O}(n|G|^{\!*})$ |
| BO iteration | $\mathcal{O}(m+n^{2}+n^{3})$ | $\mathcal{O}((m+n^{2})|G|^{\!*}+n^{3})$ | $\mathcal{O}((mn+n^{2})|G|^{\!*}+n^{3})$ |

Key properties of $k_{+}^{(D)}$:

- •
*PSD & invariance.*
$k_{+}^{(\mathcal{D})}$ is PSD and inherits argumentwise $\mathcal{G}$-invariance(^5^55$k_{\mathrm{max}}({g\bm{x}},\bm{x}^{\prime})=k_{\mathrm{max}}(\bm{x},\bm{x}^{\prime})$ implies $k_{\mathrm{max}}({g\bm{x}},\mathcal{D})=k_{\mathrm{max}}(\bm{x},\mathcal{D})$, hence invariance of $k_{+}^{(\mathcal{D})}$.) of $k_{\mathrm{max}}$.
- •
*Consistency with $k_{\mathrm{max}}$.* If ${\bm{K}}\succeq 0$, then ${\bm{K}}_{+}={\bm{K}}$ and $k_{+}^{(\mathcal{D})}$ agrees with $k_{\mathrm{max}}$ on $\mathcal{D}\times\mathcal{D}$.
- •
*Cost.* Each BO iteration involves (i) building the Gram matrix on $\mathcal{D}$,
(ii) inverting the Gram matrix to build the acquisition function, and
(iii) $m$ kernel evaluations when optimizing the acquisition function.
Step (ii) has the same cost as the SVD of ${\bm{K}}$ needed to compute both ${\bm{K}}_{+}$ and ${\bm{K}}_{+}^{\dagger}$, which makes $k_{+}^{(\mathcal{D})}$ having the same asymptotic per-iteration cost as $k_{\mathrm{avg}}$; its per-query evaluations are more expensive,
but this difference is negligible as long as we keep $m\lesssim n$. A concise complexity summary is provided in [Table 1](https://arxiv.org/html/2509.25051v1#S3.T1).
- •
*Regularity.* For finite groups, $k_{\mathrm{max}}$ is a max of finitely many smooth maps and is almost everywhere (a.e.) differentiable; the Nyström extension preserves a.e. differentiability in each argument. For continuous groups, smoothness can sometimes be obtained via closed-form formulas (e.g., as in [Example 3](https://arxiv.org/html/2509.25051v1#Thmtheorem3)).

We now illustrate the behavior of $k_{+}^{(\mathcal{D})}$ versus $k_{\mathrm{avg}}$ (in this situation, $k_{\mathrm{max}}$ is not PSD and the projection step is indeed needed to restore positive semidefiniteness).

###### Example 4 (Ackley function with $k_{+}$ ) .

[Figure 2](https://arxiv.org/html/2509.25051v1#S3.F2) compares $k_{+}^{(\mathcal{D})}$ and $k_{\mathrm{avg}}$
on the one-dimensional Ackley function (see ([15](https://arxiv.org/html/2509.25051v1#A5.E15))).
The projected kernel $k_{+}^{(\mathcal{D})}$ preserves the expected pairwise
symmetries (invariance along $x=y$ and $x=-y$) and spreads mass
more evenly across the symmetric regions, whereas $k_{\mathrm{avg}}$
concentrates covariance mostly near the origin.
Thus, $k_{+}^{(\mathcal{D})}$ better reflects the symmetry geometry
of the problem, echoing the qualitative difference observed
in [Example 3](https://arxiv.org/html/2509.25051v1#Thmtheorem3).

Figure: Figure 2: (Left) One-dimensional Ackley function ${f^{\star}}$ (see ([15](https://arxiv.org/html/2509.25051v1#A5.E15))), invariant up to sign flips, and GP posterior means $\mu_{t}(\bm{x})$ as in ([3](https://arxiv.org/html/2509.25051v1#S2.E3)) for $k_{+}^{(\mathcal{D})}$ (orange diamond) and $k_{\mathrm{avg}}$ (green circles) built from $\mathcal{D}$ (black crosses). (Center) Covariance structure induced by $k_{+}^{(\mathcal{D})}$. (Right) Covariance structure induced by $k_{\mathrm{avg}}$. Both kernels are invariant to reflections across $x=y$ and $x=-y$, but $k_{\mathrm{avg}}$ concentrates covariance near 0, while $k_{+}^{(\mathcal{D})}$ better reflects the underlying symmetry geometry. Consequently, the GP posterior mean induced by $k_{+}^{(\mathcal{D})}$ is the best at fitting the objective (left).
Refer to caption: rsc/Ackley_PostMean_kplus_kavg.png

Beyond the finite view (details in [Appendix C](https://arxiv.org/html/2509.25051v1#A3)).
The PSD projection with Nyström in [Equation 7](https://arxiv.org/html/2509.25051v1#S3.E7) is a practical,
data-dependent construction. It can be seen as the finite-sample face of a
broader, intrinsic definition that does not depend on $\mathcal{D}$. Since $k_{\mathrm{max}}$ is
symmetric, it admits a spectral decomposition
$k_{\mathrm{max}}(\bm{x},\bm{x}^{\prime})=\sum_{i}\lambda_{i}\phi_{i}(\bm{x})\phi_{i}(\bm{x}^{\prime})$ in $L^{2}$, and we can always define (a.e.)

$$ $k_{+}(\bm{x},\bm{x}^{\prime}):=\sum_{i}\max(0,\lambda_{i})\,\phi_{i}(\bm{x})\phi_{i}(\bm{x}^{\prime}),$ $$

with $k_{+}=k_{\mathrm{max}}$ whenever $k_{\mathrm{max}}$ is already PSD. On finite domains, this
precisely reduces to the matrix PSD projection in ([6](https://arxiv.org/html/2509.25051v1#S3.E6)). In
[Appendix C](https://arxiv.org/html/2509.25051v1#A3) we formalize the infinite-domain construction via integral
operators, prove that $k_{+}$ is $\mathcal{G}$-invariant, and show that the finite
projection $+$ Nyström in ([7](https://arxiv.org/html/2509.25051v1#S3.E7)) converges to $k_{+}$ at the
spectral (Hilbert-Schmidt) level under iid sampling ([Section C.3](https://arxiv.org/html/2509.25051v1#A3.SS3)).

Takeaway. $k_{\mathrm{max}}$ is the exact covariance of a natural class of $\mathcal{G}$-invariant GPs and induces a search geometry that preserves high-contrast orbit alignments ([Examples 3](https://arxiv.org/html/2509.25051v1#Thmtheorem3) and [4](https://arxiv.org/html/2509.25051v1#Thmtheorem4)). The PSD projection + Nyström step yields a valid GP kernel $k_{+}^{(\mathcal{D})}$ without introducing extra asymptotic complexity. We now measure its practical impact in [Section 4](https://arxiv.org/html/2509.25051v1#S4).

###### Example 4 (Ackley function with k + k_{+} ) .

## 4 Experiments

We evaluate $k_{+}^{(\mathcal{D})}$ against two baselines: (i) the off-the-shelf kernel $k_{\mathrm{b}}$ (no symmetry handling), and (ii) the orbit-averaged kernel $k_{\mathrm{avg}}$ (Brown et al., 2024). Benchmarks include standard synthetic objectives and a real-world wireless design task with known invariances. We ask: *(Q1) Does $k_{+}^{(\mathcal{D})}$ reduce simple/cumulative regret vs. $k_{\mathrm{avg}}$?* and *(Q2) How does performance scale with the size of the symmetry group and dimension?* Experimental details are in [Appendix E](https://arxiv.org/html/2509.25051v1#A5).

**Table 2: Performance of $k_{\mathrm{b}}$, $k_{\mathrm{avg}}$, and $k_{+}^{(\mathcal{D})}$ across benchmarks. For each kernel $k\in\{k_{\mathrm{b}},k_{\mathrm{avg}},k_{+}^{(\mathcal{D})}\}$ we report $m\pm s_{\text{err}}$, where $m$ is the empirical mean over 10 seeds (lower is better) and $s_{\text{err}}$ is the empirical standard error. Best mean is bold; means $m$ whose 95% confidence interval ($m\pm 1.96s_{\text{err}}$) confidence interval overlap with the best are underlined. Performance is measured by cumulative regret on synthetic benchmarks and by negated simple reward on real-world experiments.**
| Benchmark | $|\mathcal{G}|$ | $k_{\mathrm{b}}$ | $k_{\mathrm{avg}}$ | $k_{+}^{(\mathcal{D})}$ |
| --- | --- | --- | --- | --- |
| Synthetic (Cumulative Reg.) |  |  |  |  |
| Ackley2d | $8$ | $382.7\pm 5.7$ | $128.2\pm 10.4$ | $\mathbf{126.4\pm 3.6}$ |
| Griewank6d | $64$ | $3840.3\pm 177.7$ | $3067.4\pm 841.9$ | $\mathbf{1832.6\pm 146.3}$ |
| Rastrigin5d | $3,840$ | $3568.5\pm 91.3$ | $1583.5\pm 341.9$ | $\mathbf{813.4\pm 70.6}$ |
| Radial2d | $\infty$ | $388.6\pm 20.3$ | $480.9\pm 76.4$ | $\mathbf{199.7\pm 11.6}$ |
| Scaling2d | $\infty$ | $1820.6\pm 1135.4$ | $3361.8\pm 742.9$ | $\mathbf{25.4\pm 6.4}$ |
| Real-World (Neg. Simple Rew.) |  |  |  |  |
| WLAN8d | $24$ | $-65.0\pm 3.2$ | $-51.8\pm 1.7$ | $\mathbf{-74.4\pm 0.7}$ |

Figure: Figure 3: Cumulative regret and negated simple reward under GP-UCB with $k_{\mathrm{b}}$ (blue crosses), $k_{\mathrm{avg}}$ (orange diamonds), and $k_{+}^{(\mathcal{D})}$ (green circles). Shaded areas: standard error over 10 seeds.
Refer to caption: rsc/CumReg_Ackley2.png

Headline: $k_{+}^{(\mathcal{D})}$ wins on every task.
Across all benchmarks ([Table 2](https://arxiv.org/html/2509.25051v1#S4.T2)), $k_{+}^{(\mathcal{D})}$ achieves the best mean performance with up to 50% of improvement. This answers Q1 positively. Regarding Q2, we will see that as the group size increases, $k_{+}^{(\mathcal{D})}$ stays strong, while $k_{\mathrm{avg}}$ degrades and can even underperform the non-invariant base kernel $k_{\mathrm{b}}$.

Setup in one glance.
We run GP-UCB with each kernel $k\in\{k_{\mathrm{b}},k_{\mathrm{avg}},k_{+}^{(\mathcal{D})}\}$, using the same acquisition and optimization budgets. We report results averaged over 10 seeds. Synthetic objectives span $d\in\{2,\dots,6\}$ and symmetry sizes from $|\mathcal{G}|=8$ up to continuous groups ($|\mathcal{G}|=\infty$). The real-world task is an 8-dimensional AP-placement problem invariant to AP permutations ([Section 4.2](https://arxiv.org/html/2509.25051v1#S4.SS2)). Hyperparameters and group actions are detailed in [Appendix E](https://arxiv.org/html/2509.25051v1#A5).

### 4.1 Synthetic Benchmarks

We consider synthetic functions ${f^{\star}}$ (Ackley, Griewank, Rastrigin, etc.) that exhibit symmetries and are classically considered as challenging to optimize in the BO literature (Qian et al., 2021; Bardou et al., 2024). We cover dimensions $d=2$ to $d=6$ and group sizes $|\mathcal{G}|=8$ to $|\mathcal{G}|=\infty$. We evaluate performance using the cumulative regret $R_{T}=\sum_{i=1}^{T}\big({f^{\star}}(\bm{x}^{*})-{f^{\star}}(\bm{x}_{t})\big)$ since the global maximizer $\bm{x}^{*}=\operatorname*{arg\,max}_{\bm{x}\in\mathcal{S}}{f^{\star}}(\bm{x})$ is known.

Finite groups: the gap widens as $|\mathcal{G}|$ grows.
With Matérn-5/2 base $k_{\mathrm{b}}$ on Ackley2d ($|\mathcal{G}|{=}8$), $k_{\mathrm{avg}}$ and $k_{+}^{(\mathcal{D})}$ are tied; both dominate $k_{\mathrm{b}}$.
As $|\mathcal{G}|$ increases (Griewank6d, $|\mathcal{G}|{=}64$; Rastrigin5d, $|\mathcal{G}|{=}3{,}840$), $k_{+}^{(\mathcal{D})}$ increasingly outperforms $k_{\mathrm{avg}}$ achieving cumulative regrets that are, on average, $40\%$ and $49\%$ lower respectively ([Table 2](https://arxiv.org/html/2509.25051v1#S4.T2) and [Figure 3](https://arxiv.org/html/2509.25051v1#S4.F3), top panels).

Continuous groups: $k_{\mathrm{avg}}$ can underperform even $k_{\mathrm{b}}$.
For radial and scaling invariances (continuous groups; RBF base), $k_{\mathrm{avg}}$ degrades relative to $k_{\mathrm{b}}$, while $k_{+}^{(\mathcal{D})}$ remains strong ([Figure 3](https://arxiv.org/html/2509.25051v1#S4.F3), bottom left).

### 4.2 Wireless Network Design

A wireless network (WN) consists of $m$ access points (APs) deployed over a given area to provide Internet connectivity to $p$ users. Since the quality of service (QoS) of each AP is degraded by interference from neighboring APs, determining optimal AP placement is a central challenge in WN design (Wang et al., 2020). In this benchmark, we use a simulator that, given $p$ users and $m$ APs placed on a surface $\mathcal{A}$, evaluates the resulting QoS (see [Appendix E](https://arxiv.org/html/2509.25051v1#A5) for details). The optimization task is therefore to determine the positions of $m$ APs on a two-dimensional surface, yielding the $2m$-dimensional search space $\mathcal{S}=\mathcal{A}^{m}$. Because all APs are identical, the QoS function is naturally invariant under permutations of their positions. We use a Matérn-3/2 base $k_{\mathrm{b}}$ to better capture threshold effects in the objective induced by AP-user associations (Bardou and Begin, 2022). Performance is evaluated using the negated best reward $\min_{t\in[T]}-{f^{\star}}(\bm{x}_{t})$ attained during optimization (the regret cannot be computed because the max of ${f^{\star}}$ is unknown), since the goal is to assess the quality of the best network configuration discovered by the optimizer, rather than the cumulative negative reward across all explored configurations.

$k_{+}^{(\mathcal{D})}$ finds better network configurations. In the AP-placement task with $p=16$ users and $m=4$ APs ($d=8,|\mathcal{G}|=24$ permutations), $k_{+}^{(\mathcal{D})}$ consistently discovers higher-throughput configurations than both $k_{\mathrm{avg}}$ and $k_{\mathrm{b}}$ ([Figure 3](https://arxiv.org/html/2509.25051v1#S4.F3), bottom right; [Figure 5](https://arxiv.org/html/2509.25051v1#A5.F5) in [Appendix E](https://arxiv.org/html/2509.25051v1#A5) contains the resulting network configuration).

### 4.3 Robustness to Group Size

Both synthetic and real-world benchmarks suggest that $k_{\mathrm{avg}}$ performs comparably to $k_{+}^{(\mathcal{D})}$ when the group size $|\mathcal{G}|$ is small, but its performance deteriorates as $|\mathcal{G}|$ grows, whereas $k_{+}^{(\mathcal{D})}$ remains stable. To investigate this effect more systematically, we conduct additional experiments on the $d$-dimensional Ackley and Rastrigin benchmarks, each invariant under the hyperoctahedral group $\mathcal{G}$ of size $|\mathcal{G}|=2^{d}d!$. We compare the average regret of $k_{\mathrm{avg}}$ and $k_{+}^{(\mathcal{D})}$ after 50 iterations of GP-UCB for $d=1,\dots,5$, and include $k_{\mathrm{b}}$ as a baseline to control for the effect of increasing dimensionality.

Figure: Figure 4: Left column: Average regret $R_{T}/T$ for $k_{\mathrm{b}}$ (blue crosses), $k_{\mathrm{avg}}$ (orange diamonds), and $k_{+}^{(\mathcal{D})}$ (green circles) on Ackley (top) and Rastrigin (bottom), averaged over 10 seeds with standard error bars. Middle and right columns: Empirical eigendecays under different bases and groups (ordered, normalized eigenvalues of the Gram matrix).
Refer to caption: rsc/Perf_wrt_Symmetries_Ackley.png

The results are shown in
[Figure 4](https://arxiv.org/html/2509.25051v1#S4.F4) (left column)
. Both experiments reveal the same trend: while $k_{\mathrm{avg}}$ consistently outperforms $k_{\mathrm{b}}$, its performance also deteriorates as $|\mathcal{G}|$ increases. In contrast, $k_{+}^{(\mathcal{D})}$ remains largely unaffected by the growing number of symmetries, demonstrating a clear robustness to group size. In the next section, we discuss several explanations for these empirical observations.

Takeaway.
$k_{+}^{(\mathcal{D})}$ consistently matches or outperforms $k_{\mathrm{avg}}$ and $k_{\mathrm{b}}$, with the largest gains at large $|\mathcal{G}|$. The evidence suggests that (i) *how* a kernel encodes orbit alignments matters as much as *whether* it is invariant, and (ii) averaging across many alignments can dilute informative similarities. These themes reconnect with our discussion in [Section 5](https://arxiv.org/html/2509.25051v1#S5) and motivate analyses beyond eigendecay rates.

## 5 Spectral Analysis and Regret Bounds

So far, $k_{+}^{(\mathcal{D})}$ has shown consistently lower regret than $k_{\mathrm{avg}}$, despite comparable
computational cost. A natural question is: *can existing BO theory account for such a gap?*
Current regret bounds for GP surrogates proceed via the information gain, which is shaped by the decay of the operator spectrum of the kernel. In particular, faster spectral decay leads to tighter regret upper bounds in standard analyses
(Srinivas et al., 2012; Valko et al., 2013; Scarlett et al., 2017; Whitehouse et al., 2023).
We now compare the eigendecay of $k_{+}^{(\mathcal{D})}$ and $k_{\mathrm{avg}}$, and ask whether it can
explain the empirical gap.

Empirical eigendecays: similar or *faster* decay for $k_{\mathrm{avg}}$.
Across our benchmarks, the empirical spectra of $k_{+}^{(\mathcal{D})}$ and $k_{\mathrm{avg}}$ exhibit very similar
log–log slopes (decay rates). In several settings, $k_{\mathrm{avg}}$’s eigenvalues decay even
*faster* than those of $k_{+}$; see
[Figure 4](https://arxiv.org/html/2509.25051v1#S4.F4) (middle and right columns).
Under the usual theory, this would translate into similar, or potentially *tighter*, upper
bounds for methods run with $k_{\mathrm{avg}}$ compared to those with $k_{+}^{(\mathcal{D})}$. A more detailed discussion of the empirical spectra in
[Figure 4](https://arxiv.org/html/2509.25051v1#S4.F4)
and further insights are in [Appendix D](https://arxiv.org/html/2509.25051v1#A4).

Limitations of eigendecay as an explanation.
Since $k_{\mathrm{avg}}$ matches or exceeds $k_{+}^{(\mathcal{D})}$ in empirical decay rate, standard theory would predict similar or better regret upper bounds. Yet in practice we consistently observe lower regret for $k_{+}^{(\mathcal{D})}$ ([Section 4](https://arxiv.org/html/2509.25051v1#S4)). This suggests that eigendecay alone does not capture the structural advantages of $k_{+}^{(\mathcal{D})}$. We outline possible explanations in the conclusion.

## 6 Conclusion

Our spectral analysis highlights a gap between theory and practice: although $k_{\mathrm{avg}}$ often
exhibits *faster* empirical eigendecay than $k_{+}^{(\mathcal{D})}$, the latter consistently
achieves lower regret. Standard eigendecay arguments thus fail to explain the observed advantage
of $k_{+}^{(\mathcal{D})}$.

We hypothesize two complementary explanations.
First, geometry vs. rates: eigendecay quantifies how fast spectra shrink but ignores
*which* eigenfunctions are emphasized. In practice, $k_{\mathrm{avg}}$ often introduces
*similarity reversals*, distorting the search geometry
([Figure 1](https://arxiv.org/html/2509.25051v1#S3.F1)), whereas $k_{+}^{(\mathcal{D})}$ preserves high-contrast alignments between orbits, inherited from $k_{\mathrm{max}}$.
Second, approximation hardness: BO theory typically assumes that the black-box
${f^{\star}}$ lies in the RKHS $\mathcal{H}_{k}$ of the chosen kernel $k$. Existing work on
*misspecification* (Bogunovic and Krause, 2021) shows that the cumulative regret can be bounded from below by a linear term that involves the distance between ${f^{\star}}$ and $\mathcal{H}_{k}$. Yet even when this distance is zero,
different kernels may yield very different approximation rates, affecting how quickly BO can optimize ${f^{\star}}$. This distinction matters: in our experiments with the RBF kernel as $k_{\mathrm{b}}$ ([Section 4](https://arxiv.org/html/2509.25051v1#S4)), $\mathcal{H}_{k_{\mathrm{b}}}$ is universal (property of the RBF kernel, see Micchelli et al. (2006)),
hence invariant functions ${f^{\star}}$ always lie in $\mathcal{H}_{k_{\mathrm{avg}}}$ (consider $(Pf)(\bm{x})=\sum_{g\in\mathcal{G}}f({g\bm{x}})/|\mathcal{G}|$ the projection onto $\mathcal{H}_{k_{\mathrm{avg}}}$ (Brown et al., 2024, Appendix A) and observe that if $f_{n}\to{f^{\star}}$ with $f_{n}\in\mathcal{H}_{k_{\mathrm{b}}}$ then $Pf_{n}\to{f^{\star}}$ with $Pf_{n}\in\mathcal{H}_{k_{\mathrm{avg}}}$). There is no
misspecification in the sense of Bogunovic and Krause (2021) since $d({f^{\star}},\mathcal{H}_{k_{\mathrm{avg}}})=0$, yet $k_{\mathrm{avg}}$ still performs
worse than $k_{+}^{(\mathcal{D})}$. This suggests that ${f^{\star}}$ is simply *harder to approximate*
in $\mathcal{H}_{k_{\mathrm{avg}}}$ than in $\mathcal{H}_{k_{\mathrm{max}}}$.
A plausible reason why
Brown et al. (2024) report strong performance for
$k_{\mathrm{avg}}$ is that they focus on functions that are explicit linear combinations
of relatively few $k_{\mathrm{avg}}(\bm{x}_{t},\cdot)$ atoms (between $64$ and $512$, depending
on dimension; see their Appendix B.1). In such settings, $k_{\mathrm{avg}}$ looks very effective since its GP posterior mean can in principle
recover the function exactly once those $x_{t}$ are sampled. Typical BO objectives do not share this structure, which
may explain why in our experiments $k_{\mathrm{avg}}$ sometimes underperforms even the
base kernel, while $k_{+}^{(\mathcal{D})}$ remains more reliable. Developing regret bounds that also measure *approximation hardness*, capturing both the distance to $\mathcal{H}_{k}$ and approximation rates, seems a promising way to obtain guarantees that align more closely with empirical performance.

Finally, while our focus has been empirical, we note that the intrinsic data-independent version of $k_{+}^{(\mathcal{D})}$, which we called $k_{+}$ and which we mentioned at the end of [Section 3.2](https://arxiv.org/html/2509.25051v1#S3.SS2) (introduced formally in [Appendix C](https://arxiv.org/html/2509.25051v1#A3)), provides a natural, data-independent analogue of the practical kernel $k_{+}^{(\mathcal{D})}$. We see $k_{+}$ as a convenient object for future theoretical work, as it cleanly isolates the PSD projection of $k_{\mathrm{max}}$ from the additional data dependence introduced by Nyström. We believe that it makes $k_{+}$ a convenient starting point for any future theoretical work, in the same spirit as gradient flow serving as an idealized analogue of gradient descent.

#### Acknowledgments

This work was supported in part by the Swiss State Secretariat for Education, Research and Innovation (SERI) under contract number MB22.00027.

## References

- Baird et al. (2023)
Sterling G. Baird, Jason R. Hall, and Taylor D. Sparks.
Compactness matters: Improving bayesian optimization efficiency of materials formulations through invariant search spaces.
*Computational Materials Science*, 224:112134, 2023.
ISSN 0927-0256.
doi: https://doi.org/10.1016/j.commatsci.2023.112134.
- Balandat et al. (2020)
Maximilian Balandat, Brian Karrer, Daniel Jiang, Samuel Daulton, Ben Letham, Andrew G Wilson, and Eytan Bakshy.
Botorch: A framework for efficient monte-carlo bayesian optimization.
*Advances in neural information processing systems*, 33:21524–21538, 2020.
- Bardou and Begin (2022)
Anthony Bardou and Thomas Begin.
Inspire: Distributed bayesian optimization for improving spatial reuse in dense wlans.
In *Proceedings of the 25th International ACM Conference on Modeling Analysis and Simulation of Wireless and Mobile Systems*, pages 133–142, 2022.
- Bardou et al. (2024)
Anthony Bardou, Patrick Thiran, and Giovanni Ranieri.
This too shall pass: Removing stale observations in dynamic bayesian optimization.
*Advances in Neural Information Processing Systems*, 37:42696–42737, 2024.
- Bhatia and Elsner (1994)
Rajendra Bhatia and Ludwig Elsner.
The hoffman-wielandt inequality in infinite dimensions.
*Proceedings of the Indian Academy of Sciences – Mathematical Sciences*, 104(4):483–494, Aug 1994.
doi: 10.1007/BF02867116.
URL [https://link.springer.com/article/10.1007/BF02867116](https://link.springer.com/article/10.1007/BF02867116).
- Bogunovic and Krause (2021)
Ilija Bogunovic and Andreas Krause.
Misspecified gaussian process bandit optimization.
*Advances in neural information processing systems*, 34:3004–3015, 2021.
- Brown et al. (2024)
Theodore Brown, Alexandru Cioba, and Ilija Bogunovic.
Sample-efficient bayesian optimisation using known invariances.
In *Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 - 15, 2024*, 2024.
- Chen et al. (2009)
Yihua Chen, Maya R Gupta, and Benjamin Recht.
Learning kernels from indefinite similarities.
In *Proceedings of the 26th Annual International Conference on Machine Learning*, pages 145–152, 2009.
- Conway (2007)
John B. Conway.
*A Course in Functional Analysis*, volume 96 of *Graduate Texts in Mathematics*.
Springer, 2007.
ISBN 978-1-4757-4383-8.
doi: 10.1007/978-1-4757-4383-8.
- Curtin et al. (2013)
Ryan R Curtin, Parikshit Ram, and Alexander G Gray.
Fast exact max-kernel search.
In *Proceedings of the 2013 SIAM International Conference on Data Mining*, pages 1–9. SIAM, 2013.
- Fröhlich et al. (2005)
Holger Fröhlich, Jörg K Wegner, Florian Sieker, and Andreas Zell.
Optimal assignment kernels for attributed molecular graphs.
In *Proceedings of the 22nd international conference on Machine learning*, pages 225–232, 2005.
- Garnett (2023)
Roman Garnett.
*Bayesian optimization*.
Cambridge University Press, 2023.
- Gärtner (2003)
Thomas Gärtner.
A survey of kernels for structured data.
*ACM SIGKDD explorations newsletter*, 5(1):49–58, 2003.
- Ginsbourger et al. (2012)
David Ginsbourger, Xavier Bay, Olivier Roustant, and Laurent Carraro.
Argumentwise invariant kernels for the approximation of invariant functions.
*Ann. Fac. Sci. Toulouse Math. (6)*, 21(3):501–527, 2012.
ISSN 0240-2963,2258-7519.
doi: 10.5802/afst.1343.
URL [https://doi.org/10.5802/afst.1343](https://doi.org/10.5802/afst.1343).
- Glielmo et al. (2017)
Aldo Glielmo, Peter Sollich, and Alessandro De Vita.
Accurate interatomic force fields via machine learning with covariant kernels.
*Physical Review B*, 95(21):214302, 2017.
- Higham (1988)
Nicholas J. Higham.
Computing a nearest symmetric positive semidefinite matrix.
*Linear Algebra and its Applications*, 103:103–118, 1988.
ISSN 0024-3795.
doi: https://doi.org/10.1016/0024-3795(88)90223-6.
URL [https://www.sciencedirect.com/science/article/pii/0024379588902236](https://www.sciencedirect.com/science/article/pii/0024379588902236).
- Jones et al. (1998)
Donald R Jones, Matthias Schonlau, and William J Welch.
Efficient global optimization of expensive black-box functions.
*Journal of Global optimization*, 13(4):455–492, 1998.
- Kim et al. (2021)
Jungtaek Kim, Michael McCourt, Tackgeun You, Saehoon Kim, and Seungjin Choi.
Bayesian optimization with approximate set kernels.
*Machine Learning*, 110(5):857–879, 2021.
- Koltchinskii and Giné (2000)
Vladimir Koltchinskii and Evarist Giné.
Random matrix approximation of spectra of integral operators.
*Bernoulli*, 6(1):113–167, 2000.
ISSN 1350-7265,1573-9759.
doi: 10.2307/3318636.
URL [https://doi.org/10.2307/3318636](https://doi.org/10.2307/3318636).
- Kondor (2008)
Risi Kondor.
*Group theoretical methods in machine learning*.
PhD thesis, Columbia University, 2008.
URL [https://people.cs.uchicago.edu/~risi/papers/KondorThesis.pdf](https://people.cs.uchicago.edu/~risi/papers/KondorThesis.pdf).
Ph.D. thesis.
- Krizhevsky et al. (2012)
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.
Imagenet classification with deep convolutional neural networks.
In F. Pereira, C.J. Burges, L. Bottou, and K.Q. Weinberger, editors, *Advances in Neural Information Processing Systems*, volume 25. Curran Associates, Inc., 2012.
URL [https://proceedings.neurips.cc/paper_files/paper/2012/file/c399862d3b9d6b76c8436e924a68c45b-Paper.pdf](https://proceedings.neurips.cc/paper_files/paper/2012/file/c399862d3b9d6b76c8436e924a68c45b-Paper.pdf).
- Luss and D' aspremont (2007)
Ronny Luss and Alexandre D' aspremont.
Support vector machine classification with indefinite kernels.
In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, *Advances in Neural Information Processing Systems*, volume 20. Curran Associates, Inc., 2007.
URL [https://proceedings.neurips.cc/paper_files/paper/2007/file/c0c7c76d30bd3dcaefc96f40275bdc0a-Paper.pdf](https://proceedings.neurips.cc/paper_files/paper/2007/file/c0c7c76d30bd3dcaefc96f40275bdc0a-Paper.pdf).
- Micchelli et al. (2006)
Charles A Micchelli, Yuesheng Xu, and Haizhang Zhang.
Universal kernels.
*Journal of Machine Learning Research*, 7(12), 2006.
- Oglic and Gärtner (2018)
Dino Oglic and Thomas Gärtner.
Learning in reproducing kernel kreın spaces.
In *International conference on machine learning*, pages 3859–3867. PMLR, 2018.
- Ong et al. (2004)
Cheng Soon Ong, Xavier Mary, Stéphane Canu, and Alexander J Smola.
Learning with non-positive kernels.
In *Proceedings of the twenty-first international conference on Machine learning*, page 81, 2004.
- Petersen (2006)
Peter Petersen.
*Riemannian geometry*, volume 171.
Springer, 2006.
- Qian et al. (2021)
Chao Qian, Hang Xiong, and Ke Xue.
Bayesian optimization using pseudo-points.
In *Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence*, pages 3044–3050, 2021.
- Rasmussen and Williams (2006)
Carl Edward Rasmussen and Christopher K. I. Williams.
*Gaussian processes for machine learning*.
Adaptive Computation and Machine Learning. MIT Press, Cambridge, MA, 2006.
ISBN 978-0-262-18253-9.
- Reed and Simon (1972)
Michael Reed and Barry Simon.
Vi - bounded operators.
In *Methods of Modern Mathematical Physics*, pages 182–220. Academic Press, 1972.
ISBN 978-0-12-585001-8.
doi: https://doi.org/10.1016/B978-0-12-585001-8.50012-X.
URL [https://www.sciencedirect.com/science/article/pii/B978012585001850012X](https://www.sciencedirect.com/science/article/pii/B978012585001850012X).
- Scarlett et al. (2017)
Jonathan Scarlett, Ilija Bogunovic, and Volkan Cevher.
Lower bounds on regret for noisy gaussian process bandit optimization.
In *Conference on Learning Theory*, pages 1723–1742. PMLR, 2017.
- Srinivas et al. (2012)
Niranjan Srinivas, Andreas Krause, Sham M. Kakade, and Matthias W. Seeger.
Information-theoretic regret bounds for gaussian process optimization in the bandit setting.
*IEEE Transactions on Information Theory*, 58(5):3250–3265, 2012.
doi: doi:10.1109/tit.2011.2182033.
- Valko et al. (2013)
Michal Valko, Nathaniel Korda, Rémi Munos, Ilias Flaounas, and Nelo Cristianini.
Finite-time analysis of kernelised contextual bandits.
*arXiv preprint arXiv:1309.6869*, 2013.
- Vishwanathan et al. (2003)
SVN Vishwanathan, Alexander J Smola, et al.
Fast kernels for string and tree matching.
*Advances in neural information processing systems*, 15:569–576, 2003.
- Wang et al. (2020)
Jingjing Wang, Chunxiao Jiang, Haijun Zhang, Yong Ren, Kwang-Cheng Chen, and Lajos Hanzo.
Thirty years of machine learning: The road to pareto-optimal wireless networks.
*IEEE Communications Surveys & Tutorials*, 22(3):1472–1514, 2020.
- Whitehouse et al. (2023)
Justin Whitehouse, Aaditya Ramdas, and Steven Z Wu.
On the sublinear regret of gp-ucb.
*Advances in Neural Information Processing Systems*, 36:35266–35276, 2023.
- Williams and Seeger (2000)
Christopher Williams and Matthias Seeger.
Using the nyström method to speed up kernel machines.
In T. Leen, T. Dietterich, and V. Tresp, editors, *Advances in Neural Information Processing Systems*, volume 13. MIT Press, 2000.
URL [https://proceedings.neurips.cc/paper_files/paper/2000/file/19de10adbaa1b2ee13f77f679fa1483a-Paper.pdf](https://proceedings.neurips.cc/paper_files/paper/2000/file/19de10adbaa1b2ee13f77f679fa1483a-Paper.pdf).
- Zhang (2010)
Ziming Zhang.
*Maximum Similarity Based Feature Matching and Adaptive Multiple Kernel Learning for Object Recognition*.
PhD thesis, Simon Fraser University, 2010.
PhD thesis.

## Appendix A Proofs for Section 3

### A.1 Full statement and proof of Proposition 1

We state [Proposition 1](https://arxiv.org/html/2509.25051v1#Thmtheorem1) formally and give a slightly more detailed proof.

###### Proposition 5 (Max-kernel covariance for invariant GPs) .

Let $\mathcal{S},\mathcal{S}_{h}\subset\mathbb{R}^{d}$ be measurable spaces and let a (finite or compact) group $\mathcal{G}$ act measurably on $\mathcal{S}$.
Let $h\sim\mathcal{GP}(0,k_{\mathrm{b}})$ be a GP on $\mathcal{S}_{h}$ with an isotropic base kernel $k_{\mathrm{b}}:(\bm{x},\bm{x}^{\prime})\in\mathcal{S}\times\mathcal{S}\mapsto\kappa(\|\bm{x}-\bm{x}^{\prime}\|_{2})$ where $\kappa:\mathbb{R}_{\geq 0}\to\mathbb{R}_{\geq 0}$ is nonincreasing.
Assume there exists $\phi_{\mathcal{G}}:\mathcal{S}\to\mathcal{S}_{h}$ satisfying (i) *invariance:* $\phi_{\mathcal{G}}(\bm{x})=\phi_{\mathcal{G}}({g\bm{x}})$ for all $g\in\mathcal{G},\bm{x}\in\mathcal{S}$; and
(ii) *minimal-distance representativity:* $\|\phi_{\mathcal{G}}(\bm{x})-\phi_{\mathcal{G}}(\bm{x}^{\prime})\|_{2}=\min_{g,g^{\prime}\in\mathcal{G}}\|{g\bm{x}}-{g^{\prime}\bm{x}^{\prime}}\|_{2}$.
Define $f(\bm{x})=h(\phi_{\mathcal{G}}(\bm{x}))$. Then $f\sim\mathcal{GP}(0,k_{\mathrm{max}})$ and it is $\mathcal{G}$-invariant.

###### Proof.

Since $g$ is a GP, $f$ is also a GP, and invariance follows from (i). Its covariance kernel is $k_{\mathrm{max}}$ since:

$$ $\displaystyle\mathrm{Cov}\left[f(\bm{x}),f(\bm{x}^{\prime})\right]$ $\displaystyle=\mathrm{Cov}\left[h(\phi_{\mathcal{G}}(\bm{x})),h(\phi_{\mathcal{G}}(\bm{x}^{\prime}))\right]$ $\displaystyle=k_{\mathrm{b}}(\phi_{\mathcal{G}}(\bm{x}),\phi_{\mathcal{G}}(\bm{x}^{\prime}))$ $\displaystyle=\kappa(\min_{g,g^{\prime}\in\mathcal{G}}||{g\bm{x}}-{g^{\prime}\bm{x}^{\prime}}||_{2})$ (8) $\displaystyle=\max_{g,g^{\prime}\in\mathcal{G}}\kappa(||g\bm{x}-g^{\prime}\bm{x}^{\prime}||_{2})$ (9) $\displaystyle=k_{\mathrm{max}}(\bm{x},\bm{x}^{\prime})$ (10) $$

where we used (ii) in [Equation 8](https://arxiv.org/html/2509.25051v1#A1.E8), and monotonicity of $\kappa$ in [Equation 9](https://arxiv.org/html/2509.25051v1#A1.E9). Note that compactness of $G$ guarantees that the minimum in (ii) is indeed achieved, which makes [Equation 9](https://arxiv.org/html/2509.25051v1#A1.E9) true even when $\kappa$ is not necessarily continuous.
∎

###### Proposition 5 (Max-kernel covariance for invariant GPs) .

###### Proof.

### A.2 Averaging vs Maximization with Different Base Kernels

We extend [Lemma 2](https://arxiv.org/html/2509.25051v1#Thmtheorem2) to the case where
$k_{\mathrm{avg}}$ and $k_{\mathrm{max}}$ are built from *different* base kernels.
The result shows that even in this more flexible setting, the coincidence of $k_{\mathrm{avg}}$ and $k_{\mathrm{max}}$ can only occur in degenerate situations.

###### Lemma 6 .

Let $k_{\mathrm{b}}$ and $k_{\mathrm{b}}^{\prime}$ be two base kernels such that
$\|k_{\mathrm{b}}\|_{\infty}=\|k_{\mathrm{b}}^{\prime}\|_{\infty}=1$ and $k_{\mathrm{b}}^{\prime}(\bm{x},\bm{x})=1$ for all $\bm{x}$.
Let $k_{\mathrm{avg}}$ be the group-averaged kernel built from $k_{\mathrm{b}}$ and $k_{\mathrm{max}}$ be the maximization kernel built from $k_{\mathrm{b}}^{\prime}$.
It holds

$$ $k_{\mathrm{avg}}=k_{\mathrm{max}}\quad\text{on the orbit }\mathcal{O}(\bm{x},{g\bm{x}}):=\{({h\bm{x}},{h^{\prime}{g\bm{x}}}),\;h,h^{\prime}\in\mathcal{G}\}$ $$

for every $\bm{x}\in\mathcal{X}$ and $g\in\mathcal{G}$,
if and only if

$$ $k_{\mathrm{b}}(\bm{x},{g\bm{x}})=k_{\mathrm{max}}(\bm{x},{g\bm{x}})=1\quad\text{for every $\bm{x}$ and $g\in\mathcal{G}$}.$ $$

In particular, this forces $k_{\mathrm{b}}$ to already exhibit a form of $\mathcal{G}$-invariance on pairs $(\bm{x},{g\bm{x}})$.

###### Proof.

($\Rightarrow$)
Fix $\bm{x}$ and $g\in\mathcal{G}$. Since by assumption $k_{\mathrm{b}}^{\prime}$ is bounded by $1$ and $k_{\mathrm{b}}^{\prime}(\bm{x},\bm{x})=1$:

$$ $1\geq k_{\mathrm{max}}(\bm{x},{g\bm{x}})=\max_{h,h^{\prime}\in\mathcal{G}}k_{\mathrm{b}}^{\prime}({h\bm{x}},{h^{\prime}{g\bm{x}}})\geq k_{\mathrm{b}}^{\prime}(\bm{x},\bm{x})=1$ $$

so $k_{\mathrm{max}}(\bm{x},{g\bm{x}})=1$.

Now consider $k_{\mathrm{avg}}$. By definition,

$$ $k_{\mathrm{avg}}(\bm{x},{g\bm{x}})=\frac{1}{|\mathcal{G}|^{2}}\sum_{h,h^{\prime}\in\mathcal{G}}k_{\mathrm{b}}({h\bm{x}},{h^{\prime}{g\bm{x}}}).$ $$

Each summand is bounded by $1$ and the average is equal to $1$ as $k_{\mathrm{avg}}(\bm{x},{g\bm{x}})=k_{\mathrm{max}}(\bm{x},{g\bm{x}})=1$. Therefore each term is equal to $1$, which proves $k_{\mathrm{b}}=k_{\mathrm{max}}=1$ on $\mathcal{O}(\bm{x},{g\bm{x}})$. As this is true for every $\bm{x},g\in\mathcal{G}$, this shows the result. The converse is immediate.
∎

This shows that even when allowing different base kernels for $k_{\mathrm{avg}}$ and $k_{\mathrm{max}}$, equality between the two kernels requires $k_{\mathrm{b}}$ to already be argumentwise $\mathcal{G}$-invariant on pairs $(\bm{x},{g\bm{x}})$. This fails for standard choices (e.g. RBF kernels with translation or rotation groups), so averaging cannot replicate maximization in practice.

###### Lemma 6 .

###### Proof.

## Appendix B Radial invariance: closed form for k avg k_{\mathrm{avg}}

We prove the formulas provided in [Example 3](https://arxiv.org/html/2509.25051v1#Thmtheorem3).
Let $\mathcal{G}=\mathrm{SO}(2)$ act on $\mathbb{R}^{2}$ by in-plane rotations, and let $k_{\mathrm{b}}$ be the RBF kernel with lengthscale $l$:
$k_{\mathrm{b}}(\bm{x},\bm{x}^{\prime})=\exp\!\big(-\|\bm{x}-\bm{x}^{\prime}\|_{2}^{2}/(2l^{2})\big)$. Writing $\bm{x}=(r,\theta)$ and $\bm{x}^{\prime}=(s,\varphi)$ in polar coordinates, we have

$$ $k_{\mathrm{avg}}(\bm{x},\bm{x}^{\prime})=\frac{1}{(2\pi)^{2}}\int_{0}^{2\pi}\!\!\int_{0}^{2\pi}\exp\!\Big(-\tfrac{r^{2}+s^{2}-2rs\cos(\theta-\varphi+\alpha-\beta)}{2l^{2}}\Big)\,d\alpha\,d\beta.$ $$

Integrating out the absolute angle and keeping only the relative angle $\psi=\theta-\varphi+\alpha-\beta$ yields

$$ $k_{\mathrm{avg}}(\bm{x},\bm{x}^{\prime})=\exp\!\left(-\tfrac{r^{2}+s^{2}}{2l^{2}}\right)\cdot\frac{1}{2\pi}\int_{0}^{2\pi}\exp\!\left(\tfrac{rs}{l^{2}}\cos\psi\right)\,d\psi=\exp\!\left(-\tfrac{r^{2}+s^{2}}{2l^{2}}\right)I_{0}\!\left(\tfrac{rs}{l^{2}}\right),$ $$

where $I_{0}(z)=\tfrac{1}{2\pi}\int_{0}^{2\pi}e^{z\cos\psi}\,d\psi$ is the modified Bessel function of order 0.

## Appendix C An intrinsic PSD projection k + \,k_{+}\, and its properties

In the main text we defined a *data-dependent* kernel $k_{+}^{(\mathcal{D})}$, corresponding to a PSD projection of $k_{\mathrm{max}}$ on a finite set of samples $\mathcal{D}$, extended by Nyström. This finite-sample construction $k_{+}^{(\mathcal{D})}$ is the star of the show in practice (as it is convenient to compute, and shows strong performance in practice). However, its data-dependence might make theoretical analysis quite involved. In this appendix, we show that $k_{+}^{(\mathcal{D})}$ is the finite-sample facet of a broader, intrinsic *data-independent* PSD projection $k_{+}$ of $k_{\mathrm{max}}$ which (i) preserves the
$\mathcal{G}$-invariance of $k_{\mathrm{max}}$, (ii) coincides with $k_{\mathrm{max}}$ whenever $k_{\mathrm{max}}$ is already
PSD.
Since the PSD projection of $k_{\mathrm{max}}$ discussed here can also be applied to any other indefinite kernel $k$, we directly introduce it for an arbitrary kernel $k$.

We begin as a warmup with the finite-domain “matrix” construction to build intuition, and then lift it to general domains via integral operators.

### C.1 Warmup: finite domains

We start on a finite domain $\mathcal{S}$ to build intuition. In that case,
$k_{+}$ is simply Frobenius-nearest PSD truncation of the Gram matrix on the *full domain* $\mathcal{S}$, which is unique,
basis-independent, preserves $\mathcal{G}$-invariance, and coincides with $k$ when $k$ is already PSD.

Let $\mathcal{S}=\{\bm{x}_{1},\ldots,\bm{x}_{N}\}$ be finite, and let $\mathcal{G}$ act on $\mathcal{S}$. Consider any symmetric kernel
$k$ on $\mathcal{S}$ with Gram matrix ${\bm{K}}\in\mathbb{R}^{N\times N}$ (possibly indefinite) given by ${\bm{K}}_{ij}=k(\bm{x}_{i},\bm{x}_{j})$. We define $k_{+}$ as the kernel corresponding to the Frobenius-nearest PSD projection of ${\bm{K}}$ (Higham, 1988).

###### Lemma 7 (Frobenius PSD projection and explicit form (Higham, 1988 ) ) .

The optimization problem $\;{\bm{K}}_{+}:=\operatorname*{arg\,min}_{\bm{P}\succeq 0}\|\bm{P}-{\bm{K}}\|_{F}\;$ has a unique solution and,
for any eigendecomposition ${\bm{K}}=Q\Lambda Q^{\top}$, it is given by

$$ ${\bm{K}}_{+}\;=\;\bm{Q}\,\max(0,\bm{\Lambda})\,\bm{Q}^{\top},$ $$

where $\max(0,\cdot)$ acts entrywise on $\bm{\Lambda}$. In particular, the matrix ${\bm{K}}_{+}$ depends
only on ${\bm{K}}$ (not on the chosen eigenbasis), satisfies ${\bm{K}}_{+}\succeq 0$, and ${\bm{K}}_{+}={\bm{K}}$ iff ${\bm{K}}\succeq 0$.

We *define* $k_{+}$, the (Frobenius) PSD projection of $k$, as:

$$ $k_{+}(x_{i},x_{j})\;:=\;({\bm{K}}_{+})_{ij},\qquad i,j\in[N].$ (11) $$

###### Lemma 7 (Frobenius PSD projection and explicit form (Higham, 1988 ) ) .

##### Inheritance of 𝒢 \mathcal{G} -invariance.

Each element $g\in\mathcal{G}$ induces a permutation of the elements of $\mathcal{S}$: let $\pi_{g}$ be the permutations of the integers $j\in\{1,\dots,N\}$ defined by ${g\bm{x}_{j}}=\bm{x}_{\pi_{g}(j)}$.
Denote by $\bm{P}_{g}$ the permutation matrix associated with $\pi_{g}$. For every vector $\bm{v}$, the matrix $\bm{P}_{g}$ acts as $(\bm{P}_{g}\bm{v})_{i}=\bm{v}_{\pi_{g}^{-1}(i)}$ which is equivalent to the action on canonical vectors $\bm{P}_{g}\bm{e}_{j}=\bm{e}_{\pi_{g}(j)}$ or $(\bm{P}_{g})_{ij}=1_{i=\pi_{g}(j)}$.

Invariance in the first component guarantees $k_{\mathrm{max}}(\bm{x}_{\pi_{g}(i)},\bm{x}_{j})=k_{\mathrm{max}}({g\bm{x}}_{i},\bm{x}_{j})=k_{\mathrm{max}}(\bm{x}_{i},\bm{x}_{j})$ for every $i,j\in\{1,\dots,N\}$, i.e., the rows of ${\bm{K}}=(k(\bm{x}_{i},\bm{x}_{j}))_{i,j}$ are invariant under the permutation $\pi_{g}$, hence $\bm{P}_{g}{\bm{K}}={\bm{K}}$. Thus, for any positive integer $m$, $\bm{P}_{g}{\bm{K}}^{m}=(\bm{P}_{g}{\bm{K}}){\bm{K}}^{m-1}={\bm{K}}^{m}$ so for any polynomial $p$ such that $p(0)=0$, $\bm{P}_{g}p({\bm{K}})=p({\bm{K}})$. Now consider a sequence $(p_{n})_{n}$ of polynomials such that(^6^66We can impose $p_{n}(0)=0$ since $f(0)=0$. Indeed, take $p_{n}(\lambda)=q_{n}(\lambda)-q_{n}(0)$ where $q_{n}$ is a sequence given by Weierstrass’ theorem, which converges to $f(\lambda)=\max(0,\lambda)$ on the spectrum of ${\bm{K}}$. We have $|p_{n}(\lambda)-f(\lambda)|\leq|q_{n}(\lambda)-f(\lambda)|+|q_{n}(0)|$ and because $f(0)=0$ we get $|q_{n}(0)|=|q_{n}(0)-f(0)|\to 0$.) $p_{n}(0)=0$ and $|p_{n}(\lambda)-\max(0,\lambda)|\underset{n\to\infty}{\to}0$ for any $\lambda$ in the spectrum of ${\bm{K}}$. In the limit
$\bm{P}_{g}{\bm{K}}_{+}={\bm{K}}_{+}$,
hence $k_{+}$ is invariant under the action of $\mathcal{G}$ on the first variable ($k_{+}({g\bm{x}},\bm{x}^{\prime})=k_{+}(\bm{x},\bm{x}^{\prime})$), and invariance along the second one follows by symmetry (${\bm{K}}_{+}\bm{P}_{g}^{\top}={\bm{K}}_{+}$). This shows that $k_{+}$ inherits from the $\mathcal{G}$-invariance of $k$ (equivalently, $\bm{P}_{g}{\bm{K}}={\bm{K}}={\bm{K}}\bm{P}_{g}^{\top}$ for all $g$). We collect this result in the next lemma.

###### Lemma 8 (Invariance is preserved by the projection) .

Consider $g\in\mathcal{G}$. If $P_{g}{\bm{K}}={\bm{K}}$, then $P_{g}{\bm{K}}_{+}={\bm{K}}_{+}={\bm{K}}_{+}P_{g}^{\top}$. Hence the
projected kernel $k_{+}$ is $\mathcal{G}$-invariant on $\mathcal{S}\times\mathcal{S}$.

###### Lemma 8 (Invariance is preserved by the projection) .

##### Relation to the practical Nyström kernel.

If the set $\mathcal{D}=\{\bm{x}_{1},\ldots,\bm{x}_{n}\}$ used to build $k_{+}^{(\mathcal{D})}$ ([Equation 7](https://arxiv.org/html/2509.25051v1#S3.E7)) equals the whole domain $\mathcal{D}=\mathcal{S}$, then $k_{+}^{(\mathcal{D})}=k_{+}$. Indeed, $k_{+}^{(\mathcal{D})}(\bm{x}_{i},\bm{x}_{j})={\bm{K}}_{i:}{\bm{K}}^{\dagger}_{+}{\bm{K}}_{:j}=({\bm{K}}{\bm{K}}^{\dagger}_{+}{\bm{K}})_{ij}=({\bm{K}}_{+})_{ij}$ on $\mathcal{D}\times\mathcal{D}$, and the latter is the definition of $k_{+}$ on finite domains.

We now generalize the matrix considerations above using integral operators. The finite-domain construction is recovered as a special case.

### C.2 General definition (via integral operators theory)

We lift the finite-domain construction of the previous subsection to general domains by viewing $k$ as a
Hilbert–Schmidt operator and defining $k_{+}$ as the positive part of $T_{k}$; this yields a PSD,
data-independent kernel that inherits any $\mathcal{G}$-invariance and equals $k$ whenever $k$ is PSD.

Let $(\mathcal{S},\mathcal{T},\mu)$ be a probability space.
For a measurable, symmetric kernel $k:\mathcal{S}\times\mathcal{S}\to\mathbb{R}$ with $k\in L^{2}(\mu\otimes\mu)$,
let the (compact, self-adjoint) Hilbert-Schmidt operator $T_{k}:L^{2}(\mu)\to L^{2}(\mu)$ be

$$ $(T_{k}f)(\bm{x})\;=\;\int_{\mathcal{S}}k(\bm{x},\bm{x}^{\prime})\,f(\bm{x}^{\prime})\,d\mu(\bm{x}^{\prime}).$ $$

(Note that in the finite-domain case, $f$ is a vector indexed by the domain and if $\mu$ is the uniform measure then $T_{k}$ is simply multiplication by the Gram matrix ${\bm{K}}$ normalized by the domain size.)
By the spectral theorem, there exist $(\lambda_{i},\phi_{i})_{i\geq 1}$ with $\{\phi_{i}\}$ orthonormal in
$L^{2}(\mu)$ and $(\lambda_{i})\in\ell^{2}$ (possibly of mixed signs) such that $T_{k}=\sum_{i\geq 1}\lambda_{i}\,\phi_{i}\otimes\phi_{i}$ in $L^{2}(\mu)$ where for every $u,v\in L^{2}(\mu)$, $u\otimes v$ is the rank-one operator $L^{2}(\mu)\to L^{2}(\mu)$ such that $(u\otimes v)f:=\langle f,v\rangle\,u$ for every $f\in L^{2}(\mu)$.

##### Generic definition of k + k_{+} via operator theory.

Define the positive part of $T_{k}=\sum_{i}\lambda_{i}\,\phi_{i}\otimes\phi_{i}$ by $T_{k}^{+}:=\sum_{i}(\lambda_{i})_{+}\,\phi_{i}\otimes\phi_{i}$, where $(t)_{+}=\max\{t,0\}$. Since $\sum_{i}((\lambda_{i})_{+})^{2}\leq\sum_{i}\lambda_{i}^{2}<\infty$, the series

$$ $k_{+}(\bm{x},\bm{x}^{\prime})\;:=\;\sum_{i\geq 1}(\lambda_{i})_{+}\,\phi_{i}(\bm{x})\,\phi_{i}(\bm{x}^{\prime})\quad\text{($\mu\otimes\mu$-a.e.)}.$ (12) $$

converges in $L^{2}(\mu\otimes\mu)$ and defines a kernel $\mu\otimes\mu$-almost everywhere.
By construction(^7^77Indeed, by definition $(T_{k_{+}}f)(\bm{x})=\int_{\mathcal{S}}\Big(\sum_{i\geq 1}(\lambda_{i})_{+}\phi_{i}(\bm{x})\phi_{i}(\bm{x}^{\prime})\Big)f(\bm{x}^{\prime})\,d\mu(\bm{x}^{\prime})=\sum_{i\geq 1}(\lambda_{i})_{+}\,\langle f,\phi_{i}\rangle\,\phi_{i}(\bm{x})=\Bigl(\Big(\sum_{i\geq 1}(\lambda_{i})_{+}\,\phi_{i}\otimes\phi_{i}\Big)f\Bigr)(\bm{x})=\big(T_{k}^{+}f\big)(\bm{x})$.) $T_{k_{+}}=T_{k}^{+}$, hence $k_{+}$ is PSD as a kernel a.e., and PSD in the operator sense: $\left\langle f,T_{k_{+}}f\right\rangle\geq 0$ for all $f\in L^{2}(\mu)$.
In particular, if $k$ was already PSD (all $\lambda_{i}\geq 0$), then $k_{+}=k$ (up to null sets).
It also inherits $\mathcal{G}$-invariance of $k$ if $k$ is indeed invariant (the proof mimics the finite-domain case, we give the full details for completeness in [Section C.6](https://arxiv.org/html/2509.25051v1#A3.SS6)).

### C.3 From the finite-sample projection to the intrinsic limit: what converges to what?

We relate the practical, data-dependent Nyström kernel
$k_{+}^{(\mathcal{D})}$ ([Equation 7](https://arxiv.org/html/2509.25051v1#S3.E7)) to the intrinsic $k_{+}$: under iid sampling, the empirical spectra of $k_{+}^{(\mathcal{D})}/|\mathcal{D}|$
converge to that of $T_{k_{+}}$, with rates under mild moment assumptions. This shows that eigendecay-based regret analysis

Notations. Let $X_{1},X_{2},\dots\sim\mu$ i.i.d. and $\mathcal{D}_{n}=\{X_{1},\dots,X_{n}\}$. We write
${\bm{K}}_{n}:=k(\mathcal{D}_{n},\mathcal{D}_{n})$, ${\bm{K}}_{n}^{+}:=\arg\min_{\bm{P}\succeq 0}\|\bm{P}-{\bm{K}}_{n}\|_{F}$,
$\tilde{\bm{K}}_{n}:={\bm{K}}_{n}/n$, and recall that the practical (data-dependent) kernel defined in [Equation 7](https://arxiv.org/html/2509.25051v1#S3.E7) is

$$ $k_{+}^{(\mathcal{D}_{n})}(\bm{x},\bm{x}^{\prime})\;=\;k(\bm{x},\mathcal{D}_{n})\,({\bm{K}}_{n}^{+})^{\dagger}\,k(\mathcal{D}_{n},\bm{x}^{\prime}).$ $$

We denote by $\lambda(T)$ the (ordered, nonincreasing, each counted with its multiplicity) sequence of eigenvalues of a compact
self-adjoint operator $T$, and by
$\delta_{2}\!\big(\lambda(T),\lambda(S)\big):=\big(\sum_{i}|\lambda_{i}(T)-\lambda_{i}(S)|^{2}\big)^{1/2}$
the spectral $\ell_{2}$ distance. For symmetric matrices $\bm{M}$, $\lambda(\bm{M})$ denotes the nonincreasing sequence of eigenvalues of $\bm{M}$ (with multiplicity) padded with an infinite number of zeros. For a bounded operator $A$, $\|A\|_{\mathrm{HS}}$ and
$\|A\|_{\mathrm{op}}$ denote the Hilbert-Schmidt and operator norms, respectively. We include in [Section C.4](https://arxiv.org/html/2509.25051v1#A3.SS4) a reminder on the different notions of norms and convergence, and we now recall the essentials.

##### Relations between convergence notions.

For compact self-adjoint operators:
(i)

$$ $\max\left(\delta_{2}\!\big(\lambda(T_{n}),\lambda(T)\big),\|T_{n}-T\|_{\mathrm{op}}\right)\leq\|T_{n}-T\|_{\mathrm{HS}}$ $$

(Reed and Simon, 1972; Bhatia and Elsner, 1994);
(ii) converse inequalities do not hold in infinite dimension (see [Section C.4](https://arxiv.org/html/2509.25051v1#A3.SS4) for examples).
Thus, HS convergence is the strongest notion of convergence we manipulate here.

We now present convergence guarantees of the
data-dependent construction $k_{+}^{(\mathcal{D}_{n})}/n$ to the intrinsic $k_{+}$ under progressively stronger assumptions. With minimal assumptions we obtain almost-sure spectral consistency in the $\delta_{2}$ metric; with stronger assumptions we obtain quantitative rates in HS norm (hence also spectral $\ell_{2}$ in probability).

(a) Weak a.s. spectral consistency of positive parts (minimal assumptions).

###### Proposition 9 .

Assume the symmetric (not necessarily PSD) kernel $k$ is in $L^{2}(\mu\otimes\mu)$ so that $T_{k}$ is Hilbert-Schmidt. Let $\widehat{S}_{n}:L^{2}(\mu_{n})\to L^{2}(\mu_{n})$ be the integral operator with kernel $k_{+}^{(\mathcal{D}_{n})}(\bm{x},\bm{x}^{\prime})/n$ defined by:

$$ $(\widehat{S}_{n}f)(\bm{x})=\frac{1}{n}\sum_{j=1}^{n}k_{+}^{(\mathcal{D}_{n})}(\bm{x},X_{j})f(X_{j}).$ (13) $$

Assume the $X_{i}$ are pairwise distinct almost surely. Then, almost surely,

$$ $\delta_{2}\!\Big(\lambda\!\big(\widehat{S}_{n}\big),\;\lambda\!\big(T_{k_{+}}\big)\Big)\;\underset{n\to\infty}{\longrightarrow}\;0.$ $$

*Proof.*
Let ${\bm{K}}_{n}$ be the empirical operator on $\mathbb{R}^{n}$ with matrix $\frac{1}{n}(k(X_{i},X_{j}))_{i,j}$ and let $\lambda({\bm{K}}_{n})$ be its ordered spectrum (nonincreasing, with multiplicity) padded with an infinite number of zeros. Theorem 3.1 of Koltchinskii and Giné (2000) shows that $\delta_{2}(\lambda({\bm{K}}_{n}),\lambda(T_{k}))\to 0$ as $n\to\infty$.

Let ${\bm{K}}_{n}^{+}$ be the positive part of ${\bm{K}}_{n}$ (i.e., its Frobenius PSD projection). Since $\lambda\mapsto\max(0,\lambda)$ is $1$-Lipschitz, we have for any operators $T,S$:

$$ $\delta_{2}(\lambda(T_{+}),\lambda(S_{+}))=\sum_{i}|\max(0,\lambda_{i}(T))-\max(0,\lambda_{i}(S))|\leq\sum_{i}|\lambda_{i}(T)-\lambda_{i}(S)|=\delta_{2}(\lambda(T),\lambda(S)).$ $$

We deduce that $\delta_{2}(\lambda({\bm{K}}_{n}^{+}),\lambda(T_{k_{+}}))\to 0$ as $n\to\infty$.

It remains to observe that the spectrum of ${\bm{K}}_{n}^{+}$ as an operator on $\mathbb{R}^{n}$ is the same as $\widehat{S}_{n}:L^{2}(\mu_{n})\to L^{2}(\mu_{n})$. This identification is standard (e.g., see above Equation 1.2 in Koltchinskii and Giné (2000)). For completeness, we include the formal arguments of Koltchinskii and Giné (2000) in [Lemma 12](https://arxiv.org/html/2509.25051v1#Thmtheorem12), which shows that we can identify the spectrum of $k_{+}^{(\mathcal{D}_{n})}(\mathcal{D}_{n},\mathcal{D}_{n})/n$ with the one of ${\bm{K}}^{+}_{n}$ a.s. if the iid $X_{i}\sim\mu$ are pairwise distinct a.s, which is true as soon as $\mu$ is non-atomic; otherwise one can index the *distinct* atoms and work in $\mathbb{R}^{m}$ with $m=\#\mathrm{supp}(\mu_{n})$, obtaining the same spectral identity on that subspace. ∎

(b) Expected HS convergence with $\mathcal{O}(n^{-1/2})$ rate (stronger assumption).
Define the empirical integral operator $(T_{n}f)(\bm{x}):=\frac{1}{n}\sum_{i=1}^{n}k(\bm{x},X_{i})f(X_{i})$ and
$D_{n}:=T_{n}-T_{k}$. Let $(\lambda_{i},\phi_{i})_{i\geq 1}$ be an eigensystem of $T_{k}$ in $L^{2}(\mu)$.
Assume the following fourth-order summability condition holds:

$$ $C\;:=\;\sum_{i,j\geq 1}\lambda_{i}^{2}\int_{\mathcal{S}}\phi_{i}(\bm{x})^{2}\,\phi_{j}(\bm{x})^{2}\,d\mu(\bm{x})\;<\;\infty.$ (14) $$

###### Proposition 10 (Expected HS rate) .

Under $k\in L^{2}(\mu\otimes\mu)$ and ([14](https://arxiv.org/html/2509.25051v1#A3.E14)),

$$ $\mathbb{E}\big[\|D_{n}\|_{\mathrm{HS}}^{2}\big]\;\leq\;\frac{C}{n},\qquad\mathbb{E}\big[\|D_{n}\|_{\mathrm{HS}}\big]\;\leq\;\sqrt{\tfrac{C}{n}}.$ $$

Consequently, $\|D_{n}\|_{\mathrm{HS}}=\mathcal{O}_{\mathbb{P}}(n^{-1/2})$ and therefore using the same notations as in [Proposition 9](https://arxiv.org/html/2509.25051v1#Thmtheorem9)

$$ $\delta_{2}\!\big(\lambda({\bm{K}}_{n}^{+}),\lambda(T_{k}^{+})\big)=\mathcal{O}_{\mathbb{P}}(n^{-1/2}),\qquad\delta_{2}\!\Big(\lambda\!\big(\widehat{S}_{n}\big),\lambda(T_{k_{+}})\Big)=\mathcal{O}_{\mathbb{P}}(n^{-1/2}).$ $$

*Proof.* Fix any $f\in L^{2}(\mu)$. By Fubini-Tonelli for non-negative functions, we have:

$$ $\mathbb{E}\big[\|D_{n}f\|_{L^{2}(\mu)}^{2}\big]=\int_{\mathcal{S}}\mathbb{E}\Big[\big((D_{n}f)(\bm{x})\big)^{2}\Big]\,d\mu(\bm{x}).$ $$

By definition

$$ $(D_{n}f)(\bm{x})=\frac{1}{n}\sum_{i=1}^{n}k(\bm{x},X_{i})f(X_{i})-\int_{\mathcal{S}}k(\bm{x},\bm{x}^{\prime})f(\bm{x}^{\prime})\,d\mu(\bm{x}^{\prime})$ $$

where the randomness comes from the i.i.d. $X_{i}\sim\mu$. Hence $\mathbb{E}\big[(D_{n}f)(\bm{x})\big]=0$ and for any fixed $\bm{x}$

$$ $\mathbb{E}\Big[\big((D_{n}f)(\bm{x})\big)^{2}\Big]=\mathrm{Var}\big((D_{n}f)(\bm{x})\big)=\frac{1}{n}\,\mathrm{Var}\big(k(\bm{x},X)f(X)\big)\leq\frac{1}{n}\,\int_{\mathcal{S}}k(\bm{x},\bm{x}^{\prime})^{2}f(\bm{x}^{\prime})^{2}\,d\mu(\bm{x}^{\prime}).$ $$

The Hilbert-Schmidt
spectral theorem gives the expansion
$k(\bm{x},\bm{x}^{\prime})=\sum_{i}\lambda_{i}\phi_{i}(\bm{x})\phi_{i}(\bm{x}^{\prime})$ in $L^{2}(\mu\otimes\mu)$, with $(\lambda_{i})_{i}\in\ell^{2}$ and $(\phi_{i})_{i}$ an orthonormal set of $L^{2}(\mu)$ (see Equation 3.2 in Koltchinskii and Giné (2000), Corollary 5.4 in Conway (2007)). Thus

$$ $\displaystyle\int_{\mathcal{S}}\mathbb{E}\Big[\big((D_{n}f)(\bm{x})\big)^{2}\Big]\,d\mu(\bm{x})$ $\displaystyle\leq\frac{1}{n}\int_{\mathcal{S}}k(\bm{x},\bm{x}^{\prime})^{2}f(\bm{x}^{\prime})^{2}\,d\mu(\bm{x}^{\prime})d\mu(\bm{x})$ $\displaystyle=\sum_{i,j}\lambda_{i}\lambda_{j}\int_{\mathcal{S}}\phi_{i}(\bm{x}^{\prime})\phi_{j}(\bm{x}^{\prime})f(\bm{x}^{\prime})^{2}\underbrace{\left\langle\phi_{i},\phi_{j}\right\rangle}_{=1_{i=j}}d\mu(\bm{x}^{\prime})$ $\displaystyle=\sum_{i}\lambda_{i}^{2}\int_{\mathcal{S}}\phi_{i}(\bm{x}^{\prime})^{2}f(\bm{x}^{\prime})^{2}d\mu(\bm{x}^{\prime}).$ $$

Taking $f=\phi_{j}$ for a fixed $j$ yields

$$ $\mathbb{E}\big[\|D_{n}\phi_{j}\|_{L^{2}(\mu)}^{2}\big]\leq\frac{1}{n}\sum_{i}\lambda_{i}^{2}\int_{\mathcal{S}}\phi_{i}(\bm{x}^{\prime})^{2}\phi_{j}(\bm{x}^{\prime})^{2}d\mu(\bm{x}^{\prime}).$ $$

Since $\|D_{n}f\|_{\textrm{HS}}^{2}=\sum_{j}\|D_{n}\phi_{j}\|_{L^{2}(\mu)}^{2}$, we get the main claim:

$$ $\mathbb{E}\big[\|D_{n}\|_{\mathrm{HS}}^{2}\big]\;\leq\;\frac{C}{n}.$ $$

Jensen gives the bound for $\mathbb{E}\|D_{n}\|_{\mathrm{HS}}$. Finally,
$\delta_{2}(\lambda({\bm{K}}_{n}),\lambda(T_{k}))\leq\|D_{n}\|_{\mathrm{HS}}$ (Hoffman-Wielandt inequality in infinite dimension (Bhatia and Elsner, 1994)),
and $\lambda\mapsto\max(0,\lambda)$ is $1$-Lipschitz on $\mathbb{R}$, hence the spectral bound probability claim using Markov’s inequality, and [Lemma 12](https://arxiv.org/html/2509.25051v1#Thmtheorem12) transfers this claims to $\widehat{S}_{n}$. ∎

###### Remark 11 (On assumption ( 14 )) .

Condition ([14](https://arxiv.org/html/2509.25051v1#A3.E14)) is a fourth-order integrability requirement
that controls eigenfunction overlaps. It is standard in random Nyström analyses
(see, e.g., Equations (4.3) and (4.11) of Koltchinskii and Giné (2000)) and stronger than $k\in L^{2}$,
but it yields a dimension-free $\mathcal{O}(n^{-1/2})$ rate in HS norm.

(c) High-probability HS rates (heavier but more precise).
Under slightly stronger $L^{4}$-type conditions on eigenfunctions, the section 4 in Koltchinskii and Giné (2000) gives more more precise statements on the rates in [Proposition 10](https://arxiv.org/html/2509.25051v1#Thmtheorem10), and we directly refer the reader to it.

###### Proposition 9 .

###### Proposition 10 (Expected HS rate) .

###### Remark 11 (On assumption ( 14 )) .

##### Application to k max k_{\mathrm{max}} and to the BO kernels in the paper.

When $k=k_{\mathrm{max}}$ is bounded on a compact domain $\mathcal{S}$ (as in all our experiments),
$k\in L^{2}(\mu\otimes\mu)$ for any probability measure $\mu$ on $\mathcal{S}$, so $T_{k_{\mathrm{max}}}$
is Hilbert-Schmidt and [Proposition 9](https://arxiv.org/html/2509.25051v1#Thmtheorem9) applies. In particular, the integral operator associated with $k_{+}^{(\mathcal{D}_{n})}/n$, called $\widehat{S}_{n}$ ([Equation 13](https://arxiv.org/html/2509.25051v1#A3.E13)) satisfies

$$ $\delta_{2}\!\Big(\lambda\!\big(\widehat{S}_{n}\big),\;\lambda\!\big(T_{k_{+}}\big)\Big)\;\xrightarrow[n\to\infty]{\text{a.s.}}\;0.$ $$

This clarifies the two objects introduced in the main text: the *intrinsic* $k_{+}$
is the unique data-independent target, while the *practical* kernel $k_{+}^{(\mathcal{D}_{n})}$
(finite PSD projection $+$ Nyström) is an on-path approximation whose spectrum converges (once normalized by $n$) to that of $k_{+}$ under i.i.d. sampling.

The following subsections are only optional complementary materials added to help building intuitions on the convergence results stated above.

### C.4 Reminders on the different type of convergences for bounded linear operators

This subsection recalls standard notions of operator convergence,
included only as background to help build intuition for the convergence results above.

##### Definitions (operator norm, HS norm, spectral distance).

Let $\mathcal{H}$ be a separable Hilbert space with orthonormal basis $\{e_{i}\}_{i\geq 1}$.
For a bounded linear operator $T:\mathcal{H}\!\to\!\mathcal{H}$,

$$ $\|T\|_{\mathrm{op}}:=\sup_{\|f\|_{\mathcal{H}}=1}\|Tf\|_{\mathcal{H}},\qquad\|T\|_{\mathrm{HS}}:=\Big(\sum_{i\geq 1}\|Te_{i}\|_{\mathcal{H}}^{2}\Big)^{1/2}.$ $$

The HS norm is basis-independent. When $T$ is an *integral* operator with kernel $k\in L^{2}(\mu\otimes\mu)$ on $L^{2}(\mu)$ (Reed and Simon, 1972)

$$ $\|T\|_{\mathrm{HS}}^{2}=\iint_{\mathcal{S}\times\mathcal{S}}|k(x,y)|^{2}\,d\mu(x)\,d\mu(y).$ $$

For finite matrices, $\|A\|_{\mathrm{HS}}=\|A\|_{F}$ (Frobenius).
We say $T_{n}\!\to T$ in HS norm if $\|T_{n}-T\|_{\mathrm{HS}}\!\to 0$, and we say $T_{n}\!\to T$ spectrally if
$\delta_{2}\big(\lambda(T_{n}),\lambda(T)\big)\!\to 0$, where we recall that $\lambda(T)$ is the *ordered*
eigenvalues of a compact self-adjoint operator $T$, and where the spectral $\ell_{2}$-distance is
$\delta_{2}(\lambda(T),\lambda(S)):=\big(\sum_{i}|\lambda_{i}(T)-\lambda_{i}(S)|^{2}\big)^{1/2}$.

##### Which convergences matter, and how they relate (reminders on well-known facts).

We compare three notions:
(i) *operator norm* convergence $\|T_{n}-T\|_{\mathrm{op}}\!\to 0$;
(ii) *Hilbert-Schmidt (HS)* convergence $\|T_{n}-T\|_{\mathrm{HS}}\!\to 0$;
(iii) *spectral* convergence in $\delta_{2}$, i.e.,
$\delta_{2}\big(\lambda(T_{n}),\lambda(T)\big):=\big(\sum_{i}|\lambda_{i}(T_{n})-\lambda_{i}(T)|^{2}\big)^{1/2}\to 0$,
where $\lambda(\cdot)$ denotes the ordered eigenvalues of a compact self-adjoint operator. We recall the following well-known facts, useful to grasp the convergence results we state next.

(1) HS $\Longrightarrow$ spectral $\delta_{2}$.
For compact self-adjoint operators the (infinite-dimensional) Hoffman-Wielandt inequality yields (Bhatia and Elsner, 1994)

$$ $\delta_{2}\big(\lambda(T_{n}),\lambda(T)\big)\;\leq\;\|T_{n}-T\|_{\mathrm{HS}}.$ $$

(2) HS $\Longrightarrow$ operator norm.
For every Hilbert-Schmidt operator $S$, $\|S\|_{\mathrm{op}}\leq\|S\|_{\mathrm{HS}}$.
Indeed for unit vectors $x,y\in H$, using $x=\sum_{i}\langle x,e_{i}\rangle e_{i}$, we have
$\langle Sx,y\rangle=\sum_{i\in I}\langle x,e_{i}\rangle\,\langle Se_{i},y\rangle.$
By Cauchy-Schwarz:

$$ $|\langle Sx,y\rangle|\leq\Big(\sum_{i\in I}|\langle x,e_{i}\rangle|^{2}\Big)^{1/2}\Big(\sum_{i\in I}|\langle Se_{i},y\rangle|^{2}\Big)^{1/2}.$ $$

The first factor equals $\|x\|=1$, and for the second we use $|\langle Se_{i},y\rangle|\leq\|Se_{i}\|\,\|y\|=\|Se_{i}\|$ to get

$$ $\sum_{i\in I}|\langle Se_{i},y\rangle|^{2}\leq\sum_{i\in I}\|Se_{i}\|^{2}=\|S\|_{\mathrm{HS}}^{2}.$ $$

Hence $|\langle Sx,y\rangle|\leq\|S\|_{\mathrm{HS}}$. Taking the supremum over all unit $y$ gives

$$ $\|Sx\|=\sup_{\|y\|=1}|\langle Sx,y\rangle|\leq\|S\|_{\mathrm{HS}},$ $$

and then taking the supremum over all unit $x$ yields

$$ $\|S\|_{\mathrm{op}}=\sup_{\|x\|=1}\|Sx\|\leq\|S\|_{\mathrm{HS}}.$ $$

(3) Spectral $\delta_{2}$ does *not* imply HS nor operator norm.
Even if eigenvalues match in $\ell_{2}$, the operators may be far in norm because eigenvectors can rotate.
Let $T=\mathrm{diag}(1,1/2,1/3,\ldots)$ in the canonical basis $(e_{i})_{i\geq 1}$, and let $U_{n}$ swap $e_{1}$ and $e_{n}$.
Set $T_{n}:=U_{n}TU_{n}^{\ast}$. Then $\lambda(T_{n})=\lambda(T)$ for all $n$ (same ordered spectrum), so
$\delta_{2}(\lambda(T_{n}),\lambda(T))=0$.
Yet $\|(T_{n}-T)e_{1}\|=\|(U_{n}TU_{n}^{\ast}-T)e_{1}\|=\|(1/n-1)e_{1}\|=1-1/n$, hence
$\|T_{n}-T\|_{\mathrm{op}}\geq 1-1/n\to 1$ and, a fortiori, $\|T_{n}-T\|_{\mathrm{HS}}\not\to 0$.

(4) Operator norm does *not* imply spectral $\delta_{2}$.
Let $T=0$ and $T_{n}$ be diagonal with the first $m_{n}$ entries equal to $\varepsilon_{n}$ and the rest 0.
Choose $\varepsilon_{n}:=n^{-1/2}$ and $m_{n}:=n$. Then
$\|T_{n}\|_{\mathrm{op}}=\varepsilon_{n}\to 0$ but
$\delta_{2}\big(\lambda(T_{n}),\lambda(T)\big)=\big(\sum_{i=1}^{m_{n}}\varepsilon_{n}^{2}\big)^{1/2}=\sqrt{n\cdot(1/n)}=1$.

(5) Two useful corollaries.
(a) Spectral $\delta_{2}$-convergence implies convergence of the *largest* eigenvalue, since
$\sup_{i}|\lambda_{i}(T_{n})-\lambda_{i}(T)|\leq\delta_{2}(\lambda(T_{n}),\lambda(T))$.
(b) Operator-norm convergence forces uniform eigenvalue deviations to vanish by Weyl’s inequality:
$\sup_{i}|\lambda_{i}(T_{n})-\lambda_{i}(T)|\leq\|T_{n}-T\|_{\mathrm{op}}$,
but it does *not* control the $\ell_{2}$-sum of all deviations.

*Takeaway.* HS is the strongest notion here: it simultaneously implies spectral $\delta_{2}$-convergence
(and thus convergence of eigenvalue-based quantities) and operator-norm convergence. The converses fail in infinite
dimension because eigenvectors can drift and an infinite number of tiny eigenvalue errors can accumulate.

### C.5 Identification of the spectrum of an empirical operator in L 2 ​ ( μ n ) L^{2}(\mu_{n}) and its matrix counterpart

Here we show how the spectrum of the empirical operator can be
identified with that of its matrix form. This is complementary material meant to clarify how
operator-level and matrix-level viewpoints connect (which is useful, e.g., in the proof of [Proposition 9](https://arxiv.org/html/2509.25051v1#Thmtheorem9)).

###### Lemma 12 (Empirical Nyström spectral identity) .

Let ${\bm{K}}_{n}:=\frac{1}{n}\big(k(\bm{x}_{i},\bm{x}_{j})\big)_{i,j=1}^{n}$ and let ${\bm{K}}_{n}^{+}$ be its spectral positive part
(the Frobenius-nearest PSD projection). Define the empirical measure
$\mu_{n}:=\frac{1}{n}\sum_{i=1}^{n}\delta_{\bm{x}_{i}}$ and the Nyström kernel

$$ $k_{+}^{(\mathcal{D}_{n})}(\bm{x},\bm{x}^{\prime})\;=\;k(\bm{x},\mathcal{D}_{n})\,({\bm{K}}_{n}^{+})^{\dagger}\,k(\mathcal{D}_{n},\bm{x}^{\prime}).$ $$

Let $\widehat{S}_{n}:L^{2}(\mu_{n})\to L^{2}(\mu_{n})$ be the integral operator with kernel $k_{+}^{(\mathcal{D}_{n})}(\bm{x},\bm{x}^{\prime})/n$, i.e.

$$ $(\widehat{S}_{n}f)(\bm{x})\;=\;\frac{1}{n}\sum_{j=1}^{n}k_{+}^{(\mathcal{D}_{n})}(\bm{x},\bm{x}_{j})\,f(\bm{x}_{j}).$ $$

The map $E:L^{2}(\mu_{n})\to\mathbb{R}^{n}$, $Ef:=\frac{1}{\sqrt{n}}\big(f(\bm{x}_{1}),\ldots,f(\bm{x}_{n})\big)^{\top}$, is an isometry:
$\|Ef\|_{\mathbb{R}^{n}}=\|f\|_{L^{2}(\mu_{n})}$, and we have the intertwining identity

$$ $E\,\widehat{S}_{n}\;=\;{\bm{K}}_{n}^{+}\,E.$ $$

If, in addition, the sample points $\bm{x}_{1},\ldots,\bm{x}_{n}$ are pairwise distinct, then $E$ is an
isometric isomorphism (hence invertible) and

$$ $\lambda\!\big(\widehat{S}_{n}\big)\;=\;\lambda\!\big({\bm{K}}_{n}^{+}\big)\;=\;\lambda\!\big(k_{+}^{(\mathcal{D}_{n})}(\mathcal{D}_{n},\mathcal{D}_{n})/n\big).$ $$

###### Proof.

First note the on-sample identity $k_{+}^{(\mathcal{D}_{n})}(\bm{x}_{i},\bm{x}_{j})=({\bm{K}}^{+})_{ij}$ for the unscaled
${\bm{K}}=(k(\bm{x}_{i},\bm{x}_{j}))_{i,j}$, which follows from ${\bm{K}}({\bm{K}}^{+})^{\dagger}{\bm{K}}={\bm{K}}^{+}$. Hence
$k_{+}^{(\mathcal{D}_{n})}(\mathcal{D}_{n},\mathcal{D}_{n})={\bm{K}}^{+}$ and therefore $k_{+}^{(\mathcal{D}_{n})}(\mathcal{D}_{n},\mathcal{D}_{n})/n={\bm{K}}_{n}^{+}$.

For $f\in L^{2}(\mu_{n})$ and each $i\in\{1,\dots,n\}$,

$$ $\sqrt{n}\,\big(E\widehat{S}_{n}f\big)_{i}=(\widehat{S}_{n}f)(\bm{x}_{i})=\frac{1}{n}\sum_{j=1}^{n}k_{+}^{(\mathcal{D}_{n})}(\bm{x}_{i},\bm{x}_{j})\,f(\bm{x}_{j})=\sum_{j=1}^{n}({\bm{K}}_{n}^{+})_{ij}\,f(X_{j})=\sqrt{n}\,\big({\bm{K}}_{n}^{+}Ef\big)_{i},$ $$

which proves $E\,\widehat{S}_{n}={\bm{K}}_{n}^{+}E$. Since $E$ is an isometry by definition of the
$L^{2}(\mu_{n})$ inner product, if the $X_{i}$ are pairwise distinct then $E$ is bijective and
conjugates $\widehat{S}_{n}$ with ${\bm{K}}_{n}^{+}$, so the spectra (with multiplicities) coincide.
∎

###### Lemma 12 (Empirical Nyström spectral identity) .

###### Proof.

### C.6 Proof of 𝒢 \mathcal{G} -invariance of k + k_{+} for general domains

We conclude this appendix with the formal proof that $k_{+}$ defined in ([12](https://arxiv.org/html/2509.25051v1#A3.E12)) inherits from any group-invariance of $k$. This proof is not needed for the main results but is included for
completeness. It makes explicit why $k_{+}$ preserves any $\mathcal{G}$-invariance of $k$. The proof follows the one for finite domains but is heavier in notations because it is now stated using integral operators to generalize the matrix manipulations of finite domains. For finite domains, denoting by ${\bm{K}}$ the Gram matrix of $k$ over the whole domain and $\bm{P}_{g}$ the permutation matrix induced by the action of $g\in\mathcal{G}$ on the domain, invariance of $k$ is equivalent to $\bm{P}_{g}{\bm{K}}={\bm{K}}\bm{P}_{g}^{\top}={\bm{K}}$. Thus any polynomial $p({\bm{K}})$ of ${\bm{K}}$ such that $p(0)=0$ inherits from this invariance since we still have $\bm{P}_{g}p({\bm{K}})=p({\bm{K}})\bm{P}_{g}^{\top}=p({\bm{K}})$. And at the limit, we get invariance of ${\bm{K}}_{+}$. Here, we mimic this proof, and we start by introducing the equivalent integral operator form of the characterization $\bm{P}_{g}{\bm{K}}={\bm{K}}\bm{P}_{g}^{\top}={\bm{K}}$ for general domains.

###### Lemma 13 (Kernel invariance $\Longleftrightarrow$ operator commutation) .

Let $(\mathcal{S},\mathcal{T},\mu)$ be a probability space and let $\mathcal{G}$ act measurably on $\mathcal{S}$.
Assume $\mu$ is $\mathcal{G}$-invariant.
Let $U_{g}:L^{2}(\mu)\to L^{2}(\mu)$ be the unitary representation
$(U_{g}f)(\bm{x}):=f({g^{-1}\bm{x}}).$
Let $k\in L^{2}(\mu\otimes\mu)$ be a symmetric kernel with integral operator
$(T_{k}f)(\bm{x})=\int_{\mathcal{S}}k(\bm{x},\bm{x}^{\prime})f(\bm{x}^{\prime})\,d\mu(\bm{x}^{\prime}).$
Then the following are equivalent:

- (i)
$k$ is argumentwise $\mathcal{G}$-invariant: $k({g\bm{x}},\bm{x}^{\prime})=k(\bm{x},{g\bm{x}^{\prime}})=k(\bm{x},\bm{x}^{\prime})$ for $\mu\otimes\mu$-a.e. $(\bm{x},\bm{x}^{\prime})$ and all $g\in\mathcal{G}$.
- (ii)
$T_{k}$ satisfies $U_{g}T_{k}=T_{k}U_{g}=T_{k}$ on $L^{2}(\mu)$ for all $g\in\mathcal{G}$.

###### Proof.

*(i)$\Rightarrow$(ii).* For any $f\in L^{2}(\mu)$,

$$ $(U_{g}T_{k}f)(\bm{x})=(T_{k}f)({g^{-1}\bm{x}})=\int k({g^{-1}\bm{x}},\bm{x}^{\prime})f(\bm{x}^{\prime})\,d\mu(\bm{x}^{\prime}).$ $$

By invariance of $k$ in the first argument $U_{g}T_{k}=T_{k}$. Hence $T_{k}^{*}U_{g}^{*}=T_{k}^{*}$ and $T_{k}^{*}=T_{k}$ (self-adjoint) and $U_{g}^{*}=U_{g^{-1}}$ so $T_{k}U_{g^{-1}}=T_{k}$. This is true for all $g\in\mathcal{G}$ hence $U_{g}T_{k}=T_{k}U_{g}=T_{k}$.

*(ii)$\Rightarrow$(i).* For $\varphi,\psi\in L^{2}(\mu)$,

$$ $\iint k(\bm{x},\bm{x}^{\prime})\,\varphi(\bm{x})\psi(\bm{x}^{\prime})\,d\mu(\bm{x})d\mu(\bm{x}^{\prime})=\langle\varphi,T_{k}\psi\rangle=\langle\varphi,T_{k}U_{g}\psi\rangle.$ $$

Expanding the last inner product, we get by change of variable and invariance of $\mu$

$$ $\iint k(\bm{x},\bm{x}^{\prime})\,\varphi(\bm{x})\psi({g^{-1}\bm{x}^{\prime}})\,d\mu(\bm{x})d\mu(\bm{x}^{\prime})=\iint k(\bm{x},{g\bm{x}^{\prime}})\,\varphi(\bm{x})\psi(\bm{x}^{\prime})\,d\mu(\bm{x})d\mu(\bm{x}^{\prime}).$ $$

Hence for all $\varphi,\psi$,
$\iint[k(\bm{x},\bm{x}^{\prime})-k(\bm{x},{g\bm{x}^{\prime}})]\,\varphi(\bm{x})\psi(\bm{x}^{\prime})\,d\mu(\bm{x})d\mu(\bm{x}^{\prime})=0,$
which implies $k(\bm{x},{g\bm{x}^{\prime}})=k(\bm{x},\bm{x}^{\prime})$ $\mu\otimes\mu$-a.e. Symmetry implies argumentwise $\mathcal{G}$-invariance.
∎

We now show that $U_{g}T=T$ is preserved if we apply a function $f$ such that $f(0)=0$ to the spectrum of $T$.

###### Lemma 14 (Borel functional calculus preserves invariance) .

Let $T$ be a self-adjoint compact operator on a Hilbert space $\mathcal{H}$ with eigendecomposition $T=\sum_{i}\lambda_{i}\phi_{i}\otimes\phi_{i}$, and let $\{U_{g}\}_{g\in\mathcal{G}}$ be a unitary
representation such that $U_{g}T=TU_{g}=T$ for all $g\in\mathcal{G}$. For a bounded Borel function $f:\mathbb{R}\to\mathbb{R}$, define $f(T)=\sum_{i}f(\lambda_{i})\phi_{i}\otimes\phi_{i}$. Then for such $f$ with $f(0)=0$, we have

$$ $U_{g}f(T)\;=\;f(T)\,U_{g}\;=\;f(T)\qquad\text{for all }g\in\mathcal{G}.$ $$

###### Proof.

Proof sketch: The assumption $U_{g}T=T$ forces $U_{g}$ to act as the identity on each nonzero eigenspace of $T$, which directly yields $U_{g}f(T)=f(T)$ for any bounded Borel $f$ with $f(0)=0$.

Step 1 (spectral decomposition for compact self-adjoint $T$ without measures).
Since $T$ is compact and self-adjoint, its spectrum is $\sigma(T)=\{0\}\cup\{\lambda_{n}:n\in I\}$ where $I$ is finite or countable, each $\lambda_{n}\neq 0$ is an eigenvalue of finite multiplicity, and $\lambda_{n}\to 0$ if infinite. Let $E_{\lambda}$ denote the eigenspace for $\lambda\neq 0$, and let $E_{0}=\ker T$. We have the orthogonal decomposition

$$ $\mathcal{H}\;=\;E_{0}\;\oplus\;\bigoplus_{\lambda\in\sigma(T)\setminus\{0\}}E_{\lambda},$ $$

and $T$ acts as scalar multiplication on each $E_{\lambda}$:
$T|_{E_{\lambda}}=\lambda\,\mathrm{Id}_{E_{\lambda}}$, $T|_{E_{0}}=0$.
Let $P_{\lambda}$ be the orthogonal projector onto $E_{\lambda}$ (for $\lambda\neq 0$) and $P_{0}$ onto $E_{0}$.
Then for every $v\in\mathcal{H}$ with expansion $v=v_{0}+\sum_{\lambda\neq 0}v_{\lambda}$ ($v_{\lambda}:=P_{\lambda}v$), we have

$$ $Tv\;=\;\sum_{\lambda\neq 0}\lambda\,v_{\lambda}.$ $$

Step 2 ($U_{g}$ fixes each nonzero eigenspace pointwise).
From $U_{g}T=T$ we get, for any $v\in E_{\lambda}$ with $\lambda\neq 0$,

$$ $\lambda\,U_{g}v\;=\;U_{g}(Tv)\;=\;Tv\;=\;\lambda\,v,$ $$

hence $U_{g}v=v$. Thus $U_{g}$ acts as the identity on each $E_{\lambda}$ ($\lambda\neq 0$).
Equivalently, $U_{g}P_{\lambda}=P_{\lambda}U_{g}=P_{\lambda}$ for all $\lambda\neq 0$.
(There is no restriction on $U_{g}$ inside $E_{0}=\ker T$.)

Step 3 (defining $f(T)$ for bounded Borel $f$ with $f(0)=0$).
Because $\sigma(T)\setminus\{0\}$ is at most countable and $T$ is diagonal on $\{E_{\lambda}\}$,
we can define $f(T)$ by applying $f$ on the spectrum of $T$ as

$$ $f(T)\,v\;:=\;\sum_{\lambda\in\sigma(T)\setminus\{0\}}f(\lambda)\,v_{\lambda},\qquad v=v_{0}+\sum_{\lambda\neq 0}v_{\lambda},\;v_{\lambda}\in E_{\lambda}.$ $$

The series converges in norm since the $E_{\lambda}$ are mutually orthogonal and
$\|f(T)v\|^{2}=\sum_{\lambda\neq 0}|f(\lambda)|^{2}\|v_{\lambda}\|^{2}\leq\big(\sup_{\lambda\neq 0}|f(\lambda)|^{2}\big)\sum_{\lambda\neq 0}\|v_{\lambda}\|^{2}\leq\|f\|_{\infty}^{2}\|v\|^{2}$.
Thus $f(T)$ is a bounded operator with $\|f(T)\|\leq\|f\|_{\infty}$.
(When $f(0)=0$, there is no contribution on $E_{0}$.)

Step 4 (invariance and commutation).
For $v=v_{0}+\sum_{\lambda\neq 0}v_{\lambda}$ as above and any $g\in\mathcal{G}$,
Step 2 gives $U_{g}v=U_{g}v_{0}+\sum_{\lambda\neq 0}v_{\lambda}$ and $P_{\lambda}U_{g}=P_{\lambda}$ for $\lambda\neq 0$.
Hence

$$ $U_{g}f(T)\,v=U_{g}\Big(\sum_{\lambda\neq 0}f(\lambda)\,v_{\lambda}\Big)=\sum_{\lambda\neq 0}f(\lambda)\,U_{g}v_{\lambda}=\sum_{\lambda\neq 0}f(\lambda)\,v_{\lambda}=f(T)\,v,$ $$

i.e., $U_{g}f(T)=f(T)$. In particular $U_{g}f(T)=f(T)U_{g}=f(T)$ for all $g\in\mathcal{G}$.
∎

###### Lemma 13 (Kernel invariance ⟺ \Longleftrightarrow operator commutation) .

###### Proof.

###### Lemma 14 (Borel functional calculus preserves invariance) .

###### Proof.

##### Consequence.

If $k$ is $\mathcal{G}$-invariant, then so is $k_{+}$ ([Equation 12](https://arxiv.org/html/2509.25051v1#A3.E12)).

## Appendix D Eigendecay comparison

In this appendix, we discuss in more details the empirical observations made in [Section 5](https://arxiv.org/html/2509.25051v1#S5) and formally derive some inequalities between Schatten norms of integral operators associated with $k_{\mathrm{avg}}$ and $k_{+}$.

### D.1 Empirical Observations

Here, we further discuss the empirical spectra reported in
[Figure 4](https://arxiv.org/html/2509.25051v1#S4.F4) (middle and right columns).

##### Computation of spectra.

The normalized Gram matrices ${\bm{K}}/n$ (where ${\bm{K}}=(k(\bm{x}_{i},\bm{x}_{j}))_{1\leq i,j\leq n}$) reported in
[Figure 4](https://arxiv.org/html/2509.25051v1#S4.F4)
are computed from $n=3000$ i.i.d. samples $\bm{x}_{i}\in\mathcal{S}$. We compare the spectra obtained with $k\in\{k_{\mathrm{b}},k_{\mathrm{avg}},k_{+}^{(\mathcal{D})}\}$ with $\mathcal{D}=\{\bm{x}_{1},\dots,\bm{x}_{n}\}$ and each $\bm{x}_{i}$ being chosen uniformly in $\mathcal{S}=[-1,1]$. We also report the spectrum of $k_{\mathrm{b}}$ when observations $\bm{x}_{i}$ are instead sampled from an alternative domain $\mathcal{S}^{\prime}$ of reduced volume, chosen such that $\operatorname*{vol}(\mathcal{S}^{\prime})=\operatorname*{vol}(\mathcal{S})/|\mathcal{G}|$. Finally, note that because $\mathcal{D}$ is a set of i.i.d. observations, the spectrum of $k_{+}^{(\mathcal{D})}$ approximates the one of $k_{+}$ on $\mathcal{S}$ (see [Section C.3](https://arxiv.org/html/2509.25051v1#A3.SS3)) so our observations transfer to $k_{+}$.

##### k + ( 𝒟 ) k_{+}^{(\mathcal{D})} on 𝒮 \mathcal{S} vs. k b k_{\mathrm{b}} on 𝒮 ′ \mathcal{S}^{\prime} .

For the base kernels $k_{\mathrm{b}}$ and groups $\mathcal{G}$ considered, the spectrum of $k_{+}^{(\mathcal{D})}$ on $\mathcal{S}=[-1,1]$ exactly matches that of $k_{\mathrm{b}}$ on the reduced domain $\mathcal{S}^{\prime}$. This indicates that $k_{+}^{(\mathcal{D})}$ faithfully incorporates the extra similarities induced by $\mathcal{G}$-invariance: it retains the eigendecay of $k_{\mathrm{b}}$, but as if it were defined on the quotient space $\mathcal{S}/\mathcal{G}$ of effective volume $\operatorname*{vol}(\mathcal{S})/|\mathcal{G}|$.(^8^88For a finite group $\mathcal{G}$ of isometries, one indeed has $\operatorname*{vol}(\mathcal{S}/\mathcal{G})=\operatorname*{vol}(\mathcal{S})/|\mathcal{G}|$ (Petersen, 2006).)

##### k + ( 𝒟 ) k_{+}^{(\mathcal{D})} on 𝒮 \mathcal{S} vs. k avg k_{\mathrm{avg}} on 𝒮 \mathcal{S} .

From
[Figure 4](https://arxiv.org/html/2509.25051v1#S4.F4) (middle and right columns)
, it is clear that the spectrum of $k_{\mathrm{avg}}$ decays at least as fast as that of $k_{+}^{(\mathcal{D})}$. They coincide for the RBF kernel and $k_{\mathrm{avg}}$ decays even faster for the Matérn kernel. In principle, this suggests that $k_{\mathrm{avg}}$ should admit tighter information-gain bounds and thus better regret guarantees. However, our empirical results contradict this prediction, as $k_{+}^{(\mathcal{D})}$ consistently outperforms $k_{\mathrm{avg}}$. This discrepancy highlights the fact that eigendecay alone does not fully explain BO performance, as pointed out in [Sections 5](https://arxiv.org/html/2509.25051v1#S5) and [6](https://arxiv.org/html/2509.25051v1#S6).

### D.2 Schatten Norm inequalities

While the empirical spectra in [Section D.1](https://arxiv.org/html/2509.25051v1#A4.SS1) already highlight a mismatch between eigendecay and observed BO performance, one may ask whether formal inequalities between the operators induced by $k_{\mathrm{avg}}$ and $k_{+}$ can be established. We record here for completeness that it is possible to control the Schatten class of $k_{+}$ in terms of the one of $k_{\mathrm{avg}}$.

Assume: $(\mathcal{S},\mu)$ is a probability space on which a finite group $\mathcal{G}$ acts measurably, and the base kernel $k_{\mathrm{b}}$ is bounded, symmetric, PSD, and nonnegative. Define

$$ $k_{\mathrm{avg}}(\bm{x},\bm{x}^{\prime}):=\frac{1}{|\mathcal{G}|^{2}}\sum_{g,g^{\prime}\in\mathcal{G}}k_{\mathrm{b}}({g\bm{x}},{g^{\prime}\bm{x}^{\prime}}),\qquad k_{\mathrm{max}}(\bm{x},\bm{x}^{\prime}):=\max_{g,g^{\prime}\in\mathcal{G}}k_{\mathrm{b}}({g\bm{x}},{g^{\prime}\bm{x}^{\prime}})$ $$

and $k_{+}$ as the kernel corresponding to the positive part of $T_{k_{\mathrm{max}}}$: $T_{k_{+}}=(T_{k_{\mathrm{max}}})_{+}$.

##### Schatten norm interpolation.

Let $H=L^{2}(\mu)$ be the separable Hilbert space of squared integrable functions on $(\mathcal{S},\mu)$, $T:H\to H$ a compact operator, and write
$s_{i}(T)$ for the singular values of $T$, i.e. $s_{i}(T)=\sqrt{\lambda_{i}(T^{*}T)}$,
arranged in nonincreasing order and counted with multiplicity.
The Schatten-$p$ norm is defined as

$$ $\|T\|_{S_{p}}:=\Big(\sum_{i}s_{i}(T)^{p}\Big)^{1/p},\qquad 1\leq p<\infty,\qquad\|T\|_{S_{\infty}}:=\sup_{i}s_{i}(T).$ $$

###### Lemma 15 (Monotonicity for pointwise kernels) .

If two kernels $k,k^{\prime}$ are bounded and satisfy $0\leq k\leq k^{\prime}$ pointwise, then $\|T_{k}\|_{S_{p}}\leq\|T_{k^{\prime}}\|_{S_{p}}$ for $p=2,\infty$. If $k$ and $k^{\prime}$ are also PSD, then $\|T_{k}\|_{S_{p}}\leq\|T_{k^{\prime}}\|_{S_{p}}$ for $p=1$ too.

###### Proof.

For $p=\infty$, the Schatten $p$-norm is the operator norm $\|T\|_{\operatorname*{op}}=\sup_{\|f\|_{H}=1}\|Tf\|_{H}$.
Pointwise $0\leq k\leq k^{\prime}$ implies
$\|T_{k}f\|_{H}\leq\|T_{k^{\prime}}|f|\|_{H}\leq\|T_{k^{\prime}}\|_{S_{\infty}}\|f\|_{H}$,
so taking the supremum over $\|f\|_{H}=1$ yields
$\|T_{k}\|_{S_{\infty}}\leq\|T_{k^{\prime}}\|_{S_{\infty}}$.
If $T=T_{k}$ is the integral operator associated with a nonnegative kernel $k$, then $\|T_{k}\|_{S_{2}}=\|k\|_{L^{2}(\mu\otimes\mu)}$.
Hence pointwise $0\leq k\leq k^{\prime}$ gives
$\|T_{k}\|_{S_{2}}\leq\|T_{k^{\prime}}\|_{S_{2}}$ for $p=2$ as well. Finally when $k$ is PSD, we have $\|T_{k}\|_{S_{2}}=\int_{x}k(x,x)d\mu(x)$ (and similarly for $k^{\prime}$) and again a pointwise comparison yields the result.
∎

From this we immediately obtain, for our specific kernels that for $p=2,\infty$, and also $p=1$ if $k_{\mathrm{max}}$ is PSD:

$$ $k_{\mathrm{avg}}\;\leq\;k_{\mathrm{max}}\;\leq\;|\mathcal{G}|^{2}\,k_{\mathrm{avg}}\quad\Rightarrow\quad\|T_{k_{\mathrm{avg}}}\|_{S_{p}}\;\leq\;\|T_{k_{\mathrm{max}}}\|_{S_{p}}\;\leq\;|\mathcal{G}|^{2}\,\|T_{k_{\mathrm{avg}}}\|_{S_{p}}$ $$

###### Lemma 16 (Interpolation inequalities for Schatten norms) .

For any nonnegative sequence $a=(a_{i})_{i\geq 1}$ one has

$$ $\|a\|_{\ell^{p}}\;\leq\;\|a\|_{\ell^{2}}^{\,2/p}\,\|a\|_{\ell^{\infty}}^{\,1-2/p}\qquad(p\geq 2),$ $$

$$ $\|a\|_{\ell^{p}}^{p}\;\leq\;\|a\|_{\ell^{1}}^{\,2-p}\,\|a\|_{\ell^{2}}^{\,2(p-1)}\qquad(1\leq p\leq 2).$ $$

###### Proof.

For $p\geq 2$,
$\sum_{i}a_{i}^{p}=\sum_{i}a_{i}^{p-2}a_{i}^{2}\leq\|a\|_{\ell^{\infty}}^{p-2}\sum_{i}a_{i}^{2}$,
giving the stated inequality.
For $1\leq p\leq 2$, write

$$ $\sum_{i}a_{i}^{p}=\sum_{i}a_{i}^{\,2-p}\,a_{i}^{\,2(p-1)}.$ $$

Let $r=\frac{1}{2-p}$ and $s=\frac{1}{p-1}$ (with the usual convention $1/0=\infty$).
For $1<p<2$ we have $1<r,s<\infty$ and by Hölder,

$$ $\sum_{i}a_{i}^{p}\;\leq\;\Bigl(\sum_{i}(a_{i}^{2-p})^{r}\Bigr)^{1/r}\Bigl(\sum_{i}(a_{i}^{2(p-1)})^{s}\Bigr)^{1/s}=\bigl(\sum_{i}a_{i}\bigr)^{1/r}\bigl(\sum_{i}a_{i}^{2}\bigr)^{1/s}.$ $$

Since $1/r=2-p$ and $1/s=p-1$, this gives

$$ $\|a\|_{\ell^{p}}^{p}\;\leq\;\|a\|_{\ell^{1}}^{\,2-p}\,\|a\|_{\ell^{2}}^{\,2(p-1)}.$ $$

The endpoint cases $p=1,2$ follow by continuity (and are trivial directly).
∎

Applied to $a_{i}=s_{i}(T)$, Lemma [16](https://arxiv.org/html/2509.25051v1#Thmtheorem16) yields the standard Schatten interpolation inequalities:

$$ $\|T\|_{S_{p}}\ \leq\ \|T\|_{S_{2}}^{\,2/p}\,\|T\|_{S_{\infty}}^{\,1-2/p},\quad(p\geq 2),$ $$

$$ $\|T\|_{S_{p}}\ \leq\ \big(\|T\|_{S_{1}}\big)^{\frac{2}{p}-1}\,\big(\|T\|_{S_{2}}^{2}\big)^{1-\frac{1}{p}},\quad(1\leq p\leq 2).$ $$

Since the spectrum of $T_{k_{+}}$ is the positive part of the one of $T_{k_{\mathrm{max}}}$, we have $\|T_{k_{+}}\|_{S_{p}}\leq\|T_{k_{\mathrm{max}}}\|_{S_{p}}$. We deduce the next lemma.

###### Lemma 17 .

For $p\geq 2$:

$$ $\|T_{k_{+}}\|_{S_{p}}\leq\|T_{k_{\mathrm{max}}}\|_{S_{p}}\ \leq|\mathcal{G}|\|T_{k_{\mathrm{avg}}}\|_{S_{2}}^{\,2/p}\,\|T_{k_{\mathrm{avg}}}\|_{S_{\infty}}^{\,1-2/p}$ $$

and if $k_{\mathrm{max}}$ is already PSD then for $1\leq p\leq 2$:

$$ $\|T_{k_{+}}\|_{S_{p}}=\|T_{k_{\mathrm{max}}}\|_{S_{p}}\ \leq|\mathcal{G}|\big(\|T_{k_{\mathrm{avg}}}\|_{S_{1}}\big)^{2/p-1}\,\big(\|T_{k_{\mathrm{avg}}}\|_{S_{2}}^{2}\big)^{1-1/p}$ $$

and

$$ $\|T_{k_{\mathrm{avg}}}\|_{S_{p}}\leq\big(\|T_{k_{\mathrm{max}}}\|_{S_{1}}\big)^{2/p-1}\,\big(\|T_{k_{\mathrm{max}}}\|_{S_{2}}^{2}\big)^{1-1/p}.$ $$

###### Lemma 15 (Monotonicity for pointwise kernels) .

###### Proof.

###### Lemma 16 (Interpolation inequalities for Schatten norms) .

###### Proof.

###### Lemma 17 .

## Appendix E Benchmarks

In this appendix, we describe the experimental setting and all the benchmarks used to produce the numerical results of Section [4](https://arxiv.org/html/2509.25051v1#S4).

### E.1 Experimental Details

In our experiments, every BO algorithm is implemented with the same BO library, namely BOTorch (Balandat et al., 2020). All of them are initialized with five observations sampled uniformly in $\mathcal{S}$. After that, at each iteration $t$, every BO algorithm must:

- •
Fit its kernel hyperparameters. This is done by gradient ascent of the Gaussian likelihood, as recommended by BOTorch. The hyperparameters are the signal variance $\lambda$, the lengthscale $l$ and the observational noise level $\sigma^{2}_{0}$.
- •
Optimize GP-UCB to find $\bm{x}_{t}$. This is done by multi-start gradient ascent, using the optimize_acqf function from BOTorch. As values of $\beta_{t}$ recommended by Srinivas et al. (2012) turn out to be too exploratory in practice, we set $\beta_{t}=0.5d\log(t)$.
- •
Observe $y(\bm{x}_{t})=f(\bm{x}_{t})+\epsilon_{t}$. Function values are corrupted by noise whose variance is $2\%$ of the signal variance.

We optimize over 50 iterations and typically measure the cumulated regret along the optimizer’s trajectory.

All experiments are replicated across ten independent seeds and are run on a laptop equipped with an Intel Core i9-9980HK @ 2.40 GHz with 8 cores (16 threads). No graphics card was used to speed up GP inference. The typical time for each maximization problem ranged from $\sim$1 minute (two-dimensional Ackley, $|\mathcal{G}|=8$) to $\sim$15 minutes (five-dimensional Rastrigin, $|\mathcal{G}|=3840$).

### E.2 Benchmarks

As GP-UCB is naturally formulated for maximization tasks, all benchmarks that require minimization have been multiplied by $-1$ to produce benchmarks on maximization.

##### Ackley.

The $d$-dimensional Ackley function is defined on $\mathcal{S}=[-16,16]^{d}$ with a global minimum at $f_{\text{Ackley}}(\bm{0})=0$ and has the following expression:

$$ $f_{\text{Ackley}}(\bm{x})=-a\exp\left(-b\sqrt{\frac{1}{d}\sum_{i=1}^{d}x_{i}^{2}}\right)-\exp\left(\frac{1}{d}\sum_{i=1}^{d}\cos(cx_{i})\right)+a+\exp(1),$ (15) $$

where we set $a=20$, $b=0.2$ and $c=2\pi$ as recommended.

The $d$-dimensional Ackley is invariant to the hyperoctahedral group in $d$ dimensions, which includes permutations composed with sign-flips. Consequently, in $d$ dimensions, $|\mathcal{G}|=\underbrace{2^{d}}_{\text{sign flips}}\underbrace{d!}_{\text{permutations}}$.

##### Griewank.

The $d$-dimensional Griewank function is defined on $\mathcal{S}=[-600,600]^{d}$ with a global minimum at $f_{\text{Griewank}}(\bm{0})=0$ and has the following expression:

$$ $f_{\text{Griewank}}(\bm{x})=\sum_{i=1}^{d}\frac{x_{i}^{2}}{4000}-\prod_{i=1}^{d}\cos\left(\frac{x_{i}}{\sqrt{i}}\right)+1.$ $$

The $d$-dimensional Griewank is invariant to sign-flips of all $d$ coordinates. Therefore, in $d$ dimensions, $|\mathcal{G}|=2^{d}$.

##### Rastrigin.

The $d$-dimensional Rastrigin function is defined on $\mathcal{S}=[-5.12,5.12]^{d}$ with a global minimum at $f_{\text{Rastrigin}}(\bm{0})=0$ and has the following expression:

$$ $f_{\text{Rastrigin}}(\bm{x})=10d+\sum_{i=1}^{d}\left(x_{i}^{2}-10\cos\left(2\pi x_{i}\right)\right).$ $$

The $d$-dimensional Rastrigin is invariant to the hyperoctahedral group in $d$ dimensions, which includes permutations composed with sign-flips. Consequently, in $d$ dimensions, $|\mathcal{G}|=\underbrace{2^{d}}_{\text{sign flips}}\underbrace{d!}_{\text{permutations}}$.

##### Radial.

Our radial benchmark is defined on $\mathcal{S}=[-10,10]^{2}$ with a global minimum at $f_{\text{Radial}}(\bm{x}^{*})=0$, where $\bm{x}^{*}$ is any $\bm{x}\in\mathcal{S}$ such that $||\bm{x}||_{2}=ab$. It has the following expression:

$$ $f_{\text{Radial}}(\bm{x})=f_{\text{Rastrigin}}\left(\frac{||\bm{x}||_{2}}{a}-b\right)$ (16) $$

where we set $a=10\sqrt{2}$, $b=0.8$ and where $f_{\text{Rastrigin}}$ is the one-dimensional Rastrigin benchmark.

Our radial benchmark is invariant to planar rotations. Consequently, $\mathcal{G}$ comprises an uncountably infinite number of symmetries.

##### Scaling.

Our scaling benchmark is defined on $\mathcal{S}=[0.1,10]^{2}$ with a global minimum at $f_{\text{Scaling}}(\bm{x}^{*})=0$, where $\bm{x}^{*}$ is any $\bm{x}=(x_{1},x_{2})\in\mathcal{S}$ such that $x_{1}=x_{2}$. It has the following expression:

$$ $f_{\text{Scaling}}(\bm{x})=\left(\frac{x_{1}}{x_{2}}-1\right)^{2}.$ $$

Our scaling benchmark is invariant to rescaling of both coordinates. Consequently, $\mathcal{G}$ comprises an uncountably infinite number of symmetries.

##### WLAN.

The WLAN benchmark consists of $p$ users scattered in an area $\mathcal{A}=[-50,50]^{2}$ and $m$ access points (APs) to be placed in $\mathcal{A}$. Therefore, the search space is $\mathcal{S}=\mathcal{A}^{m}$, which is $2m$-dimensional. Given a placement $\left\{(x_{i},y_{i})\right\}_{i\in[m]}$ for the $m$ APs, each user is allocated to the AP closest to it. Each AP $i$ has now a set $\mathcal{U}(x_{i},y_{i})$ of associated users.

Assume the AP $i$ is associated to the user $j\in\mathcal{U}(x_{i},y_{i})$. The quality of service (QoS) of the AP-user association is given by the Shannon capacity in Mbps:

$$ $C_{ij}=W\log_{2}(1+\gamma_{ij}),$ $$

where $W$ is the bandwidth of the signal (in MHz), $\gamma_{ij}$ is the signal to interference-plus-noise ratio (SINR) defined by

$$ $\gamma_{ij}=\frac{P_{ij}}{N+\sum_{k\neq i}^{m}P_{kj}}.$ $$

Here, $N$ is the background noise (in mW) while $P_{ij}$ is the power (in mW) received by user $j$ from AP $i$. The power received is computed using the well-known log-distance path-loss:

$$ $P_{ij}=10^{-L/10}\min(d_{ij}^{-\lambda},1).$ $$

where $d_{ij}$ is the Euclidean distance between AP $i$ and user $j$ and where $L$ and $\lambda$ are positive constants.

Finally, the objective function to maximize is the cumulated sum of Shannon capacities for every AP-user association:

$$ $f_{\text{WLAN}}(\bm{x},\bm{y})=\sum_{i=1}^{m}\sum_{j\in\mathcal{U}(x_{i},y_{i})}C_{ij},$ $$

where $\bm{x}=(x_{1},\cdots,x_{m})$ and $\bm{y}=(y_{1},\cdots,y_{m})$ are the positions of the $m$ APs on the x-axis and y-axis, respectively. In our experiment, we set $W=1$ MHz, $L=46.67$ dBm, $\lambda=3$, $N=-85$ dBm, $m=4$ APs and $p=16$ users.

Because the main goal of this task is to optimize the QoS by placing a set of APs, our objective $f_{\text{WLAN}}$ is invariant to any permutation of the coordinates in the vectors $\bm{x}$ and $\bm{y}$. Therefore, $|\mathcal{G}|=m!$.

Figure [5](https://arxiv.org/html/2509.25051v1#A5.F5) shows a depiction of the WLAN and the best placement of APs inferred by GP-UCB using $k_{+}^{(\mathcal{D})}$.

Figure: Figure 5: WN with the best positions of APs found by GP-UCB with $k_{+}^{(\mathcal{D})}$. APs are depicted by red triangles and users with blue circles. The throughput for each user is shown in Mbps.
Refer to caption: rsc/WLAN.png

## Peer Reviews

confidence: 2
contribution: 3
initial_rating: 6
presentation: 2
questions: Repeat from the weakness section:
1. Why PSD projection matters?
2. Why consider a spectral analysis?
3. The authors can explain more about how kernel validity relates to PSD properties, and why “valid covariance” matters in GP inference, and what specific advantages “max alignment” brings in the Bayesian optimization setting (e.g., in terms of acquisition behavior, uncertainty modeling, or convergence properties).
soundness: 3
strengths: The paper presents an original and conceptually appealing extension of symmetry-exploiting Bayesian optimization methods, offering a practical and theoretically grounded approach that goes beyond prior invariant-kernel formulations. By introducing the max-alignment view and the projected-max kernel, the authors propose a framework allowing Bayesian optimization to leverage approximate or continuous symmetries without requiring exact group knowledge. The integration of spectral analysis and PSD projection is technically sound and shows thoughtful consideration of kernel stability, while the empirical results convincingly demonstrate the benefits of sharper, symmetry-aware modeling.
summary: This paper proposes Symmetry-Aware Bayesian Optimization (SABO), a framework for exploiting known or learnable symmetries in black-box optimization problems to improve sample efficiency. Traditional approaches, such as Brown et al. (NeurIPS 2024), incorporate known invariances into Gaussian Processes through orbit-averaged kernels. This paper introduces a max-alignment view that aligns input pairs via the most similar symmetry transformations.
To address the fact that the resulting kernel may violate positive semi-definiteness, the authors introduce the projected-max kernel, which applies a PSD projection based on spectral (eigenvalue) analysis to restore validity. 
Overall, the paper contributes a more general method for incorporating symmetry structure into BO, extending symmetry exploitation beyond fixed and known invariance groups to settings where symmetries can be learned or adaptively aligned.
weaknesses: This paper's presentation significantly limits accessibility and clarity, especially for a broader audience. It does not clearly explain why PSD matters and what is the motivation of spectral analysis. Similarly, although the paper includes justification of the max-alignment view, the explanation remains largely heuristic. It does not provide an analytical argument or formal characterization of when or why this leads to better Bayesian optimization performance. As a result, the motivation still feels conceptually underdeveloped and difficult to follow for readers without deep kernel-theoretic background.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 4
questions: N/A
soundness: 4
strengths: * The paper is very clear and is well written.

* The paper addresses an important issue (the detrimental effect of symmetries on GP modeling with standard kernels, and thus on BO performance). The core idea to take the max instead of the average over group orbits is not novel in the general case, but its application to Bayesian optimization is novel, and the paper provides a significant amount of useful analysis to go along with this that make it, in my mind, a very original work.

* I especially appreciated the strong theoretical motivation in Section 3.

* The paper seems particularly appropriate for ICLR as it is about representation learning with symmetries.
summary: The paper introduces a Gaussian process kernel that handles symmetries (invariance over a group action), for the purpose of Bayesian optimization. One approach is to average the kernel over the symmetries. This paper proposes instead taking a max, which is not necessarily PSD, so then a straightforward PSD projection is included as well.

The paper does a theoretical analysis that provides strong motivation for the use of the max rather than the average over the group for the kernel. Empirical results show that this new kernel performs much better than baseline approaches for handling symmetries. Spectral analysis shows that existing generalization bounds do not predict the improved performance, and the discussion raises ideas for why that might be.
weaknesses: In Section 2.2 the paper describes data augmentation as "a popular way to enforce symmetry." I certainly appreciate that it is intractable in many settings, but by virtue of being popular, it should be compared to in this work. In Ackley2d it could be done directly, since |G| is only 8, and so with 50 total iterations, it becomes a lot of data but still feasible. On other problems, the popular strategy would be to randomly sample a few (still 8 perhaps?) items from G and just augment with those. These are pretty easy to implement and would strengthen the results of the paper significantly. It should come paired with including results showing wall times; the paper suggests that k_avg and k_max will have similar wall time, but it does not actually compare them both to k_b, and so it isn't clear if increasing the amount of data by 8x will make k_b slower than k_max and k_avg.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 4
questions: I’m not an expert; why is it difficult to identify a suitable fundamental domain to restrict the search space to, if one knows the symmetry group? Is there an easy example to demonstrate this? It would be good to explain this to readers less familiar with symmetry (which includes much of the BO community).
soundness: 4
strengths: - Paper is overall well written, clear, and concise. It outlines relevant related work and explains why their method might be preferred to each, situating their method well within the literature. Exposition of method is clear.
- Method seems general—can be used with any base kernel and be PSD thanks to their construction. Can be used with any symmetry group, just need to maximize over orbits. This operation scales quadratically with the size of the symmetry group but this is a problem for previous invariant kernels too (e.g., average kernels).
- Clear 1-D examples showcase how the max kernel more accurately models the objective than the average kernel.
- Regret is impressive compared to base and average kernels.
- Compares findings with spectral analyses and finds a gap, and suggests new ways to explain this gap, which may lead nicely into future work.
summary: The authors claim to contribute:
- Introduce a PSD projection of the max-alignment kernel over a symmetry group to avoid typical kernel averaging strategies, which can dilute high-similarity alignments when the symmetry group is large. This kernel is a valid GP kernel and doesn’t change the asymptotic cost of GP inference, so can be used for BO when the objective function is invariant under a known symmetry group.
- Their max kernel behaves as one expects on toy problems and does really well on standard BO test cases in comparison to the average kernel, which is the closest invariant kernel in the literature so far. It also outperforms standard kernels.
weaknesses: - I would appreciate more real-world BO test cases that are group invariant beside the one WLAN problem, to demonstrate that this is actually an important innovation for applications people care about. More argument about the relevance of this area in the intro, e.g., examples, could also help.


General feedback for improving paper: I think the intro is a little abrupt and a smoother motivation of why we care about max alignment before introducing notation and the PSD projection of the max kernel would help the reader.


I strongly recommend acceptance — the paper is well-written, introduces a max-alignment kernel which is not in the BO literature yet (to best of my knowledge) by approximating it with a projection to make it PSD. This leads to really good results on both toy, interpretable settings and on standard (group invariant) BO test functions. It seems clear that this work would be interesting to the BO community.


Decision: Accept (Poster)