ML and AI Theory Seminar | University of California, Berkeley

Posterior Contraction Rates for Matérn
Gaussian Processes on Riemannian Manifolds

Viacheslav (Slava) Borovitskiy

https://vab.im

Talk outline

Introduction

  • Gaussian processes
  • Geometric Gaussian processes
  • Are they actually useful?

Posterior contraction rates

  • Intrinsic processes
  • Extrinsic processes

Beyond rates

  • Error decay on specific manifolds

Summary

Gaussian processes

Background: Gaussian processes (GPs)

Gaussian processes — random functions with jointly Gaussian marginals.

Determined by a mean and a kernel (covariance function).

Bayesian learning: prior GP + data = posterior GP

For zero prior mean and Gaussian noise of variance $\sigma_{\eps}^2$:

$$ \begin{aligned} \underbrace{m_{\text{post}}(\.)}_{\text{prediction}} &= \m{K}_{(\.) \v{x}} \del{\m{K}_{\v{x} \v{x}} + \sigma_{\eps}^2 \m{I}}^{-1} \v{y} \\[0.3em] \underbrace{k_{\text{post}}(\., \.')}_{\text{uncertainty}} &= \m{K}_{(\., \.')} - \m{K}_{(\.) \v{x}} \del{\m{K}_{\v{x} \v{x}} + \sigma_{\eps}^2 \m{I}}^{-1} \m{K}_{\v{x} (\.')} \end{aligned} $$

Why are they useful? Model-based decision-making

Probabilistic models: input ⟶ distribution (prediction + uncertainty)

Allows computing queries like probability of improvement: $\!\alpha(x) \!=\! \mathbb{P} \! \del{f(x) \!>\!\! f^*}$

They can drive selection of the next point to evaluate [Bayesian optimization]

Background: General-purpose GPs in $\R^d$

Matérn kernels:

$$ \footnotesize k_{\nu, \kappa, \sigma_f^2}(x,x') = \sigma_f^2 \frac{2^{1-\nu}}{\Gamma(\nu)} \del{\sqrt{2\nu} \frac{\abs{x-x'}}{\kappa}}^\nu K_\nu \del{\sqrt{2\nu} \frac{\abs{x-x'}}{\kappa}} $$

$\sigma_f^2$: variance

$\kappa$: length scale

$\nu$: smoothness

$K_\nu$: Bessel function

$\nu = 1/2$

$\nu = 3/2$

$\nu = 5/2$

Geometric Gaussian processes

Geometric domains

Manifolds
e.g. for robotics

Graphs
e.g. for road networks

Spaces of graphs
e.g. for drug design

Geometric GPs: models defined on such domains that respect their structure.

Defining them: Dead end

In the squared exponential kernel, use the geodesic distance:

$$ k(x,x') = \sigma_f^2\exp\del{-\frac{ \mathrlap{\htmlData{class=fragment fade-out,fragment-index=1}{\mkern14mu \abs{x - x'}^2}} \mathrlap{\htmlData{class=fragment,fragment-index=1}{\f{dist}(x, x')^2}} \hphantom{\f{dist}(x, x')^2} }{2\kappa^2}} $$

Not positive semi-definite for some $\kappa$.

Graphs, unless isometrically
embeddable into a Hilbert space.

Schoenberg (Trans. Am. Math. Soc. 1938)

Manifolds, unless
isometric to $\R^d$.

Feragen et al. (CVPR 2015), Da Costa et al. (SIMODS 2025)

Defining them: stochastic partial differential equations

$$ \htmlData{class=fragment,fragment-index=0}{ \ubr{\del{\frac{2\nu}{\kappa^2} - \Delta}^{\frac{\nu}{2}+\frac{d}{4}} f = \c{W}}{\t{Matérn}} } $$

$\Delta$: Laplacian

$\c{W}$: Gaussian white noise

$d$: dimension

Generalizes well

Same inductive biases: stationary and smooth

Implicit: no formula for the kernel

Whittle (Bull. Internat. Statist. Inst 1963)

Lindgren et al. (JRSSB 2011)

Making it explicit: Compact manifolds

Intrinsic Matérn prior, through its Karhunen–Loève expansion:

$$ f(\.) = \frac{\sigma_f}{\sqrt{C_{\nu, \kappa}}} \sum_{j=0}^{\infty} \del{\frac{2\nu}{\kappa^2} + \lambda_j}^{-\frac{\nu + d/2}{2}} \mkern-16mu \xi_j f_j(\.) $$

