Source-linked AI summary
Convergence of Sparse Variational Inference in Gaussian Processes Regression
David R. Burt, Carl Edward Rasmussen, Mark van der Wilk
TL;DR
Exact Gaussian process inference is costly at large N, while sparse methods require theoretical guidance on how many inducing variables preserve posterior quality. This paper derives bounds for variational sparse inference and examines inducing-point placement; for some kernels and inputs, its bounds characterize inducing-variable requirements and inform practical selection.
Problem
Sparse approximations reduce the computational burden of Gaussian process inference, but their effects on posterior quality and hyperparameter selection are not well understood.
Source: §1 · p. 2Method
The paper derives bounds for variational inference quality and analyzes inducing-point placement and posterior KL-divergence.
Source: §3 · p. 10, §4.2.2 · p. 16Results
The paper gives upper and lower bounds on inducing-variable requirements and reports that, for squared exponential kernels with Gaussian covariates, the bounds have matching dependence on dataset size.
Source: §8 · pp. 44–45Takeaways & Limitations
The bounds provide insight into inducing-point counts for different tasks and suggest which problems suit sparse variational inference.
Source: §8 · p. 45Direct analysis of gradient-based inducing-point placement is beyond the analysis because ELBO optimization is high-dimensional and non-convex.
Source: §4.2.2 · p. 16
Abstract
from arXiv · showhide
Gaussian processes are distributions over functions that are versatile and mathematically convenient priors in Bayesian modelling. However, their use is often impeded for data with large numbers of observations, $N$, due to the cubic (in $N$) cost of matrix operations used in exact inference. Many solutions have been proposed that rely on $M \ll N$ inducing variables to form an approximation at a cost of $\mathcal{O}(NM^2)$. While the computational cost appears linear in $N$, the true complexity depends on how $M$ must scale with $N$ to ensure a certain quality of the approximation. In this work, we investigate upper and lower bounds on how $M$ needs to grow with $N$ to ensure high quality approximations. We show that we can make the KL-divergence between the approximate model and the exact posterior arbitrarily small for a Gaussian-noise regression model with $M\ll N$. Specifically, for the popular squared exponential kernel and $D$-dimensional Gaussian distributed covariates, $M=\mathcal{O}((\log N)^D)$ suffice and a method with an overall computational cost of $\mathcal{O}(N(\log N)^{2D}(\log\log N)^2)$ can be used to perform inference.
1. Introduction
Exact Gaussian process inference has O(N^3) computational cost, motivating sparse approximations whose posterior quality and inducing-variable requirements need theoretical characterization. This work analyzes that trade-off and derives bounds and practical selection guidance, including near-linear-cost inference for specified kernels and covariate distributions.
1. Introduction
- The analysis studies how inducing-variable count controls computational cost and the KL-divergence between approximate and exact posteriors.The work also gives practical guidance on inducing-variable selection and the problems for which sparse variational inference is well suited.Source: §1 · p. 2
1.1 Our Contributions
- For squared exponential kernels with Gaussian or compactly supported inputs, O((log N)^D) inducing variables suffice for arbitrarily accurate approximations with high probability, at O(N(log N)^{2D}(log log N)^2) cost.D is fixed, so the stated scaling in N is nearly linear.Source: §1.1 · p. 2
- KL-divergence bounds also imply convergence of point-wise predictive means and variances.Source: §1.1 · p. 2
- Matrix-approximation guarantees for sparse kernel ridge regression can transfer to variational sparse GP regression, demonstrated with ridge leverage scores.Source: §1.1 · p. 2
- For squared exponential kernels and Gaussian covariates, lower bounds on inducing-variable counts have the same dependence on dataset size as the upper bounds.Source: §1.1 · p. 2
- The paper also provides practical inducing-variable selection recommendations based on its theory and reports empirical improvements.Source: §1.1 · p. 3
2. Background and Notation
The section introduces Gaussian-process regression and sparse variational inference, then frames approximation quality through KL divergence and the computation–accuracy trade-off. It also reviews how kernel spectra and inducing-variable selection shape the analysis.
2.2 Gaussian Process Regression
- Exact GP regression has closed-form inference, but kernel-matrix storage and inversion require O(N^2) memory and O(N^3) time.The marginal likelihood balances data fit and model complexity.Source: §2.2 · p. 5
2.3.1 Inducing Variable Methods
- Sparse methods compress the data’s effect into function values at M ≪ N locations, replacing the full kernel matrix with a lower-cost low-rank matrix.The selected inputs and function values are called inducing points; broader linear transformations are also possible.Source: §2.3.1 · p. 5, §2.3.2 · p. 6
2.3.2 The Variational Formulation
- The variational formulation selects an approximate posterior by minimizing KL divergence, often indirectly through the ELBO, whose slack is KL[Q||P].For an isotropic Gaussian likelihood, the optimal variational mean and covariance can be computed in closed form.Source: §2.3.2 · pp. 6–7
2.3.3 Measuring the Quality of a Variational Approximation
- Unlike general criticisms of KL-based variational inference, sparse GP regression obtains bounds on marginal posterior means and variances when the approximate-to-exact posterior KL divergence is sufficiently small.The paper uses KL because it is connected to the variational objective, though direct moment bounds may be tighter.Source: §2.3.3 · pp. 7–8
2.3.4 Computation and Accuracy Trade-Offs
- The ELBO and prediction parameters cost O(NM^2) time and O(NM) space, while the paper seeks bounds on how M must grow with N for a target approximation quality.The bounds depend on kernel properties that can be analyzed before observing data.Source: §2.3.4 · p. 8
2.4 Spectrum of Kernels and Mercer’s Theorem
- The quality of a rank-M kernel-matrix approximation depends on the eigenvalue decay of the kernel matrix.That decay is related to model complexity and posterior generalization properties.Source: §2.4 · pp. 8–9
- Kernel eigenvalue bounds depend on assumptions about the covariate locations, which the analysis models as i.i.d. draws from a distribution on R^D.The paper assumes X = R^D for the remainder of its analysis.Source: §2.4 · p. 9
2.5 Inducing Variable Selection and Related Bounds
- The paper extends sparse-GP convergence analysis to ridge-leverage sampling, including convergence of the ELBO and posterior KL; existing KRR matrix-approximation guarantees can transfer to variational sparse GPs.The section also reviews DPP initialization and related inducing-variable selection approaches.Source: §2.5 · pp. 9–10
3. Assessing Variational Inference: a Posteriori Bounds on the KL-divergence
This section explains why a small ELBO change after adding one inducing point is not enough to establish convergence. It presents posterior-KL bounds for checking a given approximation and motivates bounds on inducing-variable requirements before observing data.
3. Assessing Variational Inference: a Posteriori Bounds on the KL-divergence
- A small ELBO increase from one added inducing point does not establish convergence, since the point may be poorly placed or several well-placed points may improve performance.The section proposes refining selection by adding points until the upper and lower KL bounds are close.Source: §3 · pp. 10–11
- The upper and lower bounds on KL use, respectively, the operator norm and trace of Kff − Qff to construct bounds on the marginal likelihood.The trace-based bound can be computed in O(NM^2), whereas computing the largest eigenvalue for the operator-norm bound is computationally prohibitive in sparse GP problems.Source: §3 · p. 11
- When the KL upper and lower bounds are close, the section treats this as evidence that sufficiently many inducing points have been used for small posterior KL.This motivates continuing to add inducing points until the bound gap is small.Source: §3 · p. 11
- A priori bounds on required inducing-point counts matter because if M grows linearly with N, the O(NM^2) cost scales cubically in N.The paper says its later bounds show that, under stated assumptions, M can be much smaller than the data-set size while keeping KL divergences small.Source: §3 · p. 11
4. Convergence of Sparse Variational Inference in Gaussian Processes
The section develops KL-divergence bounds for sparse GP inference by relating the approximation of the kernel matrix to kernel eigenvalues under covariate assumptions. It also examines probabilistic bounds for DPP and ridge-leverage inducing-point selection, including conditions under which divergence can be small with M ≪ N.
4.1.1 Upper bounds on the KL-divergence
- Lemma 3 bounds KL divergence without assumptions on y’s distribution, using its squared norm; when ∥y∥² ≤ RN, the bound also controls conditional expected KL divergence.For a bounded function with Gaussian or bounded noise, this norm condition is reasonable; the bounds also generalize to other inducing variables discussed in Section 2.3.2.Source: §4.1 · p. 12, §4.1.1 · p. 13
4.1.2 Average Case Analysis for the Prior Model
- Under y|X,Z ∼ N(0, K_ff + σ^2I), Lemma 4 gives upper and lower bounds on expected KL divergence and a stronger upper bound than Lemma 3.This assumption holds when y follows the prior model and inducing inputs are chosen independently of y; after ELBO optimization, the KL divergence can be below the average-case lower bound.Source: §4.1.2 · pp. 13–14
4.2 Initialization of Inducing Points
- The initialization analysis uses bounds depending on the trace or largest eigenvalue of K_ff − Q_ff, so good low-rank approximations yield KL bounds for fixed training inputs.The section considers M-DPPs and ridge leverage scores as inducing-point selection methods.Source: §4.2 · p. 15
4.2.1 Minimizing the upper bounds
- The rank-M truncated eigendecomposition of K_ff minimizes both trace and operator-norm residuals among rank-M SPSD approximations, but computing it exceeds the desired computational budget.These eigenvector-based inducing features yield Q_ff equal to the truncated matrix.Source: §4.2.1 · pp. 15–16
4.2.2 M-Determinantal point processes
- M-DPP sampling of data-point inducing inputs makes expected tr(K_ff − Q_ff) relatively close to its optimum, the sum of eigenvalues beyond rank M.M-DPPs favor dispersed subsets through negative correlations; direct gradient-based optimization of inducing locations is outside this analysis.Source: §4.2.2 · pp. 16–17
Proof
- Accurate approximate M-DPP sampling has only a small effect on approximation quality, and the described MCMC sampler is known to be rapidly mixing.Its greedy initialization can be performed in O(NM^2).Source: Proof · pp. 18–19
4.2.3 Ridge Leverage Scores
- Ridge leverage score sampling offers an O(NM^2) alternative to M-DPP initialization while retaining strong theoretical guarantees for approximation quality.The section introduces an algorithm for efficiently approximating these scores; each score is defined using posterior variance with noise variance ω.Source: §4.2.3 · pp. 19–20
- Ridge-leverage sampling selects training points independently with probabilities proportional to leverage scores; approximate algorithms overestimate scores and may sample more points while retaining accuracy guarantees.The cited algorithm has runtime O(NM^2), memory O(NM), and returns at most cS log(S/δ) columns with probability 1 − 3δ.Source: §4.2.3 · p. 20
4.3 A-Priori Bounds on the KL-divergence
- Under marginal-density domination, finite-sample kernel-matrix eigenvalues are bounded using eigenvalues of the integral operator for the dominating distribution.For identically distributed covariates, the corollary specializes this comparison to their common density.Source: §4.3 · pp. 21–22
4.3.1 Bounds on the KL-divergence for M -DPP Sampling
- Expected KL-divergence bounds are established for approximate M-DPP inducing-point selection, including a conditionally Gaussian observation model.The bounds average over covariates, observations, and initialization; high-probability versions follow from Markov’s inequality.Source: §4.3.1 · pp. 22–23
4.3.2 Bounds for Ridge Leverage Score Sampling
- With probability 1 − 5δ, ridge-leverage initialization uses M < cS log(S/δ) under either theorem’s stated assumptions.The bounds cover the assumptions of Theorem 13 and the conditionally Gaussian observation case of Theorem 14, using Musco and Musco (2017, Algorithm 3).Source: §4.3.2 · p. 24
4.3.3 Are these bounds useful?
- For many inference problems, the bounds in Theorems 13, 14, 17, and 18 imply that KL-divergence can be made small with M ≪ N.The paper points to bounds on eigenvalues for common kernels and input distributions as the basis for this conclusion.Source: §4.3.3 · p. 24
5. Bounds for Specific Kernels and Covariate Distributions
This section applies convergence bounds to squared-exponential kernels with Gaussian inputs and to stationary kernels with compactly supported inputs, including Matérn kernels.
5.1 Squared Exponential Kernel and Gaussian Covariate Distribution
- For one-dimensional squared-exponential kernels with Gaussian inputs, RLS sampling needs O(log N log log N) inducing points and costs O(N(log N)^2(log log N)^2).Approximate M-DPP sampling instead uses O(log N) inducing points at O(N(log N)^4) cost; the rates hold with constants that depend on kernel and covariate hyperparameters.Source: §5.1 · pp. 25–26
5.1.1 The Multivariate Case
- For D-dimensional squared-exponential kernels with Gaussian inputs, RLS sampling needs O((log N)^D log log N) inducing points at O(N(log N)^{2D}(log log N)^2) cost.The same asymptotic inducing-point bound extends to compactly supported distributions with continuous, uniformly bounded densities; for fixed D, M grows polylogarithmically in N, but the required scaling is exponential in D.Source: §5.1.1 · p. 28
5.2 Compactly Supported Inputs and Stationary Kernels
- For stationary kernels, spectral-density decay informs eigenvalue decay, and Widom-based bounds apply to compactly supported inputs when regularity conditions hold.These eigenvalue bounds can in turn yield inducing-point requirements for convergence.Source: §5.2 · p. 29
5.2.1 Matérn kernels and compactly supported input distribution
- For Matérn kernels with compactly supported inputs, RLS bounds are non-vacuous when ν > D/2, and sparse inference costs asymptotically less than exact GP regression.The stated RLS cost is the inference cost up to logarithmic factors; M-DPP bounds are generally less favorable and can be vacuous in high dimensions or at low smoothness.Source: §5.2.1 · p. 30
6. Lower Bounds on the Number of Inducing Points Needed
The section derives lower bounds on inducing-variable counts needed to prevent KL-divergence from growing. For SE kernels with Gaussian covariates, the lower-bound dependence matches the upper bound; polynomial-decay kernels retain a gap.
6.2 Structure of the Argument
- The proof first bounds KL-divergence using Kff eigenvalues, then uses eigenvalue concentration to obtain a lower bound with fixed probability under i.i.d. covariates.Source: §6 · p. 31
6. Lower Bounds on the Number of Inducing Points Needed
- For SE kernels with Gaussian covariates, the lower bound requires M=Ω((log N)^D), matching upper-bound dependence; Matérn kernels with uniform covariates have a power-of-N lower bound but a large gap.The results apply to more general inducing variables, not only inducing points.Source: §6 · p. 31
6.1 A Lower Bound
- A general KL-divergence lower bound applies for any y and inducing inputs Z, and depends on the eigenvalues of Kff.The proof uses KL[Q||P] = log p(y) − L(y, Z) and compares eigenvalues of Kff and Qff.Source: §6.1 · p. 32
6.3 Concentration of Eigenvalues
- For i.i.d. covariates, the concentration result relates empirical kernel-matrix eigenvalues to those of the corresponding integral operator with fixed probability.Source: §6.3 · p. 33
6.4 Squared Exponential Kernel and Gaussian Covariates
- For univariate Gaussian kernels, choosing η = 0.01 in the argument yields KL-divergence Ω(N^0.99); the text says M must grow faster to keep the divergence small as N increases.Source: §6.4 · p. 34
6.5 The Isotropic SE-kernel and Multidimensional Gaussian Covariates
- For isotropic SE kernels with D-dimensional Gaussian inputs, any M=o((log N)^D) yields KL-divergence Ω(N^(1−ϵ)) with probability at least 1−δ.Conversely, M=c(log N)^D inducing inputs placed by approximate M-DPP have KL-divergence below γ in expectation for a suitable constant c.Source: §6.5 · p. 34
6.6 Lower Bounds for Kernels with Polynomial Decay
- For polynomially decaying spectra, the Matérn lower bound grows as a power of N, but can be vacuous near η=1 and remains far below the upper bound, especially for non-smooth kernels.Source: §6 · p. 31, §6.6 · pp. 35–36
7. Practical Considerations
Well-chosen inducing inputs reinitialized as hyperparameters change can yield highly accurate approximations to exact GP results; inducing-point optimization may help when models are very sparse, but is not always worth its cost. The section also explains how finite precision and jitter affect computation and the bounds used to assess approximation quality.
7.1 Finite Precision in Practical Implementations
- Ill-conditioned kernel matrices arise with highly correlated inputs, and during hyperparameter training large L-BFGS steps can reach settings where Cholesky decomposition fails.A small diagonal jitter is commonly added to K_uu to improve robustness, though it changes the problem being solved.Source: §7.1.1 · pp. 36–37, §7.1.2 · p. 37
7.1.3 Quantifying the Effect of Jitter
- Jitter stabilizes sparse Cholesky computations, but adding it makes the ELBO smaller and the upper bound larger, leaving a gap of a few nats even when M = N.The effect is typically small, and the bounds remain valid with jitter.Source: §7.1.2 · p. 37, §7.1.3 · p. 38
- Finite precision and jitter prevent approximate posteriors and bounds from reaching their exact-arithmetic values, while the variational bounds quantify both effects.The analysis assumes exact arithmetic, unlike practical floating-point implementations.Source: §7.1 · p. 36, §7.1.3 · p. 38
7.2.1 Fixed Hyperparameters
- When hyperparameters are fixed, gradient tuning performs best for very sparse models, but greedy variance selection and M-DPP recover exact-GP performance with few additional inducing variables.K-means, uniform subsampling, and RLS tend to need many more inducing variables to converge; greedy variance selection is simple and fast.Source: §7.2.1 · p. 40
7.2.2 Training procedure and hyperparameter optimization
- Alternating hyperparameter optimization with greedy variance reinitialization tailors inducing inputs to updated kernel parameters without high-dimensional non-convex inducing-input optimization.Reinitialization stops when it no longer improves the ELBO; it is useful when enough inducing points make the ELBO nearly tight for the current hyperparameters.Source: §7.2.2 · p. 42
- In constrained optimization runs, K-means underperforms the best method; reinitialization reaches the best ELBO on Naval and the optimal ELBO fastest on Elevators.On Energy, greedy variance reinitialization reaches local optima at low sparsity, an issue that disappears with more inducing points.Source: §7.2.2 · p. 42
- Reinitialized greedy variance selection converges consistently to the exact model, and the empirical conclusion is that such well-chosen inputs give highly accurate variational approximations.Gradient-based inducing-input optimization may improve performance under very sparse constraints, but is not always worth the additional effort.Source: §7.2.2 · p. 42, §7.2.3 · p. 44
7.2.3 Recommendation for Inducing Input Selection
- The recommendations apply only where sparse approximations are practically possible; for kin40k, learned hyperparameters yielded a squared-exponential model that could not be accurately approximated.The authors make no inducing-variable recommendation when the variational approximation is poor.Source: §7.2.3 · p. 44
8. Conclusions
The paper gives guarantees on sparse variational GP regression with far fewer inducing variables than data points and bounds how many are needed to keep posterior KL-divergence small. It also compares inducing-input selection methods empirically and identifies refinement of the bounds and non-conjugate inference as future research directions.
8. Conclusions
- The paper provides guarantees on variational sparse Gaussian process regression when far fewer inducing variables than data points are used.It also considers lower bounds on the number of inducing variables needed to keep posterior KL-divergence from becoming large.Source: §8 · pp. 44–45
- The bounds inform how many inducing points to use across tasks and which problems are well-suited to sparse variational inference.The paper also empirically compares methods for selecting inducing inputs.Source: §8 · p. 45
- Future work includes refining the bounds and better understanding non-conjugate inference schemes.The paper cites Hensman et al. (2015) as an example of such schemes.Source: §8 · p. 45
Appendix A. Proof of Bound on Mean and Variance of One-dimensional Marginal Distributions
The proof relates the KL-divergence of the approximate and exact posteriors to differences in one-dimensional marginal Gaussian distributions. It uses this relation to bound posterior variance and mean discrepancies.
Appendix A. Proof of Bound on Mean and Variance of One-dimensional Marginal Distributions
- The proof uses the chain rule of KL-divergence to relate the joint posterior discrepancy to marginal discrepancies.The cited reasoning relies on joint KL-divergence upper-bounding the KL-divergence between marginals.Source: Appendix A · p. 45
- For any input x_⋆, the marginal KL-divergence is between one-dimensional Gaussian distributions, whose variance ratio is bounded using γ ≥ r − 1 − log r.For γ < 1/5, the proof bounds r in [0.493, 1.78] and derives a variance bound.Source: Appendix A · p. 45
- The same marginal KL relation bounds the difference between approximate and exact posterior means by σ_2√γ.The proof obtains this from (μ_1 − μ_2)^2 ≤ γ and its variance bound.Source: Appendix A · p. 46
Appendix B. Proofs of A-Posteriori Bounds
The appendix restates the upper bound on the log marginal likelihood and derives a computable version using a trace bound on the kernel approximation error. The resulting bound can be evaluated with sparse-method time and memory costs.
Appendix B. Proofs of A-Posteriori Bounds
- The appendix restates the log marginal likelihood expression and the upper bound involving the operator norm of K_ff − Q_ff.The proof uses positive-semidefinite matrix ordering to establish the bound.Source: Appendix B · p. 46
- Replacing the operator norm of K_ff − Q_ff with its trace yields the computable upper bound U2.Computing the largest eigenvalue is computationally prohibitive in sparse GP regression, whereas the trace provides an upper bound on the operator norm.Source: Appendix B · p. 47
- U2 can be computed in O(NM^2) time and O(NM) memory, like the ELBO.Its computation depends on the low-rank matrix Q_ff and the diagonal entries of K_ff.Source: Appendix B · p. 47
Appendix C. Proofs for Results Leading to Upper bounds on the KL-divergence
The appendix proves upper-bound results for the KL-divergence and derives inducing-point bounds for the univariate squared exponential case. Its proof controls residual-matrix terms, while the corollary gives logarithmic growth in N for the inducing-point count.
Appendix C. Proofs for Results Leading to Upper bounds on the KL-divergence
- The proof of Lemma 3 uses an inverse-matrix identity to express U1−L through t and a quadratic form involving ζ.The quadratic-form bound uses a lower bound σ²(ζ + σ²) on the relevant matrix eigenvalues.Source: Appendix C · p. 47
- The upper-bound proof applies a Hölder-type inequality and uses Qff + σ²I ≺ Kff + σ²I to compare determinants.The appendix states that its lower bound was already proved in the main body.Source: Appendix C · p. 48
- The upper-bound proof controls a trace term by t/(2σ²), using the operator norm of (Qff + σ²I)^-1.The bound follows from the residual Kff−Qff and the inverse-norm bound in the proof.Source: Appendix C · p. 48
D.1 Bounds for Univariate Gaussian distributions and Squared Exponential Kernel
- For the univariate squared exponential case, an approximate M-DPP yields M = O(log(N^3/γ)) with ϵ = Θ(γ/N²).Allowing the implicit constant to depend on δ and γ gives O(log N log log N).Source: §D.1 · pp. 49–50
D.2 Bounds for Multivariate Gaussian distributions and Squared Exponential Kernel
For squared exponential kernels with Gaussian covariates in D dimensions, the appendix bounds the eigenvalue tail and uses it to derive inducing-point requirements. The stated approximate M-DPP bound scales as a power of the logarithm of N.
D.2 Bounds for Multivariate Gaussian distributions and Squared Exponential Kernel
- The eigenvalue tail is bounded by O(M exp(−αM^(1/D))), with α = −log B > 0.The implicit constant depends on covariate dimension, kernel parameters, and the covariate covariance matrix.Source: §D.2 · p. 50
- For a squared exponential ARD kernel and D-dimensional Gaussian covariates, the corollary gives M = O((log N/γ)^D).The implicit constant depends on kernel hyperparameters, the covariate covariance matrix, D, and R.Source: §D.2 · p. 51
- The corollary’s inducing-point requirement follows from combining Theorem 13 with the eigenvalue-tail result in Proposition 21.For the M-DPP case, the proof chooses ϵ = Θ(γ/N²).Source: §D.2 · pp. 50–51
D.3 Conditions for Widom’s Theorem
The appendix states conditions under which Widom’s theorem relates kernel eigenvalue counts to a volume determined by the covariate density and spectral density. It also develops a general KL lower-bound argument using the rank limit of the inducing approximation.
D.3 Conditions for Widom’s Theorem
- Under Widom’s theorem’s conditions, the number of eigenvalues above ϵ is asymptotic to the volume of points satisfying p(x)s(ω) > ϵ.The theorem applies to compactly supported covariate distributions with Lebesgue density and stationary kernels whose spectral density meets the stated conditions.Source: §D.3 · pp. 51–52
- Widom’s theorem cannot be applied to kernels with rapidly decaying spectral densities, including the squared exponential kernel, because its second condition fails.The appendix notes that more stationary kernels are analyzed for uniformly distributed covariates in Widom (1964).Source: §D.3 · p. 52
E.1 General Lower Bound on KL-divergence
- The general lower-bound proof uses that Qff has rank at most M, so its eigenvalues ψm vanish for m > M.The proof also uses Kff ≻ Qff, which implies that the eigenvalues of Kff dominate those of Qff.Source: §E.1 · pp. 52–53
E.2 Lower Bound on Eigenvalues of Multivariate Gaussian Inputs and Squared Exponential Kernel
For isotropic squared exponential kernels and isotropic Gaussian inputs, the appendix establishes a lower bound showing that inducing sets growing more slowly than (log N)^D leave a large KL-divergence with high probability. Its eigenvalue argument counts multiplicities through compositions of integers.
E.2 Lower Bound on Eigenvalues of Multivariate Gaussian Inputs and Squared Exponential Kernel
- In the multivariate eigenvalue calculation, each eigenvalue’s multiplicity equals the number of ordered ways to express s as a sum of D non-negative integers.Source: §E.2 · p. 53
- If M(N) = o((log N)^D), then with probability at least 1−δ, KL[Q||P] = Ω(N^(1−ϵ)) for any y and any ϵ > 0.This result assumes iid isotropic Gaussian covariates and an isotropic squared exponential kernel.Source: §E.2 · p. 54
- The proof relates the KL lower bound to the (M+1)th eigenvalue, with Nλ_(M+1) = Ω(N^(1−ζ/D)).The argument states KL[Q||P] ≥ Nλ_(M+1)(1 + o(1)) with probability at least 1−δ.Source: §E.2 · p. 54
Appendix F. Effect of Jitter on Bounds
The appendices analyze how jitter affects variational bounds and how ridge-leverage sampling can adapt the number of inducing points. The sampling discussion relates that number to the kernel's effective dimension.
Appendix F. Effect of Jitter on Bounds
- Jitter makes the evidence lower bound decrease and the upper bound on log marginal likelihood increase.The lower bound is monotonically decreasing in jitter, while the upper bound is monotonically increasing.Source: Appendix F · p. 55
G.1 Effective Dimension
- The effective dimension is the sum of ridge leverage scores and depends on the kernel, covariate distribution, and regularization parameter.It is used to characterize the number of points sampled by ridge-leverage methods for a desired accuracy.Source: §G.1 · p. 56, Appendix G · p. 56
- An effective-dimension upper bound can be obtained by splitting its sum and choosing S to balance the two resulting terms.The discussion considers typical effective-dimension size for fixed kernels and random covariates with identical marginals or marginals satisfying Lemma 11.Source: §G.1 · pp. 56–57
G.2 Adaptively Selecting the Number of Inducing Points with Leverage Scores
- The adaptive sampling algorithm runs in O(NM^2) time and O(NM) memory, returning M < 384 d_eff^ω log(d_eff^ω/δ) with probability 1 − 3δ.Here d_eff^ω is the effective dimension for noise parameter σ^2 = ω.Source: §G.2 · p. 57
G.3 Ridge Leverage Scores and Sparse Variational Inference
The ridge-leverage analysis gives probabilistic bounds on inducing-point counts under stated covariate and output assumptions. It also relates the bounds' quality and rates to kernel and covariate choices.
G.3 Ridge Leverage Scores and Sparse Variational Inference
- The initialization noise parameter ω need not match the regression noise parameter because Kff and Qff are independent of noise.Source: §G.3 · p. 57
- With probability 1 − 5δ, the stated assumptions yield M < 384 d log(d/δ) for inducing points selected with ω = σ^2δγ/N.The theorem applies under the assumptions on covariates and y referenced in Theorem 14.Source: §G.3 · pp. 57–58
- Without assuming y follows the prior model, the corresponding bound is M < 384 d′ log(d′/δ) with probability 1 − 5δ.The stated choice is ω = 2σ^2δγN(1 + R/σ^2).Source: §G.3 · p. 58
- The approximation-quality bounds do not depend on kernel or covariate distribution, although the resulting bounds on M do.The passage states that the two theorems imply the same asymptotic rates; Table 3 presents inducing-point bounds for Theorems 38 and 39.Source: §G.3 · p. 58, Table 3 · p. 59
- The two theorems have the same asymptotic rates because the operator norm is bounded directly, unlike the M-DPP initialization's trace-based bound.The M-DPP approach uses a trace bound as an upper bound on the operator norm.Source: §G.3 · p. 58