Optimal kernel regression bounds under energy-bounded noise
Authors: Amon Lahr
Johannes Köhler
Anna Scampicchio
Melanie Zeilinger
Venue: NeurIPS 2025 poster ()
Keywords: kernel regression
Gaussian process regression
uncertainty bounds
Primary area: theory
TL;DR: This paper provides an optimal, non-asymptotic uncertainty bound for kernel-based estimation assuming a general bound on the noise energy.

Abstract: Non-conservative uncertainty bounds are key for both assessing an estimation algorithm’s accuracy and in view of downstream tasks, such as its deployment in safety-critical contexts. In this paper, we derive a tight, non-asymptotic uncertainty bound for kernel-based estimation, which can also handle correlated noise sequences. Its computation relies on a mild norm-boundedness assumption on the unknown function and the noise, returning the worst-case function realization within the hypothesis class at an arbitrary query input location. The value of this function is shown to be given in terms of the posterior mean and covariance of a Gaussian process for an optimal choice of the measurement noise covariance. By rigorously analyzing the proposed approach and comparing it with other results in the literature, we show its effectiveness in returning tight and easy-to-compute bounds for kernel-based estimates.

Optimal kernel regression bounds under eneryy-bounded noise
Amon Lahr ETH Zurich amlahr@ethz.cl
Johannes Köhler" ETH Zurich jkoehleeehhz.c
Anna Scampicchio ETH Zurich ascampicc@ethz.chh
Melanie N. Zeilinger
ETH Zurich
mzeilinger@etha. ch
Abstract
Non-conservative uncertainty bounds key for both assessing estimation algorithm's ' accuracy and in view of downstream tasks, such as its deployment safety-critical contexts. In this paper, derive tight, non-asymptotic uncertainty bound for kernel-based estimation, which can also handle correlated noise se- quences. Its computation relies unknown function and the noise, returning the worst-case function realization within the hypothesis class at arbitrary query input location. The value of this function is shown to be given in terms of the posterior mean and covariance of a Gaussian process for an optimal choice of the measurement noise covariance. By rigorously analyzing the proposed approach and comparing it with other results in the literature, we show its effectiveness in returning tight and casy-to-compute bounds for kernel-base estimates.
mild norm-bounden boundedeudeeeess assumption the
1 Introduction
Many problems machine learning can be phrased terms of estimating an unknown (continuous) function from finite set of noisy data. A popular, non-parametric technique to perform such
task and return point-wise estimates is given by the class kernel-based methods [Wahba] 1990
Schölkopf and Smola 2001] (Suykens et al.) 2002 (Shawe-Taylor and Cristianini] 2004 Steinwart
and Christmann, [2008] Complementing such estimates with non-conservative and non-asymplotic
uncertainty bounds enables evaluating their reliability, for example, in view of deploying Bayesian
optimization [Berkenkamp el al.) 2023 Sui et al. 2018 or model-based reinforcement learning Kuss
and Rasmussen 2003] Chua et al. 2018 to safety-critical systems.
Classical uncertainty bounds for kernel-based methods have been developed in statistical learning theory [Cucker and Smale (2002) Cucker and Zhou 2007; Guo and Zhou 2013 Lecué and Mendelson 2017 Ziemann and Tu 2024]. However, these results are mostly aimed at characterizing the learning rate of the kernel-based algorithm and they tend to be difficult apply in practice, being overly conservative or even depending on the unknown function to be estimated. Another viewpoint is given by Gaussian process (GP) regression [Rasmussen and Williams) [006). a kernel-based method that naturally endowed with an uncertainty quantification mechanism. However, closed-form uncertainty bounds are only available when assuming independent and Gaussian-distributed variables [Lederer
et al,, 2019), and their computation in other cases is non-trivial [Gilks et al., 1995). To address
this issue, progbb-bbbbblityy and -on-asymptotic uncertainty bounds have been derived by Srinivas
et al. [2012]; Abbasi- Yadkori (2013]: Burnaev and Vovk (2014); |Feddler et al. [2021]; Baggio
al. 2002 Molodchyk et (2025). phrasing the problem as estimation Reproducing Kernel
Hilbert Spaces (RKHSs) [Aronszajn 1950 Berlinet and Thomas-Agnal 2004). Yet, these bounds
still heavily rely on the (conditional) independence of the noise sequence, which can be hard to
satisfy in practice. This difficulty can be circumvented by leveraging an assumed bound on the
Both co co-authors contributed equally; their ordering alphabetical.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

