Research map / Learning theory and algorithms / Kernels and regression theory

Error Bounds for Gaussian Process Regression Under Bounded Support Noise with Applications to Safety Certification

AAAI 2025 · Learning theory and algorithms › Kernels and regression theory · approach: Kernel regression under shift · 5 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Derives probabilistic and deterministic GP regression error bounds for bounded-support noise using RKHS norm bounds, Hoeffding's inequality, and a convex optimization term, and applies them with stochastic barrier functions to certify safety of unknown systems.

Problem

GP regression error bounds under bounded-support (non-Gaussian) noise are overly conservative in existing works, which limits their use in safety-critical certification.

Approach

Split the GP error into a noise-free mean-approximation term (bounded via RKHS norm and a convex-optimization lower bound c*) and a noise term bounded by Hoeffding's inequality using the bounded noise support; this yields tighter probabilistic and deterministic bounds that work with any sigma_n and with deep kernel learning.

Key results

• Across systems, the proposed probabilistic bound is at least an order of magnitude smaller than prior probabilistic bounds (e.g., 0.57 vs 5.72-7.53 L1 for 2D linear with SE kernel).
• For inverted pendulum with DKL, the proposed probabilistic bound certifies safety probability 0.999 at horizon N=1 with 95% confidence, versus 0.499 for the Lemma 2 deterministic bound.
• DKL priors yield error bounds smaller than the sample-noise level, e.g., 0.11 L1 bound vs noise bound on 3D Dubins car with sigma_v/10 (sigma_n choice).

Measured effects reported in the paper

Surprising findings

• DKL models produce probabilistic error bounds lower than the sample noise bound itself.
• Choosing sigma_n much smaller than sigma_v tightens the bounds, unlike prior results which required sigma_n tied to noise support.

Limitations

• Deterministic bound grows conservatively with noise support, and requires strictly bounded noise and a known RKHS norm bound B.
• Deep kernels are only positive semi-definite, so the approach assumes DKL remains well-behaved and satisfies RKHS norm conditions as stated in a remark rather than proven.
• Offline i.i.d. setting only; online extension is informal.

Experimental setup

Datasets: synthetic data from simulated linear and nonlinear systems (2D linear, 2D nonlinear, 3D Dubins car, 5D car, inverted pen OpenAI Gymnasium leaderboard controller data for inverted pendulum

Benchmarks: 2D linear 2D nonlinear 3D Dubins car 5D second order car inverted pendulum barrier certification 4D linear barrier certification

Metrics: L1 error bound norm true error safety probability P_s barrier synthesis time

Baselines: Chowdhury et al. probabilistic bound (Lemma 1) Hashimoto et al. deterministic bound (Lemma 2) Abbasi-Yadkori et al. probabilistic bound SKKS probabilistic bound

Builds on: Chowdhury and Gopalan GP error bounds for sub-Gaussian noise Abbasi-Yadkori kernel ridge regression bounds Hashimoto et al. kernel ridge regression deterministic bounds stochastic barrier functions Deep Kernel Learning

Closest papers by meaning

• Gaussian Process Uniform Error Bounds with Unknown Hyperparameters for Safety-Critical Applications (ICML 2022 · similarity 0.91)
• Optimal kernel regression bounds under energy-bounded noise (NeurIPS 2025 · similarity 0.88)
• Distributionally Robust Active Learning for Gaussian Process Regression (ICML 2025 · similarity 0.87)
• New Bounds for Sparse Variational Gaussian Processes (ICML 2025 · similarity 0.86)
• Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Bandits (NeurIPS 2025 · similarity 0.85)
• Robust and Computation-Aware Gaussian Processes (NeurIPS 2025 · similarity 0.85)