Relative Information Gain and Gaussian Process Regression

Hamish Flynn

TL;DR

This paper introduces the relative information gain, a novel complexity measure that bridges the gap between effective dimension and mutual information in kernel methods. By embedding this quantity into a localized PAC-Bayesian excess risk framework, the author establishes minimax-optimal convergence rates for Gaussian process regression under both polynomial and exponential kernel eigenvalue decay, without suffering from the extraneous logarithmic factors that typically plague standard information-theoretic bounds.

What Problem Does This Paper Address?

In kernel ridge regression (KRR) and Gaussian process (GP) bandits, two primary quantities measure the difficulty of learning an unknown function $f^* \in \mathcal{H}$:

  1. Effective Dimension $d_n(\eta)$: Characterizes optimal estimation error rates, but lacks a clean, intuitive information-theoretic meaning.
  2. Maximum Information Gain $\gamma_n(\eta)$: Measures the mutual information between the unknown function and the noisy observations. While mathematically intuitive, its growth rate can be larger than $d_n(\eta)$ by up to a factor of $\log(n)$, yielding suboptimal rates of convergence.

Standard PAC-Bayesian generalization bounds for GPs inherently introduce the mutual information $\gamma_n$, making derived rates suboptimal by poly-logarithmic factors. This paper sets out to answer: Can we find a quantity with an information-theoretic flavor that retains the tighter growth rate of the effective dimension, and use it to prove optimal excess risk bounds in GP regression?

