Optimal uncertainty bounds for multivariate kernel regression under bounded noise: A Gaussian process-based dual function

1. Problem Statement

The paper addresses the challenge of computing tight, deterministic uncertainty bounds for multivariate kernel-based regression (specifically Gaussian Process regression) when the underlying noise is bounded but distribution-free.

• Context: In safety-critical learning-based control, reliable predictions of latent functions from noisy data are essential. While Gaussian Processes (GPs) offer inherent uncertainty quantification, standard probabilistic bounds often assume specific noise distributions (e.g., Gaussian) and struggle with correlated noise or multi-output systems.
• Limitations of Existing Methods:
  • Probabilistic bounds: Require strong assumptions about noise distribution (e.g., zero-mean, sub-Gaussian) and do not handle adversarial or correlated noise well.
  • Deterministic bounds: Existing approaches for bounded noise are often:
    • Restricted to scalar outputs (not multivariate).
    • Conservative (loose bounds).
    • Computationally expensive (requiring constrained or non-smooth optimization).
    • Difficult to integrate into downstream optimization pipelines (e.g., Model Predictive Control).
• Goal: Derive a tight, distribution-free, multivariate uncertainty bound that can be optimized efficiently and integrated into control pipelines.

2. Methodology

The authors formulate the problem as a worst-case optimization over the Reproducing Kernel Hilbert Space (RKHS) and the noise space, then solve it using Lagrangian duality.

• Problem Formulation:

  • Latent Function: $f_{tr} \in \mathcal{H}_k$ with a bounded RKHS norm ($\|f\|_{\mathcal{H}_k} \leq \Gamma_f$).
  • Observations: $y_i = c_i^\top f_{tr}(x_i) + w_i$, where noise $w$ is bounded by a collection of ellipsoidal uncertainty sets ($w^\top P_j w \leq \Gamma_{w,j}^2$). This generalizes point-wise bounds and energy bounds.
  • Objective: Find the worst-case value of the function in a specific direction $h$ at a test point $x_{N+1}$:
    $$\sup_{f, w} h^\top f(x_{N+1}) \quad \text{s.t. measurement constraints, noise bounds, and RKHS norm bound.}$$

• Dual Formulation (The Core Innovation):

  • The authors derive the dual of the above optimization problem.
  • They show that the optimal worst-case bound corresponds to the unconstrained minimization of a specific dual function with respect to noise parameters $\sigma$.
  • The resulting bound takes a structure familiar to GP practitioners:
    $$f^\sigma_h(x_{N+1}) = h^\top f^\mu_\sigma(x_{N+1}) + \beta_\sigma \sqrt{h^\top \Sigma^\sigma(x_{N+1}) h}$$
    Where $f^\mu_\sigma$ and $\Sigma^\sigma$ are the posterior mean and covariance of a GP, but with a customized noise covariance matrix $K_w^\sigma$ derived from the ellipsoidal noise bounds and the dual variables $\sigma$.
  • Key Property: The dual function is invex (a generalization of convexity). This guarantees that any local minimum found via gradient descent is a global minimum, provided the solution lies within the open domain.

3. Key Contributions

1. Multivariate Extension: The method generalizes existing deterministic bounds (previously limited to scalar outputs) to multivariate (multi-output) functions.
2. Generalized Noise Models: It handles complex noise structures, including ellipsoidal noise bounds (covering correlated noise) and point-wise bounds, unifying them under a single framework.
3. Unconstrained Optimization: Unlike previous deterministic bounds that require solving constrained or non-smooth optimization problems (e.g., L1-norm constraints), the proposed bound is obtained via unconstrained optimization of the noise parameters $\sigma$.
4. Integration with Downstream Tasks: Because the bound is differentiable and unconstrained, the noise parameters $\sigma$ can be optimized simultaneously with the primary control or optimization objective. This allows the uncertainty envelope to be "tightened" dynamically based on the specific needs of the downstream task.
5. Theoretical Unification: The paper proves that many existing results (e.g., bounds from [13]–[16]) are special cases of their proposed formulation.

4. Results

The authors validate their approach through theoretical comparison and a numerical application example involving quadrotor dynamics learning.

• Theoretical Comparison:

  • The proposed bound is shown to be tighter (less conservative) than existing closed-form deterministic bounds (e.g., [12], [13]) because those methods correspond to fixed, suboptimal choices of the dual parameters.
  • It recovers the optimal bounds of [15] and [16] as special cases but improves computational tractability.

• Numerical Experiment (Quadrotor Dynamics):

  • Setup: Estimating residual acceleration of a quadrotor (2 outputs) under wind disturbances modeled as ellipsoidal noise.
  • Methods Compared:
    • CVX-full: Solving the original constrained problem (ground truth, but slow).
    • [15]: Iterative algorithm for point-wise bounds.
    • [12]: Closed-form suboptimal bound.
    • Dual-GD: The proposed method using gradient descent.
  • Performance:
    • Conservatism: The proposed method (Dual-GD) achieves near-optimal tightness (suboptimality < 0.03 for $N=100$), significantly outperforming the closed-form bound [12] (suboptimality ~0.70).
    • Computation Time: While slower than the closed-form [12], Dual-GD is significantly faster than the constrained solver (CVX-full) and competitive with the iterative method [15], especially as data size increases.
    • Scalability: For large datasets ($N=1000$), the method remains effective, though convergence challenges arise when optimal parameters push toward the boundary ($\sigma \to \infty$).

5. Significance

This work bridges the gap between rigorous safety guarantees and practical implementation in learning-based control.

• Safety: It provides distribution-free guarantees, meaning the system remains safe even if the noise is correlated, biased, or adversarial, provided it stays within the defined ellipsoidal bounds.
• Efficiency: By converting a constrained, non-smooth problem into an unconstrained, smooth, invex optimization, it enables the use of efficient gradient-based solvers.
• Applicability: The ability to optimize the uncertainty bound jointly with the control policy makes this method highly suitable for Safe Reinforcement Learning, Bayesian Optimization, and Model Predictive Control (MPC), where tight uncertainty estimates are crucial for performance without sacrificing safety.

In summary, the paper presents a mathematically rigorous yet computationally practical framework for obtaining optimal uncertainty bounds in multivariate kernel regression, overcoming the conservatism and scalability limitations of previous deterministic approaches.