Kernel conditional tests from learning-theoretic bounds
Authors: Pierre-François Massiani
Christian Fiedler
Lukas Haverbeck
Friedrich Solowjow
Sebastian Trimpe
Venue: NeurIPS 2025 poster ()
Keywords: kernel methods
hypothesis testing
statistical learning
Primary area: theory
TL;DR: We propose tests for general functionals of conditional distributions (including the two-sample test) with finite-sample guarantees and dependent data thanks to generalizations of time-uniform uncertainty bounds for kernel ridge regression.

Abstract: We propose a framework for hypothesis testing on conditional probability distributions, which we then use to construct *statistical tests of functionals of conditional distributions*.
These tests identify the inputs where the functionals differ with high probability, and include tests of conditional moments or two-sample tests.
Our key idea is to transform confidence bounds of a learning method into a test of conditional expectations.
We instantiate this principle for kernel ridge regression (KRR) with subgaussian noise.
An intermediate data embedding then enables more general tests — including *conditional two-sample tests* — via kernel mean embeddings of distributions.
To have guarantees in this setting, we generalize existing pointwise-in-time or time-uniform confidence bounds for KRR to previously-inaccessible yet essential cases such as infinite-dimensional outputs with non-trace-class kernels.
These bounds also circumvent the need for independent data, allowing for instance online sampling.
To make our tests readily applicable in practice, we introduce bootstrapping schemes leveraging the parametric form of testing thresholds identified in theory to avoid tuning inaccessible parameters.
We illustrate the tests on examples, including one in process monitoring and comparison of dynamical systems.
Overall, our results establish a comprehensive foundation for conditional testing on functionals, from theoretical guarantees to an algorithmic implementation, and advance the state of the art on confidence bounds for vector-valued least squares estimation.

Kernel conditional tests from learning-theoretic bounds
Pierre-François Massiani'
Christian Fiedler
Lukas Haverbeck
Friedrich Solowjow!
Sebastian Trimpe'
Institute for Data Science in Mechanical Engineering, RWTH Aachen University Department of Mathematics, School of Computation, Information and Technology, Technical University of Munich, and Munich Center for Machine Learning (MCML) (massiani, christian. f fiedler, solowjow, trimpe)@dsmm rwtth-acchen. de lukas. www.rbeeckrtthhaaacciiii.e
Abstract
We propose framework hypothesis testing on conditional probability distribu- tions, which then use to construct statistical tests of functionals of conditional distributions. These tests identify the inputs where the functionals differ with high probability, and include tests of conditional moments two-sample tests. Our key idea to transform confidence bounds of a learning method into test of condi- tional expectations. We instantiate this principle for kernel ridge regression (KRR) with subgaussian noise. An intermediate data embedding then enables more general tests including conditional two-sample tests via kernel mean embeddings of distributions. To have guarantees this setting, we generalize existing pointwise- in-time time-uniform confidence bounds for KRR previously-inaccesiie essential cases such as infinite-dimensiona. outputs with non-trace-clat kernels. These bounds also circumvent the need for independent data, allowing for instance online sampling. To make our tests readily applicable in practice, we introduce bootstrapping schemes leveraging the parametric form of testing thresholds iden- tified in theory to avoid tuning inaccessible parameters. We illustrate the tests on examples, including one in process monitoring and comparison of dynamical systems. Overall, our results establish a comprehensive foundation for conditional testing on functionals, from theoretical guarantees to an algorithmic implementa- tion, and advance the state of the art on confidence bounds for vector-valued least squares estimation.
yet
Introduction and related work
Deciding whether the inputs and outputs of two phenomena obey the same conditional relationship is essential in many areas of science. In control and robotics, one may want to detect changes in the dynamics time detect unusual perturbations; in industrial monitoring, to identify the perfor- mance of an equipment in varying operating conditions; and medical studies, to compare treatment responses based on patient characteristics. These examples exhibit the common characteristic that they concern the conditional distribution an output (next state, performance, treatment response,
Work conducted while with the Institute for Data Science in Mechanical Engineering, RWTH Aachen University
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

...) given an imput parameter, which we call the covariate (current state, patient characteristics, ...). The functional of interest the aspect of the output distribution we care about (expectation, other moment, full distribution, .... While there are methods to detect global changes or mismatches between (functionals of) probability distributions, they generally have at least one of the following limitations: (i) they already detect mismatch if the marginal distributions of the covariates differ while the conditional ones coincide [1]; (ii) they already detect a mismatch if they detect a global difference between the conditional distributions, disallowing questions such as at what covariate they differ or whether they differ at specific points of interest [2-8]; or (iii) they only provide guarantees in the infinitely- manny samples limit [2-9]. In contrast, we propose framework enabling finite-sample guarantees for conditional hypothesis testing at arbitrary covariates, generalizing such guarantees for classical hypothesis testing in the sense of Neyman-Pearsee
[10, Sections 8.1-8.3.1). To our knowledge, we are the first to formalize guarantees on the accuracy of the covariate rejection region, which is the set of points where the null hypothesis is rejected. This region and guarantees thereon enable identifying pointwise discrepancies between functionals of conditional distributions, rather than global discrepancies between joint conditional distributions.
Regardless of the covariate rejection region, conditional testing is notoriously hard - there exists no nontrivial test with prescribed level against all alternatives [3, 4J. This should be highly unsurprising to readers familiar with no-free no-free-lune free-lunch theorems in statistical learning theory [11], as conditional testing typically requires making thigh-probablln covariates where no samples were observed, and thus requires extrapolation power. We provide a systematic way to escape this negative result by making explicit the ties between conditional testing and learning theory: learning precedes testing, as confidence bounds of learning algorithms yield guarantees for conditional tests. This connection enables turning source conditions in statistical learning into "prior sets", that is, classes of alternatives for which a conditional test has guarantees. To our knowledge, we are the first to formalize this connection.
statements about conditional distributions at
The natural assumption on the data in conditional testing is that outputs are sampled according to conditional distributions given inputs. In particular, outputs are not necessarily identically distributed. They may even not be independent; e.g., in the online setting [12], where data is generated sequentially as future sampling locations depend previous measurements. This is technical challenge for sinite-sample guarantees and contrasts starkly with classical hypothesis testing [10, Chapter 8), where data is independent and identically distributed (i.i.d.) [1], approximately i.i.d. (mixing, ...) [13], or at least identically distributed given previous samples (online setting) [14, 15). A common approach in learning theory is to rely on measure along which the covariates concentrate [16-18]. We must alleviate such assumptions, however, as we seek answers that are pointwise rather than measure-dependent. We achieve this by relying on confidence bounds of learning algorithms, that is, pointwise probabilistic bounds on the error of the learned functions. This allows us not only to provide finite-sample guarantees, but also to operate on non-i.i.d. data, whereas previous studies are confined to asymptotic tests with i.i.d. data [2-9]. From a practical point of view, sequential data generation calls for repeated testing as more data becomes available, often requiring time-unifomm or anytime confidence bounds [12, 19-21]. The specific test we propose is based on such a bound, which we generalize to previously inaccessible cases thanks to new assumption we introduce and a strengthening of subgaussianity [22]. In particular, our bound is directly time-uniform.
The learning problems involved in conditional testing require mapping covariates the functional of interest. In some cases, this may be the full conditional distribution; e.g., in two-sample or indepen- dence testing [4]. Distributional learning usually addresses this by embedding said distributions as expectations in Hilbert spaces [23, 24). We leverage this idea by casting general conditional functional test as a comparison of conditional expectations with wrrrssonningly-embeeeeee however, confidence bounds applicable to such outputs. For instance, kernel ridge regression (KRR) ciine-niformm confidence bound for scalar outputs [12. 211, but its only extension outputs [20] requires strong assumptions on the kernel which exclude the data embeddings that allow testing for complex functionals such as those we identify for two-sample tests. We address this by establishing a time-uniform bound that holds under significantly weaker assumptions - this is our main technical contribution. It is the first bound to hold under such general assumptions to our knowledge, and recovers exactly the ones of Abbasi- Yadkori [12] and Chowdhury and Gopalan [20] in their settings. As a result, it also enjoys the interpretation of being frequentist correction of the Bayesian uncertainty bound obtained when interpreting KRR Gaussian process (GP) posterior mean [25, 26).
data. It requires,
admits a to

---

Our guarantees depend on quantities common in learning theory but inaccessible in practice. Further- more, saaminn-thhooreti bounds are commonly conservative as they are worst-case in the prior set, resulting in overly cautious tests. Estimation schemes for sharper bounds are thus essential. To that end, we provide heuristic bootstrapping schemes using the parametric structure of the testing thresh- old identified in theory. One is adapted from Singh and Vijaykumar [27] by modifying their standard error term in accordance with our results. In principle, they can be replaced by any alternative.
Finally, our approach is connected to several other methods, like multiple testing [28], though the hypotheses we test simultaneously are connected (through the prior set). Due to the uniform bounds, our test also enables sequential testing [29] and drift detection [30, 31], though the latter is generally performed on marginal distributions; e.g., by testing for independence between a time process and the process of interest. In addition, our tools can be used to perform anomaly detection [32], which we illustrate on an example, cf. Section 5. Finally, our general framework can be instantiated also to conditional independence testing, which in turn is known to be equivalent to conditional two-sample testing in some instances [4]. Further such investigations are left for future work.
Contributions and outline We provide a general framework for conditional testing and its finite- sample guarantees, and instantiate it for KRR together with bootstrapping schemes. Specifically:
1. We formalize the covariate rejection region and guarantees thereon, laying a basis for conditional tests (Section 3).
2. We turn confidence bounds of learning algorithms into statistical tests comparing conditional expectations (Theorem 4.2). Our instantiation for KRR (Theorem 4.4) is the first to enjoy finite-sample guarantees, and also to allow non-i.i.d. data.
3. We specialize the KRR instantiation to a test for functionals of conditional distributions which allows conditional two-sample tests (Section 4.3).
4. We provide and implement heuristic bootstrapping schemes of the resulting test.
5. We prove confidence bounds for KRR with dimense-dimeniionall outputs under unprecedent- edly weak assumptions (Theorem 4.3); specifically, Definition 2.4. The interest of this result exceeds conditional testing.
We expand on Contribution 3 above in Appendix A with its theoretical grounding and supporting ex- periments. The bootstrapping schemes and their numerical investigation are presented in Appendix B. Explicit algorithms for the test, and computing the effective test statistic and bootstrapped thresholds are in Appendix C. Appendix D further elaborates on how Theorem 4.3 relates to existing bounds in the literature. It relies the more general Theorem E.23 vector-valued least squares in separable Hilbert spaces, which we show and present as a standalone result in Appendix E. Appendix F is the proof of Theorem 4.2, and Appendix G has further information on our numerical experiments.
2 Preliminaries and notation
The set of positive integers is denoted by Nou, and for all n E N>o U {oo), [n] is the interval of integers between and n, with [oo] := N If u is a sequence and m, n E Noo, with m S n, we write Uyyn for the tuple with n - m + elements (um...., un.). If m = 1, we simply write W.n. If H, G are Hilbert spaces, L(H, 9) (resp., La (H, 9)) is the space of linear operators (resp., bounded linear operators) from H to G. If G = H. we simply write L(H) and Lo (H). Finally, for self-adjoint A Lb we define (g, A) (Ag, h), and denote the induced seminorm by IlA-
Markov kernels, conditional expectations We consider a complete probability space (2, A, IP) and input and output measurable spaces (X, and Ay),y), respectively. We assume that y C G as metric and measurable spaces, where G is a separable Hilbert space equipped with its Borel o- algebra, and that ) is closed. We define Mi (Z) as the set of probability measures on measurable space Z. We identify measures on y with their unique extension to G with support contained in V. Then, Markov kernel from X' to y is map p: Ay x X - [0, 1] such that p(-,2r) is probability measure on ) for all x E X' and p(A,) -) is measurable function for all A E Ay [33]. If P e Mī (G) probability measure such that the identity on G is (Bochner-)intes) Jintegrable w.r.t. P. we introduce its first moment E(P)- = Sy yd) E G. We say that Markov kernel from X' to ) has first moment if p(, 2)) does so for all a E X. Then, we use the shorthand (z)) == E(p(s,)) xr). Finally, we define the prior set θ as a set of Markov kernels from X to Y. Section 3 allows any such choice of θ and we specify in Section 4 assumptions on it under which can provide guarantecs.
3

---

