Research map / Learning theory and algorithms / Kernels and regression theory
Optimal kernel regression bounds under energy-bounded noise
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 a tight, non-asymptotic worst-case uncertainty bound for kernel-based estimation under RKHS-norm-bounded (energy-bounded) latent and noise functions, reducing it to a scalar optimization over a noise-scale parameter sigma that reuses GP posterior mean and covariance.
Problem
Computing non-conservative, non-asymptotic uncertainty bounds for kernel-based (GP-style) estimates when the noise may be correlated or biased, using only a bounded-energy (RKHS-norm) assumption on the latent function and noise.
Approach
Shows the worst-case latent function value at a test point under joint RKHS-norm constraints on latent and noise equals the infimum over a noise scale sigma of a relaxed GP-style bound (posterior mean plus beta_sigma times posterior std), giving an exact scalar unconstrained reformulation that recovers kernel interpolation and set-membership linear-regression bounds as special cases.
Key results
- In the low-data regime (small N) the proposed optimal and relaxed bounds are significantly less conservative than a sub-Gaussian high-probability bound, as shown by uncertainty-region area vs. number of data points N=1..1000.
- In the safe-control experiment, the proposed bound using the full dataset achieves the highest feasibility success rate, while the nearest-10-points variant has solve times independent of dataset size and similar success to probabilistic bounds.
- The optimal bound reduces in closed form to a sqrt(K_{N+1,N+1})*Gamma_f prior-covariance bound (Case 1) or to y_k + sqrt(K^w_{kk})*Gamma_w at training inputs (Case 2, Corollary).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the optimal energy-bounded-noise kernel regression bound instead of the relaxed bound with fixed σ = ε | Kernel regression uncertainty bounds · Low-data regime | uncertainty-region area | Helped |
| increase the number of training points under energy-bounded-noise bounds | Proposed and relaxed bounds · Kernel regression numerical comparison | uncertainty-region area | No clear effect |
| increase the number of training points under independent-noise probabilistic bounds | High-probability bound · Kernel regression numerical comparison | uncertainty-region area | Helped |
| use the optimal energy-bounded-noise bound instead of the probabilistic bound | Safe-control uncertainty bounds · Safe control for uncertain nonlinear systems | success rate | Helped |
| use only the nearest 10 training points instead of the full data set (ablation) | Proposed bound · Safe control for uncertain nonlinear systems | success rate | Mixed |
| use only the nearest 10 training points instead of the full data set (ablation) | Proposed bound · Safe control for uncertain nonlinear systems | computation time | Helped |
| use the optimal point-wise-bounded-noise bound instead of the proposed energy-bounded-noise bound | Kernel regression uncertainty bounds · More than one data point under point-wise-bounded noise | bound tightness | Helped |
Surprising findings
- Bounds under bounded-energy noise stay non-shrinking beyond a certain N, since multiple similar points give no extra information without probabilistic assumptions.
Limitations
- Relies on known RKHS-norm bounds Gamma_f and Gamma_w and on correct kernel specification, which are not validated rigorously.
- Robustness to kernel mis-specification and to wrong norm bounds is not rigorously analyzed.
- Computational cost of the full-data version grows with the number of training points.
Experimental setup
Benchmarks: synthetic 1D kernel regression uncertainty region area safe control of uncertain nonlinear system
Metrics: area of uncertainty region success rate solve time
Baselines: high-probability GP bounds (sub-Gaussian noise) pointwise-bounded noise optimal bounds sum-of-kernels interpolation bounds set-membership linear regression bounds
Builds on: Gaussian process regression representer theorem set-membership estimation
Closest papers by meaning
- Error Bounds for Gaussian Process Regression Under Bounded Support Noise with Applications to Safety Certification (AAAI 2025 · similarity 0.88)
- Regularized least squares learning with heavy-tailed noise is minimax optimal (NeurIPS 2025 · similarity 0.86)
- Kernel conditional tests from learning-theoretic bounds (NeurIPS 2025 · similarity 0.85)
- Kernelized Normalizing Constant Estimation: Bridging Bayesian Quadrature and Bayesian Optimization (AAAI 2024 · similarity 0.85)
- Robust Statistical Estimators with Bounded Empirical Sensitivity (NeurIPS 2026 · similarity 0.85)
- The Minimax Rate of HSIC Estimation for Translation-Invariant Kernels (NeurIPS 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.