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}$:
- Effective Dimension $d_n(\eta)$: Characterizes optimal estimation error rates, but lacks a clean, intuitive information-theoretic meaning.
- 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