Stochastic processes, subgaussianity A family of data- generating processes is family D {D, p 0}. where D is an x V-valued process indexed by N2 Such a D, is called data-generating process. If, additionally, D2 = [X p.n. pp.a))neN,,, satisfies
P\Yp.n E Xp... Xpm--1] -(:,
Xp.n) Vn E N50
almost surely (a.s.), say that Da is process of transition pairs, and that D is family of processes of transition pairs if (1) holds for all E O. Finally, we say that Dp is a process of independent transition pairs if (I) holds and (Xp.s ppn)neNso is an independent process, and similarly for D itself. For all N>o, introduce D. (X 3 and D U D,, Elements of D are called data sets, and for D == [( Yn InEN E D we define len (D) = N. Finally, a core assumption of our results is subgaussian noise. We consider the strengthening introduced in Mollenhauer and Schillings [22]. In contrast to the reference, however, we do not require that the variance proxy is trace-class, as results only require weakening of that condition.
Definition 2.1. Let R E (G) be self-adjoint, positive semi-definite. We say that a G-valued process 7 (1m) adapted a filtration F (Fo)nENso is R-subgaussian conditionally on F if
E [exp ((g, mm)c) [F]] S exp (I19)
E Vn E N>o, a.s.
(2)
If (2) holds with R pidg for some p E R20, say that n is p-subgaussian conditionally on F.. Similarly, we say that a Markoy kernel p E θ from to y C G is R-subgaussian
J exp (1g y (()) pldy, x) S exp (11911)). EgEg,
Vx E X,
(3)
and that it is sugaausssinn if (3) holds with R = pidg.
Kernel ridge regression We only provide minimal treatment of reproducing kernel Hilbert spaces (RKHSs) and KRR and refer the reader to dedicated references [34, 35] for details.
Definition 2.2. A G-valued RKHS H on X' is Hilbert space (H, (;)))x) of functions from to G such that for all x E X, the evaluation operator S, : f H + f(x) E G is bounded. Then, we define? ((- x) ;= S and K (2x,x') = S. for all x, x' E X. The map X x (9) is called the (operator-valued))
(reproducing) kernel of H.
Theorem 2.3. Let H be a G-valued RKHS with kernel K. Then, K is Hermitian, positive semi- definite", and the reproducing property holds for all x E X, (f, (.
H. and g E G: (f(x),9)g
It is well known that, for every Hermitian, positive there exists a unique G-valued RKHS of which K is the unique reproducing kernel. The kernel thus fully characterizes the RKHS, and we write (H, (s ()) =: (Hx, (s, k). We say that a kernll trace-class K (ar, x²) is, for all (x,x²) ) E X. We assume throughout that kernels are strongly measurable. We also introduce the following notion, which is new to the best of our knowledge and generalizes the common choice of a diagonal kernel, K = k idg.
function K : X x X - (G).
Definition 2.4. We say that the kernel K of G-valued RKHS Hx is uniform- mifoorm-block-diggnne (UBD) (with isometry (g) if there exists separable Hilbert spaces & and V, isometry 4g E Lb ② V.9). and kernel Kg X X > (G) (called elementary block) such that
K = Lg (Kn 8 id
In the following, we often assume that Kn is trace-class; this is weaker than K itself being trace-class. Informally, uniform-bloce ceatm--booooddignnntle is equivalent to the existence of base of where, for all (x, E X², the operator K K(x, x²) has the block-diagonal, operator-valued matrix representation
Ko(x,x')
K(x,a')
0
xo(z,x')
We emphasize that deviate from the usual convention formally, K (+, x)) is not detined as the function E X + K K(x', .x) ;= Sy E (g),), but as an element of LG(g, H). 'Recall that a bivariate function ø : X x X + (g) is Hermitian if ó(æ, x') = 6(x', x) It is positive semi-definite if for all E Noo. (x:) X², and (g)) G". DE Ejn1 (g,, 0(0r, 2, 29)91)9 2 0.

---

Finally, given a kernel K, data set D = [( [ E D, and regularization coefficient À E Ry0. we define fDA as the unique solution of the KRR problem, which has an explicit form,
N
fD, = arg min JEHx
1u f(xn))l + -151I = MM(MDM3 + AidgN) YoN, Σ
(4)
where MD = (h E Hx (M(X)))EE(NT E G E (HH GN is the sampling operator.
3 Conditional testing
We formalize conditional testing and introduce guarantees on the covariate rejection region.
Setup and outcome The general goal of conditional testing is to decide based on data whether specific statement about a conditional distribution holds at any user-specified conditioning location E X. which we call the covariate (parameter). Formally, (conditional) hypothesis is a map И x + {0, 1} such that, for every E O, the fulfillment region of H for p. defined as (p) : fz X' (x. p) 1]. is measurable. Hypothesis testing then involves two hypotheses Ho and H1. called the null and alternative hy hypothesis, respectively. We assume throughout that H1(x, p) -oo (z,P), p), where denotes the logical negation. A conditional test is then measurable map T : x D + (0, 1}. interpreted as T(x: D) = if, and only if, we reject the null hypothesis Hg the covariate
X based on the data D E D.
Types of guarantees The outcome of a conditional test T is the function T(,, D), which is equivalently characterized by the covariate rejection region.
Definition 3.1. The covariate rejection region of a conditional test T is the subset of X on which the null hypothesis is rejected based on the data. It defined for all D E as
X(D) ((; E Ax.
We emphasize that this definition finer-grained than most related approaches [2-8], which corre- spond to taking maxx T(,, D) for the outcome of the test. A conditional test has "perfect" outcome when the covariate rejection region x(D exactly recovers the complement the fulfillment region of Ho, which satisfies (p) 4 (p) and where introduced the shorthands & f i {0, 1}. follows that a test can make two "types" of errors at a covariate x E X, corresponding respectively to whether the covariate belongs to the sets
Ei D) X(D) n (o(p),
Eu(p, D) X(D) (pp)
We call the first kind a type 1 error and the second kind type 11 error; the sets Ei D) and En D) are called the error regions of the corresponding type. This terminology is consistent with the case of non-conditional hypothesis testing [10]; indeed, (i, D) contains the covariates where we incorrectly reject the null hypothesis, and En D) contains those where we fail to reject it. Then, a "guarantee" is probabilistic bound on the accuracy of (D); that is, on whether one of these regions intersects a region of interest at times of interest.
Definition 3.2. Let D (Dp)pee be family of data-genan eata--ennrating processes and i (I, The error function of type for D is the function 1); ④ x Ax x 2o + [0, 1] defined as
S, PDn N,S Ex(p, D p.m) A 0], S,A) E Ax Noo
For (S,N) Ax 2800 we say that the test has type (S, -uuarantte a E (0, sup,ce S. S a. A type (S, - is called an (S, Finally, if S = {x} or N = [n}. we abuse notation in the above definitions and replace the subset by its only element.
We emphasize the difference between having an (x. gegaranee for all E and an (X' .) guarantee. The former allows using the test at single arbitrary covariate, whereas the latter guarantees the performance when using the test jointly on arbitrary covariates and enables trusting the rejection region as whole. Similarly, guarantess for all Noo allow for one-time use of the test at an arbitrary time n E Noo. whereas (.Noo)-gurratte allows for sequential testing. Our tests have Nzo)- or (X, (X,n)-guaranteee -ugurranttsss depending on which assumptions are made.
5

---

While the formal definitions of type and type II eπrrr functions are symmetric, their reasonable targets are not. Type I errors are those we seek to control; their frequency must be less than the prescribed level everywhere in S, including in regions with little data. A false rejection of Ho must not be caused by lack of information. As result, control of type II errors is only achievable in regions of the covariate space where samples provide sufficient information (either through local sample mass or extrapolation enabled by the prior set). In other words, the type error function can only be low where the data actually enable distinguishing the alternative from the null.
4 Testing of conditional expectations and functionals
We specialize the preceding developments to tests of conditional expectations with finite-sample guarantees. We are interested in testing the null hypothesis*
Ho( (l(s,,P,P00 Pı, P2) (x)))(x)= (x)2)(x)) v.s. Hi (1,,,), (() + (x)2)()), (S) where (2), E θ x O₂ and O is a set of Markov kernels from X' to y with first moments, i E {1,2}. First, we provide an abstract result go from confidence bounds of learning algorithm to a test of conditional expectations (Theorem 4.2). We then specialize it to KRR in the well- specified case, obtaining two tests (Theorem 4.4) with similar thresholds but differing guarantees and assumptions: they are based on new confidence bounds for KRR which we present first (Theorem 4.3). We finally show how to specialize the test to functionals other than the expectation, allowing (among others) conditional two-sample test. This last point is further developed in Appendix A. Remark 4. The hypothesis (5) can be equivalently reformulated into the setup of Section 3, but we forego doing it explicitly for brevity. We emphasize, however, that we abuse notation and redefine the test T, covariate rejection region X. error regions E,, and error functions 17, E {I, II}, to take as inputs (where applicable) two data sets D₁ and D2. Markov kernels p1 and p2. and sets of integers
of interest N1 and N/.. Specifically, they are now defined as x(D,, D2) = T D D2) - EI(11,
(2, P2, D1, D2) = x(D,, D2) O (o(P), En P2, D1, D2) = x(1,, D2) n 45 (PL, and
(PI.
= TP (m11, n2) E x N2, S ECE,P,, Piim P2nin2) + o).
D(1)
(22)
respectively, where i E (T, II) and DQ) = (D()) pee,, E (1,2), are the considered families of data-generating processes.
4.1 From confidence bounds to hypothesis testing
We now provide an abstract result that connects finite-sample confidence bounds of a learning algorithm to type I guarantees for conditional two-sample test. For this, recall that a learning method 2 is map from data sets D E DD to functions fD X y.
Theorem 4.2. For i E {1,2], let L, D D +
p(( be a measurable learning method, and D be family of data- data-generaiing processes. For S E Axx N₁ S N and ó, E (0, 1), let : : B.a B.M. :D X >> Ryo be measurable function such that for all p O;
P V(a,n) SSEXXX No.
|
(z) (t)-E((())
< B, (D
21-8,
221 11-0, d, Vp e, (6)
Let T = BBB be the test defined as
1, 11
B (D.,,),
T: (I,, D1, D2) D2)
0, otherwise.
Then, T is test of Ho with N2) d1 + +8 when used on the families D(1) and D
The proof is in Appendix F. In more intuitive terms, this theorem guarantees that if one has two learning methods that come with associated confidence bounds (6) for a specific data-generating process (given by the functions B.) uniformly in O then one can leverage these intervals for
statistic [[([(( (a) $ (=)]l- This result is
conditional two-sample test with (covariate-depende very natural, and its value resides in clarifying the simple relationship between estimation and testing.
4 FFormally, (z Pl, P1.P2) P2) = if, and only if, ((p)) (z) = (x))
Seee Steinwart and Christmann [11, Definition 6.2).

---

4.2 A kernel test of conditional expectations
We now turn our attention to a specific learning method for which we show that the assumptions of Theorem 4.2 hold under sufficient regularity of the elements of è. Specifically, we consider KRR with kernel K : X X (9), as introduced
Section 2. The estimate fD.A for data set D E DD and regularization coefficient. À > 0 is given by (4).
4.2.1 Confidence bounds for vector-valued KRR
Section 4.1 has established that it suffices to provide confidence bounds for KRR with G-valued outputs. We provide such bounds in the following result.
Theorem 4.3. Let & D E + fo be KRR with regularization coefficient > and kernel K. X x + (g) Let be a Markov kernel from X' to G such that E(p) E H.g S E Ryo be such that [[[[]]] S S, and R E (g) be self-adjoint and positive semi-definite. Let = [(X,, Yn))n be a process of transition pairs of p. Introduce the usual notations for evaluations of the kernel on sequences:
((.) = (Om)me(n) E +
Σ
k(, Xm)dm E HKK E E
m=1
(8)
K(x, X.n) K(, K(, Xmn), X.)) K(,, X,n K(,
k(X,n,)) =
for all x E X and n E No0 as well as the shorthands
DD... (z) = K K(x x) - K(x, xn)) (K (K X.) + Aidgx) K (X...)).
(9)
and O D... ( = / (
Assume that is R- R-subgaussian, and assume one of the following and define 3x and N accordingly:
1. the kernel K is UBD with trace-class elementary block Ko and isometry ig E L. 3 V, and there exist p E Rz0 and Ry E (V) of trace class such that R = piig @ Ry)is Then, define N = Nya and, for all (n, 8) E Nso x (0,1). 1),
{ del idg. + x Ko X..)
1/27
Bx(D.n = S
P VX
2Tr(Rv)
(10)
2. R is of trace class, and D is a process of independent transition pairs of p. Then, define N = {N) } for some N N and, for all (n,8) Nso x (0,1).
A) = Tr(TD...) + (?) [TD lTT +
1 VĀ
+ 21n (3) | (TD...lle.(
(11)
where we introduced D..>. (VD.,, +Xid ) 11/2 Xx., ) X.n (VD... Xidxx) 11/2, with VD... K(, (., K(, )x
In both cases, all (0, 1), it holds that Pl E, N.Vr Vx E X. D,,, (x) (xpl(x) S B2(D:n, ( 21
For the readers familiar with GP regression [36, 37, 26). this result guarantees that the graph of the ground truth lies in a tube centered at the GP posterior mean with width the posterior variance scaled by 3x. with high probability. The bound is frequentist, however; the standard Bayesian assumption of GP prior replaced by the one that the conditional expectation lies in the RKHS. This result follows from Theorem E.23, which provides confidence bounds for vector vectorvalled least- squares (not necessarily an RKHS) under general assumptions. Theorem 4.3 and its generalization Theorem E.23 are together with the general setup of Section 3 - the main theoretical contributions of this work. A detailed discussion of the connections between Theorems 4.3 and E.23 and similar bounds is available in Appendix D.
7

---

Ground truth
Estimate
Function 1
Function 2
Reject
Accept
0.5
Analytical
Bootstrap
0.0
-0.5
0
0
Figure I: Analytical and bootstrapped tests toy example. The tests reject Hg (green thick line) when the confidence intervals (shaded regions) do not overlap, and accept it (red thick line) otherwise.
4.2.2 Application to testing
We can immediately apply the previous bounds to obtain kernel-based tests.
Theorem 4.4. In the setup of Theorem 4.2 and for all {1,2). assume that 2n is KRR with regularization coefficient X; > and kernel K X x X - (g()) Also assume that there exists S and R Lb(9), self-adjoint, positive semi-definite, such that any p E O, is R,-subgaussian and E(p) E HK with [[([)]] St. Let D(6) be famity of processes of transition pairs, and introduce the shorthands (9). Let a; E (0, Assume one of the following and define Br, Bi, and N accordingly:
(i) The assumptions of Case in Theorem 4.3 hold for R3 and K. Then, define Nr 2 and take B.) (e(D,a)) (x), all (D.x) E 'D x X, where B: == Bx, is defined in (10) with the corresponding choice of parameters.
(ii) The assumptions of Case in Theorem 4.3 hold for R₃ and D for all p E O. Then, define N₁ = {N:} for some N₂ E N and take B,(D,z) = (D, a.) OD. (x), for all (D,z) x² E D X, where 3 = 3x, defined in (11) with the corresponding choice of parameters.
Then, with this choice for B, in (6) for all E {1,2), (7) is a test of Ho with (2) Q1 + when used on the families (1)) and D(2).
This result formalizes the natural idea of comparing the norm difference between outcomes of KRR ran on both data sets to the sum of the (appropriately scaled) posterior variances of the associated Gaussian processes. The test is not fully distribution-fia [1] since it requires subgaussian Markov kernels, but allows data generated online. also allows pointwise testing with guarantees - regardless of the input data distribution thanks to the RKHS membership assumption. In practice, leverage the bootstrapping schemes described in Appendix to avoid tuning 3;.
4.3 From conditional expectations functionals
We now consider the announced case where we are interested in testing for equality of a functional FF of the conditional distributions; that is, we are interested in test of the null hypothesis
Ho(æ, P1, P2) ((p1(-,20 x)) =)) v.s. H1 (I, P1, F(p((. F(p2(, z)).
(12)
Examples involve FF being moments of the distributions, even the identity. Our idea is to make (12) amenable to the abstract test of Theorem 4.2 by reformulating it as a test conditional expectations. Specifically, we make the following assumption F. For consistency, we assume in this section that and P2 are Markov kernels from Ax) to measurable set (2,A)) which we call the measurement set, instead of mapping y' directly.
Assumption 4.5. There exists a separable Hilbert space G and a map 4 Z + G called a representation map of F such that = x G is closed, & is Bochner-integrable w.r.t. any probability measure on Z, and
V(P.Q) Mi(2)) (F(P)=((()))) =
f (=(s))P(()) = +)(2)d((2))
8

---

Ours
= 0.10
5 0.25
- 0.50
---- Baseline
0= 1.0%
0= 2.0%
0= 4.0%
1.0
Type EErro
Type 11 Error
Type 1I Error
0.5
0.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5 a
a
a
Figure 2: Empirical type or II errors. Left: Both tests uphold and achieve the level under Ho- Middle: Larger difference & between conditional expectations decrease the type II error. Right: Our local test can confidently detect difference in rarely (probability 0) sampled regions.
Under Assumption 4.5, (12) reduces to (5) where the Markov kernels involved are the push- forward kernels of Pr and P2 through Φy,, which we denote with ạ1 and G2. Crucially, a process of transition pairs ( = ((X,; Zn))n of p. available, the modified process D ((X,, 4 (Zn)))) is of transition pairs of q:- In other words, any learning method with guarantees for G-valued outputs be used test (12) via the data transformation Y, (..).
Assumption 4.5 satisfied many functionals common interest, such as the ones extracting the moments of distributions or the identity - the latter makes (12) conditional two-sample test. The test of Theorem 4.4 remains tractable even with infinite-dimensional G: complexity is exactly that of KRR. Furthermore, its assumptions such as subgaussianity now on the pushforward kernels gi instead of the kernels ps, E 21, We detail this and provide numerical examples in Appendix A.
Numerical results
We begin with an example illustrating the different components. We then evaluate performance (type I and II errors) in controlled settings compared to the baseline of Hu and Lei [5]. Next, we illustrate benefits of our test and its pointwise answers compared global conditional tests, thanks to the covariate rejection region and the fact that we obtain lower type II error when the tested functions differ only in rarely-sampled covariate regions. Finally, we showcase an application on change detection for a linear dynamical system. We remind the reader that Appendices A and B contain further numerical studies respectively comparing more general functionals (such as the two-sample one) and investigating our bootstrapping schemes. Finally, emphasize that the purpose of this numerical study not to establish dominance over other methods, but to investigate numerically how the framework works in well-understood scenarios. Additional information experiments, hyperparameters, and the link to the code are in Appendix G.
Metrics and setup We refer below to "type or II errors" and "positive rates" without referring to the corresponding triple (2)). They are meant as (S. n, - of type I or and as the positive rate of the test triggering anywhere in the subset of interest S with data sets of lengths E N We approximate triggering anywhere in S by evaluating the test at the locations present in the data A trigger type II error if it occurs in regions where Ho is enforced. We say "pick" a function when we randomly choose it from the unit sphere of the RKHS H on X. Except the last experiment, K is the scalar Gaussian kernel with bandwidth x2 0.25 [38]. Unless stated, data sets have 100 uniformly-sampe
points, and all results use the "naive" bootstrap (Algorithm 2).
Illustrative example With X [-1, 1], we pick two functions taking the role of conditional means to compare and generate two data sets of 25 noisy measurements. Figure 1 shows the outcome of KRR and of the test with analytical (left) and bootstrapped (right) confidence intervals (a = 0.05). The test rejects the null hypothesis exactly where the confidence intervals do not overlap. The bootstrapped intervals are much tighter, yielding higher power. Though we do not guarantee we find empirically that the true functions lie in the bootstrapped shaded region.

---

5 0.10
0.50
0.7.
d=2
d=
d=8
d=
Max. ratio
4.0
Change occurs
Norm x
1.4
3.0
Window done
2.0
adapting
1.2
1.0
1.0
0
50
100
150
200
250
300
350
200
Time
Time
Figure 3: Left: Ratio between test statistic and threshold for the process monitoring example for various dimensions (d) and perturbation magnitudes (E). Triggers correspond to exceeding 1. Solid lines are means; shaded regions are 5% and 95% quantiles. Right: Ratio (D.((.) in (9) on the reference data D between in the window and the initial state at t = 0, averaged over the window.
Empirical type I and II errors With X' = - 1-1, 1]3 we pick fi and fz. with l|f2ll = We perform the boostrapped test between noisy data sets twice: first, with both sets generated from fi (evaluating the type I error), and then with one set generated from fi and the other from fi + ʃ2 (evaluating the type II error). Figure 2 (left, middle) shows the empirical type and II errors as functions of a and Ç, as well as the baseline [5] parameterized by density estimators using the same KRR estimate as ours, together with the ground truth noise distribution. We uphold the type level everywhere, have similar type and II errors as the baseline without informing our test of the noise distribution, and achieve decreasing type II errors with increasing function difference.
Local sensitivity We now set X' = [- 3|2 3| pick fi. and set f2() At(.,0 0). We generate data from Si and fi + f2, which differ on Xditt := {ar X f2(x) 2 10-2) and (approximately) coincide on Xsame == X Kait. Data is sampled via mixture of uniform distributions on Xsame and on Xtitt Figure (right) shows the type IT error as a function of 0, the weight of Xai the mixture. Densities not estimated but set to their ground truth for the baseline [5]. Still, test achieves higher power for low values 0. This directly results from the locality of our tests (whereas the bascline computes one aggregated statistic), which is enabled by the local guarantees of theooree bounds.
Process monitoring We illustrate how the test allows dependent sampling by testing on the trajectories of linear dynamical system X' = Rd: the goal is to detect change in the dynamics. We consider a fixed reference data set of the transition pairs of 5 trajectories of length 400 with a fixed initial state. We compare trajectory by performing the test at every point in the window. We perturb the dynamics after 200 steps with a magnitude controlled monotonically by scalar parameter &. The results are shown in Fig. 3. We successfully detect the change reliably, even before the window is completely filled with data from the perturbed dynamics. This supports that the test performs well despite correlations in sampling locations. We hypothesize based on Fig. 3 (right) and the interpretation of D (x) as GP posterior variance [37] that the degraded performance for fixed
sliding window of length 50 of the transition pairs of the current
increases mainly due the perturbed dynamics driving the system in regions underexplored before the perturbation.
6 Conclusion
We rigorously introduce framework for testing conditional distributions with local guarantees. The framework broadly applicable and provides general recipe for turning Garming-thhoretee bounds into statistical tests. We instantiate it for conditional two-sample testing with KRR, enabling the comparison of not only expectations but other functionals such as arbitrary moments full conditional distributions. The guarantees are based on generalization we show of popular confidence bounds for KRR and regularized least squares to accommodate UBD kernels. To our knowledge, this is the first generalization to support such broad class of possibly pon-trace-class kernels. We present complete pipeline from conceptual foundations and theoretical analysis to an algorithmic implementation, and validate the approach through numerical experiments. Our framework offers principled foundation for developing powerful, flexible, and theoretically grounded conditional tests, laying a basis for a wide range of future applications theoretical investigations.
10

---

Acknowledgment
Friedrich Solowjow is supported by the German federal state of North Rhine- Seine-WWstppalia through the KI-Starter grant. Christian Fiedler acknowledges support from DFG Project FO 767/10-2 (eBer-24- 32734) "Implicit Bias in Adversarial Training".
References
[1] Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola. Kernel Two-Sample Test. Journal of Machine Learning Research, 13(25):723-773, 2012.
[2] Kun Zhang, Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Kernel-based conditional independence and application in causal discovery. In Conference on Uncertainty in Artificial Intelligence, pages 804 813, 2011.
[3] Rajen D. Shah and Jonas Peters. The hardness of conditional independence testing and the generalised covariance measure. The Annals of Statistics, 48(3):1514 1538, 2020.
[4] Seongchan Lee, Suman Cha, and Ilmun Kim. General frameworks for conditional two-sample testing. arXiv preprint arXiv:2410. 16636, 2024.
[5] Xiaoyu Hu and Jing Lei. A two-sample conditional distribution test using conformal prediction and weighted rank sum. Journal of the American Statistical Association, 119(546): 136-1154, 2024.
[6] Onur Teymur and Sarah Filippi. A bayesian nonparametric test for conditional independence. Foundations of Data Science, 2(2):155-11) 172, 2020.
[7] Philip A Bocken and Joris M Mooij. A bayesian nonparametric conditional two-sample test with an application local causal discovery. In Uncertainty in Artificial Intelligence, pages 1565-1575. PMLR, 2021.
[8] Anirban Chatterjee, Ziang Niu, and Bhaswar B Bhattacharya. A kernel-based conditional two-sample test using nearest neighbors (with applications calibration, regression curves, and simulation-based inference). arXiv preprint arXiv:2407. 16550, 2024.
[9] Jian Yan, Zhuoxi Li, and Xianyang Zhang. Distance and kernel-based measures for global and local two-sample conditional distribution testing. arXiv preprint 49X1v:2210.08119, 2022.
[10] George Casella and Roger Berger. Statistical Inference. CRC press, 2002.
[11] Ingo Steinwart and Andreas Christmann. Support vector machines. Springer, 2008.
[12] Yasin Abbasi-Yadkori, Online learning for linearly parametrized control problems. PhD thesis, University of Alberta, 2013.
[13] RJ Serfling. The wilcoxon two-sample statistic strongly mixing processes. The Annals of Mathematical Statistics, pages 1202-1209, 1968.
[14] Shubhanshu Shekhar and Aaditya Ramdas. Nonparametric two-sample testing by betting. IEEE Transactions on Information Theory, 70(2):1 2023.
[15] Aleksandr Podkopaev and Aaditya Ramdas. Sequential predictive two-sample and independence testing. Advances in neural information processing systems, (6:53275-53307, 2023.
[16] Ingo Steinwart and Clint Scovel. Fast rates for support vector machines using gaussian kernels. Annals of statistics, 2007.
[17] Ingvar Ziemann and Stephen Tu. Learning with little mixing. In Advances in Neural Information Processing Systems, volume 35, pages 4626 4637, 2022.
[18] Pierre-François Massiani, Sebastian Trimpe, and Friedrich Solowjow. On the consistency of kernel methods with dependent observations, International Conference on Machine Learning, pages 35013-35038, PMLR, 2024.

---

[19] Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In International Conference on Machine Learning, pages 844-853, PMLR, 2017.
[20] Sayak Ray Chowdhury and Aditya Gopalan. No-regret algorithms for multi-task bayesian optimization. In International Conference on Artificial Intelligence and Statistics, pages 1873- 1881. PMLR, 2021.
[21] Justin Whitehouse, Aaditya Ramdas, and Steven Z Wu. On the sublinear regret of gp-ueb. In Advances in Neural Information Processing Systems, volume 36, pages 35266-35276, 2023.
[22] Mattes Mollenhauer and Claudia Schillings. On the concentration of subgaussian vectors and positive quadratic forms in hilbert spaces. arXiv preprint arXiv:2306. 1404, 2023.
[23] Zoltán Szabó, Bharath K. Sriperumbudur, Barnabás Póczos, and Arthur Gretton. Learning Theory for Distribution Regression. Journal of Machine Leurning Research, 17(152):1-40, 2016. ISSN 1533-7928.
[24] Christian Fiedler, Pierre-Françon Massiani, Friedrich Solowjow, and Sebastian Trimpe. On statistical learning theory for distributional inputs. In International Conference on Machine Learning, pages 13608-1330 13632. PMLR, 2024.
[25] Christian Fiedler, Carsten W Scherer, and Sebastian Trimpe. Practical and rigorous uncertainty bounds for gaussian process regression. In AAAI conference on artificial intelligence, volume 35, pages
2021.
[26] Motonobu Kanagawa, Philipp Hennig, Dino Sejdinovic, and Bharath K Sriperumbudur. Gaus- sian processes and reproducing kernels: Connections and equivalences. arXiv preprint arXiv:2506. 17366, 2025.
[27] Rahul Singh and Suhas Vijaykumar. Kernel ridge regression inference. 202fv:2302.06558, 2023.
arXiv preprint
[28] Bradley Efron. Large-scale inference: empirical Bayes methods for estimation, testing, and prediction, volume 1. Cambridge University Press, 2012.
[29] Abraham Wald. Sequential tests of statistical hypotheses. Breakthroughs in statisties: Foundations and basic theory, pages 256-298. Springer, 1992.
[30] Fabian Hinder, André Artelt, and Barbara Hammer. Towards non-parametric drift detection via dynamic adapting window independence drift detection (dawidd). In International Conference on Machine Learning, pages 4249-4259, PMLR, 2020.
[31] Fabian Hinder, Valerie Vaquet, and Barbara Hammer. One or two things we know about concept drift-a survey monitoring evolving environments. Frontiers in Artificial Intelligence, 2023.
[32] Durgesh Samariya and Amit Thakkar. A comprehensive survey of anomaly detection algorithms. Annals of Data Science, 10(3):829 850, 2023.
[33] Olav Kallenberg. Random measures, theory and applications. Springer, 2017.
[34] Claudio Carmeli, Emesst De Vito, and Alessandro Toigo. Vector valued reproducing kernel hilbert spaces of integrable functions and mereer theorem. Analysis and Applications, 4(04): 377-408, 2006.
[35] Vern I Paulsen and Mrinal Raghupathi. An introduction the theory of reproducing kernel Hilbert spaces, volume 152. Cambridge university press, 2016.
[36] Carl Edward Rasmussen and Christopher KI Williams. Gaussian processes for machine learning. MIT press Cambridge, MA, 2006.
[37] Motonobu Kanagawa, Philipp Hennig, Dino Sejdinovic, and Bharath K. Sriperumbudur: Gaus- sian Processes and Kernel Methods: A Review on Connections and Equivalences. Technical report, 2018.
12

---

[38] Krikamol Muandet, Kenji Fukumizu, Bharath Sriperumbudur, and Berharrd Schölkopf. Kernel mean embedding of distributions: A review and beyond. Foundations and Trends in Machine Learning, 10:1-141, 2017.
[39] Steffen Grünewäller, Guy Lever, Luca Baldassarre, Sam Patterson, Arthur Gretton, and Mas- similano Pontil. Conditional mean embeddings as regressors. International Conference on Machine Leariing pages 1803-1810. PMLR. 2012.
[40] Christian Fiedler, Johanna Menn, Lukas Kreisköther, and Sebastian Trimpe. On safety in safe bayesian optimization. Transactions on Machine Learning Research, 2024.
[41] Zhu Li, Dimitri Meunier, Mattes Mollenhauer, and Arthur Gretton. Optimal Rates for Regular- ized Conditional Mean Embedding Learning. In Advances in Neural Information Processing Systems, volume 35, pages 4433 4445, 2022.
[42] Zhu Li, Dimitri Meunier, Mattes Mollenhauer, and Arthur Gretton. Towards optimal sobolev norm rates for the vector-valued regularized least-squares algorithm. Journal of Machine Learning Research, 25(181):1-51, 2024.
[43] Victor H Peña, Tze Leung Lai, and Qi-Man Shao. Self-normalized processes: Limit theory and Statistical Applications. Springer, 2009.
[44] Giuseppe Da Prato and Jerzy Zabczyk. Second order partial differential equations in Hilbert spaces, volume 293. Cambridge University Press, 2002.
[45] Heinz Werner Engl, Martin Hanke, and Andreas Neubauer. Regularization of inverse problems, volume 375. Springer Science & Business Media, 1996.
13

---

A Elaboration on functional tests
The goal of this section is to expand on the observation of Section 4.3 that Theorem 4.2 provides a test for the generalized hypothesis Hy defined in (12) for any functional FF satisfying Assumption 4.5. Specifically, we show and explain the following:
1. There are many functionals F that satisfy Assumption 4.5.
2. There is a general catalog representation maps & of functionals capturing specific properties of interest of the Markov kernels such as moments full distributions. The catalog consists of kernel functions, and the properties are the ones captured by the corresponding kernel mean embeddings (KMEs). This is summarized in Observation A.2.
3. Using KRR with a diagonal kernel K k- idg as the underlying learning algorithm enables computing of the thresholds and statistics even when the space G is anfinite-dimensional This last point is the reason why it is essential that Theorem 4.3 applies to infinite-dimensional outputs with non-trace-class kernels.
Together, these explanations show that we can specialize the test of conditional expectations into a test of more complex functionals of Markov kernels including conditional two-sample test while preserving computational feasibility. Indeed, the resulting computational cost is equivalent to that of KRR (with the chosen bootstrapping scheme, if thresholds boostrapped). We conclude this section with a numerical study highlighting the effectiveness of the test for different functionals.
We now study whether there are many functionals of interest that satisfy Assumption 4.5, and how to pick or find the corresponding map F We begin with an example exhibiting a suitable map & for the functional F extracting the conditional expectation and variance, and how to leverage KMES of distributions to capture a large class of functionals with explicit maps 2,, as it is required in the test procedure. Then, we explain how using KRR with diagonal kernel together with this idea yields the popular framework of conditional mean embeddings (CMEs) [38], enabling tractable computations even when G is highlighting how different choices of and 2 affect the test outcome.
We conclude this section with numerical study
A.1 Example: conditional expectation and variance
We begin with an example exhibiting a suitable representation map Dy of the functional F extracting the conditional expectation and variance. Assume that Z I,, and that P1(..2) 2) and p2(- x)) have well-defined first and second moments for all æ e X. This is for instance the case if Z is bounded. Introduce for (1,2} the first two conditional moments:
11 ( (z) (x) Ez~pi (-.)) [Z], and
( (x) Ez~pi (s [Za]
for all x X. Now define the functional F that maps measure the vector of its first moments.
For i E {1, 2}, we have
Mi (x)
F(p((;x)))
H2 (x)
Ez-pe [Z] Bz-pp(-sa)) (sa)) [z2]
zpi =p2((1,,0)) (d2,
(x))p;(d22,))
where introduced Φ : Assumption 4.5 with G 12.2
2 + (= =) This shows that the functional J satisfies
Let us now spell out the method summarized in Section 4.3 to obtain a test of equality of the first two moments. Assuming that one has access to processes of transition pairs (+) ((x²") ((1) DNeNs.
14

---

replace them with the processes
D = ((x(1) 1 := (0 MEN ((x29)
2
2 (1)
nENso
and use learning algorithm to learn the map from (X.")), (Yz²)), for each i E {1,2) (formally, the learning algorithm should seek to approximate the conditional expectation function of Y; condi- tioned on X which we assume is independent of n). As consequence of the data augmentation step y = (z),), notice that the output of this learning algorithm should 2-dimensional. Theorem 4.2 then guarantees that comparing the distance between the predictions of the two models to the sum of confidence bounds on the models' accuracy provides test with prescribed level of the hypothesis that the first and second moments of P1 and P2 coincide.
A.2 Generalization via kernel mean embeddings of distributions
We now generalize the ideas of the above example to find appropriate representation maps Φy of functionals of interest, as the testing procedure requires knowing these maps. The generalization based on the observation that, for a rich class of functions Assumption 4.5 are well-studied objects and capture specific properties of the underlying distributions. Furthermore, we argue that any functional J satisfying Assumption 4.5 has feature map belonging to the aforementioned class (Proposition A. justifying restricting our interest to this class.
G, the integrals involved in
Let us begin with this second point and assume that we have map Z - 9 available, where G is a Hilbert space, and let F be a functional of which & is a representation map. Another name for such
is feature map on Z, as can be thought of extracting information from a point E 2 and representing it in G. Readers familiar with RKHS theory may now recognize that the pair (#, 9) is feature map/feature space pair, and it defines unique RKHS on Z via the usual canonical isomorphism between feature space and the associated RKHS [11, Theorem 4.21). In more practical terms, the function & defines kernel
<(z, 2') (#) (z2)))
and its RKHS Mi is isometrically isomorphic to the closed span of the family (0(2) | 2 E 2} in g. It follows immediately that the map
= E k<,; E H..
also a representation map the same functional F. Summarizing, it is always possible to pick g to be an RKHS in Assumption 4.5, and + the associated canonical feature map. We formalize this in the following result.
Proposition A.1. Let F be a functional satisfying Assumption 4.5, and denote by t 2 - Go representation map of F. Let
(2,zz))) EZ (oo(=), Po(='))
Then, is is a kernel, and the map
$ : e 2 x(,;)) E H.
(13)
also satisfies Assumption for F.
Consequences Given a functional J satisfying Assumption 4.5, let us take a kernel function & such that Φ, is representation map of J. The assumption guarantees that, for any P,Q E MT (Z), we have F(P) = F(Q) if, and only if,
[ k(, x((2)))((s) = x(,2)dQ(==,
(14)
where the Bochner integrals are assumed to exist. We can immediately recognize that (14) is an equality between the KMEs of the measures P and Q for the kernel s. Introducing the KME map
H : M (M + / k(,, (()2)))M(x).
15

---

the condition (14) simply rewrites as -I, (Q). This observation is essential in practice, as the question of what information about a distribution is captured by its KME is a well-studied area of research [38]. For instance, the inhomogeneous polynomial kernel of order m E N captures the first m moments of a distribution; the exponential kernel captures the moment-generating function; and the Gaussian kernel captures the full distribution as it is characteristic [38, Sections 3.1.1 and 3.3.1J. In other words - and this is the concluding observation of this section:
Observation A.2 (Picking & in Assumption 4.5). When the map & is chosen the partial evaluation of a kernel function A as in (13), the corresponding hypothesis (12) asserts the equality of the corresponding KMEs of the conditional distributions. Therefore, the properties being tested are directly the ones these KMEs capture, and they depend on the choice of the kernel function K.
A.3 The special case of KRR with diagonal kernel: CMEs and their implementation
The challenge when following Observation A.2 and picking the representation map to be kernel canonical feature map is that the data is now composed of functions; specifically, the data sets have
the form (xx))) k((, 2/²² z="")) ))) and the model output should be an element of Hx. This may be impossible to handle for some learning methods; e.g., feedforward neural networks, which need an output of fixed, finite dimension. Furthermore, even when is possible to train and evaluate the algorithm with such data, computing the test statistic or threshold in (7) may still reveal intractable.
Fortunately, both of these concerns are void for KRR with diagonal kemel K k idw, (with le scalar kernel): it accepts functional data seamlessly, and the computations are tractable. As a matter of fact, KRR with diagonal kernel and such data recovers exactly the popular framework of CMEs [39].
Before proceeding, we emphasize that we now have two distinct kernel functions: the kernel K, which used to perform KRR, and the kernel k, which is chosen depending on the functional we wish to test for in (12) accordingly the developments of the previous section. The two are connected by the relation K = k idH... where & is a freely-chosen scalar kernel.
Computation of statistic and thresholds involved in (7). The computations achieve this are commonly known [38, Section 4. 4.1. and we report them here for completeness.
We are interested in evaluating the statistic and threshold
A first observation is that the quantities involved in the threshold specifically, those defined in (8)-(11) - only involve the kernel K. This kernel indirectly depends on k since K takes values in La (PH.), but we assume that under the UBD assumption, this assumption directly translates to the feasibility of these computations for Ko, which is trivially satisfied if & is finite-dimensional. This is the case in the standard case where = k idw., since 9 is simply R.
able compute the quantities involved for K. In particular,
Next is the computation of the statistic, [I,D,,,, (x)- - (D2 (x) x E X. Importantly, for every x X, ignoring the subscripts and 2 indexing over the two processes at hand for readability,
kCc, 21)
fD.A(1) = K(z, (AX + \id
<(., Zn)
We now leverage the fact that K le idu.. The identity operator on Hr factors out and obtain
((2,Z1)
fb.(()) = 2 Z X.) + Aidga)
((z,
Introducing now the coefficients
(x (k(x N x Aridey) - (((((())
16

---

for all i E {1 and with N = =len(D)) we obtain
I1 A22 (x)
(1)(
len D2)
Σ an (x) (1))((() )
+ Σ
7,m=1
n,m==
(x) (2) 2
Σ
a ( )
Here, we used the identity x(2, (m{. 2), kG H for all 2, 2. Concluding, if the underlying learning algorithm is KRR with kernel and threshold of the test of Theorem 4.4. We provide in Appendix C algorithms that summarize these computations for implementation purposes.
idH,, it is possible to evaluate the statistic
A.3.1 Numerical study
We illustrate the preceding ideas by showcasing how the choice of kernel influences what is being tested, and the power of the test for fixed amount data. The metries and vocabulary used the setup are identical to those introduced in Section 5, which recommend to read first.
We consider the Gaussian kemnel on X' [-1, pick a function in the RKHS of k, and generate measurements with two different additive noises: one is (N, s²), and the other is mixture of (--,, =2) and (1, s²), for different values of μu but fixed s². This choice guarantees that the noise distributions have both zero means, but differ for higher moments. We embed the measurements in = Hr. where x is either the inhomogeneous linear or the Gaussian kernel. The corresponding conditional expectations in G differ for the Gaussian kernel (since it is characteristic [38]), but coincide the linear kernel. As result, test with such data should trigger with x the Gaussian kernel, and not trigger with the linear one. We run vector-valued KRR with kernel K = k idn,, bootstrap test thresholds, and run the test on the locations present in the data set. Figure 4 shows the resulting empirical positive rate for different c-levels, confirming that the Gaussian kernel confidently sees a difference between the distributions, whereas the linear kernel only compares means and therefore does not reject more often than by chance.
However, a rich kernel like the Gaussian one can be less efficient comparing lower moments of distributions. We show this by comparing empirical eтror rates of the test for inhomogeneous polynomial kernels of different degrees and Gaussian kernels of different bandwidths for k. We use the same setup as before, but this time report type I and II errors instead of just the positive rate. the type error, we use the same function from X' 2 and noise distribution to generate different functions from X to Z, but the same additive
both data sets. For the type II error, Gaussian noise distribution, so that the distributions on Z differ by their means but higher moments coincide. Figure 5 shows that rich kernels (like the Gaussian one with small bandwidth) fime-grained distributional differences are less efficient at recognizing differences in the mean than less rich kernels (e.g., linear kernel) tailored to that particular moment of the distribution.
which see
17

---

Gaussian
Linear
y= 0.050
/ 0.075
# 0.100
1.0
Positive rate
0.5
0.0
0.0
0.2
0.4
0.6 0.8
1.0
a
Figure 4: Comparing the Gaussian and inhomogeneous linear kernels on different distributions having the same conditional mean the mcasurement set Z. A trigger is true positive for the Gaussian kernel, and false positive for the linear one. The results are averaged over 100 runs the experiment, with the shaded regions reporting the 2.5% and 97.5% quantiles.
Gaussian
=
=0100
y 0.15
Polynomial
d=1
d=2
d=
1.0
Type I Error
Type II Error
0.5
0.0 0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Figure 5: Empirical type I and II errors for different output kernels. For the type II error, conditional expectations in Z differ but higher moments coincide. We see that Gaussian kernels are more conservative and achieve higher type II error. The results are averaged over 100 runs of the experiment, with the shaded regions reporting the 2.5% and 97.5% quantiles.
18

---

B Bootstrapping
The general outcome of Theorem 4.4 is that, under the appropriate assumptions on both O and the sampling process or kernel, a suitable choice for (B(,)z) x)) has the form (D)) = 3 D. (z), where 33 O. There are three main reasons, however, for which the practical use of the specific expression of 3; may be limited. First, it significantly depends on parameters that are hard to infer, such as the RKHS norm upper bound S, and the sub-gaussianity constant or operator R, [25, 40]. Second, even when such parameters are known, evaluating the constant numerically may still be challenging due to the presence of (possibly) infiniteddimensioaal objects in the expression. Finally, these bounds may be very conservative, as they are essentially worst-case in θ, This last point is well-known in practice and further illustrated by our numerical experiments below.
These considerations motivate bootstrapping values of 31 and 32 suitable for the problem at hand. Let D1 and D2 denote the observed data sets of transition pairs from pl and p2. with respective sample sizes n1 = (D) and 12 (en(D2). We assume a sufficiently dense finite subset M j [J}} C S, obtained for instance by gridding or random sampling, on which we want the type error calibration to hold. We neglect bootstrapping over time, meaning that the resulting values are only meaningful for (S, n1, (22) -ugaranttees. We further fix B; = Bi DD so that the test T is parameterized by the vector conservative value for 3 as measured by the empirical type 11 error on test scenarios while preserving a type error of at most a.
(81,83) E R2 Our goal is finding numerically a minimally
In the following, we detail two possible approaches that calibrate 31 and 32 independently of each other. The first essentially bootstraps each value by applying the test resamplings of the same data set. The second one bootstraps the confidence bounds of the underlying KRR. Both methods work by generating M bootstrap replicates, obtaining statistics (Bem))m(s)) for each i {1, 2). and taking
= at) aqu-nnatttleeeeeee of (8,m))
= a(1 f)) -quantile of (.2.m)
with uper-fie t (0, 1). When needed, grid-search over is inexpensive. We use = 1/2 in all simulations.
The following two schemes now differ only in how the families (B,m)mm(M) are generated. Table 1 summarizes the difference in computational complexity.
Naive resampling A straightforward approach is to resample the data directly. For each {1, we draw with replacement M pairs of data sets ((Am. A'm,) Am))m from D;, where each data set in the pair has the same size as D.. For each m, we then compute Bi.m as the minimal Bi E R& such that
||/am.,, (x) fay .,, (x)] S Bm (oAm)A, + o (.
for all x E M. See Algorithm 2 for more details.
Wild bootstrap A more scalable alternative is the wild bootstrap. which replaces repeated resam- pling and re-fitting by random perturbations of the residuals of the nominal KRR estimate. Following Singh and Vijaykumar [27], we adopt anti-symmetric multipliers, which in the scalar-output case were shown to mitigate regularization bias and improve calibration accuracy. Such an analysis is un- available in more general setting, but we apply the same construction by straightforward extension to dinli--dmmesionall outputs. However, we use the standard error term (x)) defined in (9) for studentization to remain consistent with the theory-backed form of the confidence bounds identified in Theorem 4.3. For each i E (1, draw independent mean-zero multipliers (m) E R"; )e{MM]] with covariance In, 11 T /n: and collect the perturbed residual data set
((x).05m) (m) (Y; - fD.A. (X,Y)))D,"
Am
from which Be.. is obtained as the minimal Bm E RR0 satisfying
Ilfam... (z)1l < Bm (2)
for x E M. This method requires only single KRR fit since the Gram matrix for any Am the same as for D,. See Algorithm 3 for more details.
19

---

Table 1: Asymptotic time complexity for computing the test threshold with different calibration methods, in excess of fitting the models fD.. for E {1,2}, and evaluating the test statistic AA, (a) - /D2.2g (a)]l over x E S. Here n, denotes the data set size, m |M] the grid size, and M the number of bootstrap replicates.
Method
Analytical bound
Naive bootstrap
Wild bootstrap
Runtime
(1)
O (M + +Mmm?)
O (Mmn
Naive
Wild
Singh et al.
==
72 =0=0
n= 100
1.0
Type I Enror
Type II Exron
0.5
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
a
(a) Influence of data set size
712
Naive
Wild
Singh ct al.
2=00001
1 0.1
1.0
1.0
Type I Enror
Type II Error
0.5
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
a
(b) Influence of regularization parameter X A1 Au-
Figure 6: Type and II errors for the test with different bootstrapping schemes, at varying data set sizes and regularization levels A. Type error becomes faithful to the level when n and are sufficiently large. Power increases for larger n and smaller A. The results are averaged over 100 runs of each experiment. Confidence intervals are omitted for readability. "Singh et al." refers the method proposed in [27].
Validation We assess calibration and power for three bootstrapping schemes: (i) naive resam- pling bootstrap; (ii) our wild bootstrap; and (iii) the wild bootstrap of Singh and Vijaykumar [27], which differs from wild bootstrap only in the studentization term, using
DD.,. =1(((((x))) x!!I) Arnn.)
k(X(!) x))) diag (EI,,.,,EE.))
g".
where D, ((x))) (1) y )) is the data set and e, x, fD. (x)(0) are the residuals in our wild bootstrap.
We compare the performance of these methods in varying conditions on synthetic data sets generated in way that either satisfies the null (for the type error), or violates (for the type error). For that, we set X' [-1, 1, 1]2 take & as the Gaussian kernel with bandwidth y2 0.25, and generate data as measurements of functions in He with additive Gaussian noise. For the type error, we use equal mean functions with Gaussian noise, and for the type II error use different mean functions with the same noise distribution. For each configuration, we bootstrap the confidence thresholds and run the test.
20

---

Analytical
Bootstrap
o= 0.00
6= 0.10
o= 0.50
1.0
Type EError
Type II Error
0.5
0.0
000
000
000
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Figure 7: Type I and II errors for the test with the bootstrapped and analytical thresholds. Analytical thresholds yield very conservative test (level is less than a, but the type I and II errors are independent of In contrast, bootstrapping preserves the guarantee and increases power. The results are averaged over 100 runs of the experiment, with the shaded regions reporting the 2.5% and 97.5% quantiles.
Varying data set size Figure 6a reports results for data set sizes n = = n2 E {20, 50, 100). Type error increases with and improves with n. They all uphold the level, except for the naive method with n = 20. For fixed regularization X = 0.5, all methods become more conservative as n grows. Accordingly, type II error improves for increasing and n.
Varying regularization In Figure 6b, we now vary the regularization = A X e
{10-3, 11--,11,,, 11.. At fixed data size n 500, larger yields more conservative calibration. while smaller À result in overly aggressive bootstraps and the type I error exceeding the prescribed level a.
Put together, these results indicate that sufficient data and suitable choice of are critical for good calibration. Across both experiments, naive resampling is more aggressive (higher type and lower type II error), our wild bootstrap is more conservative (lower type and higher type II error), and the variant by Singh and Vijaykumar' [27] lies in between.
Power against analytical calibration To confirm the increase in power gained by bootstrapping relative analytical thresholds, now fix n and X, and vary the noise variance Because the outputs of functions in H4 are one-dimensional, the sub-Gaussian noise operator reduces to a scalar, which we the ground-truth variance. For the bootstrapping scheme, we only compare against our naive resampling method. Figure shows that the analytical thresholds are markedly conservative: type error remains well below a and both errors are essentially independent of In contrast, the type eиror of the bootstrap tracks the level a more faithfully and achieves significantly lower type II error. Overall, this indicates that bootstrap calibration yields strictly higher power fixed a without sacrificing control of the type I еттоr.
For more details the experiments in this section, Appendix G.
21

---

C Summary of algorithms
Algorithm summarizes our implementation of the test Theorem 4.4. The bootstrapping of the multiplicative constants 8; i E {1,2) it relies on is detailed in Appendix B, and summarized in Algorithms Algorithms 2 and 3. We emphasize that, principle, any other bootstrapping algorithm for KRR can be used. All routines assume the form K" = k k- (c.f Appendix A). Algorithm 4 shows how to compute the test statistic, called the conditional maximum mean discrepancy (CMMD).
Algorithm 1 Kernel conditional two-sample test
Require: data sets D1, D2; tested covariate region S S X; bootstrap covariate region M C X Ensure: Covariate rejection subregion of S, with type error at most a
1: 31 + Bootstrap(D1, D,,
> use either Algorithm or
2: 82 f Bootstrap(D2,
3: return {ær E S CMMD(D1, D2, 2, B1 (D, B2 )D.((
Algorithm 2 Naive bootstrap
Require: data set D; grid M
Ensure: Chooses s.t. does not reject on M for an a-)-fraction bootstrapped data
1: for f- 1 to M do
2: D1, D2 D
resample D1, D2 from D uniformly with replacement smallest 3 s.t. test does not reject D1, D2
(AAMD(D,.Dg.eeaeee oo, x()
3: Bj M
4: return (1 ax) quanttle of (B, 15 [M]}
Algorithm 3 Wild bootstrap
Require: data set D; grid M
Ensure: Chooses 3 s.t. test does not reject on M for an (1 a--fraction of bootstrapped data sets
I: K + |k(x, x (D..
J)D,
2: L |x(2,
( (.,))DD,
( E.
3: k [k(x, 2") (Z).)))
Va M
4: A (K + >lIi))
K
5: V. (K + \IDD)
kr
6: for < 1 to MM do
7:
q ~ No I|D|
[ 1
D wild multipliers
8:
& - q @ tr
Vx E M
D c denotes Hadamard product
9: B₁ - max.eM
TDا(TE] (ET -I L( - A)E)
-
1/2
10: return (1 a) quantile of (B, j [M]]
Algorithm CMMD: Conditional maximum mean discrepancy
Require: covariate X:; data sets D1; D2
Ensure: Computes ()D,)(z) - fD H.
1: K, < [k(x, x!) (z,))
.)ED.
V i (1,2]
2: k; < [k(2, x') (e)) (xD
iE (1,2]
3: a < (K; + ATDp.)) 'k
V i (1,2]
4: Cyyt (k(2,22))( ())=)))( ((()))))
Vi.j (1,2)
5: return (a] Cnaa a, C12ag + a C22a2)
1/2
22

---

D Connections between Theorem 4.3 and existing bounds
Case in Theorem 4.3 generalizes Corollary 3.4 in Yadkki [12] outputs in separable Hilbert spaces without introducing conservatism, as it recovers exactly the same bound as in this reference under the assumptions there. It also generalizes Theorem in Chowdhury and Gopalan [20] by removing the regularity assumptions connecting the input set X' and the kernel K (in the reference, X' is compact and K is bounded). It further generalizes this same result in yet another way by removing the assumption that K should be trace-class, replacing it by the (significantly milder) assumption that Ko should be so and hereby allowing the special case of a diagonal kernel K = k. idg. To the best of our knowledge, this is the first time-unfform uncertainty bound for KRR allowing this essential case.
The assumption that the kernel K is UBD in Case above is the central methodological contribution of the proof. It enables us to generalize the proof method of Abbasi- Yadkori [12] by leveraging a tensor factorization of the RKHS Hx (Proposition 12). Specifically, Proposition E. 12 allows avoiding the usual problems encountered with con-trace-elass kemels- more precisely, that trace-dependent quantities explode - by replacing them with the corresponding quantities for the elementary block Ko- Intuitively, all of the "estimation machinery" performed the RKHS of Ko, which is a trace-class kernel and for which classical methods work well, and we simply need to ensure that the noise is "compatible" with this structure. Here, this compatibility takes the form of the operator By being trace-class. Interestingly, special case of Proposition 1. has been used in Li et al. [41] (Theorem 1) to identify HK with a space of Hilbert-Schhiid operators in the case K = k idg. hereby avoiding problems with the trace of K by working with that of k, similarly to us. While Li et al. [41] is focused on learning rates for conditional mean embeddings, the subsequent work [42] investigates (in some settings minimax optimal) learning rates for vector- valued KRR, utilizing essentially the same strategy of identifying KRR using a kernel of the form K = k idg with regularized estimation of Hilbert--chmidt operators. Conceptually, both [41, 42] and our work use a tensor space construction to avoid problems with quantities related to trace-class operators, however, the technical details significantly differ. First, [41, 42) uses an identification with Selhirt operators, whereas we work with more general tensor product structures, that allow us formulate our results using UBD kernels. Second, [41, 42] aim learning rates in a typical supervised learning setup, in particular, with random covariates, whereas we are interested in uniform (in the covariates) confidence bounds, and hence the proof techniques are rather different. Finally, the regularized beast-squares algorithm analyzed by [41, 42] is not affected by whether the used kernel is trace-class or not, only the analysis needs to take this into account. In contrast, we need the tensor structure as formalized by our UBD assumption to even have well-defined expression for the confidence bound due to appearance of the Fredholm determinant. We would like to remark that it appears that many arguments of Li et al. [41, 42] also hold under the more general assumption that K is UBD. An interesting avenue for future work is thus to investigate to what extent this generalization carries over, and whether the derived learning rates, e.g., [41, Theorem 2], hold under UBD. Summarizing, believe the UBD assumption and the resulting structure of the RKHS identified in Proposition E. is a relevant new idea to handle large class of non-trace-class kernlls and can be used in other areas of kernel methods such as learning theory with loss functions compatible with the structure.
We emphasize that the subgaussianity assumption of Case 1 is in general a strengthening of the assumption that p p-subgaussian for P E Ryo, but also a weakening of the one that p is R'- subgaussian for R'' E (G) self-adjoint, positive semi-definite, and of trace class. This last case was first introduced Mollenhauer and Schillings [22], to which we refer for an interpretation. The structure we require on R clearly identifies how much control we need on each of the components of the noise: those that are handled by the RKHS of the trace-class kernel Kg may be simply p- subgaussian, while the those that are not must have a trace-class variance operator. In fact, if the kernel K is itself of trace class, we may take Ko = K in the theorem and the assumption simplifies to being p-subgaussian.
Finally, Case 2 does not require any structural assumptions on K (such as trace-class or UBD), but assumes independent transition pairs (excluding online sampling) and yields a time-local bound (since A = (N]). is thus of independent interest to Case 1, as they apply different settings. is also worth noting that the proof of Case 2 is considerably simpler than that of Case 1, as it follows directly from results on concentration of quadratic forms of subgaussian vectors with independent coefficients [22].
23

---

E Generalized confidence bounds in vector-valued least squares
We provide in this section the proof of Theorem 4.3. Specifically, we show more general result which does not assume that the space Hg in which the estimator lies is an RKHS; only that is generic Hilbert space H. The result show is given later in this section in Theorem E.23 and pertains to confidence bounds in vector-valued least squares estimation under general assumptions on the sampling operators; KRR is then obtained for specific choice of the measurement operators and Hilbert space where estimation is performed.
This section is organized as follows. We first provide in Section E. the general setup of vector-valued least squares estimation, and identify that the main challenge for confidence bounds is bounding specific term involving the noise. We then provide in Sections E.2 and E.3 methods to bound this term under different assumptions that we formalize. The main intermediate results of those sections are Lemma E.4, Theorem 1,14, and Corollary E.20, and are essential in the proof of Theorem E.23, which we only state and prove Section E.4 as we provide gentle introduction its assumptions first. We finally leverage it in Section E.5 to show Theorem 4.3.
E.1
Setup and goal
Let H and G be separable Hilbert spaces, and D [[Ln, In Un)neN be an Lb(H, 9) x G-valued stochastic process. The operators L,, are called the (random) evaluation operators and the vectors yn the evaluations (or measurements), n E N We assume that there exists h" E H and centered G-valued process 7 = (fn (Nn)ngN,0 such that yn. L + Ta- Let now À and define regularized least-squares problem with data D at time N Nyo as
N 11
arg min KEH
Σ
1 + XllI
(15)
This optimization problem has a well-known solution, which we recall below together with the proof for completeness.
Lemma E.1. For all N E Nyo, the optimization problem (15) has unique solution hx and
AN = (M&M + (idx) -MNNN,
(16)
where we introduced the operator My and its adjoint as
N
My:h E H + (Lali)EEN) E E and My : (gi...., .nv) E GN + Σ
Lign.
(17)
n=]
24

---

Proof. Rewriting the objective function and completing the square leads to
N
N
Vnn
Lnhll +
Σ
(Ur
L,h, Un Ln + X(h,
12
NV.
N
11unll - Σ
Uns h +
Σ
(Inh, Lnn + X(h, hip
n=1
Tx Tm idzz
h,h
2
Σ T Tun h
llyall
H n=
-| Emm
Σ
Linhin Xidx
Lin h
1. Fm Aid
M 1.y In Aidge
N
-1 N
Σ Li + Xidz
Σ
Un
n=1
D 4. h. tidx
In In + Xidæ
Σ
L
NNN Li La Aidx
1 11
N
Σ Ln + didl
Σ Li
Terms without h
MN Litii
Since E Ln Xidx MM + Xidæ is positive definite, and E Linn M this shows that the unique solution to the optimization problem (15) is indeed given by (16).
Our general goal is obtain a finite sample confidence region for the estimator hN.A of h". While we only state the precise result in Section E,4, we want - in short - high-probability bound on the quantity |L Lh llg. Here & is Hilbert space and L E (., 9) is a bounded operator capturing an appropriate property we are interested in; they are degrees of freedom of the problem. We begin with the following observation. This result, which is well-known in the case of KRR (see for example Abbasi- Yadkori [12, Chapter 3] or Chowdhury and Gopalan [19]), results from elementary algebraic manipulations, the triangle inequality, and properties of the operator norm.
Lemma F.2. For any N Noo and Ro holds that
IN.AA = h- MN + \idx)- + (M² + Xidx)-
(18)
Consequently, for any Hilbert space G, bounded operator L E L.,,, and E Nyo. the following holds:
[[LNNA Lhilll |īVVN + xidx)-112 1/2 (1.111.0) 1/121//c.
1 + II 1), (19)
where we introduced
VN MMMMM and SN MM
The general strategy to bound |[hNN - Lh lle is to bound the two terms involved the right-hand side (RHS) of (19) independently. The term involving h* is bounded as follows:
hh" ll My + - S x - 1 ||
(20)
25

---

and we will assume a known upper-bound on ||, Indeed, Xidx = MM + Aidy since MN positive semi-definite. Similarly, the operator norn rewrites
MN + xidx)) 1/2 (c.
= TIM (idx) 1/2 (T x1dx))1122)
(.(H)
(21)
[| (MNMN + (idæ) -M L- -*1l
Introducing the shorthands
Ep. = L (idw - (MNMN + Aidx) -MHM) L", and
(DL) = -
we have
|L(ME + Aidæ) (02x))11211cc VX -DD.
(22)
We are thus left with bounding the noise-dependent term [|Sw]l(M My +xdx)) Importantl, since this term is independent of L, such a method naturally yields a high-probability bound of [|LhNAA
Lh where the high-probability where the bound holds is independent of L.
E.2 Noise bound for deterministic sampling
The first assumption under which we are able to provide bound on S| ll ( My + ) that of deterministic sampling, meaning that the sampling operators are not random and the noise is independent.
Assumption E.3 (Deterministic sampling). The process I. = (In)neNoo is not random, and is an independent process.
The bound is based on Corollary 2.6 in Mollenhauer and Schillings [22], which pertains to the concentration of quadratic forms of R-subgaussian random variables. We recall it here with our notations for completeness.
Lemma E.4. Assume that is an independent process and that is R-subgaussian for all E N>o. with R E (G) positive semi- semi-defiitte and trace-class. subgaussian, and for all 8 E (0, 1), it holds with probability at least - 5 that
(g H... Then, T)N R idga-
|| < Tr(T) + 2 I/
+ 2ln [|TIla.Co)
(23)
where T = = A (R & idgx). A . E (H()) is of trace class and || = Tr(TT*) is its Hilbert-
Schmidt norm.
E.3
Noise bound for online sampling with coefficients-ttansSfomiii sampling operators
The previous case makes the central assumption that (T.,) deterministic process. While is possible to extend it to the case where (Ln), ) is uniformly bounded random process independent of 7 (leveraging Lemma formalized follows:
Mollenhauer and Schillings [22]), this still excludes online sampling,
Assumption E.5 (Online sampling). We have access to a filtration F = (Fx) for which L is predictable and n is adapted.
Under this assumption, the choice of LN+1 is random and depends on L.N and on V:N. The main difficulty then resides in the fact that Sy and (M My + Aidx)= are now correlated random variables.
We address this correlation by showing self-normalized concentration inequality for
|| || Mx +xdx))
26

---

The inequality is also time-uniform, meaning that the high- probbbbbbbbiltt set on which the bound holds does not depend on the time NN Nyo- It a generalization of Theorem 3.4 (and Corollary 3.6) in Abbasi-Yadkori
Yadkori [12] from G = IR to a general separable Hilbert space G. These results are based on the method of mixtures [43]. While we mostly follow the proof strategy from Abbasi- Yadkori [12), we introduce a general structural assumption the sampling operators (Definition E. 1 and Proposition E. 12) to handle the case where the sampling operators are not trace-class (in the RKHS case, the case where the kernel is not trace-class). Furthermore, in contrast to Abbasi- Yadkori [12] we do not employ an explicit stopping-timg construction to obtain time uniformity, but rather use Ville's inequality in Whitehouse et al. [21].
E.3.1 Challenge and goal
For the sake of discussion, let us assume that H = H.. where K is an operator-valued kernel. While extending Corollary 3.6 of Abbasi-Yadkori [12] to the case where is trace-class is relatively straightforward by following the proof technique, the method breaks if K is not trace-class. In fact, it is not even clear what the corresponding bound on ||Sy Il +w)- -1 is in that case, as using the expression given in Corollary 3.5 in the reference and replacing the scalar kernel with the operator-valued one yields a bound involving the quantity
1 det idga + X M
(24)
which is meaningless since & is not of trace class. However, in the special case where A UBD with trace-class block decomposition Ko, we have meaningful candidate to replace the determinant above: that involving Ko. Our goal then becomes upper bounding [|S [[Swll(xx+Aidd)
by a quantity involving det(idg> + +A-1 MyMM) where Mr E (H @N) ) is defined as Myh (h(zn)) DeENN E GN for all E H... Finally, while the discussion above assumes 7t = Hx and the regularizer V Aid we aim at providing a noise bound for general spaces and regularizers.
Proof summary Our proof is based the method of mixtures of Abbasi- Yadkori [12]. A close look at the proof of Theorem 3.4 in the reference reveals that the problematic determinant (24) arises when integrating the function Gv (in the notations of the reference) against Gaussian measure on HK. We circumvent this integration by leveraging a factorization Hx as a lensor space. While such a factorization Hx = H1 @ H2 trivially exists for choices of separable Hi and H2 based on dimensional arguments (i.e., ( = dim dim(H,) - ddi((H)) we choose one in which all of the sampling operators Ln, E No., admit themselves the simple form L,, ~ Ln @ id and for which f., has nice properties (specifically, ř.; f.,, is trace-class). In the case of a diagonal kernel- that is, K = k idg and T., = ((; a,), this construction known and natural: the RKHS Hx is the (closure of the) span of vectors of the form f g. where f E Hy and E G; see for instance Paulsen and Raghupathi [35, Exercise 6.3]. Then, for any >m 1 fm Im E Ha-idg. introducing hg Em fm & Im E Nk. @ g.
00 T.nh Sm( Im
00 (Inn @ id 2 gm) (in 09 idg)
~
m=1
m=1
In the more general case where K is only UBD instead of diagonal, we prove that such a factorization also exists (Proposition E.1)). In any case, this factorization allows us to write Hx _ HK, @ This enables evaluating modification of) the function GN on pure tensors h & u, where h HK, and E V. We then leverage a double mixture argument: one for the variable h, and one for the variable v. The one on h is the same as in Abbasi-Yadkori [12]: a Gaussian measure on H.g which outputs the desired determinant involving Ko. The one on U is not Gaussian and enables recovering the norm we wish to bound, I| > 1 (up to some regularization term), when combined with Jensen's inequality. Our double mixture strategy is fundamentally different from what used for Chowdhury and Gopalan [19, Theorem 1], since we use two different types of mixture distributions, and the second mixture enters a multiplicative manner (instead of an additive one). We can then conclude using standard arguments involving Ville's 's inequality for positive supermartingales, similarly to Whitehouse et al. [21]. Summarizing. this method enables showing the following result, which is a specialization of the main outcome of this section to the case H Hx and Ln K(., x,)"
27

---

Theorem E.6 (Theorem E. 14, RKHS case). Under the notations of Sections E.1 and E. assume that H. = HK. where K is UBD with block cecooppsttiie Ko : X x X + 9 and isometry ig E Lb & V) where 9 and V are separable Hilbert spaces. Assume that Ko is of trace class, that Assumptio E.5 holds, that Ln presepaara
K(; n E No and that 1i is 1-subgaussian iaagaussiann Then, there exists an isomety Uik *K,," @ V + Hx such that, for all Q E LV) self- seif-adjonna positive semi-definit and trace-class, and V E ((HKo) self-adjoint, positive definite, diagonal, and with bounded inverse, it holds for all 5 E (0,1) 1) that
PP AN E N>o. 1 Sw s 22TH(0) [det [det (idg> + MM 1/2
)
)]
2 1 5,
where VN- = MM
Proof. This follows immediately from Theorem E.14, since Proposition E.12 guarantees that its assumptions hold.
immedhater
This result has two consequences that can be immediately leveraged for KRR.
Corollary E.7 (Corollary E.20, RKHS case). Under the setup and assumptions of Theorem E.6, do not assume that y is I-subgaussian, I-sabaasssia,n but rather that there exists p E 2z0 and Ry E Lb (V) self-adjoint. positive semi-definite and trace-class, such that 1j is R-subgaussian, Then, for all 5 E 10,
R- Mabbaaussinn,,ae where R == (g @0 Ry)eg'
N so, ||Nw/|/V S oV ( In (3 [eel(idxx + MNV-111 1/2 )
P VA E
2 1-8,
where V = uH (V Corollary E,8 (Corollary E.20, RKHS with trace-class kernel case). Under the setup and assumptionn of Theorem E.6, assume that K itself is of trace class. Also, do not assume that rj is -subgaussian.
but rather that it is p-subgaussian for some p E Rzo- Then, we can take Ko = K, 9 = G. V IR. and Q = idg in Theorem E.6. In particular, for all 8 E (0,
P AN E Noo, I| S sq f [del(idgx + MxV-LM3)]
2 1-66
where V=
Proofs of Corollaries E.7 and E.8. These results follow immediately from Corollary E.20.
The next two sections are dedicated to stating and proving Theorem E. 14 and Corollary E,20, which generalize Theorem E.6 and its corollaries to the case where H. is not necessarily an RKHS. It relies on assuming the existence of the aforementioned appropriate factorization of H and of the operators (Ln).. similarly in the case of a UBD kernel. We thus begin by formalizing the assumption. .
E.3.2 Tensor factorization of Hilbert spaces and coefficients transformations
We have identified that, in the case H = Ha-idg- the core assumption for Theorem E.6 was that both H was the closure of the span of vectors of the form f-g. g. with f Hs and g E G, and that In could be identified with i., @ idg. This is the idea we generalize with the construction of this section. Specifically, we rigorously introduce tensor factorizations of Hilbert spaces, and formalize the assumption we make on the operators (In)): they should have appropriate form in the chosen factorization aooooriizttinn
Definition E.9. Let H be a separable Hilbert space. (tensor) factorization of H. is a tuple (H, H2, (H) such that H1 and H, are separable Hilbert spaces and 'H E Lb @ H2 H.) is an isometric isomorphism. We write H _x H1 & H2. The spaces H1 and H₂ are respectively called isomorpale the coefficient and base spaces of the factorization. If G is another separable Hilbert space, a tensor coeffictoo factorization of H. and G with common base space consists of factorizations H =., H @ V and G 2 9 &&l V.
28

---

L
H
-1 'H
4g
L1 1 L2
H1 H2
G1 G2
Figure 8: Action of a tensor-factorizable operator L expressed as a commutative diagram. K is UBD kernel with block Ko, then the RKHS Hx and sampling operator [(,,z)* can be factorized as such with L1 = Ko(:,²)* x)* and L2 idy, with == H2 = G2, as per Proposition E.
The existence of an isometry in such that H .. H1 @ H2 for given (separable) H. H1, and H₂ can be assessed based on purely dimensional arguments: there exists such an if, and only if, H22) (with 0 00 0 and oc oc == 20). For instance, there always exists the trivial factorization of Hilbert space H e,, R @ H. and if n = pp.. q. R 2, Rp @ Rt, follows that the relationship H _ H1 @ H2 does not impose a lot of constraints on any of the spaces involved. The main interest of the notion is when relating it to operators, as operators between Hilbert spaces may have "nice" form when seen as operators between their factorizations, as illustrated in Figure 8:
dim(?( dim (i)) dim
Definition E.10. Let H and G be separable Hilbert spaces, with respective factorizations H. Euy H, @ H2 and _ G1 @ G2, and let I. E Lb. 9). We say that I, is (enns))))nnso--fcctoraabbbe if there exists pair (I,, L2) E (H, G1) x (H2, G2) such that
L (In T22
The pair (L1, L2) is called an (Iu, (g) factorizaatinn of L. If now (Lu)neNso C Lb.H, 9) is family of operators, we say that they are co- co-(Un, ffctoorizzeee if Ln is (In factooriii,,,,,,,, for all N>o-
Intuitively, an operator L that is (1H, (g) ffattoriieeee can be written as a pure tensor operator when H and G are identified with the tensor spaces H₃ H2 and G1 @ G2. It is clear from this interpretation that factorizability is not an intrinsic property of an operator, but largely depends on the chosen factorizations of the Hilbert spaces. For instance, every operator is factorizable for the trivial factorizations of H. and G. Co-factorizability enforces that family of operators consists of pure tensor operators when the factorizations of H and G are uniform in the choice of the operator in the family. Finally, we state the assumption the we require for the generalization of Theorem E.6 to hold.
Definition E.11. Let H _ H @ V and a.g I V be separable Hilbert spaces with joint base space factorizations. Let L E L.. (H, 9). We say that L is an (IH, (g )ccefffiiiss transformation if there exists L E CH, 9) such that (L, idy) is an (1H, (g) factorizaatin of L.
Crucially, in an RKHS with UBD kernel, the sampling operators I., x.,) are co-factorizable and consist of coefficients transformations. This is formalized in the following result, which justifies that the setup we just introduced is indeed a generalization of the case H. = HK with K UBD.
Proposition E.12. Let H Hk. where K X X LG( is a kernel. Assume that K is UBD with block decomposition Ko X X + Lr()) for the isometry ug E (9 @ V,9), where and V are separable Hilbert spaces. Then, there exists an isometry LK E Lb (HK. @ V. V.HK) such that H. S.x Hko & V. G E.o Ô 8 V. and the family L = (Lx)REX = (K(,z)) 2EE (ZEx is co-(Ik, Lg) factorizill and consists of coefficients transformations
L = (L @ idy)
where L_ Ko( for all X.
Proof. Define
: u E HK, 8 V (x + 4g (Kol,x)* @ (iyy)
Forr brevity, refer to this property simply "(mx, (g) factorizabilliyy"" in the remainder of the paper.
29

---

and let F= (HH,, @ V). We show that F = H as a Hilbert space when F is equipped with an appropriate norm.
First, the map Vi is well-defined, takes values in the space of functions from X' to G. and is linear. Indeed, for any x E X, Ko(,,z)* is a well-defined bounded operator from Hxo to G. and thus Ko(+;z)" & idy E (HHK @ V. 9 @ V). This shows that is well-defined and function-valued as claimed, and linearity clear. Second, V/ also injective. To see this, take u E ker(V). It holds that (Ko(=,x)" & idy) = Day for all r E X, since ig is injective. Let now (ha) and (Em)mely be orthonormal bases (ONBs) of HKo and of V, respectively. It is known that (hi, @ Vm) (n.m)ET x is an ONB of Hk. @ V. Therefore, let us introduce such that u = mm.m On,m Mp @ Um- By definition of Ko(.,)" @ idy.
(Ko(- & idy)
Σ anm(Kol; hn) @ um = Σ
On (2) @ Um- m2,77
m.m
As result, for any E 9 and E Iv.
Σ anp (z), 9) 0) nE Ixo
= x) @ sdyy) u. uolgov =
showing that Enelko an.p (x)) = 0 for all x E X. Therefore, the function (p)) (x + EnETKo On.p' . hn (x) satisfies h(()) = 0. immediately follows that h(P) E HKp we show that hpP)) En On,p" hn where the convergence is in I1-1| It follows from the definition of 1(6) that this results from the convergence in I|- of the series EnElno Onp has which in turn holds since
Onupp" hm
Σ Cin.pOnn (pln, (aw) Ko n.n
Σo S
Σ a -u|||HK, wy < co.
mEINo
Ko
Therefore, since (In)nETK, is an ONB of H.. we deduce that an.p 0 for all n E IKo- Since this holds for all p E ly, this shows that u = 0 and that is injective. It follows that V a bijection between H.. & V and F, since F is defined its range.
We now show that the evaluation operator in x E X, denoted as S, E L(F,)), satisfies
S ig (Ko(, & idy) T-1
(25)
Indeed, for any ʃ E F, letting u = v-ts,
Szf = 5. = (Mu)(x) = ig (Kol. x²* @ u ig (Kol, @ idy) v- showing the claim. Finally, we equip F with the norm ||+||=> defined for all f E F aas
|| |/ / Fux ov.
It is immediate to verify that ||=||== is indeed norm, by bijectivity of V. Furthermore, V is an isometry, since for all u E HK. @ V. ||u| | Rxx = -' "ulll,, @v || F. This suffices to show that (F, I1=) ) a Hilbert space. It follows immediately from (25) that S. bounded for all E X, showing that F is an RKHS. Furthermore, its kernel K2 is defined for all x²) E X as Kx(x,x') = SS
= ig (Kols xx @ idy) - [&g (Ko(, x)* @ idy) o "-
= [[Ko((()x))) Kol,, Kol,, x²)) ))()))))) @ idyl'g'
=igKolz,z'00g )'g'"'
K(a,x').
follows from uniqueness of the RKHS associated to kernel that F = Hx as Hilbert spaces.
We are now ready to conclude. Taking (K = V, we have shown that H. = <k (HK, @ V), with 4K an isometry. Furthermore, for all E X. follows from (25) that
K(. ng 2)) & (x) showing that the family (K xx' is co-(1x, , 'g) factorizzblee and consists of the claimed coeffi- cients transformations.
30

---

E.3.3 Self-normalized concentration of vector-valued martingales with tueffciiett-trausffrnnng measurements
The main result of this section is the following theorem, which the generalized version of Theo- rem E.6. We name the relevant assumptions for future reference.
Assumption E.13. Under the notations of Section E.I, H and g admit the fuctorizations with joint base space z.n H @ V and G _ 9 @ V. (Ln)nENso is co-(un, ug) -a)-toctrrizbble and consists of coefficient transformations, a.s., and (Ln, idy) is an (vH fg) of Ln with Ln L, of trace class, a.s. and for all n E >u
Theorem E.14. Under the notations of Section E. I, assume Assumptions E.5 and E.13 hold. Assume that is 1-subgaussian conditionally on F. Let Q E Lv(V) be self-adjoint, positive semi-definite, and trace-class, and V L(H) be self- eelf-adjoint, positive definite, diagonal, and with bounded inverse. Then, Mx M is a.s. of trace class for all N E Nso and, for all 8 E (0,1), it holds with probability least 8 that
VN e Nso Sw 100 S (Tr(Q) In (1 det(idga + MN MMV->NN))) (26)
where we introduced
My + (IID)eE E E and VN = MrMN E (Pt)..
(27)
We prove this theorem first under the assumption that À-1 is of trace class rather than L,, L is, it enables detailing all of the arguments in a technically simpler setup. We then generalize the proof to handle the setup of Theorem E. 14.
Lemma E.15. Under the same setup and assumptions as Theorem E.14, not assume that L, L is of trace class for all n E Ny,, but rather that V-1 is of trace class. Then, for all E (0, 1), (26) holds.
To show this, we follow the method announced in Section E.3.1.
Lemma E.16. Under the setup and assumptions as Lemma E.15, define for all N E Ny0
GN : F. V + Rzo
(28)
exp
+ exp (1nth SNYH - 1
Then, for all u E V.
[ #
GN GN V-1
(29)
det (idgx + 11 V- )
-1/2
1
155 (Sw(t))l
exp 2
where
Sx(u) Σ (on & idv)
where Cont(u) E (. @ V. H.) is the tensor contraction of v, that is, the unique bounded operator that satisfies Cont(v)(u & w) (v. w) u for all u & w E H & V.
31

---

Proof. For v = 0, the claim is trivial, so assume that v + O. We have
N
(4n @ (0, SNhH
Σ
lin (h @ v), No
N
Σ
[nni @ nolo
n=l
N
Σ
(En @ idv) / (h @ v), n.lo
==1
Σ (t.,, s idv) @ v), ion
N
Σ
(h o v. (ig @ id
N
Σ (h, Cont(v) @ idm))
(h, Sw())
Furthermore,
N Σ
|1 (h @ v)lle>
In 0v
m=1
Σ (Ln @ @h @ w)13
N
[[En, @ idv) @ 1)133v
Σ
|L h 13
= | |/:b/
Now, since #
/ Gr(hsu)dN( 10,
/ exp
(h, (x,))(()) - 11111111111 Larih |0, 1-1
(o 0,
/ exp
(x,)x(t)) - fllll (av( 10, 1111o///DD))
by performing the change of variables u I and introducing = ||0||5 u. Since
- v 1/2 id
the resulting integral can be evaluated using Proposition 1.2.8 in Da Prato and Zabezyk [44], showing that it is equal to
det (idæ + 11u1B/3 - 1/2/xx1 1/2
[
11/2
[id + 112
Vollvv-1/33,
exp
22
We handle the determinant by leveraging the Weinstein-Aronszajjn identity for Fredholm determinants, which states that (eB = (et(id+BA)), where A and B are operators which can be composed
32

---

in both directions with AB and BA both of trace class and the identity is taken on the appropriate
space. In this case, by noting that VN M MN. we take A = 3 = 11 M and obtain
det (id 1/
vx11122) = det (idgx + |
We now rewrite the squared norm in the argument of the exponential as
|| (d 11/2/01 -1/2
J0llv0-1/255
V-11/2 (id + 1|1111/ 1113--1122W0-1133 -1 (w)), Sx(v)) R
(30)
(v +1elBBNN -1 (V). Sw()
(x)
where we used |o]))áx(0)) = 55 in the first equality. Altogether, found (29).
We now introduce second mixture on the resulting integral (29) to handle the remaining dependency V. We choose for the measure of the mixture the one given in the following lemma.
Lemma E.17. Let Q E LG( be eeff-adjoin, positive semi remi-definite, and trace-class, with Q + O. Then, there exists a Borel probability measure p.Q on G such that supp(μ) C Sg. the unit sphere in G. and
1 0000 gdu(())))) Tr(Q) Q.
Proof. Under the assumptions of the lemma, the operator Q is also compact. The spectral theorem for compact, self-adjoint operators then ensures the existence of complete orthonormal family (ej)jes and a summable sequence (Ej)jeJ such that Q = Ejes Eye @ ey. Define now
uQ Σ (o(() JEJ
It is immediate to verify that vo is a nonnegative measure with support included in {e, i JJ c sg. where nonnegativity comes from the fact that & Z 0 for all j since Q is positive semi-definite. Furthermore, for any u, E G. we get using standard calculation rules for Bochner- and Lebesgue integrals.
u,
gdva(s)u)
) 5
- (u, (g 2 g)
Σ (ō(es)
(g)
Σ E / (u, (g @ g)v)ed (6(m)) (g)
JEJ
Σ
E (u, (eg e
jeJ
Eslle (5(ee
u.
jEJ
(u, Quis.
showing that و6 @ gdv (g) = Q. Finally,
vQ(
[))
(T=T((QQ) =
Ryo.
jEJ
jEJ
and thus taking pq ThQ UQ satisfies all of the requirements.
33

---

Lemma E.18. Under the setup and assumptions of Lemma E.15, let GN be defined for all N E N50 as in (28). Assume that Q + O, and let piq be a probability measure on V as given Lemma E. Then,
J/ Gv(h @ o)d | ov)hh)
2 det (idgy -N )]
1/2 exp
|
Sw 100]
Sw
2T+(Q)
Proof. It follows from Lemma 1.16 and the fact that pe has support in 8 that
J J GN(h @x(hov)aN(h 0, V=))du(())
= -Los [det (idgv + 11u11/. x
(--1(w))) ]]
1/2
1 1|5x (w)) (1 + due(v)
exp
2
= =[det (idga + MMN--IMN) )] )] 1/2
/ exp
1 Sw (w)ll (due(()) duu((o).
Now, by Jensen's 's inequality,
f 8t
exp
1
2
[1 _ dee(lo) 2 exp 2 8s
[
| (w)l dra(es)
Jie) Let us now introduce families (e. (d)) hie C & and (f!" )ee c V such that 177m = Eies o sm for all n E Nso. We have
f || oo)
N
Σ
Σ (( + UN) "Tnt="Con(t))L;, @ (e @ ()),
=
8) n.m=lijEJ
(ont(v)(L; @ id)) (mm) & ((")))) ))
N
Σ
(v, /v ((m)) M(( + VN) -L,ze(") L ) (2))
8) n.m=l IJEJ
N
Σ
+ V (m) Lme,
(1/)) 3 ( (v. (o (mm
Jeh
n,m=1 JJEJ
Tr(Q)) Σ
Σ
((V VN) - (n) I (m)
B.m=1 LJEJ
N
Tr(Q)) Σ Σ
(I: (I "d e)
m.m=l IJEU
(in @ idv)(e (mm) 8 s/mm)) Hov
Σ
([(++ (w)+ Q] (i; @ idv) (Iz @ idv) ) Rov
TT(Q)) 1,==1
where we used the fact that (v) @ w) = (v, w)yu for the second equality and the definition of suo for the third one. We now leverage the fact that
N
N
N
SN = Σ
Σ (
(ix @ idy)
Σ
mn @ idv))
Tm
=
n=1
1=1
34

---

showing that
[ st [|
15x(0)lle+
1
' SN ([ VNN +x)
Tr(Q)
HBV
1 T((Q)
| SN Sx
and concluding the proof.
Lemma E.19. Under the setup and assumption of Lemma E.15, define GN as in (28). Then, for all E H @ V. (Gy(h)) is an F-supermaringale and [B))(())) S for all N E N
Proof. Let h E H. V. and define Go(h) a.s. We have
E[GN(( (h)
Fx-1l
N Σ
llenth Illectilee, )
[
E
exp
(unch, Lond)
nmm
E exp
2 (rzch, LiLneih
I exp((4xrghh Fx-1]
exp
FN- -
exp { [ (h)
S exp (
= (h),
where used the fact that LN and GN-1 (h) are FN FN-1- mees-uauer and 1-subgaussianity of nn conditionally on FN-1- This shows that (G (h)) v a supermartingale, and it follows immediately that E (h)] (h)] = concluding the proof.
Proof of Lemma 15. First, the claim is trivial if Q = 0. Assume that Q * Under the assumptions of the lemma, we apply Lemma 1. and obtain that EEG y (h) < for all N E N>o and h E H @ V. In particular, this is the case for any & of the form / = h @ v, where E H and v E V. Therefore, by Fubini's theorem, the process (GN)x N defined for all N N
GN = - Gx & v) 0 V dduQ(v)
is again a supermartingale with LE|GN] I 1. As result, can apply Ville's inequality and obtain that for any d 1)
VN E GN S 2 8.
Lemma 18 now shows that it holds with probability at least 1 that
VN E Noo: (det (idgx + (AN--MM)
1/2 exp
Sx 15 Sx
S
2Tr(Q)
The result follows by rearranging.
We are now ready prove Theorem 1. It does not directly follow from Lemma E.15, but rather its proof is an adaptation of that of this lemma.
Proof of Theorem E.14. Take D = dim E Nso U (oo), (bm)me(D) an ONB of H. and family (Am)me(pp) C Rzo such that V Σdd mm Amb & bm. which all exist since V diagonal. The inverse of V exists and is given by
V
Σ
Am bm 8 bm.
m=1
35

---

Note that V-1 is not necessarily of trace class, but is bounded by assumption. Define for M E [D]
WM Am bm bm
and observe that War of rank M and hence trivially of trace class, and it is self-adjoint and positive semidefinite. Although Lemma E. 16 does not directly apply by setting V-1 to WM since WA. Ms may not be invertible, we see from the proof that the only point where this invertibility is used in (30).
Therefore, the proof carries over until this point, showing that for all v e V
J GN(h v) |0, WM)
det (idex + 11ll 111l W 1/2
]
1 -
[idR
Well VN
W w SN (v)
x exp
2
Furthermore, WM - V-1 in the weak operator topology, since for u, E H we have
M
D
Ku, WMre'R (u, w()))) =
(ul, bm) b
Σ
X
(u', bm)
u,
m=1
||u|| x
Σ
Xm
+ 0,
M+1
H
for M - D. It follows by continuity of the operations taken on Vss w.r.t. the weak operator topology that
[1db +
1/2
W1/33
(v)
- (id /-1/2 1/2 v- v-1/25x(u)
as M + D. The same computations as in (30) show that this limit is equal to S| (+ 1
(v)
Next, we claim that the convergence MN W M My + Vv M holds in the trace norm topology. and not only in the weak operator topology. Indeed, denoting the trace norm (also called the Frobenius norm) by I|-II1.
WMNWMMr -NN-1 -ioV-1M
Σ
N (M)bm) @ (Mxbm)
m=
Σ
X (MMxbm) & (Mdxb))la
m=M+1
< sup (x=1)
[l(xxb)) @ (Mxbm)ll1- Σ mE(D) M=M+1
Now, since (Mxbm) @ (Mxbm) ) is of rank 1, is clear that (l,,xbb)) @ (Mrbm)ll = 1m Furthermore, since M My is a.s. of trace class, the series Σ ?I N 11 converges for any ONB (um)meN2o of H. a.s. (and is equal to Tr(My )). This is in particular the case for (bm)m. Finally, supme(D) Am < (Vlll which is finite since V-1 is bounded. As result,
JM W M Mr - V ll + 0. M D. and thus My W MM + V- M in the trace norm. Crucially, the Fredholm determinant is continuous in the trace norm topology, and thus
lim det(id M W M det (idæx M-D
36

---

Taken together, this shows that for all N E Nso and v E V
GN(U):= == lim M R
Gw(h 8 v)aV(h 0, WM)
exists and
Gx(u) - det (idgx + IIol (
exp ( ( (HI
By the exact same computations as in the proof of Lemma (which do not rely on whether or not V-1 is trace-class), it follows that
GN == /x== Gx(v)duq(v)
2 det (idgx + MNN- MR)
exp (Tr(Q) 11 SN iv (V++)))-00
Furthermore, by construction ON is nonnegative. Finally, have a.s. from Lemma E.19 that
E|GN [FN-]]= f lim / GN u)dN(io, v))Voo Ww))dp(()) | --x
/ M
lim / F [. @ v) FN dN(A O, War)du((v)
/ GN- & o)dN(A 0, (x)(((()))
lim
Jy M - A
GN-1-
This ensures that (Gx) NN is still supermartingale. Since G, = 1, we also have E|GN] S for all N E N We can thus leverage Ville's inequality, and conclude similarly in the proof of Lemma E.15.
Before concluding this section, we provide important corollary of Theorem E. 14, which provides an upper bound on ||Sv +V - rather than on ||Sx (V -w at the price of slightly stronger assumptions on the noise.
E.3.4 Corollary: bound for the noise term of valued least-squares
We now specialize our results to the situation that appears in vector-valued least-squares. The following bound allows to derive a time-unifomm high-probabilit, bound for vector-valued least- squares when combined with Lemma E.2, ef. Theorem E.23 below.
Corollary E.20. Under the setup of Section E. assume that Assumptions E.5 and E. 13 hold. Let V E C()) be self-adjoint, positive-defiitt, diagonal, and with bounded inverse. Assume that there exists E Rzu and Ry E LV) self adjoint, positive semi-definite, and trace-class, such that is R-subgaussian conditionally on F, where R. == prig(idg @ By) Then, for all E (0,
1/2) VN Noo, [[Sw][(VwW))) 1 pV (Tr(Rv) In (3 dot(idgx + MNV-IMM) My
2 1-88
where V 1 (V & 1
Before proving this result, let briefly comment the subgaussianity assumption used.
Remark E.21. The subgaussianity assumption of Corollary E.20 is in general a strengthening of the assumption that is p-subgaussian for P E Ry., but also a weakening of the one that 17 is R-subgaussian for R E (G) self-adjoint, positive semi-definite, and of trace class. Indeed, the operator R given in the corollary is not trace-class when is diminit-diimesiinall. Furthermore, for any such operator it, there exist E I and Q E (V()) self-adjoint, positive semi-definite, and of trace class such that R < R = (idg @ Qu=²² Indeed, define the trace-class operator and Q (F'( where
R' 1 E (H & V). and take p (rw(A) the partial trace over W of trace-class operator A defined on tensor-product space involving W. We forego proving this construction for brevity.
(Rl,,,
37

---

The proof of Corollary E.20 relies on the following lemma.
Lemma E.22. Let R E ()) be self-adjoint, positive semi-definite, Let rj be G-valued, zero-mean random variable, and assume that yi is R-subgaussian. Then, oi takes values in cl(ran(R)) a.s.
Proof. Let ran R) The variable X (e, is real-valued, Re = ||elle- random variable, as [[X] = (c, [[7] = 0 and
E[exp(cX)) = [ce, m)) - exp [ (R(cee,, = exp 2R, ACE R.
Classical results on scalar subgaussian variables then guarantee that Var[X] I R2 Yet, E r = ker( [t*) ker(It), since R is self-adjoint, and thus Re = 0. As a result, Ree |el|| = (Re, e)) = O, and thus Var[X] = 0 and X is constant a.s., and this constant is since is O-mean. We deduce by separability of g and continuity of the scalar product that PI3e E ran( (n,e) * OJ = 0, which shows that it holds with full probability that e (ran(R)") = (((ra((R)). concluding the proof.
Proof of Corollary E.20. Under the current assumptions, the scaled noise The = (R In is 1- subgaussian conditionally on F, where R2 the Moore-Penrose sseudo-invesse of R. Indeed, (conditionally) O-mean and for any 9 E G.
E EexplK Kg. (18)) /2 mn) Fn-1] EEexpl ( (1E)) 1/2 9, nn)
((R5) 1/2 g. R(RR)112))
S exp
1
exp
|1 RA!
S Sexp
exp
119113
The second equality comes from the fact that R!/2 and R commute; the proof is technical exercise that follows from the spectral theorem applied to Ry and the spectral definition of R We also leveraged in the last inequality the fact that RR is an orthogonal projection, and thus |ggl|R S |g: see for instance Proposition 2.3 in Engl et al. [45]. Theorem E. 14 applied with = Ry then guarantees that for all 8 E (0, 1), it holds with probability at least 5 that, for all N Noo.
S (Tr(By In z deet(idax + M2 M 1/2)
|| (I
where we introduced Ryy (BN)NEIN) GN (R'gg) E GN. We conclude by showing that
(Rt)) (IN - = a.s.
Indeed,
N
My (R 1/2 n:N
Σ
L (2
Tipg (dgg s 112) 'g'm
N
VH iim の idds) 15 rotis (idg s (122)2122 '5'm
n=1
N
1 4
[i @ (22) , n
38

---

and thus
lee MN (R²) 2/2
N p
(( <((V+V>) - @ [1v(1) 'g Ths (inn @ (1t 'g mm nov
n,m==1
N
([ + V 1T 2
Ry Ry (v( (
mmm mn (Im @ idy)'s' mm Hvsl
R,m==
N
[ ([++i))+ 8 idy
i @ idyy lids @ Rv idg @ Ry) 'g'm..
R,m=1
(t idv) 1/mn FLEV
N
(x (V +
Vx))~ +Vx) RT: " -1 Ii (mm Floo
n,m=
N
((V + VN) RR. 1 9
7,m==
where we leveraged in the third equality the fact that (R2 and Ry commute, and that (V Vx--- & idy = ' (V + Vxa)-1a in the fourth one. Next, RR is the orthogonal projection on cl(ran(R)) see for instance Proposition 2.3 in [45]. Yet, Th is a.s. in cl(ran(It) by Lemma E.22, follows that RR Thi a.s., for all N As result, it holds a.s. that
N
(R TAN 1I (V++W) 1881. =p-
Σ
((V + VN) Li Bm)
n,=1
= p "IMMinnNRR
The result follows.
E,4
Main result
We now combine all that precedes to obtain the announced concentration bound in vector-valued least-squares.
Theorem E.23. Under the notations of Section E.1, let R E (g( be self-adjoint, positive semi- definite, and S E R2 Assume that || S. S, and assume one of the following and define 3x and N accordingly:
1. Assumptions E.5 and E.13 hold, R prig & Ry) for some p E R>0 and Ry LVV self-adjoint, positive semi-definite, and trace-class, and 1j is R-subgaussian conditionally on F. Then, define N = N and, for all (n, (n,8) E N X (0, 1).
8 1 det idgw + 1 x ( )
1/2
3x(N8)) S VX
(Tr(Rv) In
where My is introduced in (27).
2. Assumption E.3 holds, R is of trace class, and v is R-subgaussian. Then, define N = (No) for some No E Nzo and, for all (n, 8) E Nyo x (0, 1).
TT(TN.A) + +2 In (?) | + 2ln (3) || ITN.Allann10)
BN 8) = S
V
where introduced TN, (VN + Xidx) (R iddiwddW + Xidx)
39

---

In both cases, for all E (0,
P[ E Lb 9), - S Bx(N,8) oN.(LL)] 2 2
(31)
Proof. Let å E 10. In case 2, it follows from Lemma E,4 that it holds with probability at least that
I(V + VNo) (Na))_/2MM,
MNo J:Nol
S Tr(TNo.)) + 2 In (z) | No.all + 2
(7) | No.oaalann0
(,,,
where we applied the lemma with = (idæ + idgoo A and. In case I, follows from Corollary E.20 that holds with probability least that, for all N Nyo.
1/2 ) yielding T TNo.A = A. (R x
1 { In [ det idgy + x JM Nix
[1
)]} 1/2
|| |[wll<++w> S spl (T)(())))
(8)
In both cases, it holds with probability at least - 5 that
AA ENW, [IN,I|SSwl(v+vw>>>> S (0).
The result then immediately follows from Lemma E.2, (20), and (22), noting that (x(,,
S VX (6).
E.5 Proof of Theorem 4.3
Proof. The result follows immediately by applying Theorem E.23 with = Hx. Ln = K(,;,,); and V/- (X.,), for all E N Indeed, for these choices, the optimization problem (15)
equivalent to that in (4), since for all h E HK. E G, and n E N
(h(X.) g). (h, Xn)9)
(K hx),
showing that the evaluation operator in X,, is (*, Furthermore, the process 7 satisfies the appropriate assumption E.3 or E.5 depending on the considered case, since D is assumed to process of transition pairs of p. process of independent transition pairs of p. In case 2. the assumptions case Theorem E,23 are satisfied, and the result follows. Similarly, In case 1, the assumptions of case in Theorem E.23 are satisfied by Proposition 1.1 and the result follows well.
40

---

F Proof of Theorem 4.2
Proof. For any P1.P2 E O we have
12,1,P2,
= =P]5(m,,n) n2) E EN x N2 : S Er(r, p2, ((1) D.2 Dpaine) + 0]
pr
= =P
x) EN u2,
N2 S: (R(p)((())))))))))))))
((p2)(x)
2
A
{() D
(x) - ( (a)
Σ
B,
(Dii) : 20
i=1
2
<
P
n2, EN x NN2 SS: Σ
p(i) (x) - B(a)(z))
> Σ
B:
(D!0 : x))
D
1=1
1=1
IP
U (() E N, x 8 $115500
D (gg(())) (z) ((p))(z)
> B: [D.
1=11
(), E M, x8: | (1) B(n)(())
> Bi [x)
S 81 0
where we used the fact that (x) = (x))) for any x E Ei P2, D1, D2) and (D₁, D2) e D2
41

---

G Experiment details
This section presents the detailed setups for each of numerical experiments. Addition- ally, the code to reproduce all experimental results is available at https://github. com/ hhw.aaaeeeeaannaa---aaaaeeeeeeee
Unless stated, all our experiments with bootstrapped test thresholds use the naive resampling scheme outlined in Appendix B.
G.1 Illustrative example (Figure 1)
Figure illustrates our test on a simple example with one me--imensiooal inputs and outputs. We use
a Gaussian kernel on = [-1,1] and the inhomogeneous linear kernel on = R. We pick two mean functions S1, /2 E Hg. from which we collect data sets D, = {(a) (6) _[(()) (0) + (5) ))=
i e {1,2). The covariates zj sampled uniformly from X and e, (9) ~ N(. 0, s²), such that the Markov kernel corresponding each data set p;(;, NN( f((x), s²), where N u4 s2 is the Gaussian measure on R with mean and variance s². Consequently, Ho(æ, P1. P2) is equivalent
(i)
f1()) f2(2).
We apply our test with analytical thresholds (Figure 1, left) and bootstrapped thresholds (Figure 1, the ground truth RKHS function (that is. 1) and the
right). For the analytical thresholds, Gaussian noise standard deviation for the corresponding upper bounds on these quantities in Theorem 4.3.
Table 2 reports the hyperparameters for this experiment.
G.2 Empirical error rates
This section provides implementation and design details for experiments evaluating the empirical type I and type II errors of our tests in controlled, well-specified settings. All experiments in this section were conducted on an Intel Xeon 8468 Sapphire CPU, using 10 GB of RAM.
G.2.1 General setup
Data generation We evaluate our test by generating two data sets, D1 and D2, each containing transition pairs of the form
D. = ((1)) M((,)") + + iE (1,2).
(8) Here, the inputs 3 are sampled (uniformly, unless stated otherwise) from X, Ej are i.i.d. noise, and is random unit-norm element of H4 whose sampling is detailed below. In particular, choose Si directly from the RKHS H4 of k. In all our experiments in this section, we use a Gaussian kernel
(1)
k(x,, 3) = exp (- ||
y11 272
(32)
on X' C IR.2 with bandwidth 72 0.25.
Remark G. In the case where x is the linear kernel, the procedure above ensures that E[p.] E HK with K = ks idz... This guarantee is lost when k is more complex kernel. While this means that the simulations may use the test in contexts not covered by the theory, this is precisely the interest of the bootstrapping schemes we propose: the test still be applied, and its performance evaluated empirically.
Sampling of mean functions Following Fiedler et al. [25], we sample mean functions fo E Hg randomly by first sampling m points I1, Zm uniformly random from X and then sampling fi uniformly from the sphere
a1. am E R. ffll = Hk. f T-Eykk(-ann (5)k(1zz) (
(33)
where the RKHS norm r depends on the concrete experiment setting. When reporting hyperparame- ters, refer to m the "mean function dimension"..
42

---

Empirical error rates We quantify both the type I and type II error rates through the test's empirical positive rate- the proportion of data set pairs on which at least one covariate triggers rejection in the region of interest
regimes. Under the global null (Ho(r, PI: P2) holds for all z E X), this positive rate directly estimates the type error. Under an alternative (Ho(r, P1. P2) fails for some X), the same quantity measures the test's power, from which we compute the type 11 error as one minus that power.
under two data-generale
To compute the positive rate in practice, we draw T independent data set pairs ((D))) D2 )12-1 For each pair, we take the observed covariates
( = fIr E X 32 E 2, (x, DI U )
(34)
as the region of interest and compute the covariate rejection region
(IDP,DD91 XDD non)
(35)
= =tx = S
= =}.
We then take
1
T
0
if TX(D(",D)) 0
(36)
T J=1
otherwise
as the empirical positive rate.
Repeating this under the null and alternative regimes while varying the significance level a and other parameters, obtain detailed error-rate curves that reveal how closely the observed type error matches its nominal level and how the test power depends on the various parameters. Enforcing either regime requires appropriate choices of the mean functions f1 and f2. and noise distributions. For instance, to enforce the global null, it is sufficient (but depending on the kernel K. not strictly necessary) generate both data sets from identical mean functions fi f2 with identical noise distribution. For the alternative, we can introduce a controlled discrepancy, such as choosing f2 - fi + for some function h Ha, or alter the noise distribution in the case where we introduce a kernel & to test for other properties such as higher moments. Because the exact construction for enforcing null and alternative hypotheses depends on the specific experiment setting, we defer those specific design details to the individual experiment descriptions that follow.
Finally, we always compute positive rates from T = 100 independently sampled data sets and report curves that are averaged over 100 independent experiment runs (i.e., samples of mean function pairs), together with 2.5% and 97.5% quantiles taken over the experiment runs.
G.2.2 Global and local sensitivity (Figure 2)
Figure 2 presents the empirical positive rate of our test in three different scenarios: (1) when the Ho is enforced enforced everywhere on X' (Figure 2, left); (2) when Ho is violated at frequently sampled covariates (Figure 2, middle); and (3) when Ho is violated at rarely sampled covariates (Figure 2, right). In all three scenarios, we use the inhomogeneous linear kernel for and Gaussian noise ((00 x²) such that Ho()) holds if and only if f1(r) = f2(Ø). In the following, we describe how each scenario enforces its corresponding hypothesis.
Scenario 1: Global null We pick unit-norm function fi E Hy and set f2 = fi. Consequently, P1 = P2 such that every rejection is a false positive, and the empirical positive rate estimates our type I error.
Scenario 2: Frequent violations We pick a unit norm function fi E: H4. and independently pick a perturbation h E Hy with norm ç. By setting f2 = fi + h, f1 and fz differ almost everywhere almost surely, thereby creating global discrepancy between p1 and P2 whose magnitude is controlled by ç. In this setting, a rejection is taken to be a true positive, neglecting the edge case where h(r) = 0 incidentally causes fi (I) = (z). We then take the empirical positive rate as the true positive rate, translating directly to our type Il error.
Scenario 3: Rare violations We pick a unit-norm function fi H/ and set f2 f1 + k(. 0). Then, pi (-.z) and pz(,, z) are approximately equal for r E Xaame == {x X k(,,z) 10-2) but
43

---

differ significantly for z E Xair = X' Xsame. The value 10-² was chosen as an order of magnitude which unrealistic to expect detecting the difference from the considered data set sizes. To control how often this anomalous region Xlitt is sampled, we now sample covariates from mixture; namely from Xuit with probability 0, and from Xame with probability - 0. Varying then controls the difficulty of detecting a violation, and the empirical positive rate again translates to our type IT error under this more challenging alternative.
Baseline comparison We compare our test to the conditional two-sample procedure of Hu and Lei [5], which casts hypothesis testing as a weighted conformal- prredccciinniiiioonn problem and builds a sum statistic from estimated density ratios. In their framework, one classifier is trained on covariates alone to learn their marginal density ratios, and a second on the joint covariate-response pairs to learn the conditional density ratios. Because the baseline's performance hinges on the accuracy of the density ratio learning method, we provide it with oracle-style information in each scenario. Firstly, inform the method in all scenarios that the marginal densities are identical between the two samples. Secondly, in Scenarios I and 2, we supply the true Gaussian noise distribution and restrict the conditional density- model to the Gaussian parametric family with known variance, so the learner only estimates conditional means via KRR (as in our test). In Scenario 3, we go one step further and provide the baseline with the ground truth conditional density ratios. This alignment makes outcomes directly comparable and focuses the comparison on the heart of each test, namely, global testing using one aggregated statistic versus our local, covariate-specific decisions.
Table 3 reports the hyperparameters for Scenarios and 2, and Table 4 those for Scenario 3. The experiments used 50 core hours.
G.2.3 Comparison of higher-order moments (Figure 4)
Figure 4 shows the positive rate of our test for different kernels k on Z = E when the conditional means coincide, but the conditional distributions still differ. We pick unit-norm mean function f and set fi fz = f. such that both data sets D2 and D2 in each pair are generated from the same mean function. However, Dj and D2 differ in the noise applied to the observations. The observations in Dj are corrupted with Gaussian noise ((0 s²). In contrast, the observations in D2 are corrupted with noise sampled from an equally weighted mixture of (V s²) and N(u, s²). For this data gett-generating process, the conditional means coincide while the conditional distributions differ. We compute the empirical positive rates in this setting for (i) a linear kernel; and (ii) a Gaussian kernel on Z.
Table 6 reports the hyperparameters for this experiment. The experiment used 20 core hours.
G.2.4 Influence of using an overly rich kernel (Figure 5)
Figure 5 shows the type I and II errors of our test for different Gaussian and polynomial kernels on Z = R. For the type error, we pick a single unit-norm mean function f = fi = fa and report the empirical positive rate. For the type II error, we pick two mean functions f1 and fa independently. In either case, we apply the same Gaussian noise (0, 82) to both data sets.
Table 7 reports the hyperparameters for this experiment. The experiment used 15 core hours.
G.2.5 Bootstrapping schemes (Figures and 7)
Figure shows the type and IT errors of our test for different bootstrapping schemes when varying the data set size and regularization of the KRR. For the type I error, we pick single unit-norm mean function f = fi = f2 and report the empirical positive rate. For the type 11 error, we pick two mean functions fi and f2 independently. We use a linear kernel x on Z and apply the same Gaussian noise (0, s²) to both data sets. In Figure 6a, we fix the regularization À = 0.5 and vary the data set size n. In Figure 6b, we fix
50 and vary X.
Figure reports type I and II errors for analytical and bootstrapped test thresholds, using the same setup before but fixing both n 100 and À 0.25.
Tables and 9 report the hyperparameters for these experiments. The experiments used 30 core hours.
44

---

Table 2: Hyperparameters used in generating Figure 1.
Parameter
Value
Input set
X [-1, 1]
Input kernel bandwidth
72 = 0.25
Data set size
n 25
Noise variance
8² 0.05
Regularization
À = 0.01
Bootstrap resamples
M 1000
Table 3: Hyperparameters used in generating Figure (left and middle).
Parameter
Value
Input set
X' [-1, -1,1] 1]²
Mean function dimension
m 12
Data set size
= 100
Noise variance
2² 0.12
Regularization
À 0.1
Bootstrap resamples
M = 500
G.3 Process monitoring (Figure 3)
Figure shows the ratio between the test statistic and threshold averaged over the sliding window following the trajectory of perturbed linear dynamical system (left), and the average value of (Z) over the window when is the reference data set. We detail this experiment here.
We set X' Rd d E N>o. and choose the linear operator- valued kernel ( x') = (z,=")ga idge, wish to compare linear functions mapping I2d to itself. We randomly sample matrix A O(d), the group of orthonormal matrices in dimension d, pick fixed initial state X, J [1....11 1] E Rd.
and generate single trajectory (X,,) [N as Xa+1 = AXx, En. where cn (O, s² La) is ii.d.
Gaussian noise. We enforce that A is orthonormal so the trajectory neither shrinks nor explodes exponentially. Then, the observations Y = (Ya)xeN,, are taken as Yn = Xn+1. It is immediate to verify that ((X,; DeN), Az, Ia). where A((1 μ, ss Ia) is the Gaussian measure on Rd with mean μ Rd and covariance matrix s² la Rdxdd"
process of transition pairs of the Markov kernel p(:, x)) N/.1
Using this procedure for independent system trajectories of length 400, we collect a data set of Nyef 2000 data points, which we call the reference data set D. We then follow the trajectory with sliding window size Rwwin = 50 data points, and perform the test at every step on the points in the sliding window. After 200 steps, introduce change in the matrix A, replacing it with the matrix A' A Aexp( | H). Here H [ BT) is antisymmetric and the entries of B sampled i..dd from (00, 1). such that distora A') = ç. where distora) (A, A') = || log A') [| is the usual geodesic distance on (d). This construction ensures that A' is orthonormal as well, and controls the distance between and A' in a way consistent with the geometry of O(d).
Figure (left) shows the result this procedure, for varied values and of & (E only varied with d 16), and averaged over 100 independent choices of the data sets and 50 independent choices of the matrix A. We observe that the change is detected rapidly, even before the sliding window is entirely filled with data from the dynamics. Notably. higher dimensions require higher disturbances to be successfully detected with a fixed amount of data. Figure 3 (right) suggests reason for this: the variance of the reference data indicating that the dynamics with A' bring the trajectory into regions unexplored when following the dynamics with A. In other words, the lack of power in high dimensions seems to result from lack of local data, as it is "easier" to go in unsampled regions by changing the dynamics.
the current state increases after change,
Table 5 presents the hyperparameters for this experiment. The experiment used 2000 core hours.
45

---

Table 4: Hyperparameters used in generating Figure (right).
Parameter
Value
Input set
X' [-3,3] 3|2
Mean function dimension
m 36
Data set size
500
Noise variance
8² 0.025
Regularization
0.1
Bootstrap resamples
M = 500
Table 5: Hyperparameters used in generating Figure 3.
Parameter
Value
Regularization
À 0.01
Noise variance
82 0.01
Significance level
a 0.05
Bootstrap resamples
M = 100
Table 6: Hyperparameters used in generating Figure 4.
Parameter
Value
Input set
X' [-1, 1, 1]2
Gaussian output kernel bandwidth
72 0.05
Mean function dimension
m = 12
Data set size
100
Noise variance
22 0.025²
Regularization
0.5
Bootstrap resamples
M = 500
Table 7: Hyperparameters used in generating Figure 5.
Parameter
Value
Input set
X [-1, 1]2
Mean function dimension
12
Noise variance
s 0.22
Regularization
À 0.5
Bootstrap resamples
M = 500
Table 8: Hyperparameters used in generating Figure 6a and 6b.
Parameter
Value
Input set Mean function dimension
X' [-1, 11,1] 1]
m 12
Noise variance
s 0.22
Bootstrap resamples
M = 500
Table 9: Hyperparameters used in generating Figure 7.
Parameter
Value
Input set
X [-1, 1]2
Mean function dimension
m 12
Data set size
n 100
Regularization
À 0.25
Bootstrap resamples
M 500
46

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We claim in the abstract and introduction that we formalize guarantees on the rejection region in conditional testing. provide a general recipe for conditional two-sample tests, instantiate it for KRR thanks to generalized bound, and provide bootstrapping schemes and showease how to use our tools practice. We address all these points, either by dedicated sections or formal mathematical results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We emphasize the necessity and limitations of our theoretical assumptions (well-specified case) and acknowledge that our bootstrapping scheme is heuristic. We also acknowledge that further empirical studies are necessary to establish the empirical performance of the method and obtain more thorough understanding of hyperparameters, as the present work is only on laying foundations.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
47

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All our theorems come with their assumptions, and we have appendices dedicated to their proofs well as summaries of them when applicable (Section E.3.1).
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
We provide algorithms describing the pseudocode of our implementations, as well any hyperparameters relevant the study. We also provide code coming with scripts enabling a strict reproduction of the figures and numerical results.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
48

---

(c) If the contribution is a new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide access code with scripts reproduce the results and do not use external data sets. The code is available in an anonymized repository during the review process, and will be published in permanent repository upon publication.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c ec/ public/ public/guides CoodeSummissionoo commocllyy for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips.
/ttggdddd/eeeueuumiiii.. SooeeSubissssstieeoooco ssiossolicyy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
We answer these questions in dedicated appendix (Appendix G).
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
49

---

Answer: [Yes]
Justification: We report quantiles of distributions where appropriate and when this does not hurt readability.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We report information on the compute resources we used in Appendix G.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: //nerrrp/////ss./m/
Answer: [Yes]
Justification: The process in which this work was conducted abides by the Code of Ethics. Our work seeks advance the field of Machine Learning and has many potential societal consequences, some harmful, but to an extent neither greater nor lesser than research in Machine Learning in general.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
50

---

The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper is foundational research and is not tied to particular applications, and there is no direct path to harmful or negative applications that we believe should be highlighted here.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairesss considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
51

---

Answer: [NA]
Justification:
The paper does not use such existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We provide code (anonymized at submission) together with its documentation and instructions for reproducibility.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification:
The paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
52

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https: http///eerpp../e/ cc/Confferencee/2255 for what should or should not be described.
53


Reviews:
[{"review_id": "CrqPRBMeMr", "reviewer": "Reviewer_qzic", "summary": "A general framework is proposed for kernel-based conditional two-sample tests that use sequences of input-output measurements, which are not necessarily independent and identically distributed (i.i.d.). The noises are assumed to be sub-Gaussian. The null hypothesis tested is that of equal conditional expectations given a covariate (input). A key advantage is that the output can be abstract, originating from a separable Hilbert space. This feature, combined with the theory of kernel mean embedding, allows the framework to be applied to test other hypotheses, such as those involving higher moments or even full conditional distributions. The paper also introduces the concept of uniform-block-diagonal kernels. An abstract test is first defined by building on finite-sample confidence bounds for learning algorithms. The paper's main results come in the form of confidence bounds for vector-valued kernel ridge regression (KRR) methods, summarized by Theorem 4.3 and later generalized by Theorem D.23 in the supplementary material. Based on these findings, kernel-based two-sample tests are defined and experimentally demonstrated using toy examples.", "questions": "- Are these tests mainly useful for small sample settings or do you expect them to be scaleable?\n- What is the primary obstacle to achieving a distribution-free test? Is it possible to eliminate the bootstrap step?", "limitations": "The paper adequately addresses its limitations; however, a deeper discussion on its practical applicability is noticeably absent.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths of the paper include:\n- The paper addresses the crucial statistical problem of two-sample homogeneity tests (initially, for conditional expectations, which can applied for conditional distributions, as shown in the Appendices), proposing and rigorously studying a novel and promising framework for these problems.\n- The approach is highly abstract, allowing for a wide range of design choices. Its flexibility is demonstrated in the appendix, for example, through an example of process monitoring.\n- The concepts are clearly defined, and the theorems are precisely stated and proven.\n- The results are placed in context, with their connections to existing bounds further discussed in Appendix C.\n- The proposed methods apply to non-i.i.d. data and allow online data generation.\n- The specific tests and toy examples provided effectively illustrate the approach.\n- The code for the numerical experiments is made available online.\n\nWeaknesses of the paper:\n- The current title is overly general. A more specific title that highlights that the tests are based on guarantees of vector-valued KRR would be beneficial.\n- Subgaussianity is a core assumption of the framework, and therefore, it should be explicitly mentioned in the abstract.\n- In Section 4, both the null hypothesis (H_0) and the alternative hypothesis (H_1) should be explicitly defined.\n- Curiously, the paper's core contributions appear to be the confidence bounds for vector-valued KRR methods (Theorem 4.3), with the two-sample tests emerging as a straightforward corollary. Yet, the paper identifies the tests themselves as its main contributions.\n- The abstract also refers to material which can only be found in the supplementary material (e.g., process monitoring).\n- The numerous technical assumptions required may limit the practical applicability of the results beyond toy examples.\n- Since the tests are based on kernel methods, their scalability might be an issue.\n- Even the applications to the toy examples need a heuristic bootstrap step.\n- The conclusion's claim of presenting a complete pipeline from conceptual foundations to practical implementations seems an exaggeration. Practical issues are only briefly touched upon, with, for example, the bootstrap scheme detailed solely in the appendix.\n- A minor, yet annoying issue is that many formulas in the supplementary material extend beyond the margins.\n- I had the impression that the authors tried to squeeze too much material into the paper, and valuable contributions are therefore placed in the supplementary material, due to lack of space (e.g., generalized confidence bounds for vector-valued least squares).", "was_revised": true, "final_justification": "The paper's contribution is strong; it provides a new and valuable method for conditional two-sample tests based on kernel techniques. The authors have addressed most of the issues I have raised, with a few smaller issues remaining (such as the practical applicability and scalability of the KRR-based instantiation). I suggest accepting this paper.", "rebuttal": "Thank you very much for your thoughtful review.\nWe address each of your points below.\nIf you find our responses satisfactory, we would be grateful if you would consider raising your score.\n\n> the core contributions are confidence bounds and the tests are corollaries. Yet, the tests themselves are presented as main contributions.\n\nWe see two main contributions:\n* **Conceptual**: the testing framework (Sec. 3) and its connection to learning theory (Thm 4.2).\n* **Technical**: new confidence bounds for KRR (Thm 4.3) and for vector-valued least squares (Thm D.23).\n\nThe final kernel test then combines these two ingredients. Because the test both motivates the bounds and showcases their practical value, we chose to present all three elements together and build the story of the article around the final test, which is common practice for such bounds; cf. [12, 19, 20].\n\n> overly general title\n\nThe title reflects the intersection of our two contributions: a kernel conditional test instantiating our general setup and derived from new bounds. While the bounds are more general, the test is the most practically relevant outcome, so we chose to highlight it in the title.\n\n> technical assumptions and applicability\n\nWe have two main technical assumptions:\n1. **RKHS membership** of the conditional expectation, and\n2. **subgaussian noise**\n\nA form of the second assumption is common in the learning literature of kernel methods (we discuss this further in a later comment). The validity of the first assumption is more debated [R1] with CMEs, but is generally accepted in the literature on bandits [12,19,20].\nIn any case, our Theorem 4.2 and [3] highlight that **such technical assumptions are unavoidable** to limit the hardness of the underlying problem and escape no-free-lunch results.\nIt is a known caveat of all of learning theory that such assumptions are hard to enforce or verify. This is not an artifact of our method, however, but a characteristic of conditional testing, since a learning problem is at the heart of conditional testing. \nCrucially, our method *makes the assumption explicit*. Competing tests that invoke asymptotic normality also hinge on similar assumptions --- they are merely implicit in the convergence rate.\n\nOther conditions are less restrictive: choosing a UBD kernel is a design choice, and our online sampling setting relaxes the usual i.i.d. requirement.\n\n> scalability\n\nIt is true that our kernel test inherits the computational footprint of KRR and particularly its bootstrapping. However:\n1. When necessary, our bootstrap can be drop-in replaced with more scalable alternatives (e.g., [R4]) that do not require re-learning the KRR model for each resample. A GPU implementation of [R4] handles $\\approx$ 25 k samples in a few seconds, covering many intermediate-scale problems. We will include a presentation of scalable bootstrapping and results with [R4] in the revision.\n2. Scalability can be further improved with approximate KRR/GP methods, though this breaks the guarantee that the bound has the form $\\beta\\cdot\\sigma(x)$.\nExtending the guarantees to that setting is interesting future work.\n3. Finally, the kernel instantiation is just that --- an instantiation. The general framework is also applicable to methods that scale better, if they are available. This is left for future work.\n\n> toy examples need a heuristic bootstrap step\n\nBootstrapping serves two roles:\n1. removing inaccessible tuning constants, and\n2. increasing power.\n\nEven when exact parameters are known (Sec. 5), the second point matters. Theorem 4.3 is **worst-case** over the prior Markov-kernel set, so, even if its raw bounds are sharp (which is still an open question to the best of our knowledge), they tend to be conservative. Bootstrapping leverages problem-specific structure for sharper thresholds. \nWe emphasize that bootstrapping is also essential in the unconditional case of [1], which our work generalizes.\n\n> claim of presenting a complete pipeline from conceptual foundations to practical implementations seems an exaggeration\n\nOur intention was simply “from theoretical foundations to a usable Python package” (which we provide). We did **not** mean a full end-to-end empirical study. We will clarify this wording and adjust the abstract accordingly.\n\n> paper has too much material; valuable contributions are in the supplementary material\n\nThis is a valid point, and we thank you for acknowledging the value of our contributions.\nThe density stems from two deliberate choices:\n1. Demonstrating that the concentration bounds enable a powerful application (conditional testing), as is customary [19, 20].\n2. Keeping the bounds general, not limiting them to the particular application of KRR of conditional mean embeddings and requiring an abstract Hilbert-valued output. The proof for KRR alone is barely shorter than the full vector-valued least squares version, so separating them would only save little space.\n\n> obstacle to achieving a distribution-free test\n\nWe understand this is related to the assumption of subgaussian noise, and not to the assumption of RKHS membership.\nA tail condition on the noise is a common assumption in learning theory, though it does not necessarily take the form of subgaussianity ([Eq. (9), R2], [R3]).\nThat said, an important question is what noise exactly the assumption considers.\nIndeed, for the conditional _two-sample_ test, the noise is mapped through the kernel partial evaluations (Section A.1). With a bounded kernel --- standard for CMEs --- the transformed noise is bounded, and subgaussianity only adds a mild trace-class requirement on its covariance.\nRelaxing even this would likely require a new super-martingale $G_N$ (cf. (28)); see [21] for a possible direction.\n\n> Other comments: subgaussianity in the abstract, $H_1$ in (5), abstract mentioning supplementary results, overflowing formulas\n\nWe will correct these in the revision and, given the extra space, move the monitoring application from the supplement into the main text.\n\n[R1] Klebanov et al., A rigorous theory of conditional mean embeddings, 2020\n\n[R2] Caponnetto and De Vito, Optimal rates for the regularized least-squares algorithm, 2007\n\n[R3] Mollenhauer et al., Regularized least squares learning with heavy-tailed noise is minimax optimal, 2025\n\n[R4] Singh and Vijaykumar, Kernel ridge regression inference, 2023"}, {"review_id": "IKxldeZwgz", "reviewer": "Reviewer_CBs5", "summary": "The paper proposes a conditional two-sample testing framework using kernel methods with finite-sample guarantees. The approach builds confidence bounds via kernel ridge regression (KRR), leveraging existing tools like Abbasi-Yadkori's bounds. While the core idea of using KRR confidence intervals for testing is intuitive, the claimed ability to perform pointwise inference in regions with vanishing probability mass appears to conflict with known impossibility results (the paper even acknowledges this in Section 2: \"Conditional testing is notoriously hard—there exists no nontrivial test with prescribed level against all alternatives.\" ). The authors propose an ad-hoc bootstrapping scheme to address conservative non-asymptotic confidence regions, but this lacks theoretical justification. More fundamentally, the well-specified assumption (that true conditional means lie in the RKHS) is both unrealistic and fails to address how the method circumvents the acknowledged impossibility results for conditional testing.\n\nThe paper proposes a framework for conditional two-sample testing that focuses on identifying covariate values x where the conditional expectations $\\mathbb{E}\\_{p_1}[Y\\mid X=x]$ and $\\mathbb{E}\\_{p_2}[Y\\mid X=x]$ differ. Concretely, the authors reduce the testing problem to comparing two Kernel Ridge Regression (KRR) estimators. The core idea (Theorem 4.2) is that if each KRR estimator $f_{D_i}$ comes with a confidence bound $B_i(D_i,x)$ (i.e. with probability $1-\\delta_i$ we have $|f_{D_i}(x) - \\mathbb{E}[Y\\mid X=x]|\\le B_i(D_i,x)$ for all x in some set S and all sample sizes in N), then one can reject the null $H_0:\\mathbb{E}\\_{p_1}[Y\\mid x]=\\mathbb{E}\\_{p_2}[Y\\mid x]$ whenever $\\| f_{D_1}(x) - f_{D_2}(x)\\| > B_1(D_1,x) + B_2(D_2,x)$. Under these conditions the authors claim that the test has (pointwise) type‐I error bounded by $\\delta_1+\\delta_2$. So, the paper then aims to supply the required confidence bounds by deriving novel KRR concentration results. In Theorem 4.3 the authors claim a time-uniform (anytime) bound for vector-valued KRR under fairly general “uniform-block-diagonal” (UBD) operator-valued kernels $K(x,x')=\\iota(K_0(x,x')\\otimes {\\rm Id}_V)\\iota^{-1}$ and subgaussian noise. This result extends classic scalar KRR bounds to infinite-dimensional outputs and non-trace-class kernels (covering, e.g., conditional mean embeddings). Combining these bounds Theorem 4.4 yields a concrete test: both data sets produce KRR predictors and associated posterior variances $\\sigma(x)$, and one rejects $H_0(x)$ if $|f_1(x)-f_2(x)| > \\beta_1,\\sigma_1(x)+\\beta_2,\\sigma_2(x)$, where $\\beta_i$ depend on confidence levels. Theorem 4.4 shows this test has level $\\alpha_1+\\alpha_2$ over the covariate region X (or a chosen subset S). The authors also propose a practical bootstrap calibration (Appendix B) to estimate the thresholds $\\beta_i$ from data, avoiding manual tuning of RKHS-norm bounds. Empirically, the paper demonstrates in synthetic experiments that the proposed test controls type I error and can achieve higher power than a global conditional-distribution test (Hu & Lei [5]) when the difference in conditional means is localized in rarely-sampled regions of X. They also present toy illustrations of process change-detection using a sliding-window test on linear dynamical systems (Appendix A.3). Overall, the paper claims to provide a “comprehensive foundation” for conditional two-sample testing – bridging theoretical guarantees and practical implementation", "questions": "NA", "limitations": "Not discussed.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "### __Strengths__\n\n- __Related works:__ The authors did a good job reviewing related works and properly citing why conditional testing is a hard problem. \n\n- __Theoretical framework:__ The reduction from conditional testing to learning-theoretic confidence bounds in Theorem 4.2 (any two regression learners with high-probability error bounds yield a valid conditional test) seams elegant. \n\n- __Handling non-i.i.d. data:__ By allowing online sampling (a process of transition pairs) the method covers dependent or sequentially collected data. This is a strength over classical tests that require i.i.d. samples; the authors correctly emphasize that “outputs may not be independent”.\n\n\n### __Weaknesses__\n\n-  __Theoretical Issues:__ The method's claim to detect differences in vanishing-probability regions ($\\theta\\rightarrow 0$) lacks proper theoretical support and seem to contradict well-known impossibility results. From my point of view, the  __authors fail to__: \n(a) Specify necessary assumptions (e.g., density bounds, smoothness) to circumvent impossibility results.\n(b) Explain how their well-specified assumption and UBD kernels with trace-class constraints overcome fundamental limitations \nIn that regard, I suspect that the well-specified assumption and UBD kernel structure may implicitly restrict the complexity of joint distribution of Y|X to simple scenarios, significantly limiting practical applicability.\n\n- __Scope:__  The core method explicitly tests equality of conditional expectations. If two conditional distributions differ in higher moments (e.g. variance) but have the same mean, the basic test will not flag a difference. The authors mention that one can embed outputs or transform data (Algorithm 3 for CMMD) to compare other moments or full distributions, but these extensions are not the main focus. It should be emphasized that the presented test is primarily for conditional mean differences, and that extending to full distributional tests requires additional work.\n\n- The proposed __bootstrapping method lacks theoretical guarantees__ and may overfit\nThe well-specified assumption (that the true conditional means lie in the RKHS) is overly restrictive in practice. There is no guarantee that the chosen UBD kernel can adequately model arbitrary conditional distributions, especially without strong prior knowledge.\n\n- __Empirical Shortcomings:__ \n     - No validation on non-IID or sequential data despite claims \n     - Experiments limited to toy examples: \n     - Low-dimensional X (in dimension 1 or 2)\n     - No testing on high-dimensional complex objects or mis-specfied settings\n\n- __Baseline Comparisons:__\n     - Only compared to one baseline ([5]), omitting modern alternatives \n     - No ablation study to demonstrate UBD's contribution \n\n\nI summary, I cannot recommend this submission for acceptance due to: \n1. Insufficient theoretical justification for key claims (particularly rare-region testing) \n2. Lack of theoretical guarantees for the bootstrapping approach \n3. Narrow experimental validation that doesn't support practical utility", "was_revised": true, "final_justification": "Based on the authors' rebuttal, I believe that they can successfully revise manuscript to integrates all the remarks from myself and other reviewers and meet the acceptance bar. Therefore, I rise my score. That said, I find that revision is very much needed to improve clarity (narrative-wise and theory-wise), especially stressing out fine-line aspects of the impact of assumptions (in particular well-specified) to testing and discussing limitations of the approach taken.", "rebuttal": "Thank you very much for your review and comments. You give the following reasons for suggesting non-acceptance:\n* Insufficient theoretical justification,  particularly for rare-region testing\n* Lack of guarantees of bootstrapping\n* Narrow experiments\n\nWe address each of these points in our rebuttal below, together with the other points you raise. In summary:\n* We respectfully disagree on the lack of theoretical justification on the rare-region testing;\n* Bootstrapping is only a pragmatic heuristic that can be replaced with any available alternative; our core contributions are the **formalization of conditional testing guarantees**, **new confidence bounds for KRR and vector-valued LS**, and their **instantiation in a conditional test**.\n* Our experiments enable understanding the test in controlled scenarios, cover non-iid data generation up to dimension 16, and compare to a modern baseline.\n\nIf you find our responses satisfactory, we would be grateful if you consider raising your score.\n\n> contradicting well-known impossibility results (rare-region sampling, $\\theta\\to0$)\n\nWe believe this comment stems from a misunderstanding: Theorem 4.3 guarantees that, with high probability, the difference between the estimator and the truth is at most $\\beta\\cdot \\sigma$ **everywhere**.\nHence the test can still trigger in sparsely sampled regions --- though the threshold grows where data are scarce and does not fire where no data exist without a strongly extrapolating kernel.\n\nThe key assumptions for this **input-uniform** bound is **RKHS membership** of the conditional expectation.\nFor common kernels (e.g. Gaussian, Matérn) this is a smoothness condition.\n\nFor those reasons, **our results do not violate known impossibility results**: rather, the assumption of RKHS membership appropriately limits the class of allowed Markov kernels to those for which the learning algorithm has some (mild, and depending on the kernel) extrapolation power.\n\nAs you highlight it, **such assumptions are necessary** to escape no-free-lunch results.\nWhether this particular one is \"too strong\" is thus highly dependent on context. It is a commonly accepted assumption in bandits [R2] and in Bayesian optimization, where it has led to highly successful algorithms [R3,20].\nIt is more criticized in the presence of conditional mean embeddings [R4], which our setup allows.\nIn any case, we see it as a starting point: yes, this assumption does impose *some* restriction. Such restrictions are *necessary*, but we are currently investigating whether we can relax RKHS membership while preserving input-uniformity.\nFinally, note that our framework also accepts *any* learner for which similar bounds exist; KRR is just one example.\n\n> the authors fail to: (a) Specify necessary assumptions to circumvent impossibility results. (b) Explain how their well-specified assumption and UBD kernels (...) overcome fundamental limitations\n\nOur previous answer fully addresses these concerns: the core necessary assumption is RKHS membership. Subgaussian noise and UBD kernel are *also* essential technical assumptions to make the proof work, but the core idea overcoming known impossibility results is the regularity of conditional expectations imposed through RKHS membership (with known norm upper-bound).\n\n> the well-specified assumption and UBD kernel structure may implicitly restrict the complexity of joint distributions of Y|X to simple scenarios, significantly limiting practical applicability.\n\nIt is **correct** that well-specification restricts the complexity of the joint distribution.\nIt is **necessary** to restrict this complexity for any guarantees to hold, as shown by the impossibility results you mention.\nWe fail to see why our assumption restricts the joint distribution to only simple scenarios or significantly limits the practical applicability, and would appreciate additional clarifications on this point to address remaining concerns you may have.    \n\n> the method tests equality of conditional expectations (...)  extensions [to compare other moments or full distributions] are not the main focus (...) extending to full distributional tests requires additional work.\n\nWe strongly emphasize that **the method we present in Appendix A to compare other moments or full distributions is not an extension, it is a special case**.\nThe test of Section 4 compares conditional expectations *in an abstract Hilbert space*.\nWe *specialize* it in a distribution-level test by choosing $Y = \\kappa(\\cdot, Z)$: for a characteristic kernel $\\kappa$, we compare full conditional distributions.\nWe claim this pertains to experiment design, however, and does not require additional theoretical work.\nWe will (i) rename Section 3 “Testing of conditional expectations’’ and (ii) move the CME specialization from Appendix A to the main text for clarity.\n\n> The proposed bootstrapping method lacks theoretical guarantees and may overfit\n\nWe present bootstrapping purely as a power-enhancing **heuristic**; it is not a main contribution. Any alternative can replace it without affecting our theory. In the revision we will additionally report results with the scheme of [R1], which enjoys some guarantees under suitable assumptions.\nPreliminary results indicate that this method is more robust to the misspecification of the regularization parameter, but also leads to significantly more conservative bounds and lower power.\nFormal guarantees for input- and time-uniform bootstrapping with online data is an open research problem to our knowledge and is out-of-scope.\n\n> The well-specified assumption (that the true conditional means lie in the RKHS) is overly restrictive in practice\n\nOur comments above illustrate why an assumption of this kind is necessary to escape impossibility results, as you identify it.\nWe would thus appreciate additional details on why you believe this specific assumption is overly restrictive in practice to enable further discussion.\n\n> no guarantee that UBD can adequately model arbitrary conditional distributions, especially without strong prior knowledge\n\nWe emphasize again that it is precisely the purpose of our assumptions to **appropriately restrict** the conditional distributions that can be modeled, as is necessary to escape no-free-lunch results.\nIn particular, any fixed kernel will not be able to capture some conditional distributions.\nThis is in particular the case for any UBD kernel.\nInstead, *the role of the kernel is to encode the prior knowledge about the functions at hand*.\n\n> No validation on non-IID or sequential data despite claims\n\nThese experiments are presented in Section A.3, where data consists of input-output pairs of a dynamical system and is generated sequentially by following trajectories. Our test reliably detects changes as the dynamics are changed.\nWe will use the additional space in the revision to move this section to the main text.\n\n> Experiments limited to toy examples, Low-dimensional X (in dimension 1 or 2), No testing on high-dimensional complex objects or misspecfied settings\n\nWhile we do consider 1- or 2-D inputs in toy cases for illustrative purposes, outputs are up to infinite dimensional. Further, some other cases reach 16-dimensional inputs.\nGiven that the purpose of these experiments is to illustrate the capabilities in well-understood scenarios, we deem this adequate for a first methodological paper.\nFull-scale applications merit separate, dedicated work.\n\n> Only compared to one baseline ([5]), omitting modern alternatives\n\nThe baseline [5] we compare to is less than a year old and leverages conformal methods, which are an active area of research. \nIn our opinion, it thus qualifies as a \"modern alternative\". \nWe would be happy to consider additional baselines that you find appropriate.\n\n> No ablation study to demonstrate UBD's contribution\n\nThe goal of UBD is to be a theoretical tool enabling the most general pointwise concentration bounds for KRR to this day.\nFurthermore, in practice, the kernel is a design choice supposed to accommodate for prior knowledge.\nIn any case, it is not meant as a structure to benchmark on. \nWe would appreciate further details on what kind of ablation study you would expect. \n\n> The approach builds confidence bounds via kernel ridge regression (KRR), leveraging existing tools like Abbasi-Yadkori's bounds\n\nWe thoroughly emphasize that we **do not** leverage the bounds of Abbasi-Yadkori. Rather, we **generalize these bounds to previously inaccessible setups**.\nThe original bounds only consider the scalar case, and available generalizations are limited to trace class kernels and impose strong regularity conditions on the kernel.\nWe remove these assumptions and allow for non-trace class kernels.\nWhat we leverage is the *proof method* of Abbasi-Yadkori, which we adapt to accommodate for the more general assumptions.\n\n[R1] Singh, R., Vijaykumar, S. (2023). Kernel ridge regression inference. arXiv preprint arXiv:2302.06578.\n\n[R2] Srinivas, N., Krause, A., Kakade, S. M., Seeger, M. (2010). Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design. In Proceedings of the 27th International Conference on Machine Learning (ICML).\n\n[R3] Garnett, R. (2023). Bayesian optimization. Cambridge University Press.\n\n[R4] Klebanov et al., A rigorous theory of conditional mean embeddings, 2020"}, {"review_id": "0euIByRtvz", "reviewer": "Reviewer_PbDf", "summary": "The authors establish conditions under which confidence bounds for KRR are equivalent to credible intervals given by Gaussian Process regression. They then show how they can be converted into conditional hypothesis tests. The main idea seems to be to base the hypothesis test on the pointwise overlap between two GP posteriors: the more overlap, the more likely one fails to reject the null hypothesis (at that particular input).", "questions": "1) Why frame the learning algorithm as KRR with confidence bounds? The equations appear much more similar to GP regression with credible intervals given by the posterior covariance. A similar point is mentioned in passing in line 308, but to me this seems like the core insight behind the whole theorem! If that's true, then I think this should be emphatically mentioned earlier.\n\n2) If it is true that the proposed test is equivalent to examining the (pointwise) posterior distribution of the difference between the two estimators and testing whether the credible interval contains 0, then can you clarify how Theorem 4.3 is different from the standard theory of GP regression?\n\n3) It is known that functions that are less smooth w.r.t. to chosen kernel (i.e., have larger RKHS norm) are harder to learn (in KRR and GP regression). Intuitively, it seems that one should be less likely to reject the null in the case that the data generating processes is not smooth (and thus hard to learn). However, my understanding is that the posterior variance is blind to the alignment between the kernel and E[p](x), so the hypothesis test cannot depend on the smoothness of E[p](x). Can you provide some intuition as to why the hypothesis test does not seem to depend on this? Is it simply that the estimation error is contained in the posterior mean rather than the variance? (It could be that I'm simply mistaken about the relationship between estimation error and hypothesis testing.)", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "I preface this review by stating that the research area and proof techniques are quite unfamiliar to me. I can't fairly evaluate the impact or originality of the work.\n\n**Strengths.**\n* The writing is very clear, and the main argument is not too hard to follow.\n* There are no clear errors in the mathematical framing.\n* The idea is pretty neat -- in general it seems useful to find Rosetta stones between learning theory and statistical testing, and this result seems to be a big one. To be honest, I'm a bit surprised that this has not been done before!\n\n**Weaknesses.**\n* The technical formality obscures the main idea, in my opinion. I understand that rigor is important to some researchers, but I found it quite difficult to parse the theorem statements. Perhaps informal versions of the theorems can be given early in the paper.", "was_revised": true, "final_justification": "My main concern was understanding the significance of the work. The result initially seemed very similar to standard results in Gaussian process regression. The authors clarified that their results *generalize* the previous results. In particular, in order to devise tests comparing various *distributional* quantities, one needs to consider regression with infinite-dimensional outputs. (I did not independently verify this claim, but it seems plausible.) The authors' technical contribution is in devising confidence bounds for regression problems of this class. My evaluation of the significance of this work is now much higher.\n\nI would rate my confidence as 2 or 3. I am not an expert in this area but the explanations are consistent with what I have seen before.", "rebuttal": "Thank you very much for your review and the positive evaluation. \nBelow we address each of your concerns and questions in turn.\nIf you find our answers satisfactory, we would be grateful if you consider raising your score.\n\n> The technical formality obscures the main idea, in my opinion. I understand that rigor is important to some researchers, but I found it quite difficult to parse the theorem statements. Perhaps informal versions of the theorems can be given early in the paper.\n\nWe understand that this comment is particularly referring to Theorems 4.3 and 4.4, given that an intuitive interpretation of Theorem 4.1 is available right after its formal statement.\nWe thank you for your comment and will provide informal summaries in the text surrounding them. \nWe believe this is more suitable than stating them informally earlier (e.g., in the introduction) given that the whole of Section 3 is about making precise the terminology of conditional testing.\n\n> Why frame the learning algorithm as KRR with confidence bounds? The equations appear much more similar to GP regression with credible intervals given by the posterior covariance. A similar point is mentioned in passing in line 308, but to me this seems like the core insight behind the whole theorem! If that's true, then I think this should be emphatically mentioned earlier.\n\nYour identification between GP regression and KRR is correct; the two estimators coincide up to rescaling of the noise/regularization parameter [R1].\nThe name given to the algorithm is thus mainly a matter of preference.\nHistorically, the bounds of the form of Theorem 4.3 have been mainly used in bandits [R2] and Bayesian optimization [R3].\nThey are thus often called \"frequentist uncertainty bounds for Gaussian process regression\".\nWe decided to break from this terminology for two main reasons.\nFirst, Gaussian processes are often used in Bayesian frameworks; yet, the bound is *not* Bayesian. It quantifies the difference between the estimator (the GP mean) and the ground truth, which does not have an equivalent in Bayesian methods. Furthermore, the proof is *not* based on the confidence intervals of the Gaussian distribution nor on the fact that the posterior of a GP is a GP. The posterior variance also appears from an entirely different mechanism than conditioning (specifically, it appears in the beginning of the proof in (19) in Lemma D.2).\nSecond, Gaussian processes are often used in settings with a simple output space (e.g., just scalar outputs), whereas here we allow even outputs in an abstract Hilbert space. \nThis is relatively uncommon for Gaussian processes, but more usual with KRR.\n\nWe do agree that there is value in the Gaussian process interpretation, however, and will highlight it further in the revision, both in the introduction and around Theorem 4.4.\n\n> If it is true that the proposed test is equivalent to examining the (pointwise) posterior distribution of the difference between the two estimators and testing whether the credible interval contains 0, then can you clarify how Theorem 4.3 is different from the standard theory of GP regression?\n\nYour interpretation is almost perfect: the posterior variances need to be scaled by the appropriate factor $\\beta$, which can be interpreted as a correction term to obtain frequentist bounds from the Bayesian ones.\nThis being clarified, Theorem 4.3 is *not* different from the standard theory of GP regression; it is a generalization.\nSpecifically, GP regression admits well-known frequentist confidence intervals.\nThe most well-known ones hold in the scalar output case [R2,12,19].\nRecent generalizations allow *infinite-dimensional outputs with a trace-class kernel*, and require strong additional assumptions on the kernel and the input set (bounded kernel on a compact set).\nIn contrast, our result is the first to allow *infinite-dimensional outputs with non-trace-class kernels*, which allows the classical case of $K = k\\cdot\\mathrm{id}_{\\mathcal G}$, and also removes *all* regularity assumptions connecting the kernel to the input set, allowing a more varied class of such sets.\n\n> it seems that one should be less likely to reject the null in the case that the data generating processes is not smooth (...) my understanding is that the posterior variance is blind to the alignment between the kernel and $\\mathbb E[p]$ (...) Can you provide some intuition as to why the hypothesis test does not seem to depend on [the smoothness of $\\mathbb E[p]$]?\n\nYour understanding that testing for less smooth functions is harder is indeed correct, and the test *does* depend on the smoothness of $\\mathbb E[p]$ in two ways:\n1. We assume that $\\mathbb E[p]$ lies in the RKHS. \n2. We also assume a known upper-bound on $\\lVert\\mathbb E[p]\\rVert_k$, and this upper bound enters the threshold in the constant $\\beta$ ($\\beta$ has the form $\\lambda^{-1/2}(B + \\cdots)$, where $B$ is the upper bound). In other words, testing for functions with higher RKHS norms (which can be interpreted as more complex functions) leads to higher thresholds, and thus require more data to trigger.\n\n[R1] Kanagawa et al., Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences, 2018\n\n[R2] Srinivas et al., Information-theoretic regret bounds for gaussian process optimization in the bandit setting, 2010\n\n[R3] Sui et al., Safe exploration for optimization with Gaussian processes, 2015"}, {"review_id": "UYxxLy8raR", "reviewer": "Reviewer_psDa", "summary": "This paper's major contributions are:\n\n- A framing of the relationship between conditional two-sample testing – particularly when it is desired to find for _which_ conditioning values those distributions differ – and learning-theoretic bounds on estimation error of regression.\n- A new learning-theoretic bound for the estimation error of kernel ridge regression.\n- A bootstrapping scheme for KRR that avoids using the overly-conservative and hard-to-estimate precise form of the bounds derived for the test.", "questions": "- How does Theorem 4.3/D.23, particularly in case 2, compare to the results of https://www.jmlr.org/papers/volume25/23-1663/23-1663.pdf that follow up [40]?\n- Can the Singh and Vijaykumar KRR bootstrap help here?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "- The connection between estimation and testing is clear, and while the formal result of Theorem 4.1 is straightforward, setting it out in this way is illuminating. Connecting to the no free lunch theorem and the hardness result of Shah and Peters for conditional dependence is particularly helpful.\n  - It might be _more_ helpful to expand further, perhaps in an appendix, on the relationship between conditional two-sample testing to conditional independence testing. It is probably not obvious to all readers that the problems can be directly reduced to one another, nor that doing so actually breaks the jointly-continuous assumption that was vital to the construction of Shah and Peters but does not invalidate hardness in this setting.\n  - That this construction allows directly using time-uniform bounds is exciting! The paper could probably emphasize the practical implications of this a little bit more.\n\n- Theorem 4.3, and the generalization D.23, appear novel and interesting.\n  - It's a little disappointing that they don't yield practical tests, but this is also fairly expected; for instance, the 2012 paper after which this paper styles its title constructed bounds based on concentration inequalities (much simpler in the non-conditional setting).\n  - Appendix C's discussion of the relationship to the results of [40] in particular seems quite sparse. These authors also had a more recent followup generalizing the setting: [https://www.jmlr.org/papers/v25/23-1663.html](Li et al. 2024). Especially, they remove the trace-class assumption in a slightly different way, but their construction (as discussed eg in Remark 2) seems closely connected to your UBD definition.\n\n- The bootstrap scheme is straightforward and seems fine as a heuristic.\n  - It would be good to relate this to other bootstraping schemes for kernel ridge regression, especially the scheme of [Singh and Vijaykumar (2023)](https://arxiv.org/abs/2302.06578) who provide finite-sample guarantees. Can their scheme be used here?\n\n- Generally: I imagine some of the other reviewers will complain about the readability of this paper. It is certainly not a particularly approachable paper to non-experts in the field, but that seems somewhat inevitable for a paper taking on this set of results and framed in this way. This highlights a bit that Theorem 4.3/D.23, while relevant to the test procedure, is (a) a completely standalone result and (b) not actually used in the test procedure. Another strategy could be to write one more-accessible paper about conditional testing and its relationship to estimation error along with the heuristic for estimating it, and another paper about the theorem; I'm not sure this is necessarily a better strategy, but some reviewers might disagree.", "was_revised": true, "final_justification": "The importance of the difference between UBD and the form used by Li et al., although they are clearly related, has been clarified a bit for me. I think an appendix going into further detail about this relationship will be quite important for the final version of this paper.", "rebuttal": "Thank you very much for your detailed review and positive evaluation.\nWe will address each of your concerns and questions in turn.\nIf you find our answers satisfactory, we would be grateful if you consider raising your score.\n\n>It might be _more_ helpful to expand further, perhaps in an appendix, on the relationship between conditional two-sample testing to conditional independence testing. It is probably not obvious to all readers that the problems can be directly reduced to one another, nor that doing so actually breaks the jointly-continuous assumption that was vital to the construction of Shah and Peters but does not invalidate hardness in this setting.\n\nThank you very much for this suggestion. This would indeed be helpful for readers, and we will include a corresponding discussion in the appendix.\n\n>Theorem 4.3, and the generalization D.23, appear novel and interesting.\nIt's a little disappointing that they don't yield practical tests, but this is also fairly expected; for instance, the 2012 paper after which this paper styles its title constructed bounds based on concentration inequalities (much simpler in the non-conditional setting).\n\nWe agree that the situation somewhat parallels the situation in [1]. However, we would like to point out that while the uncertainty bounds from Theorem 4.3 / D.23 are in general not directly applicable in practice (due to the need for an RKHS norm bound and potential conservatism), they are useful for deriving a practical testing procedure by providing a theoretically-sound and convenient form of the uncertainty bound, that in turn suggests a practical Bootstrap approach. \n\n>That this construction allows directly using time-uniform bounds is exciting! The paper could probably emphasize the practical implications of this a little bit more.\n\nThis is a very good point and we will add corresponding remarks in the revised version. Indeed, time-uniform uncertainty bounds play an important role in many practical algorithms, from bandits / Bayesian optimization, sequential testing, to learning-based control. For example, our uncertainty bounds might be of direct use in multi-task Bayesian optimization, cf. [20].\n\n>Appendix C's discussion of the relationship to the results of [40] in particular seems quite sparse. These authors also had a more recent followup generalizing the setting: https://www.jmlr.org/papers/v25/23-1663.html (Li et al. 2024). Especially, they remove the trace-class assumption in a slightly different way, but their construction (as discussed eg in Remark 2) seems closely connected to your UBD definition.\n\nThank you for pointing this out. We will extend the corresponding passages in Appendix C, and we provide a detailed discussion in the answer to your first question below.\n\n>Generally: I imagine some of the other reviewers will complain about the readability of this paper. It is certainly not a particularly approachable paper to non-experts in the field, but that seems somewhat inevitable for a paper taking on this set of results and framed in this way. This highlights a bit that Theorem 4.3/D.23, while relevant to the test procedure, is (a) a completely standalone result and (b) not actually used in the test procedure. Another strategy could be to write one more-accessible paper about conditional testing and its relationship to estimation error along with the heuristic for estimating it, and another paper about the theorem; I'm not sure this is necessarily a better strategy, but some reviewers might disagree.\n\nThank you very much for your thoughtful comment. \nWe agree that the manuscript is rather technical, but since we want to develop a general, theoretically-grounded framework that is also applicable, we need some machinery to realize this.\nTo increase the readability and accessibility of the manuscript, we have already included a tutorial-style overview on practical aspects in Appendix A.1 and a convenient summary of the algorithms in Appendix A.2, and we will include your and the other reviewer's comments to further improve the user-friendliness.\nFurthermore, we agree that Theorem 4.3 / D.23 is indeed a result of significant independent interest. However, it is essential for our testing approach since 1) it informs the type of bootstrapping approach and 2) it provides a theoretical justification of the overall approach,\nand hence the application to our general testing framework provides a compelling and concrete demonstration of the utility of Theorem 4.3 / D.23.\nFor these reasons, we think that combining our general framework, our results on uncertainty bounds, and the concrete kernel-based tests, leads to a cohesive article, and that the advantages of this approach outweigh the potential disadvantages.\n\n>How does Theorem 4.3/D.23, particularly in case 2, compare to the results of https://www.jmlr.org/papers/volume25/23-1663/23-1663.pdf that follow up [40]?\n\nConceptually, in both [40] / Li et al '24 and in our work, a tensor structure (of the vRKHS) is used to circumvent a trace-class assumption. More precisely, in both cases a multiplicative structure of the kernel leads to a tensor product structure on the vRKHS, which in turn is used for the analysis. However, we would like to point out the following important differences.\n1. We introduce a novel structural assumption (UBD) generalizing the common multiplicative structure of kernels which has been used in [40] / Li et al '24. The UBD assumption essentially encapsulates the minimal structure that is required to make our proof technique work. We suspect that the UBD structure might actually be suitable for further generalizing the results from [40] / Li et al '24, but this is an interesting direction for future work and beyond the scope of this manuscript.\n2. The actual use of the tensor structure is rather different. Whereas [40] / Li et al '24 use it to generalize the classic integral operator technique without a trace class assumption, we use it (actually, the more general UBD structure) to adapt the method of mixtures (more precisely, to use a multiplicative double-mixture argument), leading in our case to a novel uncertainty bound.\n3. [40] / Li et al '24 are concerned with the analysis of the KRR learning algorithm (in particular, learning rates), whereas we derive new uncertainty bounds for KRR, which in turn can be used in downstream algorithms or statistical procedures (like the conditional tests in our case). The issue of the trace-class assumption becomes particularly relevant here, since in existing uncertainty bounds a Fredholm determinant appears, which is not even defined for non-trace class operators. In other words, we need this tensor product approach to even formulate the right result, instead of just analyzing an existing method.\n3. Finally, the concrete use of the tensor structure (ignoring for now the generalization to UBD) is different. [40] / Li et al '24 rely primarily on an identification with Hilbert-Schmidt operators, whereas we work directly with the tensor structure.\n\n>Can the Singh and Vijaykumar KRR bootstrap help here?\n\nYes. Our bootstrapping scheme can be drop-in replaced with any available alternative, which we will emphasize more in the revision.\nFurthermore, we will include results with the Singh and Vijaykumar KRR bootstrap in the revision. Their method is computationally more scalable and more robust to misspecification of the regularization parameter. However, preliminary results indicate that it also leads to more conservative bounds and lower power in low-data settings. Please also note that their guarantees do not hold in our more general setting (e.g., they assume i.i.d. data and scalar-valued outputs)."}, {"review_id": "nGVgLtTds6", "reviewer": "Reviewer_nADy", "summary": "This paper introduces a novel framework for hypothesis testing on conditional probability distributions, specifically developing a conditional two-sample test. The primary goal is to determine if the relationship between inputs (termed covariates) and outputs is the same across two different phenomena, with applications in fields like process monitoring, robotics, and medical studies.", "questions": "1. While the paper introduces bootstrapping schemes to avoid tuning inaccessible parameters, are there specific scenarios or types of datasets where these schemes might face practical limitations or lead to less accurate results? For instance, how robust are they to outliers or highly noisy data?\n\n2. The framework is built upon kernel methods. What guidance can be provided on the selection of appropriate kernel functions for different types of data and applications to ensure optimal performance of the conditional two-sample test? Are there specific types of kernels that are more suited for certain conditional distribution characteristics?", "limitations": "NA", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n1. A central idea is the transformation of confidence bounds from learning methods into conditional two-sample tests. This principle is applied and demonstrated using Kernel Ridge Regression (KRR) and conditional kernel mean embeddings.\n\n2. To enhance practical usability, the paper introduces bootstrapping schemes. \n\n\n**Weaknesses**\n\n1. The central null hypothesis, as stated in Equation (5), is E(p1)(x) = E(p2)(x). This is a test for the equality of conditional expectations, not a conditional two-sample test in the general sense. \n\n2. The authors dedicate a substantial portion of the paper to laying out a highly abstract mathematical foundation involving Markov kernels, subgaussian processes in Hilbert spaces, and reproducing kernel Hilbert spaces (RKHS) for vector-valued functions. While this formalism is necessary for the paper's specific theoretical proofs, it is disproportionate to the narrowness of the final result. \n\n3. The entire framework is built on transforming the confidence bounds of Kernel Ridge Regression (KRR) into a statistical test. Consequently, the method inherits all the limitations of KRR. The most critical of these is the \"well-specified\" assumption, which requires that the true conditional expectation function lies within the chosen RKHS. This is a strong assumption that is difficult, if not impossible, to verify in practice, casting doubt on the reliability of the test's guarantees in real-world applications where model misspecification is the norm.\n\n4.  The paper claims an advantage in its ability to provide \"local\" guarantees, identifying at which covariates two functions differ. However, the value of this localization is severely diminished when the test can only detect differences in the mean. A practitioner could use this test and find no significant difference across the entire covariate space, incorrectly concluding the conditional distributions are identical, while in reality, one might have collapsing variance or other critical behavioral changes that the test simply cannot see.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your detailed review. \nWe address each of your points in details below.\nIf you find our responses satisfactory, we would be grateful if you would consider raising your score.\n\nFirst, we would like to point out that the uncertainty bound in Theorem 4.3 / D.23 are, in our opinion, another key contribution of our paper in addition to the ones you emphasize in your summary, as they are the most general ones available in the literature.\nTheir proof also involves novel steps and a novel assumption, which are major technical advances in the field.\n\n>The central null hypothesis, as stated in Equation (5), is $\\mathbb E(p_1)(x) = \\mathbb E(p_2)(x)$. This is a test for the equality of conditional expectations, not a conditional two-sample test in the general sense.\n\nWe would like to stress that our framework and the resulting tests are **not** limited to just testing equality of conditional means. \nThe test of Section 4 for conditional means holds for outputs in an abstract Hilbert space.\nWe *specialize it* into a distribution-level test by a preliminary embedding of the data of the form $Y = \\kappa(\\cdot, Z)$.\nThis yields a *conditional mean embedding*, but just as in the case of \"unconditional\" kernel two-sample tests [1], this does **not** mean that only equality of means can be tested. The properties of conditional distributions that can be tested depend on the kernel $\\kappa$. For instance, a linear kernel can test for equality of means, polynomial kernels test for higher-order moments, and sufficiently expressive (*characteristic* [26, Section 3.1.1]) kernels like the Gaussian kernel can test for all moments. In Appendix A.1, we give a detailed exposition of these considerations and also conduct careful numerical experiments investigating the different testing behavior with respect to higher-order moments arising from different embedding kernels.\n\nWe will clarify this in the revision by renaming Section 4 to \"Testing of conditional expectations\" and moving parts of Appendix A.1 to a dedicated subsection of Section 4 explaining how to specialize the test for full two-sample testing.\n\n>...While this formalism is necessary for the paper's specific theoretical proofs, it is disproportionate to the narrowness of the final result.\n\nOur results and methods actually use the abstract foundations in its formulation and usage, not just in its proof. In particular, the specialization to comparing higher-order moments of distribution fully relies on the fact that the output lies in an abstract Hilbert space to accommodate general embeddings for the data, which eventually allow us to use rich characteristic kernels and compare full distributions, eventually resulting in tests for complex properties of conditional distributions. The level of abstraction is thus a *feature* and is essential for practical usage.\n\nFurthermore, the final result that you emphasize (Theorem 4.4) is only **one** of our main contributions, as the concentration bounds for KRR we establish in Theorem 4.3 are also essential to our contribution. More restrictive variants of Theorem 4.3 have been widely used in bandits and Bayesian optimization with great success, leading to many practical and popular algorithms [R1,R2,20], and hence our generalization to more permissive cases is an important milestone in our opinion, as it enables a new class of applications by allowing conditional mean embeddings of distributions.\n\n>... the method inherits all the limitations of KRR. The most critical of these is the \"well-specified\" assumption...\n\nWe preface this answer by saying that a similar point has been raised by Reviewers qzic and CBs5, and we refer you to our answers there for other aspects of the discussion.\n\nThe known results of impossibility of conditional two-sample testing [3] indicate that **assumptions limiting the class of conditional expectations considered are necessary for guarantees**. Without such assumptions, no-free-lunch theorems apply and adversarial examples on which learning is impossible can be constructed.\nOur Theorem 4.1 formalizes that **one can escape the no-free-lunch of conditional testing via classical assumptions in learning theory**.\nIn that regard, the well-specified assumption of KRR is a standard assumption in learning theory to enable successful learning. \nWhether or not it is restrictive is fully determined by context: it is widely accepted in Bayesian optimization [R2], and more debated for arbitrary conditional mean embeddings [R3].\nWe would appreciate additional details on why you believe this assumption is too strong to enable further discussion on this point.\n\nRegarding how hard it is to check, it is again an unavoidable consequence of no-free-lunch results: such assumptions should capture the *prior knowledge* on the problem at hand, as there is no way of checking them a priori. \nWe emphasize that this comment is *not* restricted to RKHS membership: it would be equally impossible to verify a priori that a function is Lipschitz continuous with a given Lipschitz constant [R4], or that it belongs to an interpolation space between an RKHS and $L_2$ (which is the classical assumption to handle the misspecified case in KRR) [40].\nWhile practitioners may have a better sense of whether *some* of these assumptions effectively hold, they ultimately remain assumptions that one cannot check.\n\nSummarizing, while we agree that it is unfortunate that such assumptions cannot be checked a priori, it is also a consequence of known no-free-lunch results in conditional testing, and *any* conditional test with guarantees must rely on such assumptions.\n\n\n>...the value of this localization is severely diminished when the test can only detect differences in the mean...\n\nAs discussed above, our framework *does go beyond comparing conditional means*. We agree that in practice, capturing differences in higher moments is crucial—this is precisely what our general setting enables.\n\n>While the paper introduces bootstrapping schemes to avoid tuning inaccessible parameters, are there specific scenarios or types of datasets where these schemes might face practical limitations or lead to less accurate results? For instance, how robust are they to outliers or highly noisy data?\n\nThese are very relevant questions for practical applications, but they exceed the scope of this study, which is a methodological paper introducing the new method from its theoretical foundation to the implementation.\nFor this reason, we limit the scope of the experiment to illustrate the capabilities and behaviours in simple and well-understood scenarios, mainly for illustrative purposes and checks of performance.\nWe do not try to explore all possible applications or explore the limitations of the heuristic.\n\nThat being said, we also emphasize that the bootstrapping scheme we introduce is only a **heuristic** used to enhance power and avoid tuning hyperparameters.\nIt can be directly replaced with any alternative without affecting the method.\nAs an example, we will include in the revision results leveraging the bootstrapping scheme of [R5].\nYet, a full study on benchmarking bootstrapping schemes for KRR to find the best performing ones and their limitations is left for future work.\n\n>The framework is built upon kernel methods. What guidance can be provided on the selection of appropriate kernel functions for different types of data and applications to ensure optimal performance of the conditional two-sample test? Are there specific types of kernels that are more suited for certain conditional distribution characteristics?\n\nThis is a very relevant question. In fact, for the concrete kernel-based test we propose, one has to make two choices of kernels: One for the conditional kernel mean embedding, and one for kernel ridge regression.\n\nRegarding the first one, the choice of kernel determines which distributional properties of the conditional distributions are tested for (we discuss this in Appendix A.1 in detail), and ultimately it depends on the concrete application.\nWe would like to stress that these considerations appear in all kernel embedding-based approach (for testing or even regression, like in distributional regression with two-stage sampling), and hence this has been discussed thoroughly in the literature.\nAs a rule of thumb, if only lower moments are of interest, a linear or polynomial kernel should be chosen, whereas if all moments are of interest, an expressive kernel like the Gaussian kernel should be used. However, there can be tradeoffs, as we demonstrate with numerical experiments in Appendix A.1. \n\nRegarding the choice of kernel for KRR, this is a standard problem and many approaches have been proposed in the literature, cf. [37] for an overview and [26, Section 6.1] for a discussion of the fact that this is a general question in kernel methods.\nA detailed discussion of this question is therefore beyond the scope of this work.\nIn general, the kernel should reflect the known or assumed smoothness properties of the regression function, and it should be sufficiently expressive. \nFor example, in the context of conditional testing for physical dynamical systems, one can often assume a considerable degree of smoothness, and hence the smooth, yet expressive Gaussian kernel is a good default choice. \nFinally, we would like to point out that our UBD assumption allows a very broad range of admissible constructions of kernel with infinite-dimensional output spaces, and hence offers substantial freedom for the choice of the kernel for KRR.\n\n[R1] Srinivas et al., Information-theoretic regret bounds for gaussian process optimization in the bandit setting, 2010\n\n[R2] Sui et al., Safe exploration for optimization with Gaussian processes, 2015\n\n[R3] Klebanov et al., A rigorous theory of conditional mean embeddings, 2020\n\n[R4] Fiedler et al., On safety in Bayesian optimization, 2024\n\n[R5] Singh and Vijaykumar, Kernel ridge regression inference, 2023"}]

Author rebuttal:

Meta-review: The paper exploits a relationship between conditional two-sample testing and learning-theoretic bounds on estimation error of regression to propose a conditional two-sample testing framework using kernel methods with finite-sample guarantees. The approach builds confidence bounds via kernel ridge regression (KRR), leveraging existing tools like Abbasi-Yadkori's bounds. 
I agree with most reviewers that this is a strong contribution to conditional two-sample testing based on kernel methods that makes an elegant connection with learning theory.
Decision: Accept (poster)