Methods

  • Relative Information Gain: Defined as the difference in information gain under two different observation noise levels (learning rates) $\eta > \beta \ge 0$: $$\gamma_n(\eta, \beta) := \gamma_n(\eta) - \gamma_n(\beta)$$
  • Interpolation & Derivative Connection: Drawing on the I-MMSE relationship from information theory (Guo et al., 2005), the author connects $d_n(\eta)$ to the derivative of $\gamma_n(\eta)$ ($d_n(\eta) = 2\eta \gamma'_n(\eta)$). The scaled relative information gain smoothly interpolates between $d_n(\eta)$ (as $\beta \to \eta^-$) and $2\gamma_n(\eta)$ (when $\beta = 0$).
  • Localized PAC-Bayes Analysis: Standard PAC-Bayes bounds evaluate the Kullback–Leibler (KL) divergence against an uninformative prior $P_\alpha$, leading directly to $\gamma_n(2\eta\alpha)$. Using Catoni’s localization technique, the author substitutes a data-dependent Gibbs prior $Q_{n, \beta, \alpha}$ (with a smaller learning rate $\beta < \eta$). The resulting KL divergence between the posterior and localized prior naturally produces the relative log-determinant: $$\frac{1}{2} \log \det\left(\frac{2\eta\alpha \mathbf{K}_n + \mathbf{I}}{2\beta\alpha \mathbf{K}_n + \mathbf{I}}\right) = \gamma_n(2\eta\alpha, 2\beta\alpha)$$

Datasets

  • Real-world Datasets: Not discussed in the paper (the paper is purely theoretical).
  • Synthetic Evaluation: A 1D simulation using the squared exponential (Gaussian) kernel on $x_i \sim \text{Uniform}[0, 1]$ across sample sizes $n \in [1, 3000]$ (averaged over 20 runs) was conducted to compare the empirical scaling rates of $d_n(\eta)$, $\gamma_n(\eta, \beta)$, and $\gamma_n(\eta)$.

Key Insights and Ideas

  • Thinner Sandwich Bounds: Calandriello et al. (2019) bounded $d_n(\eta) \le 2\gamma_n(\eta) \le \mathcal{O}(d_n(\eta)\log n)$. This paper shows a significantly tighter sandwich: for $\beta = c\eta$ ($c \in (0, 1)$), $$d_n(\eta) \le \frac{2\eta}{\eta - \beta} \gamma_n(\eta, \beta) \le \frac{\eta}{\beta} d_n(\eta)$$ Hence, relative information gain has strictly the same growth rate as the effective dimension.

  • Physical Interpretation: The relative information gain quantifies the marginal information gained when measurement noise variance drops from $1/\beta$ to $1/\eta$.

  • Saving Log Factors in Subspace Decomposition: Bounding $\gamma_n$ typically involves projecting onto the leading $D$ eigenfunctions of a Mercer kernel, which incurs a $\frac{1}{2}D \log(1 + \frac{k n \eta}{D})$ factor (growing with $\log n$). For relative information gain, bounding the ratio of gram matrix determinants replaces this term with $\frac{1}{2}D \log(\eta / \beta)$, which is constant with respect to $n$.

Key Results

  • Empirical Separation: In 1D Gaussian kernel experiments, $\mathbb{E}[\gamma_n(1)] \approx 0.267 \log^{8/5}(n) + 0.347$, whereas the relative information gain scaled as $\mathbb{E}[\gamma_n(1, 1/2)] \approx 0.113 \log(n) + 0.144$, experimentally confirming a gap of approximately $\log^{3/5}(n)$.
  • PAC-Bayesian Excess Risk Bound (Theorem 5): $$\int R_n(g) dQ_{n,\eta,\alpha}(g) \le \frac{2\gamma_n(2\eta\alpha, 2\beta\alpha) + \frac{1}{2\alpha}\|f^*\|_\mathcal{H}^2 + 2\log(1/\delta)}{n(\eta - 2\sigma^2\eta^2 - \beta - 2\sigma^2\beta^2)}$$ (Also bounds the excess risk of standard kernel ridge regression via Jensen’s inequality).
  • Minimax-Optimal Rates: Combining the excess risk bound with Mercer spectral decays yields:
  • Polynomial Eigenvalue Decay ($\xi_i \le C_p i^{-\beta_p}$): Excess risk scales as $\mathcal{O}\left(n^{-\frac{\beta_p}{1+\beta_p}}\right)$ with $\alpha = n^{-\frac{1}{1+\beta_p}}$, exactly matching the minimax lower bounds for Sobolev spaces without extraneous $\log$ terms.
  • Exponential Eigenvalue Decay ($\xi_i \le C_{e,1} e^{-C_{e,2} i^{\beta_e}}$): Excess risk scales as $\mathcal{O}\left(\frac{\log^{1/\beta_e}(n)}{n}\right)$ with $\alpha = 1$, matching the optimal rate.

Limitations and Future Work

  • Fixed-Design Setting: The current proofs assume deterministic inputs $x_1, \ldots, x_n$ (fixed design) and positive-definite kernel matrices $\mathbf{K}_n$.
  • Known Target Class: The derivations assume the true function lies strictly inside the RKHS ($f^* \in \mathcal{H}$); well-specified settings were assumed throughout.
  • Future Directions:
  • Extending the localized PAC-Bayes framework to random-design regression.
  • Exploring misspecified kernel regression scenarios ($f^* \notin \mathcal{H}$).
  • Adapting the bounds to sparse or approximate Gaussian process inference schemes (e.g., Nyström approximations or inducing point methods).

Summary updated

Abstract

The sample complexity of estimating or maximising an unknown function in a reproducing kernel Hilbert space is known to be linked to both the effective dimension and the information gain associated with the kernel. While the information gain has an attractive information-theoretic interpretation, the effective dimension typically results in better rates. We introduce a new quantity called the relative information gain, which measures the sensitivity of the information gain with respect to the observation noise. We show that the relative information gain smoothly interpolates between the effective dimension and the information gain, and that the relative information gain has the same growth rate as the effective dimension. In the second half of the paper, we prove a new PAC-Bayesian excess risk bound for Gaussian process regression. The relative information gain arises naturally from the complexity term in this PAC-Bayesian bound. We prove bounds on the relative information gain which depend on the spectral properties of the kernel. When these upper bounds are combined with our excess risk bound, we obtain minimax-optimal rates of convergence.
BibTeX
@inproceedings{flynn2026relative,
  author = {Hamish Flynn},
  title = {{Relative Information Gain and Gaussian Process Regression}},
  booktitle = {ALT},
  year = {2026},
  url = {https://openreview.net/forum?id=PXg1o5NhSk},
}
Figure