Optimal kernel regression bounds under energy-bounded noise
Amon Lahr, Johannes Köhler, Anna Scampicchio *, Melanie N. Zeilinger · 2025
Read Optimal kernel regression bounds under energy-bounded noise by Amon Lahr, Johannes Köhler, Anna Scampicchio *, Melanie N. Zeilinger (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-22235.txt.
Introduction
Amon Lahr and co-authors published this estimation study in 2025. Kernel regression is a flexible way to learn an unknown function from noisy data points. Users of such estimates need honest error bounds, especially before trusting them in safety-critical systems. The catch is that the noise may be correlated over time and only loosely bounded in total energy. The team derived a bound for this setting that is tight, meaning no valid bound can be smaller.
Their bound returns the worst-case function value still consistent with the data at any chosen input point. It takes a clean form: the mean and spread of a Gaussian process, once the noise level is chosen well. Computing it stays cheap. The authors checked the method against earlier results in the field. They show it stays sharp where older bounds grow loose, which makes it practical for judging estimation accuracy.
Catalog record
| CREATOR | Amon Lahr, Johannes Köhler, Anna Scampicchio *, Melanie N. Zeilinger |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 100 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-22235
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Optimal kernel regression bounds under energy-bounded noise Amon Lahr, Johannes Köhler, Anna Scampicchio *, Melanie N. Zeilinger 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. 1 Introduction Many problems in machine learning can be phrased in terms of estimating an unknown (continuous) function from a finite set of noisy data. A popular, non-parametric technique to perform such a task and return point-wise estimates is given by the class of 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-asymptotic uncertainty bounds enables evaluating their reliability, for example, in view of deploying Bayesian optimization [ Berkenkamp et 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 to 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, 2006 ] , a kernel-based method that is 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, high-probability and non-asymptotic uncertainty bounds have been derived by Srinivas et al. [2012] ; Abbasi-Yadkori [2013] ; Burnaev and Vovk [2014] ; Fiedler et al. [2021] ; Baggio et al. [2022] ; Molodchyk et al. [2025] , phrasing the problem as estimation in Reproducing Kernel Hilbert Spaces (RKHSs) [ Aronszajn, 1950 ; Berlinet and Thomas-Agnan, 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 noise [ Maddalena et al., 2021 ; Reed et al., 2025 ; Scharnhorst et al., 2023 ] – however, these results tend to 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 kernel-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-probability 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 \sigma^{2} that depends on the test input location. Furthermore, we show that the derived bound recovers results from kernel interpolation [ Weinberger and Golomb, 1959 ; Wendland, 2004 ] and linear regression [ Fogel, 1979 ] as special cases. Finally, we contrast the proposed robust treatment to existing bounds for GP regression. Notation The matrix I_{n}\in\mathbb{R}^{n\times n} denotes the identity matrix of dimension n . For a symmetric positive-semidefinite matrix A\in\mathbb{R}^{n\times n} , A^{1/2} denotes the (positive-semidefinite) symmetric matrix square root, i.e., A^{1/2}A^{1/2}=A , and \|x\|_{A}^{2}\doteq x^{\top}Ax denotes the weighted Euclidean norm of a vector x\in\mathbb{R}^{n} . The Dirac delta function is denoted by \delta:\mathbb{R}^{n_{x}}\rightarrow\mathbb{R} , with \delta(x)=1 for x=0 and \delta(x)=0 otherwise. Superscripts f and w will refer to the latent function and the noise, respectively. Accordingly, the kernel function is denoted by k^{\square}\colon\mathbb{R}^{n_{x}}\times\mathbb{R}^{n_{x}}\to\mathbb{R} , with \square\in\{f,w\} , and the associated RKHS is denoted by \mathcal{H}_{k^{\square}} . For two arbitrary ordered sets of indices \mathbb{I},\mathbb{J}\subseteq\mathbb{N} , the matrix K^{\square}_{\mathbb{I},\mathbb{J}}\doteq[k^{\square}(x_{i},x_{j})]_{i\in\mathbb{I},j\in\mathbb{J}} is the Gram matrix collecting the evaluations of the kernel function k^{\square} at pairs of input locations x_{i} , x_{j} , with i\in\mathbb{I} and j\in\mathbb{J} . We denote by 1:N\doteq\{1,\dots,N\}\subseteq\mathbb{N} the set of indices for the training data points, while we use x_{N+1} to represent the arbitrary test input. For instance, K^{f}_{N+1,1:N}\in\mathbb{R}^{1\times N} corresponds to \begin{bmatrix}k^{f}(x_{N+1},x_{1}),\ldots,k^{f}(x_{N+1},x_{N})\end{bmatrix} 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^{\mathrm{tr}}\colon\mathcal{X}\to\mathbb{R} , with \mathcal{X}\subseteq\mathbb{R}^{n_{x}} from noisy measurements \displaystyle y_{i} \displaystyle=f^{\mathrm{tr}}(x_{i})+w^{\mathrm{tr}}(x_{i}),\quad i=1,\ldots,N, (1) collected at known training input locations x_{i}\in\mathcal{X} . Our goal is to compute worst-case uncertainty bounds around the latent function f^{\mathrm{tr}} given the observed data set \mathcal{D}\doteq\{(x_{i},y_{i})\}_{i=1}^{N} , which is subject to the unknown noise w^{\mathrm{tr}}\colon\mathcal{X}\to\mathbb{R} . 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 f^{\mathrm{tr}} and the noise w^{\mathrm{tr}} as elements of an RKHS with a known kernel and a bound on their RKHS norm. Assumption 1 . The unknown latent and noise functions are respective elements of the RKHSs corresponding to the positive-semidefinite kernel k^{f}\colon\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}_{\geq 0} and the positive-definite kernel k^{w}\colon\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}_{\geq 0} , where both k^{f} and k^{w} are uniformly bounded. There exist known constants \Gamma_{f} , \Gamma_{w}>0 strictly bounding their respective RKHS norms, i.e., \|f^{\mathrm{tr}}\|_{\mathcal{H}_{k^{f}}}^{2}<\Gamma_{f}^{2} and \|w^{\mathrm{tr}}\|_{\mathcal{H}_{k^{w}}}^{2}<\Gamma_{w}^{2} . Characterizing boundedness of the noise using a kernel k^{w} and an RKHS-norm bound \Gamma_{w}^{2} 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 or 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 2 . The training input locations in \mathbb{X}\doteq\{x_{1},\ldots x_{N}\} are pairwise distinct, i.e., x_{i}\neq x_{j} for all i,j=1,\ldots,N and i\neq 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 \underline{f}(x_{N+1})\leq f^{\mathrm{tr}}(x_{N+1})\leq\overline{f}(x_{N+1}) for the value of the latent function at an arbitrary test point x_{N+1}\in\mathcal{X} . This task can be formulated as an