$\xi_j \stackrel{\text{i.i.d.}}{\sim} \c{N}(0, 1)$

$\lambda_j, f_j$: Laplace–Beltrami eigenpairs

$C_{\nu, \kappa}$: normalization

Matérn kernels $k(\bullet, x)$

Borovitskiy et al. – Matérn Gaussian Processes on Riemannian Manifolds (NeurIPS 2020)

Geometric GPs in practice

Robotics

Learn the orientation of a robotic arm
with less data than baselines.

Jaquier et al. (CoRL 2022)

Medicine

Regression on a manifold which models
the geometry of a human heart.

Coveney et al. (Phil. Trans. A 2020)

All good and well.
But are they actually useful?

The alternative: Just use the ambient space

$\c{M} \subset \R^D$, isometrically embedded.

Take the ordinary Matérn kernel, with the Euclidean distance $\norm{x - x'}_{\R^D}$,
and restrict it to $x, x' \in \c{M}$. This is the extrinsic Matérn prior.

Intrinsic

Formulated directly on the manifold.
Need to know $\c{M}$.

Extrinsic

Agnostic to the manifold geometry.
Works even when $\c{M}$ is unknown.

Intrinsic vs. extrinsic: Samples

Intrinsic

Extrinsic

Close in the ambient space,
far along the manifold:
spurious dependencies.

Intrinsic

Extrinsic

Distances are approximated well:
little qualitative difference.

The question

Wouldn't it be great to have a proof
that intrinsic models are better than ambient ones?

I met Paul Rosa, working on the same question, hence the paper:

(PhD student at Oxford at the time, now a postdoc in Cambridge)

Posterior Contraction Rates for Matérn Gaussian Processes on Riemannian Manifolds
P. Rosa, V. Borovitskiy, A. Terenin, J. Rousseau
NeurIPS 2023 (spotlight)

The angle:
Posterior contraction rates

Setting: Random design regression

Truth

$$ \begin{aligned} y_i \given x_i &\sim \c{N}(f_0(x_i), \sigma_{\eps}^2) \\ x_i &\sim p_0 \end{aligned} $$

Model

$$ \begin{aligned} y_i \given x_i, f &\sim \c{N}(f(x_i), \sigma_{\eps}^2) \\ f &\sim \Pi \end{aligned} $$
  • $\c{M} \subset \R^D$: smooth, compact, no boundary, of dimension $d < D$.
  • $p_0$: density w.r.t. the Riemannian volume, bounded above and below.
  • $\sigma_{\eps}^2$: fixed and known. $\;\Pi$: a Gaussian process.

Does the posterior uncover $f_0$ as $n \to \infty$? How fast?

Posterior contraction rate

$$ \htmlData{class=fragment,fragment-index=0}{ \underbrace{\E_{\v{x}, \v{y}}}_{\text{true data}} \, \underbrace{\E_{f \sim \Pi(\. \given \v{x}, \v{y})}}_{\text{posterior}} \norm{f - f_0}_{L^2(p_0)}^2 \; } \htmlData{class=fragment,fragment-index=1}{ \leq \; C \underbrace{\eps_n^2}_{\text{rate}} } $$

By Jensen's inequality, the posterior mean $m_{\text{post}}$ inherits the rate.

What is known: The Euclidean case

$f$: Matérn prior on $[0, 1]^d$, with smoothness $\nu > d/2$.

$f_0 \in H^\beta \cap \mathrm{C}\mathrm{H}^\beta$ (Sobolev and Hölder), with $\beta > d/2$.

$$ \E_{\v{x}, \v{y}} \E_{f \sim \Pi(\. \given \v{x}, \v{y})} \norm{f - f_0}_{L^2(p_0)}^2 \leq C n^{-\frac{2 \min(\beta, \nu)}{2 \nu + d}} $$

Best when true and prior smoothness match, $\nu = \beta$: $\;n^{-\frac{2 \beta}{2 \beta + d}}$

van der Vaart and van Zanten (JMLR 2011)

Optimal in which sense?

Minimax: no estimator does better uniformly over a smoothness class.

$$ \inf_{\h{f}} \, \sup_{f_0 \in \c{F}_\beta} \E_{\v{x}, \v{y}} \norm{\h{f}(\v{x}, \v{y}) - f_0}_{L^2(p_0)}^2 \asymp n^{-\frac{2 \beta}{2 \beta + d}} $$

$\h{f}$: any estimator, a rule mapping data to functions. $\;\c{F}_\beta$: a ball in $H^\beta \cap \mathrm{C}\mathrm{H}^\beta$.

The posterior mean attains this at $\nu = \beta$: $C$ depends only on norms of $f_0$.

Tsybakov (2008)

First: Intrinsic processes

Smoothness on a manifold

Sobolev space $H^s(\c{M})$: decay of Laplace–Beltrami coefficients.

$$ \norm{f}_{H^s(\c{M})}^2 = \sum\nolimits_{j \geq 0} (1 + \lambda_j)^s \abs{\innerprod{f}{f_j}_{L^2(\c{M})}}^2 $$

Besov space $B_{\infty, \infty}^s(\c{M})$: Hölder-like, via approximation by low frequencies.

$$ \norm{f}_{B_{\infty, \infty}^s(\c{M})} = \norm{f}_{L^\infty(\c{M})} + \sup_{j \geq 0} 2^{j s} \norm{P_j f - f}_{L^\infty(\c{M})} $$

$P_j$: smooth low-pass filter, keeps $\sqrt{\lambda_l} \leq 2^j$ and removes $\sqrt{\lambda_l} \geq 2^{j + 1}$.

Result #1: Intrinsic Matérn

$f$: intrinsic Matérn prior with smoothness $\nu > d/2$.

$f_0 \in H^\beta(\c{M}) \cap B_{\infty, \infty}^\beta(\c{M})$ with $\beta > d/2$.

$$ \E_{\v{x}, \v{y}} \E_{f \sim \Pi(\. \given \v{x}, \v{y})} \norm{f - f_0}_{L^2(p_0)}^2 \leq C n^{-\frac{2 \min(\beta, \nu)}{2 \nu + d}} $$

Minimax optimal at $\nu = \beta$, with the intrinsic dimension $d$.

Yay!

Same rate when truncating the series to $J_n \geq c \, n^{d \min(1, \nu / \beta) / (2 \nu + d)}$ terms.

Proof idea: The concentration function

Gaussian prior with continuous sample paths and RKHS $\bb{H}$:

$$ \htmlData{class=fragment,fragment-index=0}{ \varphi_{f_0}(\eps) = \underbrace{- \ln \P \del{\norm{f}_{L^\infty(\c{M})} < \eps}}_{\text{small ball}} + \underbrace{\inf_{g \in \bb{H}: \, \norm{g - f_0}_{L^\infty(\c{M})} < \eps} \norm{g}_{\bb{H}}^2}_{\text{decentering}} } $$

If $\;\varphi_{f_0}(\eps_n) \leq n \eps_n^2$, the posterior contracts at the input locations:

$$ \E_{\v{y} \given \v{x}} \E_{f \sim \Pi(\. \given \v{x}, \v{y})} \frac{1}{n} \sum_{i=1}^n \abs{f(x_i) - f_0(x_i)}^2 \lesssim \eps_n^2 $$

Holds for every fixed $\v{x}$, with the same constant.

van der Vaart and van Zanten (JMLR 2011, Theorem 1), on any compact metric space

Proof idea: The plan

  1. Identify the RKHS $\bb{H}$.
  2. Bound $\varphi_{f_0}$: this gives the rate $\eps_n$ at the input locations.
  3. Go from the input locations to the whole manifold.

Proof idea, 1/3: The RKHS

The covariance operator is diagonal in the $f_j$,
with eigenvalues $\asymp (1 + \lambda_j)^{-(\nu + d/2)}$.

$$ \norm{\sum\nolimits_{j} a_j f_j}_{\bb{H}}^2 \asymp \sum\nolimits_{j} (1 + \lambda_j)^{\nu + d/2} \abs{a_j}^2 $$

So $\bb{H} = H^{\nu + d/2}(\c{M})$, with equivalent norms.

The length scale $\kappa$ only changes the constants.

Follows Borovitskiy et al. (NeurIPS 2020)

Proof idea, 2/3: The small ball

Small ball probabilities are governed by the entropy of the RKHS unit ball:

$$ \underbrace{\ln N(\eps)}_{\text{entropy}} \lesssim \eps^{-\frac{d}{\nu + d/2}} \quad \Longrightarrow \quad - \ln \P \del{\norm{f}_{L^\infty(\c{M})} < \eps} \lesssim \eps^{-\frac{d}{\nu}} $$

$N(\eps)$: number of uniform $\eps$-balls needed to cover the unit ball of $\bb{H}$.

By step 1, the unit ball of $\bb{H}$ lies in a Sobolev ball on $\c{M}$.

Charts reduce the entropy of that ball to the known bound on $\R^d$.

Implication: Li and Linde (Annals of Probability 1999). Entropy on $\R^d$: Giné and Nickl (2015)

Proof idea, 2/3: The decentering

We need $g \in \bb{H}$ uniformly $\eps$-close to $f_0$, with a small RKHS norm.

$f_0$ itself need not lie in $\bb{H} = H^{\nu + d/2}(\c{M})$: it may be too rough.

Instead, keep only its low frequencies: $\;g = P_j f_0 \in \bb{H}$.

Higher cutoff: smaller error

$$ \norm{g - f_0}_{L^\infty(\c{M})} \lesssim 2^{-\beta j} $$

Because $f_0 \in B_{\infty, \infty}^\beta(\c{M})$.

Higher cutoff: larger norm

$$ \norm{g}_{\bb{H}}^2 \lesssim 2^{2 j (\nu + \frac{d}{2} - \beta)} $$

Because $f_0 \in H^\beta(\c{M})$, for $\nu \geq \beta$.

Taking $\;2^{-\beta j} \approx \eps\;$ gives $\;\norm{g}_{\bb{H}}^2 \lesssim \eps^{-\frac{2}{\beta} (\nu + \frac{d}{2} - \beta)}$.

Proof idea, 2/3: The rate

For $\nu \geq \beta$, the decentering term dominates:

$$ \varphi_{f_0}(\eps) \lesssim \eps^{-\frac{d}{\nu}} + \eps^{-\frac{2}{\beta} (\nu + \frac{d}{2} - \beta)} \lesssim \eps^{-\frac{2}{\beta} (\nu + \frac{d}{2} - \beta)} $$

Solving $\;\varphi_{f_0}(\eps_n) \leq n \eps_n^2\;$ gives $\;\eps_n \propto n^{-\frac{\beta}{2 \nu + d}}$.

For $\beta > \nu$: also $f_0 \in H^\nu(\c{M}) \cap B_{\infty, \infty}^\nu(\c{M})$, so replace $\beta$ by $\nu$.

Altogether, $\;\eps_n \propto n^{-\frac{\min(\beta, \nu)}{2 \nu + d}}$.

Proof idea, 3/3: To the whole manifold

From the input locations to $\;\norm{f - f_0}_{L^2(p_0)}$.

We follow van der Vaart and van Zanten (JMLR 2011, Theorem 2).

The main change: we must prove Hölder regularity of prior samples on $\c{M}$.

$$ \E \norm{f}_{\mathrm{C}\mathrm{H}^\gamma(\c{M})}^2 < \infty \quad \text{for a version of } f \text{ and all } \gamma < \nu $$

Otherwise, a rough $f$ could fit at the inputs and miss elsewhere.

Driscoll's theorem and Sobolev embedding only give $\gamma < \nu - d/2$.

Instead, we use Kolmogorov's criterion in charts.
The hard case is $\gamma > 1$, where it must be applied to derivatives of $f$.

Next: Extrinsic processes

What should we expect?

The extrinsic process is completely agnostic to the manifold geometry.

We would expect it to be less performant.

A slower rate would be the proof we were hoping for.

Result #2: Extrinsic Matérn

$f$: extrinsic Matérn prior with smoothness $\nu > d/2$.

$f_0 \in H^\beta(\c{M}) \cap B_{\infty, \infty}^\beta(\c{M})$ with $\beta > d/2$.

$$ \E_{\v{x}, \v{y}} \E_{f \sim \Pi(\. \given \v{x}, \v{y})} \norm{f - f_0}_{L^2(p_0)}^2 \leq C n^{-\frac{2 \min(\beta, \nu)}{2 \nu + d}} $$

The same rate. Yikes!

The dimension in the exponent is $d$. $D$ enters through the constant $C$.

The prior is not designed to be adaptive, but it adapts to the manifold.

What changes in the proof? Mainly the RKHS

Restriction

$$ \norm{h}_{\bb{H}} = \inf_{g|_{\c{M}} = h} \norm{g}_{\tilde{\bb{H}}} $$

Ambient RKHS: $\tilde{\bb{H}} = H^{\nu + D/2}(\R^D)$,
with equivalent norms.

Trace and extension

$$ H^{s}(\R^D) \,\xrightleftharpoons[\;\f{Ex}\;]{\;\f{Tr}\;}\, H^{s - \frac{D - d}{2}}(\c{M}) $$

Bounded linear maps, $\f{Tr} \o \f{Ex} = \f{id}$,
for $s > \frac{D - d}{2}$.

Restricting to $\c{M}$ loses $\frac{D - d}{2}$ of smoothness: $\;\nu + \frac{D}{2} - \frac{D - d}{2} = \nu + \frac{d}{2}$.

$\bb{H}$ is norm-equivalent to $H^{\nu + d/2}(\c{M})$, as for the intrinsic process!

Große and Schneider (Math. Nachrichten 2013)

This actually makes sense

Up to norm equivalence, the RKHS is determined by $\nu$ only.

So the rates do not see the length scale $\kappa$ either.

Similar in spirit to Yang and Dunson (Annals of Statistics 2016).

Extrinsic mixtures of squared exponential GPs: optimal rates for Hölder smoothness $\leq 2$.

In this setting, asymptotic rates cannot detect geometry.

So is this whole framework
of geometric GPs useless?

Beyond rates: Worst-case error

Differences are down to constants. So we look at errors numerically.

$$ v^{(\tau)}(t) = \sup_{\norm{f_0}_{\bb{H}^{(\mathrm{i})}} \leq 1} \E_{\v{\eps}} \abs{m_{\text{post}}^{(\tau)}(t) - f_0(t)}^2 $$

$\tau = \mathrm{i}$: intrinsic. $\;\tau = \mathrm{e}$: extrinsic. $\;\bb{H}^{(\mathrm{i})}$: the intrinsic RKHS.

Inputs $\v{x}$ fixed, $\;\v{y} = f_0(\v{x}) + \v{\eps}$, with $\v{\eps}$ the noise.

A function of $t \in \c{M}$: shows how error varies across the manifold.

Beyond rates: How to compute it

Posterior means are linear in the data, with weights:

$$ \v{\alpha}_t^{(\tau)} = \m{K}_{t \v{x}}^{(\tau)} \del{\m{K}_{\v{x} \v{x}}^{(\tau)} + \sigma_{\eps}^2 \m{I}}^{-1} $$

Reproducing property, then supremum over the unit ball:

$$ v^{(\tau)}(t) = \norm{k^{(\mathrm{i})}(t, \.) - \sum\nolimits_{j} \alpha_{t j}^{(\tau)} k^{(\mathrm{i})}(x_j, \.)}_{\bb{H}^{(\mathrm{i})}}^2 + \sigma_{\eps}^2 \norm{\v{\alpha}_t^{(\tau)}}^2 $$

Intrinsic

Simply the posterior variance.

Extrinsic

Approximate the norm numerically,
on points sampled uniformly from $\c{M}$.

Beyond rates: The setup

Intrinsic kernel

Extrinsic kernel

Intrinsic kernel

Extrinsic kernel

  • Meshes of a dumbbell, a sphere and the Stanford dragon.
  • Extrinsic length scale: maximum marginal likelihood, to make it fair.
  • $J = 500$ eigenpairs, $\;\sigma_f^2 = 1$, $\;\sigma_{\eps}^2 = 0.0005$, $\;10$ repetitions.

Beyond rates: The plots

Mean of $v^{(\tau)}(t)$ over $t \in \c{M}$. Shading: spread over the 10 repetitions.

Beyond rates: What the plots say

Dumbbell, dragon

Geometry differs from the ambient space.
Intrinsic: lower errors.

Sphere

No bottleneck-like areas.
Both models perform similarly.

The gap depends on the geometry, but the rates alone do not show it.

Summary

Summary

  • Intrinsic and extrinsic Matérn GPs: the same (optimal) rates.
  • Rates are a guarantee a reasonable model should satisfy, rather than a distinguishing feature.
  • Constants hide the key differences.
Main author
Paul Rosa
Paper Info
Posterior Contraction Rates for Matérn Gaussian Processes on Riemannian Manifolds
P. Rosa, V. Borovitskiy, A. Terenin, J. Rousseau
NeurIPS 2023 (spotlight)