stat.MLNov 5, 2026

pESTO: Iterative p-greedy kernel regression with risk-driven Early STOpping

Authors: L. Bruni Bruno, P. Massa, E. Perracchione, M. Trombini

Organizations: Dipartimento di Scienze Matematiche Giuseppe Luigi Lagrange, Politecnico di Torino, Italy · Gruppo Nazionale per il Calcolo Scientifico INδAM, Rome, Italy · Institute for Data Science, University of Applied Sciences and Arts Northwestern Switzerland, Switzerland

Abstract

Kernel-based greedy algorithms select suitable approximation nodes by minimizing point-wise error indicators, such as the power function; in this context, they are usually referred to as p-greedy approaches. In the presence of noisy data, deterministic criteria may fail, as the discrepancy between the true solution and its estimate is influenced by both approximation error and noise amplification, and the balance between the two is unknown. This study explicitly separates these two contributions, which are governed by the power function and a Lebesgue-type term, respectively. These bounds motivate the use of the Stein's unbiased risk estimator (SURE) as a proxy of the mean squared error, which in turn provides a principled and computable stopping criterion for the number of nodes to select in the p-greedy procedure. Numerical experiments demonstrate that this approach effectively balances deterministic accuracy and statistical noise contributions.

Figures & tables

Explore similar work

Mar 26, 2026

Practical Efficient Global Optimization is No-regret

Efficient global optimization (EGO) is one of the most widely used noise-free Bayesian optimization algorithms.It comprises the Gaussian process (GP) surrogate model and expected improvement (EI) acquisition function. In practice, when EGO is applied, a scalar matrix of a small positive value (also called a nugget or jitter) is usually added to the covariance matrix of the deterministic GP to improve numerical stability. We refer to this EGO with a positive nugget as the practical EGO. Despite its wide adoption and empirical success, to date, cumulative regret bounds for practical EGO have yet to be established. In this paper, we present for the first time the cumulative regret upper bound of practical EGO. In particular, we show that practical EGO has sublinear cumulative regret bounds and thus is a no-regret algorithm for commonly used kernels including the squared exponential (SE) and Matérn kernels (ν>12ν>\frac{1}{2}). Moreover, we analyze the effect of the nugget on the regret bound and discuss the theoretical implication on its choice. Numerical experiments are conducted to support and validate our findings.
Feb 26, 2025

Gaussian Process Upper Confidence Bound Achieves Nearly Optimal Regret in Noise-Free Gaussian Process Bandits

We study the noise-free Gaussian Process (GP) bandits problem, in which the learner seeks to minimize regret through noise-free observations of the black-box objective function lying on the known reproducing kernel Hilbert space (RKHS). Gaussian process upper confidence bound (GP-UCB) is the well-known GP-bandits algorithm whose query points are adaptively chosen based on the GP-based upper confidence bound score. Although several existing works have reported the practical success of GP-UCB, the current theoretical results indicate its suboptimal performance. However, GP-UCB tends to perform well empirically compared with other nearly optimal noise-free algorithms that rely on a non-adaptive sampling scheme of query points. This paper resolves this gap between theoretical and empirical performance by showing the nearly optimal regret upper bound of noise-free GP-UCB. Specifically, our analysis shows the first constant cumulative regret in the noise-free settings for the squared exponential kernel and Matérn kernel with some degree of smoothness.
May 10, 2026

On Uniform Error Bounds for Kernel Regression under Non-Gaussian Noise

Providing non-conservative uncertainty quantification for function estimates derived from noisy observations remains a fundamental challenge in statistical machine learning, particularly for applications in safety-critical domains. In this work, we propose novel non-asymptotic probabilistic uniform error bounds for kernel-based regression. Compared to related bounds in the literature that are restricted to (conditionally) independent sub-Gaussian noise, our bounds allow to consider a broad class of non-Gaussian distributions, such as sub-Gaussian, bounded, sub-exponential, and variance/moment-bounded noise. Moreover, our results apply to correlated and uncorrelated noise. We compare our proposed error bounds with existing results in terms of the induced uncertainty region and their performance in safe control, demonstrating the tightness of the proposed bounds.