noise [aaddalena et al. 2021; Reed et al. 2025; Scharnhorst et al. 2023 however, these results
tend be conservative or rely on solving a computationally intensive, constrained optimization problem to evaluate the uncertainty bound.
Contribution In this paper, we propose a novel non-asymptotic uncertainty bound for kemel- based estimation assuming a general bound on the noise energy. In particular, for each query input location, the proposed bound exactly characterizes the worst-case latent function within the given hypothesis class. The obtained uncertainty bound has the same structure as the high-pri prob-brbbyyilityy uncertainty bounds from GP regression [Srinivas et al. 2012 Abbasi- Yadkori 2013 Fiedler et al.) 2021, Molodchyk et al. 2025], but with a measurement noise covariance o² that depends on the test input location. Furthermore, we show that the derived bound recovers results from kernel interpolation (Weinherger and Golomb| 1959 Wendland] (004) and linear regression [Fogel] 1979) as special cases. Finally, we contrast the proposed robust treatment to existing bounds for GP regression.
The matrix I, E R denotes the identity matrix of dimension For a symmetric positive-semidefnitte matrix A E RRxx, A denotes the (positive-semidefiiig symmetric matrix square root, ic.. A = A, and ||=]||a = T Az denotes the weighted Euclidean norm of vector 2: E Rd. The Dirac delta function is denoted by : R - R, with d(x) = 1 for x = 0 and 6(x) = otherwise. Superscripts f and w will refer to the latent function and the noise, respectively. Accordingly. the kernel function is denoted by : R"= x R" + R. with O E {f. w) and the associated RKHS is denoted by Hgo. For two arbitrary ordered sets of indices I, S N, the matrix is the Gram matrix collecting the evaluations of the kernel function k= pairs of imput locations 24, Zz,, with i I and j We denote by N = .......N] S N the set of indices for the training data points, while we use ÆN+1 to represent the arbitrary test input.
Notation
KD = (z),
For instance, K K 1+1. E g corresponds to [k/ (IN41, ...., ...,,..... [NN+1, and can be interpreted as the covariance matrix between the test- and training input locations.
2 Problem set-up
We consider the problem of estimating an unknown latent function f" X - R, with X C R" from noisy measurements
y: = (x;) + nh (x:), i 1= N,
(1)
collected at known training input locations x; E X. Our goal is to compute worst-case uncertainty bounds around the latent function fo given the observed data set D - {z 9:) F which is subject to the unknown noise w.' X' - RR. We phrase the problem in the framework of estimation in RKHSs [Aronszajn 1950: Berlinet and Thomas-Agnan 2004), and we model both the latent function y and the noise w as elements of an RKHS with a known kernel and a bound on their RKHS norm.
Assumption The unknown latent and noise functions are respective elements of the RKHSs corresponding the positive-semidefiite kernel k X x X + R20 and the positive-defintte kernel kz : X x X + R2o, where both kd' and A.M are uniformly bounded. There exist known constants I 1
Iw > 0 strictly bounding their respective RKHS norms, i.c., || < 13 and | " < r
Characterizing boundedness of the noise using a kernel k and an RKHS-norm bound I provides a very general description and can model various scenarios: for instance, it captures the setting in which the noise sequence has bounded energy, as we elucidate in Section 4.1] Additionally, modeling noise as a deterministic quantity allows us to by-pass additional assumptions on the distribution or independence of the noise, latent function input locations.
Since we model both the latent function and the noise as deterministic objects, there cannot be multiple output measurements at the same input location. Hence, we consider distinct inputs.
Assumption The training input locations in X f.1,... NND are pairwise distinct, i.e., x; # x. for all i 1,...,N N and i j.

---

3 Kernel regression bounds for energy-bounded noise
In the following, we present the main result of our paper, determining tight point-wise uncertainty bounds (xNN11) I (= S
f(xN+1) for the value of the latent function at an arbitrary test
point NN+1 E This task can be formulated as an infiniteddimensional optimization problem, taking the bounded-RKHS. Rkrm- assumption into account. The optimal upper bound [(xN+1) defined as
[(NN+))
sup SEH wEH
f(xN+))
(2a)
s.t.
f(x;) + w(x)) = Us. 1. L....,, N,
(2b)
11 s STT,
(2c)
|| S r
(2d)
Analogously, the optimal lower bound is given by:
[(N++1)
inf
F(NN+1)
(3a)
SEH,r w
S.L.
2b) 2b)-(2d)
(3b)
In the following, we focus on computing the upper bound J (1)+ for the lower bound, the presented results in Sections 3.1 and 3.2 are analogously derived in Appendices [ respectively.
Stated as in (2). the optimization problem is infiniteddimensional and not directly tractable. Our key result, presented in the remainder of the section, consists in finding exact reformulation of the constrained, infiniteddimensionall problem (2) as scalar, unconstrained one. The solution the latter at arbitrary input location is expressed in terms of familiar quantities from Gaussian process regression, for an optimal choice of measurement noise covariance. We present our derivation by first studying a relaxed formulation of this optimization problem in Section Then, in Section 3.2 discuss how to recover the optimal solution from the relaxed problem.
3.1 Relaxed solution
The relaxed formulation of optimization problem ( considers the sum of the RKHS-norm con- straints (2c.. (d) instead of enforcing them individually:
8dd (IN+1)= sup
f(xN41)
(4a)
SEHLf
WeH
s.t.
f(x;) + w(x;) Uir i= 1, I,
(4b)
r
|lf + 11wll124 S
(4c)
o²
This problem uses a scaled noise kernel k. (z, x²) 022"0 (x, x') with constant output scale o >
which is key in relating the solution of the relaxed problem 44) to the original formulation (2).
Additionally, note that the scaling implies || = || Hew 70" < 1 /o as displayed in
constraint 4c).
The bound f (IN+1) obtained from the relaxed problem depends on the noise parameter a, as the
joint RKHS-norm constraint (4c) is given by weighted sum of both original constraints (cc and (2d). Any feasible solution of ( tuple (f, w) of functions satisfying the constraints (2b) 2d is also
feasible solution for Problem 4 for any E (0, xo). Thus, ["xxx++1] < f(IN+1) S J (IN+1),
i.e. the uncertainty envelope obtained by solving the relaxed problem 44 contains the one obtained
by solving the original problem (2) for all test points N--1 X' and noise parameters E (0, oo).
Before stating the first result of this paper, the following definitions in terms of known quantities from Gaussian process regression are required. First, we define
(*(N++1)= = KETLLNN (KILNANN o² o2KTN.IN
V,
(5a)
[x(=+11 = K KETTIEN (KEAN.IN + oEKKNN,N)) Kg
K
(5b)
3

---

with measurements = 1y1,..... E TR For the particular choice of noise kernel as ke (x, = h² (I, = =f0(( - z'), it holds that K K.N..:N Ty and the above quantities re- spectively correspond to the GP posterior mean and covariance for independently and identically distributed (i.i.d.) Gaussian measurement noise with covariance r² |Rasmussen and Williams/ 2006
Chapter 2]. Additionally, we denote by
l1 11 p
min g
s.t. g(xi) = yis i i
=v- KNNNNN + o² 12KKNNINN y
(6)
the RKHS norm of the minimum-now norm interpolant in the RKHS H4r44= defined for the sum of kernels kf +k" (Berlinet and Thomas-Agnan 2004 Theorem 58]. Lastly,
r 8 = r
11g5 H
(7)
o²
defines the maximum norm (4c) in the RKHS H4r44> based on Assumption I reduced by the minimum norm required to interpolate the data.
The relaxed problem
4 admits the following closed-form analytical solution.
Lemma 1.
Let Assumptions
and 2 hold. Then, the solution of Problem is given by
(#N+1) = (x + Bor Ed (xN+1).
Sketch of proof: First, following arguments from the Representer Theorem [Kimeldorf and Wahba 1971 Schölkopf et al. [201]] we show that the solution of Problem (4) is finiteddimensional Next, two coordinate transformations are employed to reduce the number free variables resulting from the interpolation constraint (4b), and to address the possible rank-deficiency of the kernel matrix Ki 11:N+1.1:+++ for the latent function at the test and training input locations. Finally, the problem is reduced to equivalent linear program with norm-ball constraint that can be analytically solved. Expressing the solution in terms of the original coordinates then leads to 88. The detailed proof can be found in Appendix B
This leads to the relaxed bound f'd (xx+1) S (IN+11) S T (IN+1). valid for all (0, oo). Due to the relaxation, the obtained upper and lower bounds are conservative with respect to the original problems (2) and B nevertheless, the optimal solutions of (2), (3) can be retrieved for suitable choice of the noise parameter a, as shown the following subsection.
3.2 Optimal solution
Our main result is formulated in the following theorem. Theorem 1. Let Assumptions 7 [and[hold. hold. Then, the solution of Problem 22 is given by
[(N+11== inf J (xx41))
oE(0,00)
Sketch of
proof: Similarly to Lemma I we first show that Problem 2 admits a fnite-dimensional representation. The latter analyzed depending on which of the constraints (2cp and (2d) are active, ie.. influence the optimal solution and have a corresponding strictly positive optimal Lagrange multiplier * x This leads to three non-trivial scenarios: In Case it holds that \ >
x = 0 and the optimal solution of (2) can be recovered by the relaxed problem for o + oc, for which the combined RKHS- constraint (4c) reduces (2c). In Case 2, A 0. A > 0 and
o² + 0 recovers the optimal solution, rendering the constraint (4c) equivalent to (2d). In Case 3, both constraints are active and the optimal noise parameter is determined by 0² v //.+>/>m.> E (0, oo), i.e. the ratio of the optimal Lagrange multipliers. The set active constraints at the optimal solution can be determined by case distinction, based on the feasibility of the primal solutions under the respective active-constraint set. Finally, shown that the optimal noise parameter a² in three cases minimizes (9) This is illustrated in Fig. Il which depicts the optimal noise parameters sup- oin

---

10a
10a
0 1.0
100
10
10-2
10:
Sup
X data
true fd (2N44)
inn
mean f (xx+1)
optimal (Thm. 1)
Figure Illustrative example for Theorem The optimal upper and lower bounds (solid black) for the (unknown) latent function ftr (dashed white) determined by the relaxed bounds (shaded) around the GP posterior mean (dotted black) for an optimal choice noise parameter duup (upper bound) and onf (lower bound). The three upper plots show the relaxed upper and lower bounds, 7" and l" for the values a = (102 100, 10-2), respectively. The two bottom colorbars indicate the respective optimal values Sup and ofe for the upper and lower bound. The plotted relaxed upper (lower) bounds equal the optimal upper (lower) bound for each test point where the color of the shaded area matches the color indicated in the colorbar for the optimal value Sup (oin.).
for which the relaxed upper and lower bound, J (I ) and f (IN++)), correspond to the optimal bounds, f(IN+1) and f(xx+1), respectively. The detailed proof can be found in Appendix C
Theorem T reduces the solution of the infiite-dimmensinnal optimization problem 2 to scalar, unconstrained optimization problem over the noise parameter σ. As such, it is amenable for efficient iterative optimization. Since running a fixed number of iterations of, e.g., gradient descent applied to Problem 99) returns a valid, improved upper bound 7" (x this allows for iterative refinement of the uncertainty envelope. The solution thereby obtained can thus be easily integrated into existing pipelines for downstream tasks, such as uncertainty quantification streaming-dee data settings or model-based reinforcement learning (Deisenroth and Rasmussen, 2011 Berkenkamp al. 2017 Kamthe and Deisenroth 20188)
3.3
Special cases
For both cases with only one active constraint, the optimal bound can be determined directly in closed form, without optimizing for the noise parameter a. In the following, we provide the respective optimal solutions, as well as easy-to-evaluate expressions for determining the active constraint set. Noteworthy, the analytic solutions recover known bounds in specific regression settings, highlighting that the proposed bound is a generalization thereof: we detail these connections Section
Case 1 -a- - x.). When the value 22 is sufficiently permissive, constraint 2d does not influence the optimal solution of (). This leads to the optimal latent function f* being chosen irrespective of the training data, while the optimal noise function w" ensures consistency with the data (2b). The optimal bound 7 x(xx+1) +1) is then given by the prior GP covariance inflated by the full available RKHS norm I recovering classical kernel interpolation bound [Fasshauer and McCourt 2015 Eq. (9.7)).
5

---

Proposition 1. Let Assumptions and hold. If
y - KIN,N+1
$ r 10
(10)
V VKN+LN (KEN
then the solution of 2 is given as
]( = lim ((N++1) KNNLIN+T 00000
(11)
The feasibility condition (10) verifies if the bound (2d) on the noise function's RKHS norm allows
for it to interpolate the points w" (x,) = - (x1)), i i= = I.....,,, N, given the data-independent,
worst-case latent function (-)- k (1IN+1) Tf
VKKIIN
Case 2 (a - 0). For infinite-dimensional hypothesis spaces, regularity constraint on the latent function the form (2)) typically required to yield finite uncertainty bounds [Scharnhorst et al.) 2023 Remark 1]. Therefore, it is possible that merely constraint (2d) h is active only in degenerate cases when the kernel matrix K
1,N+1,1::41 is singular, i.e., has rank S N. The kernel matrix
can then be expressed K [NN4IINN441 11:N+1 11 where 11:N+1 E [(++1)xr denotes the
r-dimensional map of linearly independent features at the training and test input locations. This results in the following closed-form optimal solution
(
Proposition 2. Let Assumptions 9 = P I:N (KEN,INN y. Then, if
and hold. Define P= (TIN (KEN..:N) -1 PI:N)- and
2
PΦ N+1
I Vt (KWNAN) -1
||0*10 =
1 1
y
1|
p-1
S r
(12)
the solution of 2 is given as
F(ØN-1) = lim J (xN+11== = 2 + + +1 pa y (KYMANN) + o-0
10
(13)
Since the RKHS norm of the noise function the limiting factor this case, the optimal pair of functions (f", w*) generally shows the opposite behavior in Case 1, utilizing the minimum RKHS norm of the noise w² to interpolate the data in order to achieve a maximum value of the latent function f at the point. The feasibility condition [12 verifies that the RKHS norm of the optimal latent function f satisfies the bound 2c
Case 2 = - (.)
happen in two scenarios: For finite-dimensional hypothesis spaces, i... L....,,, r, the latent function (I(N+11 (-). @ for some features (.(.). = i..............
generally does not have sufficient degrees of freedom interpolate an arbitrary data set. As such, the optimal bound f (INN41 in (13) consists of two components, the value of the least-squares estimator (*( 1 N O0,, as well as a term proportional to the maximum RKHS norm of the noise r subtracted by y (KINN.i:
||0'|] the minimum RKHS norm required to eliminate the offset between the least-squares estimator and the data. For infinitediimnssionn hy- pothesis spaces, the latent function f' can generally interpolate the offset between the optimal noise function w* and the training data; however, neglecting the RKHS- constraint (2c) on f" only leads to sensible estimates when the test point coincides with a training input location. this case, the feature vector T N+1 E (N+)))r has rank which simplifies the general result in Proposition 2
Corollary 1. Let Assumptions and hold. Suppose that K! K.NNNN is invertible and x = I E X.
Then, if
Tw
10+13 =
KYN.
$ <T7
(14)
K
(K)
(K(NN.IN)

---

the solution of 2 is given as
F(aN+1) lim F' (xN-1) yn + & Fu. a-0
(15)
In this case, the optimal solution at training input location IN+1 = E X is given by the corre- sponding measurement yi, inflated by the maximum RKHS norm I of the noise function.
Related work and discussion
In this section, we discuss the obtained bounds also in view of known results from the literature. In particular, Section 4.1 we detail known bounds that are recovered as special cases of Theorem In Sections 4.2 and 4.3 we respectively compare Theorem T with deterministic bounds, obtained for bounded noise sequences, and probabilistic bounds, for noise sequences with an assumed probability distribution. Specifically, Section 4.3 encompasses thorough numerical comparison of the bounds, including an application on safe control that shows the effectiveness the proposed bounds on downstream task.
4.1 Recovering existing bounds as particular cases
Linear regression under energy-boundee noise We first elucidate the connection between As- sumption| I on the deterministic noise function and mwergy-boundedeess of the noise sequence. As straighttorward consequence the Representer Theorem [Wahba 1990, |Schölkopf al. 200T]. for the presented results in this paper. the values of the noise function outside the training input locations are irrelevant (see Appendix A there exists noise- geisseegnnraiigg function w for the data set D satisfying Assumption [ if and only if the minimum-noo norm interpolant w of the (unknown)
noise realizations wx = [w(x1),..... wxx)]] satisfies the RKHS- bound | || 11.4. < r2 where
|| 1e
min w wEH
I 8.t. w(xx) wd (xx), i= I..,,,,, N,
wy (KEN,I:N) wx.
Therefore, instead of imposing maximum RKHS norm on wtr, one could equivalently assume bounded RKHS norm for the minimum-norm interpolant generating the data set. For the Dirac noise assumption on the
kernel (=, x²) = 6(x ), since K I.N.I:N = IN. the Bounded-RKHSSnonn noise function implies bounded energy of the noise sequence, i.e..
Σ "" (z,)² r
The assumption of bounded energy for the data set has been employed by Fogel [1979] to obtain bounds for the latent function in the setting of linear regression, i.c., kinite-dimensione hypothesis spaces. Using the notation adopted Section 3.3 the non-falsified parameter set obtained as
||0"r 10
T ||0'11
(16)
see Fogel 1979 Eq. (3)). Proposition shows that the obtained bound recovers this known result
from set-membership estimation for mnite-dimensional hypothesis spaces. In fact, for the Dirac noise kernel, the worst-case realization of the unknown parameters is given by 0 in (12). for which (16) holds with equality. Note that the optimal bound in Theorem [ does only recover the bounds by |ogeel [9799 for the linear-regression case, but, moreover, provides bounds under the additional complexity constraint | 1 1
Noise-free kernel interpolation Building upon the kernel interpolation bound by Weinberger and
Golomb [1959] (sce [Wendland] 20044 p. 192], Fasshauer and McCourt 2015 Section 9.3]), under
Assumption the following bound can be derived, cf. [Maddalena al. 2021
Proposition 1]:
[f(#N+1) (x((41)) $ /ry 11 11 V Σ/ (#)+1).
(17)

---

where f is the minimum- norm interpolant in the RKHS Hyr (see 6 and /E (# is commonly referred to the function. The relaxed bound in Lemma Lennaaaeeenr this result: for noise-free free measurements, i.., r - O, and in the limit for the noise parameter o + 0, (I7) is recovered exactly by noting that the bound in Lemma is symmetric around the estimate.
4.2 Comparison with existing deterministic bounds
Interpolation using sum-of-kernels For the Dirac noise kemnel (x' = 6(x x²), uncertainty
bounds have also been obtained by [Kanagawa al. 2025 Section 6.4] based on the minimum-now norm interpolant 9 E +k" using the sum of kernels k- ke Utilizing the fact that, for all x $ X, the GP posterior mean (5a) and covariance (5b) are equal to the interpolant g and the corresponding power function. respectively, a bound on the true data-generating function E Her++* + has been established by [Kanagawa al.) 2025] Corollary 6.8]. However, the bound does not take into account the actual value of the measurements {g(xz) Vi ) but rather the worst-case realization thereof, rendering conservative. Additionally, the bound is only valid for the data-generating process g and does not provide bounds for the latent function.
Point-wise bounded noise As mnergy-boundedness is a weaker assumption than point-wise bound- edness of the noise, Theorem I can also be applied in the setting of point-wise bounded noise, see Section 4. In this setting. Maddalena et al. 2021 Reed et al. 20255 provide closed-form, yet con- servative, bounds for the latent function under an RKHS- -oomm constraint on the latter. The bounds are improved upon by SShhrphhrsst et al. (2023), which provides optimal point-wise bounds for the latent function. As the bounded-energy and hhuntwise-boundediee
assumptions are equivalent for N 1 data points, so are the bounds by |Schannhorst et al. [2023] and Theorem [ in this case. For larger assumption, the optimal bounds by [Scharnhorst et al.) [2023] are tighter than the optimal bounds in Theorem Jobainedd under the weaker bounded-energy assumption. Still, their computation relies on solving a constrained convex program, ef. [Scharnhorst al. [2023] Eq. (6)]. whose number of optimization variables is proportional to the number of training data points N. Additionally. this optimization problem has to be solved to optimality in order to obtain valid bounds for the latent function, while optimization over the noise parameter in returns a valid upper bound for all a E (0, co).
data sets, under the seent--ws--bbudeddeeee
4.3 Comparison with existing probabilistic bounds
High-probability bounds for Gaussian- processs regression are derived in (Srinivas al. 2012 Abbasi-
Yadkori 2013 Fiedler et al., 2021 Molodchyk et al. 2025). which are generally of the form
Pr
f#(x) s 3, [x (2) 2
Compared Theorem these bounds hold with user-chosen probability p E (0, 1). use a fixed con- stant a > 0, but otherwise have the same structure and the same assumption on the latent function für in terms of known bound on its RKHS norm. However, while the proposed analysis considers energy-bounded noise, ||o Ha < 2 (Assumption 1b. these results apply to (conditionally) in-
dependent sub- nub-Gaussian noise [Srinivas et al. 2012] Abbasi- Yadkori 2013 Fiedler al. [02T]. This is a stronge requirement as it does not allow for biased or correlated noise, which can be difficult to ensure in real-world experiments. Nonetheless, both the proposed bound and existing high-prod high-probability bounds can be applied in case of independent, zero-mean and bounded noise; in the following, we numerically investigate the conservativeness of the bounds in this setting?
Numerical comparison In this experiment, the size of the uncertainty regions is compared. Using squared-exponentiaa kernel / (x. x²) = exp(-Ila - x' 22), ,, f = 1, for the latent function, as well Dirac noise kernel k:" (xx x.) 5(x - x²) the domain X' [0, 4], random latent functions
'To be precise, if the noise is sub Gaussian we can derive an energy bound 1 such that w" satisfies Assumption with the kernel (x, x²) 8(æ z') and desired probability E (0, 1). However, the converse is not true as energy-bounded noise may be correlated and biased.
"The code to reproduce the experiments is publicly available at
www..ch.hecceceee ch/ics/ ennnrydd-eeergy--o heayyrkhs--ooooe bounds and battps:///olf org/10. /00 39293999222e htwee/eehz-aaa 000785083
8

---

Area of uncertainty region
Bounded-energy (optimal)
104
Bounded eneryy (o
=
Probabilistic
100
10
10
10a
10a
Number of data points
Figure 2: Numerical comparison of area of uncertainty region for increasing number of data points N with (5%, 95%] -percentils shown in shade.
are generated with || = following zero-mean truncated Gaussian distribution with standard deviation and bounded absolute value equal to 0.01, which is R-sub-Gaussian for R = e. The corresponding noise-energy bound derived _ Nee. We compare the proposed bound (Theorem p.. which is optimal given only the information || H < r 1os the relaxed bound (Lemma 1 with a = 6, and standard 2013]. ef. (Fiedler al. 2024 Eq. (7)], which uses
-1 ,
Training data are sampled based on measurement noise
high-probabiility error bound [Abbasi-
only sub- Gausssanssit of the noise and provides a valid bound with probability = 0.99, similar (Srinivas et al. by solving convex reformulation of (2) (see Appendix A) using CVXPY [Diamond and Boyd 2016
et al., 2021]. Optimality of the numerical solution (9) is guaranteed
Agrawal et al. 2018 Figure 2 compares the area of the uncertainty region for 1, 10 randomly sampled training points, averaged over 10 runs for randomly sampled latent functions for In the low-data regime, the proposed optimal and relaxed bounds, leveraging energy- boundeddeedds of the noise, are significantly less conservative. However, multiple similar data points may provide no additional information without probabilistic information, they do not significantly improve after certain number of data points N. In contrast, the probabilistic bound leverages independence, asymptotically attaining smaller uncertainty bounds with increasing data. However, should be noted that these probabilistic bounds are only valid if indeed the noise is (conditionally) independent and aero-mean; otherwise, these shrinking confidence intervals would be mislcading.
Safe control for uncertain nonlinear systems Lastly, we demonstrate the application of the proposed bounds to the downstream task of safe control. Consider the uncertain (for simplicity scalar) nonlinear dynamical system
<( + =) fknown u(()), + f
f" (z(kk, u(k)),
(18)
with known dynamics fkuowa and unknown residual dynamics f Given the current state arkk) E IR of the system at time h E N. the goal is to find an optimal control input u(k) E that minimizes a user-defined cost function c(<((k) u(k),, subject to safety-critical (1 (k)))=(k)-- similar to control barrier func- tion [Agrawal and Sreenath 2017 Ames et al. 2019 Jagtap al. 2020]. The uncertainty in the system dynamics handled by leveraging the proposed (the probabilistic) bound to enforce robust constraint satisfaction for all functions in the uncertainty set, containing the unknown function fü (with probability p). Importantly, this makes tight uncertainty bounds desirable, since they generally lead to lower costs and larger feasible region, where safety of the control input can be guaranteed.
constraint, fknown (x:k)) u(k)) + +( (x<kk, u(k))
We compare the bounds for the following example setup: flenown (I, u) = 0.5x exp(-2* sin(10z), c(z, u) = [fknowai (x, u) ft' (z, u))² + u² kf, k above with e = v2/20. 20. For the proposed bound, the optimization problem is formulated using the relaxed bound in Eq. 8 optimizing E (0, oo) and u(ks) 1-2, 2] simultaneously; for the probabilistic bounds, o c is fixed with the same noise assumptions as in Section 4.3) see Appendix for implementation details. Additionally, we implement the proposed bound using only the nearest 10 training points to construct the uncertainty bounds. Fig- 3 shows the success rate in terms of the share of feasible problems for an increasing amount of training data on a grid of 500 test points in the domain ar(k) E [-2, repeated 20 times with random noise realizations. Due to the smaller uncertainty bounds, the proposed bound
1, f u) =

---

Success rate [%6
50
26
Bounded-energy (full data set)
Solve time [s]
10
Bounded-energy (10 nearest neighbors)
Probabilistic (full data set)
10
10
10
10a
10a
Number data points
Figure 3: Application of uncertainty bounds for safe control. Success rate (upper plot) and solve time
(lower plot) with (5%, (0%.)9%%%ecceee -pprcenntiles shown in shade.
using the full data set achieves the highest success rate, albeit at high computational cost. In contrast, using the probabilistic bounds and the subset-of-data variant of the proposed bounds leads similar success rates, with the latter exhibiting significantly lower computation times due to its independence of the number of training points. Note that utilizing the probabilistic bounds with test-poit-deeeedeen subsets of data would generally deteriorate the probability p of their joint validity for all test points, compromising the controller's safety guarantees.
4.4 Limitations
The obtained bounds suffer from common criticalities and limitations of kernel-based learning, which (a) dealing with kernel mis-specification and (b) knowing valid RKHS-norm bounds. Both issues are typically addressed empirically, (a) by hyper-parameter tuning via cross-validation or maximum- likelioood estimation ([Wahbal [990]. (Rasmussen and Williams 2006 Section 5.4], [Kavvnen et al. 2020)) and (b) by estimating the bound value from data [Csáji and Horváth 2022] Tokmak et al. [224]] While a rigorous investigation of (a) beyond the scope of this paper, we note that mis specification of & may also be compensated by an inflated RKHS- -orm bound r Regarding (b), for the latent function, this is common assumption in the literature on kernel-based uncertainty bounds; for the noise function, we discuss in Section 4. how it generalizes the common setting energy-bounder noise. Under-estimation in the RKHS-norm bounds could be detected by checking feasibility of the optimization problem. Conversely, we point out that considering conservative values r and w merely results a sublinear inflation of the computed uncertainty envelope, cf. Eq. (7p. Nevertheless, further research will be devoted to rigorously assessing the robustness of the obtained bounds with respect to possible seecsscccfiiatinnns in (a) and (b).
Conclusions
The main contribution of this paper an optimization-basse distribution-free bound for kernel-based estimates that is tight, even in the non-asymptotic, low-data regime, and that can handle correlated and biased noise sequences. The proposed bound generalizes known results from kernel interpolation in the noise-free setting and from linear regression under energy bounded noise. In the case of bounded uub-Gaussian noise, the numerical results highlight the competitiveness of the bound with existing probabilistic bounds in terms of its conservatism, and showcase its high potential for safe control as downstream task. Moreover, the experiments highlight how the deterministic nature of the proposed bound enables the rigorous certification of subset-of-data selection or mixture-of-expers strategies to handle large data sets. Future work may investigate the effectiveness of the proposed bound for further downstream tasks, such Bayesian optimization model-based reinforcement learning.
energy-bounded
10

---

Acknowledgments and Disclosure of Funding
This work was supported by the European Union's Horizon 2020 research and innovation programme, Marie Sklodowska-Cun grant agreement No. 953348, ELO-X. The authors thank the anonymous reviewers for their constructive comments. AL thanks Philipp Hennig, Motonobu Kanagawa and Manish Prajapat for helpful discussions.
References
Y. Abbasi-Yadkori. Online Learning for Linearly Parametrized Control Problems. PhD thesis, University of Alberta, 2013.
A. Agrawal and K. Sreenath. Discrete Control Barrier Functions for Safety-Critical Control of Discrete Systems with Application to Bipedal Robot Navigation. In Robotics: Science and Systems XIII. Robotics: Science and Systems Foundation, 2017. ISBN 978-0-99237477.2 doi: 2115607/RSS..017.XIII
A. Agrawal, R. Verschueren, S. Diamond, and S. Boyd. A rewriting system for convex optimization problems. Journal of Control and Decision, 5(1), 2018.
A. D. Ames, S. Coogan, M. Egerstedt, G. Notomista, K. Sreenath, and P. Tabuada. Control barrier functions: Theory and applications. In Proc. 18th European control conference (ECC), pages 3420-3434 Ieee, 2019.
A. E. Andersson, J. Gillis, G. Horn, J. B. Rawlings, and M. Diehl. CasADi: A software framework for nonlinear optimization and optimal control. Mathematical Programming Computation, 11(1), 2019. doi: 100/// 2533--188-11111
N. Aronszajn. Theory of reproducing kernels. Transactions of the American Mathemat- ical Society, 68, 1950. URL /tttps://ww ams
068-03/
S0002 19950-005143777/80002 9947 1900-19500000 19500000514377.111
G. Baggio, A. Carè, A. Scampicchio, and G. Pillonetto. Bayesian frequentist bounds for machine learning and system identification. Automatica, 146, 2022. doi: 10.1016f..utommaica.2.. automatica.2202.. 10599,
F. Berkenkamp, M. Turchetta, A. P. Schoellig, and A. Krause. Safe Model-based Reinforcement Learning with Stability Guarantees. In NIPS' 17: Proceedings of the 3 International Conference Neural Information Processing Systems, 2017. htLhhttp///rxiiii org/ /b///////// 1705. 08551
Berkenkamp, A. Krause, and A. Schoellig. Bayesian optimization with safety constraints: Safe and automatic parameter tuning in robotics. Machine Learning, 112(10), 2023. doi: 1001007/ 5109944021--0011..
A. Berlinet and C. Thomas-Agnan. Reproducing Kernel Hilbert Spaces in Probability and Statistics. Springer US, Boston, MA, 2004. ISBN 978-1-4613-4792-7 911-11-4789999999999 9419-99419-9 doi: 10.1007/ 978- 978-1-4419-9096-9,
E. Burnaev and V. Vovk. Efficiency of conformalized ridge regression. In Proceedings of The 27th Conference on Learning Theory. PMLR, 2014. URL (tLLitttp:////oceediii .mm.eeeeedennnmm.......mm.m..m.. wwl.r.pres//ee /v35/ burnaev14. html
K. Chua, Calandra, R. McAllister, and Levine. Deep Reinforcement Learning in Handful of Tri- als using Probabilistic Dynamics Models. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL httpss://proceeeeinggs http:///pprooeddnnng.......r..p.
www..ps.ccpppppp.eeeeee html
f
B. C. Csáji and B. Horváth. Nonparametric, Nonasymptotic Confidence Bands With Paley- Wiener Kernels for Sand-Limited Functions. IEEE Control Systems Letters, 6, 2022. doi: 10.1109/L.CSS. 2022.3185143.
Cucker and S. Smale. On the mathematical foundations learning. Bulletin of the American Mathematical Society, 39, 2002.

---

F. Cucker and D. X. Zhou. Learning Theory: An Approximation Theory Viewpoint. Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, 2007. doi: 10.1017/C809788511 1618796
M. Deisenroth and C. E. Rasmussen. PILCO: A model-based and data-efficient approach policy search. In Proceedings of the 28th International Conference on Machine Learning (ICML-11), 2011.
Diamond and S. Boyd. CVXPY: Python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83), 2016.
G. E. Fasshauer and M. McCourt. Kernel-Based Approximation Methods Using MATLAB, vol- ume 19 of Interdisciplinary Mathematical Sciences. World Scientific, 2015. URL https
// "Rorldscienttffc..com wtt.c/oo/.cooccc/../eecc 1tt////0.1112/9333
C. Fiedler, C. W. Scherer, and S. Trimpe. Practical and Rigorous Uncertainty Bounds for Gaussian Process Regression. Proceedings of the AAAI Conference on Artificial Intelligence, 35(8), 2021. doi: 10.1699/aaii 16912.
C. Fiedler, J. Menn, L. Kreisköther, and S. Trimpe. On Safety in Safe Bayesian Optimization. arXiv 109.12948, 2024. doi: 10.48550//rXi..240.11 12948.
E. Fogel. System identification via membership set constraints with energy constrained noise. IEEE Transactions on Automatic Control, 24(5), 1979. doi: 10.1109/AAC.999.11000 1021444
W. Gilks, Richardson, Sylvia, and Spiegelhalter, Daniel. Markov Chain Monte Carlo in Practice. Chapman and Hal//CRC, New York, 1995. ISBN 978-0-422 978-0-429-1702344 doi: 10. 10.1201/b14835
Z.-C. Guo and D.-X. Zhou, Concentration estimates for learning with unbounded sampling. Advances in Computational Mathematics, 38(1), 2013. doi: 10. 1007/s 10007/s10444000 0444-011-44000 1-9238-8.
Jagtap, G. J. Pappas, and M. Zamani. Control Barrier Functions for Unknown Nonlinear Systems using Gaussian Processes. In 2020 59th IEEE Conference on Decision and Control (CDC), 2020. doi: 10. 10100/CDD442240.0000000000
S. Kamthe and M. Deisenroth. Data-Efficient Reinforcement Learning with Probabilistic Model Predictive Control. In Proceedings of the Twenty-First International Conference Artificial Intelli- gence and Statistics. PMLR, 2018. URL RtLLitttps///oocedding mlr wwwpppeesssseeeee vv84/ het//////tt/tteeee kaakkammteee html
M. Kanagawa. P. Hennig, D. Sejdinovic, and B. Sriperumbudur. Gaussian Processes and Repro- ducing Kernels: Connections and Equivalences, 2025.
T. Karvonen, G. Wynne, F. Tronarp, C. Oates, and S. Särkkä. Maximum Likelihood Estimation and Uncertainty Quantification for Gaussian Process Approximation of Deterministic Functions. SIAM/ASA Journal Uncertainty Quantification, 8(3), 2020. doi: 00.1137/201111 3159668.
G. Kimeldorf and G. Wahba. Some results on Tchebycheffian spline functions. Journal of Mathemat- ical Analysis and Applications, 33(1), 1971. doi: 10.1016/0022-247XX77 99118844433))
M. Kuss and C. Rasmussen. Gaussian Processes in Reinforcement Learning. In Advances in Neural Information Processing Systems, volume 16. MIT Press, 2003. URL https:://ppp:pe nips
cc/ httppp/....iipppr.///./////////0 html
G. Lecué and S. Mendelson. Regularization and the small-ball method II: Complexity dependent eтror rates. Journal of Machine Learning Research, 18(146), 2017. URL http::/jjmr org/ papers/v18/16-1
html
A. Lederer, Umlauft, and Hirche. Uniform Error Bounds for Gaussian Process Regression with Application to Safe Control. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL WtRRRitttts://. htttpp::/pproeeeinngge nwwrinuun.... paarrripsscc//ppppp////////aaee
fe7 71776668778305528221166666666222 Abstratt.bbt.................... html
12

---

E. T. Maddalena, P. Scharnhorst, and C. N. Jones. Deterministic error bounds for kernel-based learning techniques under bounded noise. Automatica, 134, 2021. doi: http:f/auutomatic.2221......
O. Molodchyk, J. Teutsch, and T. Faulwasser. Towards safe Bayesian optimization with Wiener kernel regression, ArXiv.2411.02255 2025. doi: 10.48550/rXXw.2411 1.02253.
S. Müller and R. Schaback. A Newton basis for Kernel spaces. Journal of Approximation Theory, 161(2), 2009. doi: jat.0100. 10.014.
M. Pazouki and R. Schaback. Bases for kernel-based spaces. Journal of Computational and Applied Mathematics, 236(4), 2011. doi: 10. 10.10.//..cmm200) 1.05.021. 1...0.....
C. E. Rasmussen and C. K. I. Williams. Gaussian Processes for Machine Learning. Adaptive Computation and Machine Learning. MIT Press, Cambridge, 2006. ISBN 978-0-262-18253--
R. Reed, L. Laurenti, and M. Lahijanian. Error Bounds for Gaussian Process Regression Under Bounded Support Noise with Applications to Safety Certification. Proceedings of the AAAI Conference on Artificial Intelligence, 39(19), 2025. doi: 10.16099aaai.
P. Scharnhorst, E. T. Maddalena, Y. Jiang, and C. N. Jones. Robust Uncertainty Bounds in Reproduc- ing Kernel Hilbert Spaces: Convex Optimization Approach. IEEE Transactions on Automatic Control, 68(5), 2023. doi: 10. N0.10999AA.2202..2779977
B. Schölkopf and A. J. Smola. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press, Cambridge, MA, USA, 2001. ISBN 0-262-19475-9.
B. Schölkopf, R. Herbrich, and A. Smola. Generalized Representer Theorem. In Computational Learning Theory, volume 2111 Springer Berlin Heidelberg, Berlin, Heidelberg, 2001. ISBN 978-3-540-42343-0 978-3-540-4458144 doi: 00.1007/3-540-448811
S. R. Searle and A. I. Khuri. Matrix Algebra Useful for Statistics. John Wiley & Sons, 2017. ISBN 978-1-118-93516.3.
Shawe-Taylor and N. Cristianini. Kernel Methods for Pattern Analysis. Cambridge University Press, Cambridge, 2004, ISBN 978-0-521-811997-6 doi: 10. 10.1017/CB09988011 1809682.
N. Srinivas, A. Krause, S. M. Kakade, and M. W. Seeger. Information -heooreioo-Thoooetiiic Regret Bounds for Gaussian Process Optimization in the Bandit Setting. IEEE Transactions on Information Theory, 58(5), 2012. doi: 11111/0TTT211121122200
I. Steinwart and A. Christmann. Support Vector Machines. Springer Publishing Company, Incorpo- rated, 1st edition, 2008 ISBN 0-387-77241-3.
Y. Sui, V. Zhuang, J. Burdick, and Y. Yue. Stagewise Safe Bayesian Optimization with Gaussian Processes. In Proceedings of the 35th International Conference on Machine Learning. PMLR, 2018. UtL/attps:/prrroediin
mlr pwwss/vv00 sui 18a.1818.mmmmmm.
J. A. K. Suykens, T. V. Gestel, J. Brabanter, B. D. Moor, and J. Vandewalle. Least Squares Support Vector Machines. World Scientific, Singapore, 2002.
A. Tokmak, T. B. Schön, and D. Baumann. PACSBO: Probably approximately correct safe Bayesian optimization. In Symposium on Systems Theory Data and Optimization, 2024. doi: 10.48550/ arXiv.2409.01
A. Wächter and L. т. Biegler. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming, 106(1), 2006. doi: 10. 1007/ s10107-004-0559.y
G. Wahba. Spline Models for Observational Data. SIAM, 1990. ISBN 978-0-89871-24455
HE. Weinberger and M. Golomb. Optimal approximation and error bounds. On Numerical Approxi- mation, Univ of Wisconsin (RE Langer ed.), Madison, 1959.
13

---

H. Wendland. Scattered Data Approximation. Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, Cambridge, 2004. ISBN 778-0-521-84335-5 doi: 0L10077/B809788511165553
1. Ziemann and S. Tu. Learning with little mixing. In Advances in Neural Information Processing Systems, volume 35. Curran Associates, Inc., 2024, doi: 10.48550/r2xx22226..0000
14

---

Technical Appendix
The following sections contain the proof' of the mathematical claims made in the paper, as well as implementation details for the numerical examples. Specifically, Appendix(AAcolleeed ancillary results, showing that the original anfinitedimmensioaall problems yielding the upper- and lower bounds admit mnite-dimensional representation, which is the first step in computing their analytical solutions; additionally, it also presents two coordinate transformations that are useful for the following results. proenddd with those for the special cases presented in Propositions) T and Corollary [ Finally, Appendix [ provides further implementation details for the numerical example on "Safe control for uncertain nonlinear systems" in Section
Appendix provides the proof of Lemma [ Appendix C contains the proof of Theorem T together
15

---

A Finite-dimensional representation of optimization problems
In this Section we first prove that optimization problems (2 and admit finite-dimensional representation (Lemma A.] and Lemma A.2 in Appendix A. Next, in Appendix [A2 we present
Iwo coordinate transformations that will be deployed the remaining sections.
A.1 Representer Theorems
By using standard ideas from the representer theorem Kimeldorí and Wahba [1971] Schölkopf et al.
[2001] and [Scharnhorst et al. 2023 Appendix C.1]. it can be established that the maximizer of diite-dimensional.
Lemma A.1. A global maximizer of Problem 2 is given by
N+1
N
r =
Σ
kf (1x))a E Har, w/ w²() = Σ
km ((,z)) E Hys
(A.1)
1=1
=11
Furthermore, Problem with c K IIN,IN T E
is equivalent the following finite-dimensional problem
F(IN+1)
sup N+1 ER
K KI
(A.2a)
s.t.
K = KINNLLNNII -ooo---7- -13 S0
(A.2b)
(T
(A.2c)
1
0z ((KENNN) - -1?) s 0.
(A.2d)
Proof. Let f21,..., be the set of training input locations and X+ - (IN+1). the same set augmented with the test point. We denote by Hyr (s Hur ff span(k: (,,0)), E X4)) the span of kernel functions evaluated at the training and test input locations, well by Hy its orthogonal complement, i.e., Hy { Hyr (f1, >
for all fll H. Hence, any function f E 74s can be written f = fll f where fll Hll and f Hy. Note that the cost of the optimization problem is f(IN+1) (f, (f,k(EN+1, ))H which is insensitive the orthog- onal part f Regarding the constraints, note that all functions f E Hiy do not affect the equality constraint 2bb while tightening the incquality constraints (2c): hence, it is optimal to set ft 0. By the same arguments, it is optimal to set w- = O. where the orthogonal complement is defined with respect to the finite-dimensional subspace H!! = (w E HAw us E span (A: (., xxx), a; E X)), which excludes k. (." (=##N+1) as the cost is insensitive to w(IN+1). the value of the noise function at the test point. Hence, it follows that for all functions f E Hg/ and w E Hge, the respective orthogo- nal parts f H4 and w E Hys can be set to zero without affecting feasibility optimality of the candidate function.
Next, we show that the supremum is actually attained, i.e., that the optimizers f and "n elements of the respective finite-dimensional subspaces H!ll and H!l First, we note that the norm constraints (2ch and (2d) define closed and bounded sets in the metric spaces Hys and Ha",, respectively. By the Cauchy-Schwarte inequality, the norm constraints (2c) and (2d) imply bounds on the pointwise evaluation of f and w: 1f(x))) = (f, k (I:, "rn,,, I [|Kd (x,,,, (22,,))l,, Ilfll ScyT,, where cj = supzex Vkl (x, x). Similarly, it holds that (w((x:)) = (w, k" (ma, )) H2n S ||A"(<;; Il || S T.r where cu = supxex / (I=(x, Note that Cw. Cs interpolation constraint (bb), this defines closed and bounded sets
holds by Assumption Jointly with the data
D. = =1(((2)), w(;))) f Hill fgrr, Hk..., f(x)) + w(x:)) y4. fxx)) efT (w(xa)) cwT
in R for all i 1,.., N. As the evaluation functionals Bf, f(xx) kl,k' / (zi, )) and EW, (w) w(z,) (f, n (z,, HEw corresponding to the RKHSs Hy/ and respectivll.
16

---

linear and continuous, the pre-image of D,, - (f(z;), w(z;)) E Dih. is closed in Ml We for all i == i......, N. Furthermore, the intersection of pre(D;), 1, ..... N and the bounded norm constraints (2c) and 2d is closed and also bounded in H x Hg.... i.e, the mnite-dimensional, by the Borel theorem, the feasible set is compact; the value of the continuous objective [Ix++1)
feasible set of Problem (2) is closed and bounded. Since H and H.
(f. k (xN+1:))) is thus attained by the Weierstrass extreme value theorem.
The saite-dimensional formulation (A.3) follows directly from inserting the mnite-dimensional representations of f H and w² Hy.. 22 and defining et 1iN,1..'"
Similarly, we now prove that the relaxed infinite diminie-dimensionall problem admits a liite-dimensional representation.
Lemma A.2. A global maximizer of Problem 4 is given by A.1 and the resulting fintte-iimenioonal problem can be written as
T (xN+1)= sup V-1
K K
(A.3a)
e" CRER""
s.t.
KL KIN.NN + = v,
(A.3b)
r2
|| Kg KINILINN
+ |||0" 11o0
(A.3c)
o²
Proof. Analogous to Lemma A.1 it holds that setting f = 0 retains optimality of any candidate function ʃ E Hss with f = fll f Similarly for the noise, it holds that w- = 0. Attainment of the supremum is also established along the lines of Lemma A.T] noting that the of norm- constraints
4c) defines a closed and bounded set in H x H Finally, the fimite-dimensional optimization problem follows from replacing w with their finite- mnite-dimensionall expressions (A.I)
A.2 Coordinate transformations
We now present two transformations that will allow us to simplify the finite-dimensional represen- tations (A.2) and (A.3). The first one will be used to deal with the possible rank-deficiency of the kernel matrix, the second one, to decompose the hypothesis space into orthogonal features. A subset of the corresponding weights will be fully determined by the training data, while the remaining ones will be adversarially chosen to obtain the worst-case value of the latent function at the test point. We point the interested reader to Müller and Schaback [2009] Pazouki and Schaback [011 for details on similar basis transformations for kernel spaces.
Eliminating the null space of the kernel matrix
For degenerate kernel functions, i.e., finite-dimensional hypothesis spaces, as well as in the case when the test point coincides with a training data point, the kernel matrix K/ K with the latent function f can be singular. To handle the rank-deficiency, let us denote the rank of the matrix K- 1:N+1,1:441 by r, which satisfies N + 1 by definition. To eliminate redundant variables, we employ a singular value decomposition (SVD) of K!
associated
K1NN+111:+11
Kf.N.EN KL
K KN+IN+11
KJ EN+LEN++
VSV
(A.4)
KKTLEN
K
V11
V12
S,
0
VT
V
(A.5)
VeL
Vn
0
Vi2
V22
Thereby we have partitioned the rows of the orthonormal matrix V, with VVT I, according to the separation of Kf K1,N41,1::41 into evaluations the training points and the test point. Note that
if KJ Kf 11N41,4441 has full rank, i.e., N + 1, then the diagonal and positive-definte matrix S..
17

---

containing the non-zero singular values of K 11NN+11:N+1+ is equal to the matrix S containing all singular values, S = S,; and the the matrices V12, V22 are void in this case. The first r vectors in V form a basis for the image of KG +1N+11N++1 A coordinate transformation
E1
21
a
f
V1 V21
V12
(A.6)
62
V22
U2
V11
reveals that [ af
S, Hence, neither the optimal cost nor the constraints
V21
of (A.1) and
A.3
depend on 12, implying that there exists an optimal solution which satisfies #22
To simplify notation, we denote by
I:N+1 = 4 xx++1
11:N
V11 V21
5t/2
(A.7)
the feature matrix associated with the kernel matrix
K KEN+1,N441 = PI.N 1:N+1
(A.8)
Defining as 0 = S./200 E IR' the corresponding weight vector, it holds that
KIN+LLLN110 +I.N+10.
(A.9)
Eliminating the subspace determined by training data
Interpolation of the training data by the latent function and noise process uniquely determines the components of the optimal solution in N-dimensional subspace, while the remaining orthogonal components are not affected by this constraint. We find this subspace by applying QR decomposition
T
Qu Q21
Q12
R
I:N =
(A.10)
(OR
Q22
0
+Q
where Q (N++)) is an orthonormal matrix, R E IR NxN is upper-triangular, and
o² KENIN = a (o
(A.11)
the (upper-triangulary Cholesky decomposition of the noise covariance matrix or, equivalently,
(o (22KTN)'
(A.12)
the standard (lower-triangular) Cholesky decomposition of the inverse noise covariance matrix. We use the orthogonal matrix Q from the QR decomposition to define a coordinate transformation
Qu Q21
Q
51 82
(A.13)
Ra (aRTINN.LN)
22
Cm
with 61 E N 82 E R", which allows compute the components of the solution determined by the training data. For clarity, we emphasize that the partitioning of the matrices Eq. (A.13) on the left- and right-hand side is different: the first line on the left-hand side contains N rows, the first line on the right-hand side, r rows.
18

---

B Proof of Lemma I
Starting from the finite-dimensional formulation of the relaxed problem (4 given (A.3), we first apply the two coordinate transformations presented in Appendix A.2 (Appendix B.... This allows us obtain a simplified problem formulation linear program with a single norm-ball constraint that can be solved directly (Appendix B.2). Finally, we also present the result for the lower bound (Appendix [33).
B.1 Preliminary coordinate transformation
Using the SVD of the kernel matrix A.5 as well as the coordinate transformation AA.13 the data equation (A.3b) reads
P1.N c
IN
O
0
PIN
BINNINN
Cw
QI Q12
Q
IN
0
R
Q 22
0
(oRY.N.I:N)-
Cw
A.13
R 81.
(B.1)
This leads to 01 = RR y being fully determined by the data, leaving only d2 E IR" to be optimized. The RKHS norm constraint (A.3c) is reformulated as
(a')T K K + (o"K"oooN A.8
A.S.
[N
(N
(o
Cw
A.13
|6 l12 + 11021
(B.2)
where we have used that Q is orthogonal, i.e., ||Q=11 = |1:1 for all x E R Finally, in the new coordinates, the cost expressed as
K 1
N++1 N N+ (441QQ11110 Q1202).
(B.3)
Problem A.3 is thus equivalently reformulated follows:
(#N+1)=
sup 6.ER"
Φx++ Q1202 + + 0110
(B.4a)
r2
s.1. |621|3 < r +
|10
(B.4b)
B.2 Analytical solution
With its linear cost and norm-ball constraint, problem (B.4) has the unique optimal solution
re
5
N+1
r2
1101
(B.5)
11Q N+
o2
and associated optimal cost
/ +
T2 o² - 1111-11
(xN+1) = QI.0 + 10
(B.6)
To obtain the formulation in tion A.10)) :
we use the following relations inferred from the QR decomposi-
Q12 Qu
(B.7a)
Qn = + R-1
(B.7b)
R R R TQQQRR
QR L TT + (ORRN TOR
19

---

K INNIN +
(B.7c)
We can now simplify the terms in the optimal cost (.6). First, it holds that
@ 1N+1Q1101 Sh.0
(pN+1 (NN+IIIN)ER PRTRO y,
B.7 KNILN (KEN, + + k y,
Sd (IN+1).
Then, we have
N 1 Q12012 N+1
B
PN+1 - (11 P
B.
1N+1 2 NN11 - (4N+1 R ( -1
B 7c
K W+IN++ K W41,N (
(KIN.IN a² KKNNIN)
K KIN
56
(xN+1).
Lastly, we obtain
|
y R R RR-RRTA Ty
K (KE.N.LA + o² K )
To summarize, this shows that the optimal cost of (4) is given by
2
(8((N+1) + Vr +
r3
llst
11
W (xN+1).
a2
B.3 Optimal relaxed solution for the lower bound
For the lower bound, the same derivations apply with a minor change. Flipping the sign in the cost leads leads to a flipped sign in the optimal solution for the free variables 62, i... 5t.nf 82 This results in the optimal cost for the lower bound
T2 +
f (IN+1) (C(NN41) V 17
l1 10 li 4x- V (xN+1).
o²
Due to the symmetry of the relaxed bounds around f6 ( 1), the following corollary is immediate. Corollary 2. Let Assumptions 7 Land2ba be satisfied. Then, for all a E (0, oo), it holds that
T2 (f"((N+1)) -f(( S vr
- 11g 11 12 Pi (xN+1))
σ²
20

---

C Proof of Theorem 1
Taking its finite-dimensional formulation (A.2). we eliminate the noise coefficients as function of the latent function coefficients, ct y 2 1.N0, and deploy (A.7) obtain the following reformulation:
In the following, derive an analytic solution to Problem 2
[(EN+1)
sup BER"
DN+10
(C.
s.t.
T
- r 50
(C.
( - 1I.NO) (KTT,,I))
11-1111101 (U- r 5.
(C.1c)
We will analyze the solution of Problem C.I for different active sets. Here, the term "active set" refers to a subset of the RKHS-norm constraints (C.I and (C.Tc) that are strictly active, i.e., influence the optimal primal solution of the problem. For strictly active constraints (C.Tb) and (C.lc there exist respective Lagrangian multipliers, X and A", that are strictly positive. We investigate the following combinations:
Case only
C. lb
strictly active (X > 0, A" = 0):
Case 2 only C.Ic
strictly active (\ 0, A 0),
Case 3 both C.1b
and CC.lc) are strictly active (A > 0, Am 0).
Case both
c.1l and (C.Tc) are not strictly active (A = -- 0),
Based on the solutions for fixed active sets the optimal solution can then be found by case distinc- tion. We discuss each case separately, obtaining the corresponding analytical solution, presenting the feasibility check and elucidating the connection with the solution of the relaxed problem in Appendices Co to C.4, note that Appendices C.2 and C.3 provide the proofs for Propositions [ [nd 2 and Corollary [ We then show how to practically check which set is active, and obtaín the desired claim (9) Appendix C.5
We conclude the section by presenting the result for the lower bound
(Appendix C.6).
C.1 Case 1: Noise constraint inactive
We now consider the case which only (C.Ib) is active, proving Proposition
Optimal solution
Problem C.1 with omitted constraint (C.lc is given by
[1( sup HER"
+ 1N+10
(C.2a)
s.t. 8 0 0.
(C.2b)
The solution of the above optimization problem is given which results in the optimal cost given in namely
+ N+1 rj,
g
(C.3)
c N
[I(44))
T N 1 N+1TT
PN
V K
1
Feasibility check noise coefficients
The optimizer 1+11 is a feasible solution of (C.l if the corresponding optimal
11 N+1
A. y
KS
KINNNH1
I
N N+1
VK
'The presented analysis of Cases 1-3 considers slightly more permissive setting, which allows some of the Lagrange multipliers to be zero, i.e., the corresponding constraint to be inactive or weakly active. Thus, in some scenarios multiple cases might be applicable (see Appendix C.5 yet. this does not affect our analysis as the cover all possible scenarios.
21

---

satisfy the neglected constraint Cc.c. i.e., if
T,
y KL
LNN++1
V
K
S
w0
(KENaa))
as given in (33
Connection to relaxed solution holds that
For a - co, for the relaxed solution J (xNN11 in Appendix B it
lim fd = lim K
K441NN
(KENNIN + o2 KYNNAN)"
0-200
0,
r2 + a²
lim Bg = lim
13
-
-11g Pi 120
000
=[,,
lim (x
lim K 0
N+INN+1
K
KHLIN (KiN,N + o² o KK K(NN,N41
KK N+1N++1
Thus, the relaxed solution converges to the optimal solution for - oc, i.e.
lim J (xN+1) = lim ftr + B0 Vo oz
0 00000
a a
=I((N41).
C.2 Case 2: Function constraint inactive
We proceed by considering the case in which only (b. is active, proving the result given in Propo-
sition? 2
Optimal solution
Problem
C.I1 under this active set given as
F2(2N+1)= sup
& N
(C.4a)
PER"
s.t. (y PI.NO) (KW
(KNN (AAN
1I.10) r S
(C.4b)
This optimization problem only has finite optimal cost if the span of Φ 1+1 R is contained in the span of T. E RrxN i.e., if span(#] (T)+)) S span( Otherwise, there would exist a direction d1 s T such that P1:vd_ = 0: the optimal solution to (C.4 would then be unbounded and thus would not satisfy the constraint (C.1b) of the original problem. Hence, in the following, we focus on the case where span($ x41) C span (.x)
spann t T N+1) S span(B I. we can write T N44 as a linear combination of the column vectors of I:v, i.c., 2 N+1 =T TT. where E Nx1, Since the feature vectors in
$1.N NN+1
IN x
PEN+1
=
+ 11N
(C.5)
linearly independent, & has full column rank. As & thus has full row rank, À can be determined as À II.v
{b I.N -
To reformulate constraint C.4b) as norm-ball constraint, we employ QR decomposition. Recalling the upper-triangular Cholesky factor Ri.N.I:N (RY Ki KINNINN of the noise covariance
22

---

matrix from A.11 we factor the matrix
Qu
Q12
R
(Bi,,,1-N)
PIN
(C.6)
Q21
Q22
0
+
to obtain an orthonormal matrix Q E IRNNN, with @ I, and an upper-triangular matrix
R E Rexr. The QR factorization implies the following relations required for the proof:
QQ =
(C.7a)
Q11]
Q21 =(Hi:N,1:N -
PINN PINN
(C.7b)
R Rt = Rt QEQQQIN =VIN PI.N (KY.N.1
PINN,
(C.7c)
Q12
[Q1]
[212
02 =
[Q Qh1-
(C.7d)
22
Q21
This allows to write the constraint (C.4b)
r
|| (RT.N,1
) (y $
1 11
( Tty-ty-
R
0
(U(RENNLN) R 0
| Qi (R (RI.N.I:N) - R0
[1 1112 -111 TI1 (RY
R 2 i:N (K (.N.IN.)) 1 Re
(1 (.N.I.N)
m112 T (K INN.NN) 11y1
|2 y (KY.N,I:N .M g.
where we used the following definitions in the last line:
it T (KYNNINN) " 120,
(C.8)
= (KNNN y,
(C.9)
M = di.N @T.. (.NN
$ TT..
(C.10)
Using the coordinate transformation and + N+1
$ A, the cost C.4a) is rewritten as
A 1 = P Rt it T T
21
= - A RINN 21,
(C.11)
leading to the formulation of C.4 in the transformed coordinates:
Fz(xN+1) sup ER"
X A T 1I.NR
(C.12a)
s.t.
| < (r - T (KENNIN - M)
(C.12b)
Noting that, by Assumption I. the right-hand side of the constraint (C.12) non-negative, the optimal solution of the above problem is given
R
TT
2
I:N
r2 DJ (KY.N.NNN M)
(C.13)
R
T
1.N
23

---

leading to the corresponding optimal cost 13
T((eN+))= T "7 (KY.NIN M) & A Mÿ.
(C.14)
CBC
C.10
| -opalll-iii 1118 -N (KYNMNN)
+ |001| + IN+10" (C.15)
where C.15 follows by utilizing that & .l.N = =$ NN as well as by defining the weighting matrix
P - ( (KGT.N,I:)) $1IN)
and the least-squares estimator for the unknown parameters
P iN (KENNNN))
y-
Feasibility check In the original coordinates, the optimal solution is given
g+ R T i. (K (KINNNNN)
2-
KT INN.IN
-M)
① (KN.NNNNN PIN)) D
D
VA
PΦ
0
T - vT (KEN,IN)
+ 11001
(C.16)
Ph
N+1
the point 0r.2 is feasible for the original problem
C.II if satisfies the neglected constraint (C.lb)
ie., if 10+.213 s 17. retrieving (12
Connection to relaxed solution The quantities in the optimal cost (C.14) can be expressed as limiting values related to the relaxed solution for a - O. For the matrix M in (C.00) it holds that
M PINN (LIN (KEN. (1:N) TT.N
-
lim PI.N (o² PIN (IINN) o-
PINN
lim 21NN (4,-21. PIN ((o2 KENINN) PIND I.N)
(INN) DIN
o
lim o 2²
TIINNTTN T.N (ooK KENNIN) + DIN) MI.NIIN
With A T 1N+1, this results in
1
lim A MM
@N+1 - IN+1 (lo2 (oPKKNINN)) + QIN PIN
0-00
/²
lim
K
Kcf
KL KULLNN
+ +KIN, K(NNNN
lim
Eí (#N+1).
(C.17)
The offset A Mÿ in C.14 is equivalent to the offset fb' (2N+11 in the optimal cost C. for the relaxed problem:
X Mÿ lim Φ2
UNNIIOTN TN (O²KKY + DINNDT.N) DINN (KHNN,
lim & T.N 0-+0
(l02 ((oRKEN.LNN) + PINN
(DI:N PINN + o²
+ KK (o (.N.NNNN))
lim Kf 0
+ Kf KENINN)
N4111:

---

lim Po (xN+1) o 000
(C.18)
For the last term, 1 - (K [KE,NN M) iJ, we have that
r 8. (KI.NIINN-N) M) y
lim o² r + r
(KENAN- - -M)
o
r
lim d² の
[ +
~ (KYNIIN-A1)
r²
2
lim o²
r2 +
y (W-
0
r²
(C.19)
where we have introduced the abbreviation W = 0² K N:N for notational simplicity; similarly, we abbreviate F K- i.N, Recalling that M = - F(W + F) and by using [Searle and
Khuri 2017 Exercise 16.(d), Chapter 5], the data-dependent term in the above expression can be simplined follows:
W-1-W- W-1 F (W + +F) F) W-1
=W-1 W-- W FW-1 (W (W-1 W--WW-FFWW- --
=W-1 - (W-1 - FW-
-W- + w 10--1FF----p = (W + +
To summarize, it holds that r 87 (KEN.INN - M) lim o² 22 o
r TJ (KENEN -M
lim Ø² 0
[2
1
T K (KENNIN' + (o (HN,N)))))) y)
r2
lim σ²
r
w
11 10 Nat
and the total bound for Case 2 is given as
[2(#N+1) = -ATAA r - TJT (KY.NINN - M) x Mi
r2
V
lim o 0²
Et (ON+1))
lim o² o-0
17+
l1 Hlys +x-
+ lim f o
o²
r2
lim a-0
[3
||
+ Sth
Hes I00
lim F (IN+1). o-2
Proof of Corollary
We now prove Corollary [ which simplifies the general result of Proposition under the assumptions that the kernel matrix K Ki,N i:N,1:N is invertible and the test point is equal to the k-th training point, i.c., NN+I = Tk, for some A E (1,...,NN In this case, the k-th and (N + 1)-th row of the kernel matrix Kf K 1i are identical, In terms of the singular value decomposition, by (.55) this implies that
Kf k. 1:N = cg PI.N & I.N = 4 N = KSLLEN
ie.. the relation 2 T4 D A holds for = ex. with Gg being the k-th unit vector. Since P1 E x has rank r = N, it is invertible. This allows to simplify the expression for the optimal cost using that Mÿ y. with M and defined in Eqs. (C.) and C.10):
F2(x1) = Vei Mex T +eTv
25

---

ck PIN (N II +
Vez KEN.LNeT tkgy
KW + Uy:
which is the optimal cost as given in (15). By inserting the simplified expressions into (C.16). the optimal / becomes
VT
gr = (1T.N (1I..N(AEM....) (AN.IN
- PI.N
8 Ø- Ex
e MEx
Tw
4 I:N
y +KKKN
KK
Recalling the low-rank factorization of Kf neglected constraint (C.Ib) reduces to
A.7
the feasibility condition based on
Tw | + KIN&
S rr
VKE. Kik (KEN
presented in (14).
Remark. Corollary has been derived as particular case of Proposition which provides the analytic solution for the case o - 0 occurring when the kernel matrix is rank-deficient. From this perspective, the scenario in which the test-input belongs the training data-set is one of the particular situations leading to drop in the rank of the kernel matrix. However, the proof of C could be alternatively carried out following the steps of one of Proposition
C.3
Case 3: Both constraints active
Next, we consider the case when both constraints (C.Ib) and C.Icc are active.
Optimal solution We first show that strong duality holds for both the relaxed problem (A.3 as well as the original problem (C.T). Afterwards, we establish that there exists a value a E (0, oo),
such that the primal optimizer of the relaxed problem is primal optimizer for the original problem.
For the original problem (C.T). we show that a strictly feasible solution can be constructed using the true latent function and noise process. Let ftr,int Has be the minimum-ma normmmmmm-ommmm interpolant of the latent function at the test and training input locations, i.e.,
ptr,int
arg min fEH,r
||
(C.20a)
s.L.
= ((x=)=(((x;)) i=
(C.20b)
Similarly, let toti, E Hiw be the minimum-norm interpolant of the noise-generating process at the training input locations (excluding the test point).
w triint
arg min
|| 1
(C.21a)
WE Hew
s.t.
w(xx)) n (x;). i I,..,,N
(C.21b)
The representer theorem [Kimeldorf and Wahba 1971] establishes that the solutions the above optimization problems is dimensiimensioal and given by
N-1
N
itr,int (-)
Σ
2. w tr. (.)
k (, (.,r%) (,a:))a witr
26

---

A.33 if and only By design, the sum of both functions interpolates the training data, i.e., (xr, + w (ott:)n((;;) = y: for i ...
Additionally, by Assumption [ it holds that frr,int and u satisfy their corresponding RKHS-norm bound, i.e., || Il S 11 Hn < <Ty and | in 1l Hem I ||=*1 1124 <
Thus, the corresponding coefficient vector
ger Sr g1/2 u S//² [VT V122 ffrr constitutes strictly feasible solution of the finite- dimensional problem formulation (C.I). This implies that Slater's condition is satisfied for the convex program (C.T). which implies that strong duality holds. Since every strictly feasible solution for the original problem (C.I) is also strictly feasible for the relaxed problem (B.4) similarly, Slater's condition and strong duality hold for the relaxed problem.
Due to strong duality, the point 6* is the unique minimizer of the relaxed problem if the primal-dual pair (0 x) satisfies the KKT conditions
V (0 : 2x. = 0,
(C.22a)
(1000013 rt+)
r² (Iv 4 PI.N0r Ri
1 m) S 0,
(C.22b)
2 (10 - r3) + o² (Il - 11.00'111
1
(K (KP
r = 0,
(C.22c)
X 2 0,
(C.22d)
with the corresponding Lagrangian
Lo (g) 2b N+++0 bo (10113 r3 +
1
(1y 1I.N0 N
I'2
σ2
= 2 Xo (100 13))
Ag /2
(Ilv 2 1I.N0 (K
12
Similarly, due strong duality, the point 0+ is the unique minimizer if the original problem (C.1) if and only the primal-dual pair (0*, Xj. Axe)) satisfies the KKT conditions
VoL(B* Xj. X =
100 11 - r3 < 0
l1y
r < 0
A2 11101113
17)) 0
d (IV- 1 (KT
1
X². 2 2
with corresponding Lagrangian
[(O, As, Aw) 4 N - Ay - - >mn (1v- IN 122
Let (6+.3 3.3 x) be the optimal primal-dual solution satisfying the KKT conditions of the original problem C.T under the imposed active set. Since the constraints (C.16) and (C.Tc) are active, it
holds that A X A > O. Now, let (a+)² x7 Then, 27 ) and the primal-dual pair x
(0+., x) satisfy the KKT conditions CC22) of the relaxed problem:
1. Since (0 )/.3)= VoC(Or. 17 x²3) = 0, the stationarity condition is fulfilled.
2. As both constraints (b. and (C.lc) are active,
||00.31 2 17- = [ly L1 +. 31 11 (KY
12 = O,
i.e., primal feasibility and complementarity slackness are fulfilled.
3. The optimal multiplier X;" = X3 0 for the relaxed problem is positive.
Hence, due to strong duality since both constraints (C.1b) and C..cc are active, (0-.3, 2x33 is the
optimal primal-dual solution for the relaxed problem A.3 with σ = a² = /x33 A//0/200 /x and only if (0..3 Ai
+.3 3) is the optimal primal-dual solution for the original problem (C.I
27

---

Feasibility check The solution is feasible by definition.
Connection to relaxed solution As shown above, the optimal can be recovered by the of the relaxed problem for a specific choice of noise parameter o = a", i.e.,
F2(IN+1)= = (ØN+1).
(C.23)
C.4
Case 4: Both constraints inactive
Last, investigate the case when both constraints (C.1b) and (C.1c inactive.
Optimal solution The optimal solution to the unconstrained linear program given by case distinction:
Fa(xN+1) = sup OER"
2N+10
(C.24)
[0,
if + N+1
00,
if T N #
Feasibility check For @N+1 # 0, the optimal solution is unbounded, it is infeasible for the original problem (C.I). whose feasible set compact, in particular due to constraint (C.Ib). Hence, this case never corresponds to the optimal solution.
If o N+11 any H+ IR" optimal. Thus, any feasible solution satisfying constraints (C.lb) and CC.cc is also optimal.
Connection relaxed solution If f O, the solution of the relaxed problem (A.3) given by F (IN+1)= i.c., it recovers the solution of the original problem (C.24) for any a E (0, co).
C.5 Finding the correct active set
Let f denote the primal solution corresponding to Case i, with = 1,... 4. The active set for the optimal solution given by the one for which the corresponding primal solution 0 is feasible for the original problem and leads to the maximum cost among all feasible optimizers 0* for a specific active set, i.e.,
7(EN+1)=
(C.25a)
#E(1,2,3,4)
s.t. ||0 S r
(C.25b)
lly - 1I "1 ( I T2
(C.25c)
The solution the above problem be obtained by case distinction. The optimal cost for a subset of active constraints lower-bounds the optimal cost for a superset, i.e., @ @N+10+A xx++0* 2 00+3 for j E (1,2). Thus, if (+.4 is feasible, will be optimal. Otherwise, if either 0=.1 or g+.2 feasible, will be optimal. neither the other cases is feasible, 0 is the optimal solution.
Now, we compare the optimal cost both d=11 and 8-22 are feasible. If 0+11 a feasible solution of (C.T) then it holds that the neglected constraint (C.1ch does not change the optimal solution of (C.I). Similarly, ge.l is a feasible solution of (C.I). then it holds that the neglected constraint (C.1b) does not change the optimal solution of (C.I Combining both facts, it holds that
T NN+1 0
T 10= = 0
iee, the optimal cost in Case and Case 2 is equal, _, (xN+1)) = (
(xN+1). Finally, we note that in 10410115,1 E (1, (1,2,3), i.e., the optimal cost in
Case it holds that x + @N410 0 all four cases is equal. Therefore, it does not need to be considered explicitly.
28

---

To summarize, the optimal cost is determined as follows:
KNN+IN-1-
in Cases 1 and 4,
-1
[(N+1))
4N+10#
||0 N+ 14-1lp-11 Th y (KENINN)
y + 110
in Cases 2 and 4, in Cases 3 and 4.
(IN++)) +
+ [
r2 (a+)²
1195 ll wo V D/g (1ON+1))
J (IN+1),
if
K (KN+L1N44 (KENNN)))
rr
r
2
1i I (IN+I),
if
0 + |P
Pb P
2 - y
K (KEN.IN)
1 +
10-1
S rrg.
2
(nfog(0,.c)) I (IN+1), otherwise.
Finally, we show that the analytical solutions all cases can be reduced single expression:
1. Let Case 1 be feasible, ie.. F(xN+1) F (xN+1) lim F (IN+1). Since (1)N41) fz(#x=+), it holds that lim, f (IN+1) S (0, I (IN+1). How-
ever, for the infirmum it also holds that inf _ (xN+1) S lim, f (IN+1). There- fore, holds that f(xN+1)= limo- F (xN+1) inf c00.00)))) f (IN+1).
2. Let Case 2 be feasible, i.e., [(NN+1) = [2(NN+1)= = limo J (IN+1). Analogously as above, since (2(4N+1) - ( and (00,) F (IN+1) I limo f (IN+1), holds that f(#N+1) = lim, 7 (IN+1) = inf in0,0() 7 (IN+1).
3. In Case 3, since it holds that (x(NN+1) T (xN+1) for a specific value of a²
(0, oo), this implies that (0.c) I (IN+1) S (z(NN+1). However, since any feasible solution 0 E R. of the original problem (C.I) is also feasible for the relaxed problem (.3) for any a (0, oo), the cost of the original problem upper-bounded by the cost of the relaxed problem, i.c., also holds that (2(NN+1) & infoe(0.co) F (IN+1). Combining both inequalities, it thus follows that (z(2N+1) inf inf F (IN+1).
Therefore, have shown that
F(xN+1) = inf F (#N+1); oE(0.00)
as claimed in 9
C.6 Lower bound
The lower bound corresponding to Theorem [ is obtained by the same steps as the upper bound, replacing "sup" with "inf". In Cases and 2, this leads a flipedd sign the solutions of the free components in Eqs. (C.3) and (C.13), affecting the feasibility checks. Overall, the optimal lower bound is also obtained by case distinction:
V -K WKNINNII
in Cases 1 and 4,
[(xN+1)= = IN+10" - |P T
P-1 r - yT
Kw KEN.INN
y ||0u13
in Cases 2 and 4,
N+1
(xN+1) - 1 +
12
11 Ilo
1./ (IN+1),
in Cases 3 and 4.
limg ff (IN41),
if
y + K
K. K VKKELLNN
S I w
(KY
2 < r7.
lim f" (IN+1),
if
@r 1P N -- V
P
12 -yT (KYN
y + ||0 11
supbe(0,cc) l (xN+1),
otherwise.
29

---

Analogous to Appendix C.5 by replacing "inf"" with "sup" and flipping the corresponding incqualities, the optimal solution is shown be given
fØN+11)
sup f (IN+1).
(C.26)
oE(0,c0)
Note that this bound is not symmetric, as the supremum and infimum can be attained for different values of the noise parameter o.
30

---

D Numerical example on safe control for uncertain nonlinear systems: Implementation details
In the following. we describe the setup of the optimization problem solved in the nu- merical example "Safe control for uncertain nonlinear systems" in Section 4.3 Inserting the system dynamics (18) into the safety constraint s=kk + 1) 2 (1 (k), the condition flanww (x((k, u(k)) + (k)),, u(k) 2 (1-7) (k)( can be enforced robustly by utilizing the lower uncertainty bound (z, u) - Po B (z, S (z, u), leading to the tightened constraint
(1 (1-r)z(k)) < kkowwn (z)), kb) (z(k), ukk) 3o v Vo (x((), u(k)).
Minimization of the user-defined cost ckx((k), u()) subject to the above constraint can be achieved by solving the following optimization problem:
min No
c uo) + wi
s.t.
Tp z(k),
3 fknowa (Io, up) + f (Io, un),
2 (1 7)00 + Bo v (2o, un) 8,
$20 0,
Umax 2 Umin.
Therein, the added slack variable 8 allows the optimizer to converge even in case the decrease condition is impossible to satisfy given the bounds Umin, Mmnx the control input. A large linear penalty w > 0 thereby incentivizes 8 = 0, i.e., constraint satisfaction; a solution is classified as feasible if the optimal slack value s* satisfies s* - 10-6 The optimization problems are implemented in CasADi [ndersson et al.) 2019 and solved using the interior-point optimizer IPOPT (Wächter Intel 19-7940X CPU. Table provides all parameters and expressions used
and Biegler 2006
For the implementation.
Parameter
Value
planown x, u)
0.5x + -1 (knoonn (x, u) + (x, x) +u² u²
dx, u) Umin
Umax
?
0.95
3
10a
Table 1: Parameters and expressions for the CBF example
Additional implementation details can be found in the published source code https:// gitlab. ethz. http:://hccccocoddeeeeeeeeeeeeee wtwp://ounddddeerg-----rr---eeee resis-rrssbbooooe bounds and at httpp:://do: org 10. 3929 ethz c- 000785083
31

---

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: Yes, the abstract claims tight error bounds for norm-bounded noise. The optimal error bound derived in Theorem | in the setting of disturbances with bounded RKHS norm.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: In Section 4.4 the work discusses limitations in terms of dealing with kernel mis-specification, as well as regarding the estimation the bound on the RKHS norm of the unknown function and noise.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The complete set of assumptions (Assumption 1 and 2) is stated. The paper provides sketch of the proof and the full technical proof is contained in the appendix.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: For the numerical comparison, all relevant constants stated to compute the bounds. In addition, code details can be checked in the published code at https //gitlab. ethz. http:///c//oondeeeeeeee -nouuy--k-s---uudddd and htttps://doi. org/ 20..999///0
3tt339999//t--eee ethz - 000785083
5. Open access to data and code
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?
Question:
Answer: [Yes]
Justification: The full code to reproduce the experiments and generated figures is pub- lished online at lhttps://gittee at lhttps://dot http:////oooooo/...eeeo. w9t.:/t22///eeeeeeeeeee -ttp://ethhc-----0 C007855083 It contains README file that
ethz wwticcsbounnded energy-reeeeee wary--hss---. rrondbbunddsss and details the install instructions.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: For the numerical experiments, parameters used for the bounds are specified in the main text and in the appendix in Appendix D Additional details can be found in the
ethz. ch/ ics bbwnddboddddd-e beooundddeenergy--eeee -rcys- bounds published code .ro.orgg//o1 wtt.////....99///// 3929/9thz/ c- 000785083
and at /tttttss///oi.....
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?
32

---

Answer: [Yes]
Justification: The numerical experiments in Section 4.3 are averaged over 1000 and 20 runs, respectively. The plots include the corresponding (5%, 95% -percentiles.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: In Section 4.3 the paper provides detailed analysis of the run- time for the second numerical example, with the CPU model described Ap- pendix D Further information regarding the overall runtime of both experiments can be found in the README file of the code available online at htttss///gitaal ethz. fthz..ch/ics/boundeer -eroooudddddeeeeg--eeeee sertgy-rrks-bbuudee and https://doi. http////o..r//////////// 3929/ etbz-c-000785003 The memory requirements are negligible (< 4GB) and therefore not provided.
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: No potential conflicts with the NeurIPS Code of Ethics could be identified by the authors.
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
The work is fundamental mathematical work in kernel-based estimation and does not discuss potential societal impacts. While the societal impact of fundamental research hard to evaluate, no direct potentially harmful societal impact could be identified by the authors.
Justification:
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The work is of purely theoretical and uses academic examples to illustrate and compare against existing work.
12. Licenses for existing assets
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?
Question:
Answer: [NA]
Justification: The code submitetd as part of this work is original work by the authors; beyond software code, no further assets are used.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
14. Crowdsourcing and research with human subjects
33

---

Question: 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 as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects. 15. Institutional review board (IRB) approvals or equivalent for research with human subjects
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: LLM technology does not impact the core research of this work and thus not declared.
34


Reviews:
[{"review_id": "oVwN1mPtt5", "reviewer": "Reviewer_fxeu", "summary": "The paper studies kernel regression with both target and noise assumed to belong to certain RKHS's. The specific problem addressed is the maximum and minimum of the target at a new point given noisy observations on a training set and RKHS norm constraints for the target and noise. The paper shows that the solution can be obtained by solving a respective problem with a single linearly aggregated constraint. The paper particularly discusses two extreme special cases corresponding to permissive noise constraints and degenerate scenarios. Additionally, the paper shows that its results generalize earlier results on energy-bounded noise and noise-free interpolation, and compares its results to other deterministic and probabilistic bounds.", "questions": "I suggest to clarify for the reader the points I indicated above.\n\nI suggest to provide the appendices in the same file after the bibliography; they are easier to access this way.", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The paper is written at a high mathematical level, is generally quite readable, the authors are very familiar with the relevant literature and point out various connections of their results to earlier ones. The addressed problem is reasonable.  \n\nOn the other hand, I'm not quite convinced in sufficient importance of the contribution, and there are some issues with the exposition. \n\nline 91: *the optimization problem is infinite-dimensional and is not directly tractable.* - It is an exaggeration to call optimization problem (2) infinite-dimensional. It is obviously $(N+1)$-dimensional (or $2(N+1)$-dimensional): everything in the problem can be expressed in terms of suitable scalar products on the linear span of $N+1$ vectors corresponding to the measurement points $x_i$. The problem can be analyzed using an explicit finite-dimensional Lagrange function.\n\nline 91: *Our key result, presented in the remainder of the section, consists in deriving an analytical solution for the bound evaluated at an arbitrary input location* - I only see analytic solutions for the two extreme cases $\\\\sigma=0$ and $\\\\sigma=\\\\infty$ in the main text. In Lemma 1 (and in the appendix) there is also an explicit formula for the general case $0<\\\\sigma<\\\\infty,$ but it depends on the unknown $\\\\sigma$, for which no explicit formula seems to be provided. \n\nThe main result (Theorem 1) asserts that the solution of the problem (2) can be obtained by minimizing the solutions of the relaxed problems with linearly aggregated constraints. This looks like a special case of a very general and well-known property of problems with linear objectives and convex constraints. Problem (2) has exactly this structure, as it can be written with a linear objective of the form $f\\\\mapsto\\\\langle v, f\\\\rangle$ and constraints $h_1(f)\\\\le 0, h_2(f)\\\\le 0$ with some convex quadratic polynomials $h_1,h_2$. Writing the Lagrange function and taking the gradient $\\\\nabla_f,$ we get $v-\\\\lambda_1 \\\\nabla_f h_1(f)-\\\\lambda_2 \\\\nabla_f h_2(f)=0.$  Assuming now, for example, that both constraints are active at the solution and $\\\\lambda_1,\\\\lambda_2>0,$ we get that the problem with the aggregated constraint $\\\\lambda_1 h_1(f)+\\\\lambda_2 h_2(f)\\le 0$ has the same solution. There might be some subtleties related to degenerate cases, etc., but in any case Theorem 1 looks like a standard and expected result in constrained convex optimization, rather than a special feature of the RKHS optimization problem in question. This point is not properly clarified in the paper. \n\nSince, as admitted by the authors themselves, the result in the special case $\\\\sigma=\\\\infty$ (effectively no noise constraint) is well-known, probably the most significant specific new result of the paper is the analysis of the opposite case $\\\\sigma=0$ associated with degenerate kernel matrices. Proposition 2 provides here an explicit answer. However, it's not very clear to me why this degenerate scenario is important or interesting.\n\nIt seems that Corollary 1 can alternatively be established without Proposition 2, just by replacing the objective $f(x_k)$ by $y_k-w(x_k)$ and using the $f$ - $w$ duality and Proposition 1.", "was_revised": true, "final_justification": "I don't have any significant concerns regarding this paper, and the authors have provided constructive responses to me and the other reviewers, so I have increased my score.", "rebuttal": "We thank the Reviewer for the insightful comments.\\\n**On the claims in line 91:** We definitely agree that the problem\nstated in (2) becomes finite-dimensional after applying the Representer\nTheorem presented in Lemma A.1: nevertheless, the original problem is\nstated as searching for functions in infinite-dimensional spaces, and\nwithout exploiting the RKHS structure it might appear to be intractable.\nWe plan to use a more precise wording to clarify this point. Also, we\nwill make sure not to use \\\"analytical solution\\\" for the general\noutcome of Theorem 1: indeed, analytical (closed-form) solutions are\navailable only for the two limit-cases $\\sigma \\to 0$ and\n$\\sigma \\to \\infty$. The general result of Theorem 1, encompassing both\nlimit cases $\\sigma \\to 0$ and $\\sigma \\to \\infty$ as well as the\nscenario $0 < \\sigma < \\infty$, reduces (2) to a scalar, unconstrained\noptimization problem. This formulation is amenable for efficient\niterative optimization and each iterate returns a valid (iteratively\nimproving) bound for the unknown latent function.\\\n**On Theorem 1 being standard in constrained convex optimization:** One\nof the core contributions of our work is to reduce the challenging\nproblem of non-parametric function regression under non-i.i.d. noise to\nthe analysis of a convex optimization problem. This solution is only\nobvious in hindsight, as we directly posed the problem in terms of an\noptimization problem in Equation (2). Existing results, especially\n\\[Kanagawa+2018, Prop. 3.8\\], also tried to address the same problem;\nhowever, their approach does not utilize a connection with convex\noptimization and, as we discuss in Section 4.2, fails to determine tight\nbounds for the robust regression problem. We note that the exact\ncharacterization of the optimal solution to this convex optimization\nproblem is more involved than it may seem, as it cannot be simply\nassumed that both constraints are active -- instead, a careful handling\nof four different cases, corresponding to the possible sets of active\nconstraints, is required. These are detailed in the supplementary\nmaterial (Appendix C, pages 17-26).\\\n**On the relevance of the case $\\sigma \\to 0$:** As we discuss in\nSection 3.3, degenerate kernel matrices leading to the case\n$\\sigma\\to 0$ occur in two practical situations:\n\n1.  when the hypothesis space is determined by a finite set of $r<N$\n    basis functions, making it finite-dimensional and thus returning a\n    rank-deficient kernel matrix. This scenario occurs in many\n    approximations of kernel-based regression that aim at reducing its\n    $\\mathcal{O}(N^3)$-computational complexity: these methods rely on\n    providing the eigen-decomposition of the kernel operator thanks to\n    Mercer's Theorem, and on considering a finite number of\n    eigenfunction as the basis (approximately) representing the\n    hypothesis space \\[Zhu+1997\\]; in the stochastic setting, a\n    paradigmatic approach leveraging this rationale in frequency domain\n    is that of \\[Lázaro-Gredilla+2010\\].\n\n2.  when the test input $x_{N+1}$ belongs to the training data-set,\n    which can happen then evaluating the bound over the whole domain of\n    interest (cf. Figure 1 in the paper).\n\nThus, the case $\\sigma \\to 0$ is also of practical relevance, and our\nanalysis sheds some new light on regression with degenerate kernels.\nHowever, it is a byproduct of the general analysis in Theorem 1, which\nis capable of capturing and generalizing known results; see also the\ncase $\\sigma \\to \\infty$ and the discussion in Section 4.1 of the\npaper.\\\n**On Corollary 1:** Thank you for this suggestion. In the current\nexposition, Corollary 1 follows directly from the more general claim of\nProposition 2, which provides the analytic solution for the case\n$\\sigma\\to 0$ occurring when the kernel matrix is rank-deficient. From\nthis perspective, the scenario in which the test-input belongs to the\ntraining data-set is one of the particular situations leading to a drop\nin the rank of the kernel matrix. However, we agree that Corollary 1\ncould potentially be established analogously to Proposition 1 -- an\ninsight that we are happy to convey in the paper.\n\n**References:**\\\n \\[Zhu+1997\\] H. Zhu, C. K. Williams, R. Rohwer, and M. Morciniec,\n\"Gaussian regression and optimal finite dimensional linear models,\"\nAston University, NCRG/97/011, 1997;\\\n \\[Lázaro-Gredilla+2010\\] M. Lázaro-Gredilla, J. Quinonero-Candela, C.\nE. Rasmussen, and A. R. Figueiras-Vidal, \"Sparse spectrum Gaussian\nprocess regression,\" The Journal of Machine Learning Research, vol. 11,\npp. 1865--1881, 2010;\\\n \\[Kanagawa+2018\\] M. Kanagawa, P. Hennig, D. Sejdinovic, and B. K.\nSriperumbudur, \"Gaussian Processes and Kernel Methods: A Review on\nConnections and Equivalences,\" arXiv:1807.02582, 2018;\\\n \\[Fogel 1979\\] E. Fogel, \"System identification via membership set\nconstraints with energy constrained noise,\" IEEE Transactions on\nAutomatic Control, vol. 24, no. 5, pp. 752--758, 1979."}, {"review_id": "T31uqRIDq8", "reviewer": "Reviewer_sCCF", "summary": "This paper introduces a novel framework for deriving tight, non-asymptotic uncertainty bounds in kernel-based regression under energy-bounded noise, formulated as a deterministic optimization problem. The proposed method generalizes existing kernel interpolation and linear regression results, offering a robust alternative to probabilistic approaches. Theoretical derivations are rigorous, and the connection to Gaussian process (GP) regression and RKHS theory is well-structured. The bounds are computationally efficient, relying on scalar optimization, and demonstrate advantages in low-data regimes.", "questions": "1.\tWhat practical strategies (e.g., cross-validation, online adaptation) could be employed to estimate the latent function complexity and noise energy from data?\n2.\tUnder what conditions (kernel choices, noise structures) can we guarantee convexity in the σ optimization problem?\n3.\tHow sensitive are the bounds to parameter misspecification, particularly when the true function lies outside the assumed RKHS?", "limitations": "The authors do discuss the limitations including challenges of kernel mis-specification, estimating the RKHS-norm bound, and handling large datasets in their work.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n1.\tThe use of RKHS-norm-bounded noise provides a deterministic framework that relaxes traditional i.i.d. or Gaussian noise assumptions, addressing a gap in the literature. The derived bounds are tight and non-asymptotic, with elegant connections to GP posterior variance.\n2.\tThe reliance on scalar optimization makes the approach computationally tractable and suitable for iterative refinement in practical applications like safe reinforcement learning and Bayesian optimization.\n3.\tAs reported, empirical results demonstrate superior performance to probabilistic methods in low-data regimes.\n\nWeaknesses \n1.\tThe method's core premise is prior knowledge of latent function complexity and noise energy, which are challenging to estimate in practice. Sudden increases in noise energy (e.g., adversarial perturbations) may violate preset noise energy, compromising safety guarantees. \n2.\tUnlike probabilistic bounds, the proposed bounds do not improve with more data under energy-bounded noise. This trade-off between robustness and asymptotic efficiency requires deeper discussion.\n3.\tComprehensive testing of parameter sensitivity and validation under noise correlation structures is lacking.", "was_revised": true, "final_justification": "As my rating is already positive, I would like to keep my current rating.", "rebuttal": "We thank the Reviewer for the insightful comments.\\\n**On the energy bounds and adversarial noises:** Assuming to have known\nRKHS-norm bound for the unknown latent function is quite standard in the\nliterature \\[Srinivas+2012,Chowdhury+2017,Fiedler+2021\\] (see the\nparagraph \"Practical strategies to estimate RKHS-norm bounds\\\" below for\nfurther discussion and existing techniques to estimate the RKHS norm).\nTherefore, given adequate RKHS-norm bounds, our approach is capable of\naddressing the case of adversarial noise, possibly with non-zero mean:\nby construction, the proposed bound accounts for the worst-case\nadversarial noise, regardless of its distribution. Note that this is\ntypically not the case for standard regression results, which leverage\nthe assumption that noises are zero-mean i.i.d. and cannot handle\nadversarial noise.\\\n**Discussion on the performance as the data-set size increases:** We\nwould like to clarify that the derived bound is tight, i.e., given the\nposed assumptions, it provides the exact description of uncertainty\nenvelope for the latent function given the data. Under the assumption\nthat the noise is zero-mean i.i.d., one can usually guarantee to learn\nthe unknown function up to any tolerance. With the proposed method, we\ncan also generate monotonically improving estimates of the unknown\nfunction; however, due to the adversarial noise assumption, there is no\nguarantee that the bounds will asymptotically shrink to zero (cf. Figure\n2 in the paper). Note that standard stochastic regression bounds working\nwith i.i.d. and zero-mean noises cannot handle adversarial (or just\nslightly biased) noises, and their well-known behavior of returning\nvanishingly small uncertainty bounds would lead to an incorrect bound in\nsuch a set-up.\\\n**Testing of parameter sensitivity and validation under noise\ncorrelation:** Modeling noise sequences as energy-bounded members of\nsome deterministic function space allows us *by construction* to handle\nbiased and correlated noise. An informed choice of the noise kernel can\nthereby lead to improved estimates; in particular, by using the Dirac\nkernel $k^w$, the derived bounds are valid for any noise sequence\nsatisfying $\\sum_{i=1}^N w_i^2< \\Gamma_w^2$ (see Equation (16)), even if\nthe noise is correlated.\\\n**Practical strategies to estimate RKHS-norm bounds:** Many\nstate-of-the-art uncertainty bounds for kernel-based methods rely on\nRKHS-norm bounds \\[Srinivas+2012,Chowdury+2017,Fiedler2021\\], which are\nof high relevance in downstream tasks, such as safe reinforcement\nlearning \\[Berkenkamp+2023\\] and Bayesian optimization \\[Sui+2018\\].\nThis has motivated works on estimating the RKHS-norm bound. For\ninstance, \\[Tokmak+2025\\] and its preceding works elaborate an\nextrapolation-based technique to estimate such a quantity, and\n\\[Csaji+2025\\] derives bounds for Paley-Wiener kernels of band-limited\nfunctions using a uniformly-randomized Hoeffding's inequality or an\nempirical version of Bernstein's inequality. Additionally, one would\nalso be capable of detecting the inadequacy of the norm bounds (i.e.,\nthem being too small) by checking feasibility of the constraints in the\nformulation given in Equation (C.1): this would allow to rule out\ncertain configurations, as they cannot explain the data.\\\n**What conditions would yield convexity in the $\\sigma$-optimization\nproblem?** This is a very interesting point. We would like to highlight\nthat we never claim that the problem is convex and application of the\nderived bound to downstream tasks also does not require this. Instead,\nthe key point regarding Problem (9) is that any variable\n$\\sigma\\in(0,\\infty)$ provides a correct error bound. Hence, for\ndecision making, we can simply treat $(x_{N+1},\\sigma)$ as a decision\nvariable, and Theorem 1 ensures that we always obtain correct error\nestimates and that the optimal choice of $\\sigma$ also ensures that this\nbound is sharp. As both the ground truth function $f^{\\mathrm{tr}}$ and\nthe upper bound $\\bar{f}^\\sigma(x)$ are typically non-convex, convexity\nin $\\sigma$ plays no crucial role. Moreover, convexity is not required\nto achieve global optimality using simple gradient descent algorithms.\nIn this regard, we expect that Problem (9) satisfies the\nPolyak-Łojasiewicz (PL)-conditions, although we currently have no formal\nproof.\\\n**Sensitivity of the bounds to parameter misspecification, especially\nwhen the RKHS does not contain the true function:** The proposed method\ncan deal with the presented misspecification, because we do not treat\nthe noise sequence as a stochastic object, but as a member of a\ndeterministic function space. As long as the latter is rich enough, the\nnoise is therefore capable of compensating for the misspecification of\nthe latent-function RKHS. In particular, if data are generated by\n$y_i=h(x_i)$ with some function $h$ that is not in the RKHS, then we can\ndecompose $h(x)=f(x)+w(x)$, where $f$ lies in the RKHS and $\\Gamma_f$\nbounds its RKHS norm, while $w$ is the residual. By picking $k^w$ as the\nDirac kernel, Assumption 1 holds with\n$\\sum_{i=1}^N |h(x_i)-f(x_i)|^2<\\Gamma_w^2$ (see Equation (16)): for the\nnoise to \"compensate\" the RKHS misspecification, its bound on the RKHS\nnorm of the noise has to be larger than the point-wise squared distance\nbetween the true function and the function that lies in the RKHS.\n\n**References:**\\\n \\[Srinivas+2012\\] N. Srinivas, A. Krause, S. M. Kakade, and M. W.\nSeeger, \"Information-Theoretic Regret Bounds for Gaussian Process\nOptimization in the Bandit Setting,\" IEEE Transactions on Information\nTheory, vol. 58, no. 5, pp. 3250--3265, 2012;\\\n \\[Chowdury+2017\\] S. R. Chowdhury and A. Gopalan, \"On Kernelized\nMulti-armed Bandits,\" in Proceedings of the 34th International\nConference on Machine Learning, PMLR, 2017, pp. 844--853;\\\n \\[Fiedler+2021\\] C. Fiedler, C. W. Scherer, and S. Trimpe, \"Practical\nand Rigorous Uncertainty Bounds for Gaussian Process Regression,\"\nProceedings of the AAAI Conference on Artificial Intelligence, vol. 35,\nno. 8, Art. no. 8, 2021;\\\n \\[Tokmak+2025\\] A. Tokmak, K. G. Krishnan, T. B. Schön, and D. Baumann,\n\"Safe exploration in reproducing kernel Hilbert spaces\", 2025, arXiv:\narXiv:2503.10352;\\\n \\[Csaji+2025\\] B. C. Csáji and B. Horváth, \"Derandomizing Simultaneous\nConfidence Regions for Band-Limited Functions by Improved Norm Bounds\nand Majority-Voting Schemes\", 2025, arXiv: arXiv:2506.17764;\n \\[Berkenkamp+2023\\]: F. Berkenkamp, A. Krause, and A. P. Schoellig,\n\"Bayesian optimization with safety constraints: safe and automatic\nparameter tuning in robotics,\" Mach Learn, vol. 112, no. 10, pp.\n3713--3747,2023;\\\n \\[Sui+2018\\]: Y. Sui, V. Zhuang, J. Burdick, and Y. Yue, \"Stagewise\nSafe Bayesian Optimization with Gaussian Processes,\" in Proceedings of\nthe 35th International Conference on Machine Learning, PMLR, 2018, pp.\n4781--4789."}, {"review_id": "VMr7kCetKY", "reviewer": "Reviewer_Ep7a", "summary": "This paper presents tight non-asymptotic uncertainty bounds for kernel-based regression under the assumption of energy-bounded noise.   In this setting, no distribution is assumed on the noise, nor any independence assumptions.   Both the latent function being recovered and the noise are modeled as elements in reproducing kernel hilbert spaces (RKHS).\n\nThe authors formulate the problem as an infinite dimensional optimisation problem to characterise the worst case deviation of the function at a single arbitrary evaluation point.   The very neat idea, is that by relaxing / collapsing two inequality constraints, the problem can be simplified into one with a closed form solution, which is very nice.   The exact bound can then be recovered by optimising the solution over the scalar noise parameter.   The approach generalises and recovers classical results in kernel interpolation and linear regression, and is shown empirically to yield less conservative uncertainty regions than standard probabilistic bounds in low data-regimes.", "questions": "1. How sensitive are your results to mis-specification of the rkhs norm bounds?   Could you provide some examples of how they can be estimated from data, and how estimation error affects your bounds?\n\n2. Can some details be provided about how the optimisation in (9) can be carried out?   Does this run into stability issues as $\\sigma\\rightarrow 0$?  If so, is some regularisation needed?\n\n3. Is it possible to demonstrate how these bounds are used in a down-stream setting?  e.g. Bayesian optimisation or similar applications?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. This approach provides a tight, non-asymptotic bounds for kernel regression that handles noise under no distributional assumptions.\n2. The bounds derived are straightforward to recover through the relaxation approach.\n3. Various classical results are obtained as a special case, and some novel bounds are obtained in the probabilistic case.\n\n\nChallenges with this approach:\n1. The main challenge is the assumption of a known RKHS bound of both the function and the noise.    In practice this would be approached empirically which would influence the derived bounds significantly - as mentioned in the paper as an acknowledged limitation.\n2. The method does not appear to lend itself well to bounds over multiple prediction points.   It is not clear to me that it would be straightforward to extend the approachd directly to ths setting.\n3. It would have been nice for the authors to add a demonstration of how these bounds can be effectively deployed in downstream tasks.", "was_revised": true, "final_justification": "The authors have addressed all my questions, and I appreciate their efforts in adding a good downstream example.  I have updated my score accordingly.", "rebuttal": "We thank the Reviewer for the careful reading of the paper.\\\n**On knowing the RKHS norm bound:** This assumption is common with other\nstate-of-the-art bounds (e.g.\n\\[Srinivas+2012,Chowdury+2017,Fiedler+2021\\]) that have been successful\nin downstream tasks such as safe reinforcement learning and Bayesian\noptimization. Given the practical impact of such results, there exist\nworks that estimate RKHS norms: see e.g. \\[Tokmak+2025\\] and references\ntherein for extrapolation-based approaches, and \\[Csaji+2025\\] for the\ncase of Paley-Wiener kernels of band-limited functions using the\nuniformly-randomized Hoeffding's inequality or the empirical Bernstein\ninequality. Another strategy for estimating the RKHS bounds can be\ndeveloped by expanding on ideas from the robust regression literature,\nsuch as \\[Calliess+2020\\]: one starts from the smallest bound that is\nnot falsified by the data (i.e., such that the problem remains feasible)\nand increases it with a small proportional buffer according to the\nso-called \"lazy adaptation\\\" technique; then, such a bound can be\ncombined with recent RKHS-norm extrapolation heuristics \\[Tokmak+2025\\].\nHowever, a formal analysis of this technique to the considered setting\nand intensive numerical validations would be required. We plan to expand\non this point in the limitation section of the paper.\\\n**Sensitivity of result to norm-bound misspecification:** A thorough\nquantitative analysis depends on the adopted estimation strategy and\nwill be deferred to future works. Nevertheless, we can mention the\nfollowing cases:\n\n-   if the norm bounds are too small, this could be detected by checking\n    feasibility of the constraints in the problem formulation (C.1);\n\n-   if the problem (2) remains feasible despite $\\Gamma_f$ being too\n    small, then the noise function given by a positive definite noise\n    kernel $k^w$ can generally compensate for the inadequacy of the\n    constraint on the latent function norm.\n\nFinally, we would like to point out that taking conservative (too large)\nnorm bounds for both the noise and the latent function does not have a\ndramatic impact on the resulting bound. In fact, as displayed in\nEquation (7), conservative values for $\\Gamma_f^2$ and $\\Gamma_w^2$ lead\nto a just sublinear inflation of the uncertainty envelope.\\\n**Validity of proposed bound over multiple prediction points:** Our\ndeterministic guarantees are derived for any query point $x_{N+1}$ given\nthe training data -- this is also what is done in our experiments\n(cf. Figure 1 and 2), where the bound is computed for any input in the\ngiven domain.\\\n**Deployment in downstream tasks:** We agree that quantifying the\nperformance of the proposed approach in a downstream task would better\nhighlight some of the benefits. Therefore, we conducted the following\nexperiment. We are given a dynamical system with unknown (scalar)\ndynamics, which is estimated from $10^2$ data points using kernel-based\nestimation. The estimated dynamic model and its uncertainty bound is\nutilized in a control barrier function (CBF) to ensure that the\noptimized control input satisfies safety-critical constraints. Through\nthe size of the uncertainty envelope, the conservatism of the employed\nbound determines the feasible domain for which safe inputs can be\ncomputed, with smaller confidence sets leading to a larger feasible\nregion. Similar to the numerical comparison in Section 4.3, we compare\nthree methods for computing the uncertainty bound: (a) the probabilistic\nbound by \\[Abbasi-Yadkori 2013\\]; (b) the derived robust regression; (c)\nthe derived robust regression using only the closest $10^1$ data points\nfor each test point. Apart from the number of data points used, the\ncorresponding optimization problems only differ in the number of\noptimization variables (for the robust bounds, we additionally optimize\nover the free noise parameter $\\sigma$), as well as the definition of\nthe scaling factor $\\beta$, cf. Eq. (7) for the robust case and\n\\[Fiedler+2024, Eq. (7)\\] for the probabilistic case. Crucially,\nbenchmark (c) also highlights the fact that the derived bound remains\nvalid for any subset of data, independent of how it is chosen (in\ncontrast to stochastic error bounds). The following table compares the\nrobust and probabilistic bounds in terms of the computational\ncomplexity, as well as their conservatism in terms of the portion of the\ndomain for which the size of the bound retains feasibility of the\noptimization problem:\n \n |                             |     (a)    |    (b)  |     (c) |\n | ----------------------- | ------- | ------- | -------  |\n |    Time / iter. \\[ms\\]  |   5.7  |  17.9  |  0.4 |\n |  Feasible domain \\[%\\]  |  63  |    81   |   62 |\n\n\nWhile optimization over the noise parameter in (b) leads to larger\ncomputation times for the same number of data points, it leads to a\nlarger feasible domain due to its reduced conservatism even in the\nzero-mean i.i.d. setting. The subset-of-data approach (c) highlights\nthat the method can be computationally more efficient, while also\nproviding rigorous guarantees for safety-critical applicants in\ndownstream tasks.\\\n**On solving (9):** The main difficulty when optimizing (9) lies in the\nfact that the optimizer $\\sigma$ can tend towards the boundaries of\n$(0, \\infty)$, which can be addressed numerically by using adequately\npermissive box constraints, for example by enforcing\n$\\sigma^2 \\in [10^{-6}, 10^6]$. To avoid scaling issues, in our\nexperiments we have found that optimizing over $\\log(\\sigma^2)$ improves\nnumerical stability; alternatively, squashing functions can be employed\nto optimize in the large parameter space. Additionally, we have added a\nsmall constant \"jitter\" $\\sigma_{\\mathrm{jitter}}^2 = 10^{-6}$ to the\nkernel matrix, i.e., used\n$K^f + (\\sigma^2 + \\sigma_{\\mathrm{jitter}}^2) I$ in the implementation,\nas is commonly done to avoid numerically indefinite kernel matrices.\nUsing these techniques, we have not experienced numerical issues in the\nlimiting case $\\sigma \\rightarrow 0$, which we observed in our\nexperiments for some query input locations $x_{N+1}$ that are close to a\ntraining input location. This is expected since, as shown in\nProposition 2, the optimized bound attains a finite value for\n$\\sigma \\rightarrow 0$.\n\n**References:**\\\n \\[Srinivas+2012\\] N. Srinivas, A. Krause, S. M. Kakade, and M. W.\nSeeger, \"Information-Theoretic Regret Bounds for Gaussian Process\nOptimization in the Bandit Setting,\" IEEE Transactions on Information\nTheory, vol. 58, no. 5, pp. 3250--3265, 2012;\\\n \\[Chowdury+2017\\] S. R. Chowdhury and A. Gopalan, \"On Kernelized\nMulti-armed Bandits,\" in Proceedings of the 34th International\nConference on Machine Learning, PMLR, 2017, pp. 844--853;\\\n \\[Fiedler+2021\\] C. Fiedler, C. W. Scherer, and S. Trimpe, \"Practical\nand Rigorous Uncertainty Bounds for Gaussian Process Regression,\"\nProceedings of the AAAI Conference on Artificial Intelligence, vol. 35,\nno. 8, Art. no. 8, 2021;\\\n \\[Tokmak+2025\\] A. Tokmak, K. G. Krishnan, T. B. Schön, and D. Baumann,\n\"Safe exploration in reproducing kernel Hilbert spaces\", 2025, arXiv:\narXiv:2503.10352;\\\n \\[Csaji+2025\\] B. C. Csáji and B. Horváth, \"Derandomizing Simultaneous\nConfidence Regions for Band-Limited Functions by Improved Norm Bounds\nand Majority-Voting Schemes\", 2025, arXiv: arXiv:2506.17764;\\\n \\[Calliess+2020\\]: J.-P. Calliess, S. J. Roberts, C. E. Rasmussen, and\nJ. Maciejowski, \"Lazily Adapted Constant Kinky Inference for\nnonparametric regression and model-reference adaptive control,\"\nAutomatica, vol. 122, p. 109216, 2020;\\\n \\[Fiedler+2024\\]: C. Fiedler, J. Menn, L. Kreisköther, and S. Trimpe,\n\"On Safety in Safe Bayesian Optimization\", 2024, arXiv:\narXiv:2403.12948;\\\n \\[Abbasi-Yadkori 2013\\]: Y. Abbasi-Yadkori, \"Online learning for\nlinearly parametrized control problems,\" University of Alberta,\nEdmonton, Alberta, 2013."}, {"review_id": "uTlGGXo80r", "reviewer": "Reviewer_BU3a", "summary": "The paper considers the problem of obtaining uncertainty bounds for the problem of kernel-regression. As opposed to the standard i.i.d. assumption on noise, the authors consider a bounded-energy scenario, where the noise is assumed to have a bounded norm in a certain RKHS space. Under this setting, the authors derive a closed expression for the worst case upper and lower bounds on the mean predictor providing concise descriptions of the worst-case uncertainty. They also provide simplified expressions under specific cases and relate the obtained bounds to classical results in kernel and linear regression.", "questions": "One thing that is bugging me is the premise and the motivation of this problem. At a basic level, the problem of function estimation/prediction using training data first requires a certain modelling assumption. Existing studies on kernel-based regression model the data assuming that the true function belongs to an RKHS and the noise is i.i.d. Gaussian. In this work, the authors use a different modelling assumption, where in they assume that noise is an element of a different RKHS (this is not statistical in nature in anymore).\n\nFirstly, in my opinion, neither of them is inherently better than the other. The better model usually depends on the application at hand. Moreover, this modelling assumption is not a \"remedy\" for Gaussianity or iid-ness of noise. This seems to have been suggested implicitly in the text, which is something I don't think is correct. This is not a dealbreaker but an important point to keep in mind.\n\nSecondly, modelling the noise as an RKHS function is unusual. Is there some inherent motivation as to why this is a good model to capture the underlying process? In particular, this is non-statistical model which is a very uncommon method to account for noise. Is there a particular reason for which the authors use this as a part of their model, apart from analytical tractability? Are there specific applications for which such a model would be a reasonably good approximation of the true underlying process?\n\nThirdly, the term \"energy-boundedness\" is thrown pretty loosely throughout the paper. The energy of a function or a signal is usually measured in its L2 norm, not the RKHS norm. While these ideas coincide when the noise kernel is taken to be the dirac delta, this is not the case in general.  Once again, this modelling assumption seems uncommon. Can the authors justify this particular choice beyond the fact that is makes the problem tractable. More importantly, a bounded L2 norm implies a bounded RKHS norm but the converse does not hold. Thus, this is a more stringent assumption than the standard interpretation of energy-boundedness.\n\nFourthly, the authors make the following claim:\n> we derive an analytical solution that exactly characterizes the worst-case realization within the function hypothesis class\n\nIf I understand this correctly, the authors are referring to Eq.8, the statement of Lemma 1. If the authors are referring to $\\overline{f}^{\\sigma}(\\cdot)$ as \"the worst-case realization within the function hypothesis class\", then the statement is incorrect because it does not belong to RKHS. In particular $\\Sigma_{\\sigma}^{f}$ is not an element of the RKHS and hence neither is $\\overline{f}^{\\sigma}(\\cdot)$. I am not saying that Lemma 1 is incorrect. All I am saying is that you are not obtaining \"an optimal f\", but an optimal value of (an upper bound on) \"$f(x_{N+1})$\", a scalar. These two are different things.\n\n\nI am also curious about the actual benefit of using this approach in downstream tasks. Let us compare the uncertainty estimates from the classical iid Gaussian and the proposed methodology in this work (the comparison is not really apple to apple, but let us assume for the moment). Say the idealized optimal bounds in this work are tighter than those produced by the Gaussian assumption. However, there is no quantification of the improvement over the classical conservative bounds. Moreover, in practice the optimal value of $\\sigma$ will not be known and will be estimated using some sort of iterative procedure, which will worsen the estimates obtained from this method. Furthermore, optimizing over $\\sigma$ is computationally expensive as calculating a single gradient requires $\\mathcal{O}(N^3)$ operations. Thus, despite the increased computational requirements it is not clear how much benefit, if any, is obtained using such an approach. I understand that carrying out such experiments is beyond the scope of this work and I don't expect it to be a part of this paper either. However, without any quantification of improvement in uncertainty estimates, the benefit of such an approach remains unclear.\n\nLastly, how sensitive is the proposed approach to the choice of the RKHS, especially for the noise? If the estimates vary wildly depending on the choice of RKHS, then such a methodology is not practically robust.\n\n\nMy current score is more reflective of the questions above rather than the core technical content of the paper. I am willing to reconsider it if the authors can provide answers to my questions above.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "I think the paper is decent. It seems to be technically sound and has some new ideas in there. My main concern with the paper is regarding the modelling aspect, which I have explained in the section below.", "was_revised": true, "final_justification": "Please refer to my comment to the author's response.", "rebuttal": "We thank the Reviewer for the careful reading of the paper.\\\n**On modeling noise sequences as members of deterministic function\nspaces:** We agree that the choice of giving a stochastic or\ndeterministic representation of the noise depends on the problem at\nhand. There are indeed situations in which stochastic modeling is\npreferable -- e.g., when samples are i.i.d. with known distribution.\nHowever, the choice of modeling noise sequences as energy-bounded\nmembers of a RKHS (which is also performed in \\[Kanagawa+2018\\]) allows\nus to overcome two main difficulties of stochastic representations,\nnamely dealing with biases and correlation among samples. Additionally,\nsuch a set-up allows us to deal with adversarial noises (in fact, we are\ncomputing the bound accounting for the worst-case noise realization),\nand rich-enough hypotheses classes for the noise allow us to compensate\nfor model misspecification of the latent function. Therefore, the\npresented modeling choice has practical advantages that go beyond\ntractability. Finally, we would like to point out a further connection\nbetween our set-up and the stochastic one (cf. footnote 2, p.8): if one\nconsiders sub-Gaussian and i.i.d. noise, it is possible to find a\ncertain probability level for which the norm-bounds in Assumption 1 hold\n-- but the converse is not true.\\\n**On energy-boundedness:** While the reviewer is correct that an\nRKHS-norm assumption is significantly more restrictive than a bound on\nthe $\\mathscr{L}^2$ norm, we would like to clarify that we are never\ninvoking energy bounds or $\\mathscr{L}^2$ norms on continuous functions.\nWhen introducing the RKHS condition in Assumption 1, we directly\nreference Section 4.1 regarding its interpretation as energy-bounded\nnoise. In particular, for Dirac noise kernels, Equation (16) in\nSection 4.1 shows that the condition is equivalent to bounded energy of\nthe finite noise sequence affecting the measurements, i.e.,\n$\\sum_{i=1}^N w_i^2 \\leq \\Gamma_w^2$. Such energy-bounded noise\nassumptions are common in classical robust regression works such as\n\\[Fogel 1979\\], \\[Bertsekas+2003\\] and many others. We see that the word\n\"energy\\\" might also be interpreted as a $\\mathscr{L}^2$-energy bound\nand we plan to use a more precise wording to highlight that this is a\nbound on the finite and discrete noise sequence that affects our finite\nand discrete measured data $(x_i,y_i)$, $i=1,\\dots N$. Our general\ntheoretical results are valid for any positive definite and uniformly\nbounded kernel $k^w$ characterizing the noise. This general modeling\nframework ensures that we can simultaneously recover results from\nclassical energy bounded regression \\[Fogel 1979\\], connect our results\nto to recent kernel error bounds \\[Kanagawa+2018\\], and provide an\ninterpretation of the bound in terms of mean and covariance of a GP (cf.\nSection 4).\\\n**On the claim in the contributions:** As the Reviewer correctly points\nout, our sentence \"we derive an analytical solution that exactly\ncharacterizes the worst-case realization within the function hypothesis\nclass\\\" is not precise. Indeed, given the non-parametric nature of the\nproblem, the worst-case function $f^\\star$ depends on the query point\n$x_{N+1}$ -- thus, the whole function $\\bar{f}(x_{N+1})$, which takes\nthe evaluation of different worst-case functions at different query\npoints, is no longer in the hypothesis space. What we mean is that, for\nany given query point $x_{N+1}$, our procedure returns a worst-case\nlatent function $f^\\star$ in the RKHS space, cf. its parametrization in\nterms of the weight vector $\\theta^\\star$ in Eqs. (C.3), (C.16) for\nCases 1 and 2. The evaluation of this function at the point $x_{N+1}$\nthen returns the error bound $\\bar{f}(x_{N+1})$. We plan to better\nconvey this idea by moving some of the expressions of the worst-case\nfunction $f^\\star$ from the Appendix to the main text.\\\n**On the benefits of the proposed approach and application on a\ndownstream task:** First, we would like to emphasize that if the\ndistribution of the noise is known, probabilistic bounds are the most\nnatural choice to quantify the uncertainty -- and this would be the case\nfor Gaussian i.i.d. noise. However, as soon as the distribution is\nunknown (e.g., biased and correlated), applying GP bounds would return\nwrong results, possibly endangering safety for downstream tasks. This\ndisplays one of the strengths of the proposed approach: it is\ndistribution-free, and is also capable of dealing with adversarial\nnoises. We defer to footnote 2 for a discussion on the connection\nbetween the proposed bound and the probabilistic ones, but we plan on\nexpanding on this point in the paper.\\\nRegarding the optimization of $\\sigma$, we highlight that this is only\nneeded to obtain the least conservative error bound, while *any* value\n$\\sigma$ provides a valid estimate that can be safely used for\ndownstream tasks, as discussed at the end of Section 3.2. In other\nwords, optimizing $\\sigma$ leads to a refinement of the uncertainty\nenvelope, and the termination of iterative optimization procedures can\nbe dictated by the downstream task at hand.\\\nTo highlight these aspects and also display the performance of the\nproposed approach, we conducted an experiment where we apply the\nproposed bounds to a downstream task. Specifically, we consider\nsafety-critical control of an uncertain dynamical systems, where we\ndemonstrate significant benefits of the reduced conservatism and\nmanageable computation times when jointly optimizing $\\sigma$.\nAdditionally, we highlight another key property of the proposed bound --\nthey still hold when considering a subset of data -- which has a\nsignificantly bigger impact on the computational demand compare to the\nscalar $\\sigma$.\\\n*Experimental details:* We compare the proposed robust bound and a\nprobabilistic bound akin to the setup in Section 4.3. The downstream\napplication of the bound is thereby given by an optimization-based\ncontroller (specifically, a control barrier function) that ensures\nsafety (constraint satisfaction) of an unknown dynamical system modeled\nusing kernel regression with $10^2$ data points. The only difference in\nthe application of the probabilistic bound, denoted by (a), compared to\nthe proposed robust bound, (b), is the simultaneous optimization over\nthe noise parameter $\\sigma$ (one additional optimization variable), as\nwell as the different scaling factor $\\beta_\\sigma$ of the covariance\nmatrix, see also the discussion in Section 4.3. Additionally, we applied\nthe proposed bound to a subset of data containing the 10 nearest\ntraining input locations and we denote this approach by (c). Notably,\nthe derived robust bounds remain valid under arbitrary data selection\nrules, while the probabilistic approach relies on martingale bounds,\nwhich would fail under such data-selection rules. The following table\ncompares the three approaches in terms of their computation time to\nsolve the optimization problem to convergence, as well as the\nconservativeness of the bound, indicated by the share of the input\ndomain for which a safety-preserving (feasible) input is computed:\n\n |                             |     (a)    |    (b)  |     (c) |\n | ----------------------- | ------- | ------- | -------  |\n |    Time / iter. \\[ms\\]  |   5.7  |  17.9  |  0.4 |\n |  Feasible domain \\[%\\]  |  63  |    81   |   62 |\n\nThe larger feasible domain of the proposed bound (b) illustrates the\nreduced conservatism of the bound. While, for the same number of data\npoints, the computation time for optimizing the robust bound (b) is\nvisibly larger than for the probabilistic one (a), the subset selection\nmechanism (c) leads to a similarly large feasible domain as the\nprobabilistic bound at significantly reduced computation times.\\\n**On the sensitivity of the bounds to the choice of the RKHS:** Choosing\nthe RKHS is a widely investigated topic in the statistical learning\nliterature, and connects with results obtained in the realm of Gaussian\nprocess regression, cf. \\[Rasmussen+2006, Sec. 5.4\\]. Our set-up falls\nalso into this framework: indeed, a key result of our work is that the\nworst-case error bound has the same formula as the error bound for\nstandard Gaussian process regression for a suitably chosen noise\n$\\sigma$ when choosing a Dirac kernel for the noise, see Equation (8).\nAlthough less prevalent, we note that also general (non-Dirac) noise\nkernels $k^w$ are leveraged for Gaussian process regression\n\\[Rasmussen+2006, Sec. 5.4.3\\] and the equivalence (Eq. (8)) equally\napplies in this case. Hence, the sensitivity of our bound to the choice\nof the RKHS is comparable to the sensitivity of general Gaussian process\nregression to the choice of the kernel. For this reason, we see no need\nto separately investigate the sensitivity to related hyperparameters.\n\n**References:**\\\n \\[Kanagawa+2018\\] M. Kanagawa, P. Hennig, D. Sejdinovic, and B. K.\nSriperumbudur, \"Gaussian Processes and Kernel Methods: A Review on\nConnections and Equivalences,\" arXiv:1807.02582, 2018;\\\n \\[Fogel 1979\\] E. Fogel, \"System identification via membership set\nconstraints with energy constrained noise,\" IEEE Transactions on\nAutomatic Control, vol. 24, no. 5, pp. 752--758, 1979;\\\n \\[Bertsekas+2003\\]: D. Bertsekas and I. Rhodes, \"Recursive state\nestimation for a set-membership description of uncertainty,\" IEEE\nTransactions on Automatic Control, vol. 16, no. 2, pp. 117--128, 1971;\\\n \\[Rasmussen+2006\\]: C. E. Rasmussen and C. K. I. Williams, Gaussian\nprocesses for machine learning. in Adaptive computation and machine\nlearning. Cambridge, Massachusetts: MIT Press, 2006."}]

Author rebuttal:

Meta-review: The paper considers the worst-case bounds for kernel regression. It assumes the data are generated by the sum of two functions (a target function and a noise function) from a RKHS, and shows how to explicitly calculate bounds on the target function at a given out-of-sample point in terms of the RKHS norm bounds on the functions (assuming their respective kernels are bounded).

All reviewers liked it. They had some questions, all of which were suitable addressed by the rebuttals.

This is a theory paper, and NeurIPS has a lot of very strong theory papers and it cannot accept all of them. So I took a look, and I asked myself if the **setting** is interesting enough for a wide-range of NeurIPS readers. And I think it is: the setup seems very fundamental, and it also is an active area of research. I think kernel methods are one of the few areas of ML that have near state-of-the-art performance while still having guarantees; and similarly, GP regression and Bayesian Optimization are of interest to the typical NeurIPS reader. I don't know if this paper will have direct practical impacts, but it is making a theoretical contribution in an interesting area of ML.

Thus I'm pleased to recommend acceptance.
Decision: Accept (poster)