Sampling from a Gaussian process (GP) posterior, a probabilistic model that places a distribution over functions, normally requires inverting an $N \times N$ kernel matrix. A recent line of work avoids this. It turns each posterior sample into the solution of a linear system: draw a function from the prior, then correct it toward the data. Iterative solvers such as conjugate gradients (CG), stochastic gradient descent (SGD), or stochastic dual descent can handle that system at scale. In practice these solvers are stopped early. The usual reading of the convergence–accuracy trade-off is that an unfinished solve leaves an error floor, so the samples have the wrong covariance and the uncertainty estimates cannot be trusted.
This note argues that this reading is wrong for a large and identifiable class of solvers. Suppose the solver acts on its right-hand side through a fixed linear operator: a fixed number of gradient or Chebyshev steps, or SGD that reuses the same minibatch sequence for the mean and for every sample. Then the early-stopped sampler still produces exactly calibrated credible intervals when averaged over data drawn from the prior, at every iteration count. Stopping early costs sharpness, meaning wider intervals than the true posterior. It does not make the samples overconfident. The guarantee breaks for solvers whose effective operator depends on the right-hand side. CG with per-sample Krylov polynomials, or with tolerance-based stopping, is the main case. The guarantee also breaks when the prior draw comes from a truncated random-feature basis that does not match the kernel used in the correction. The program is to prove this split, test it empirically, and use it to choose solvers and compute budgets.
Core Claim
Write the data as $y \in \mathbb{R}^N$ at inputs $X$. Let $K$ be the kernel matrix, $\sigma^2$ the noise variance, and $k_{*}$ the kernel vector between a test point and $X$. Pathwise conditioning, introduced in Pathwise Conditioning of Gaussian Processes via Matheron's rule, draws a prior function $f$ and noise $\varepsilon$, then outputs $f(x_*) + k_*^\top (K+\sigma^2 I)^{-1}(y - f(X) - \varepsilon)$. An iterative solver run for $k$ steps replaces the inverse with some operator $A_k$:
$$ s_k(x_*) = f(x_*) + k_*^\top A_k\,\big(y - f(X) - \varepsilon\big). $$
Assume $A_k$ is the same for the mean and for all samples, and does not depend on $y$ or the sample's own right-hand side. For instance, $A_k = p_k(K+\sigma^2 I)$ for a fixed polynomial $p_k$, possibly conditioned on a shared random seed. In the eigenbasis of $K+\sigma^2 I$, with eigenvalues $\mu_i$, write the solver's "filter" as $g_i = \mu_i\, p_k(\mu_i)$. The filter equals 1 when direction $i$ is fully resolved and 0 when it is untouched.
A short calculation then gives the sample covariance as the exact posterior covariance plus an excess term $\sum_i (k_*^\top u_i)^2 (1-g_i)^2/\mu_i$, where $u_i$ are the eigenvectors. The expected squared error of the early-stopped mean, under the prior, equals the posterior variance plus the same sum. Because everything is jointly Gaussian, it follows that
$$ \frac{f_{\text{true}}(x_*) - \mathbb{E}[s_k(x_*)\mid y]}{\sqrt{\operatorname{Var}[s_k(x_*)\mid y]}} \sim \mathcal{N}(0,1) $$
exactly under the prior, for every $k$. The excess term is also never negative, so the sample covariance is never smaller (in the matrix ordering) than the true posterior. It stays below the prior whenever every $g_i$ lies in $[0,2]$, which holds for gradient descent with a stable step size.
This result formalizes the "benign non-convergence" observed in Sampling from Gaussian Process Posteriors using Stochastic Gradient Descent. That paper showed empirically that early-stopped SGD resolves the top kernel eigendirections and falls back to the prior elsewhere, but it gave no error-floor theory. The calculation above says the fallback is not an approximation to be bounded. It is self-consistent uncertainty, and the samples already carry it.
The same calculation predicts where calibration fails. CG builds a different Krylov polynomial for each right-hand side, so the operator applied to the mean differs from the one applied to each sample, and the identity no longer holds. Stopping at a residual tolerance makes $k$ depend on $y$, which breaks it as well. A prior drawn from finitely many random features, rather than from the kernel $K$ used in the correction, breaks it too.
Research Program
The theoretical part has three pieces. First, we state and prove the identity above, together with the two-sided covariance bound, for deterministic fixed-polynomial solvers: gradient descent, heavy-ball, and Chebyshev iteration.
Second, we extend it to stochastic solvers by conditioning on the solver's random seed. Primal SGD in the style of Lin et al. and stochastic dual descent from Scalable Gaussian Processes: Advances in Iterative Methods and Pathwise Conditioning are both linear in the right-hand side once the minibatch indices and random features are fixed. Sharing that randomness across the mean and all samples therefore keeps calibration exact. Drawing it independently per sample adds a variance term that depends on $y$, and we will compute that term. Sharing randomness across coupled runs is the same mechanism that Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson–Romberg Extrapolation uses to cancel bias. Here it serves a different purpose: keeping the solver operator independent of the data.
Third, we quantify how calibration fails for solvers that depend on the right-hand side (CG at fixed $k$ and at a fixed tolerance) and for random-feature priors with $M$ features. The aim is to bound the deviation of the standardized error from $\mathcal{N}(0,1)$ in terms of how far each Krylov polynomial departs from a common one, and in terms of the kernel approximation error.
The methodological part turns the identity into tools. Under the identity, the convergence–accuracy trade-off is purely a question of sharpness. The excess variance is computable from the samples themselves, which gives a principled stopping rule: stop when the excess variance at the query points no longer justifies the compute.
Real data are not drawn from the model, so we add a cheap adequacy check. The data residual after $k$ steps, $y - (K+\sigma^2 I)A_k y$, can be compared against the residuals of the sample right-hand sides. Under a correct prior, those sample residuals follow exactly the null distribution of the data residual. A data residual far larger than the sample residuals means the unresolved directions contain more signal than the prior expects. In that case early stopping will under-cover, and the solver should continue.
We also compare primal and dual solvers in these terms. The dual landscape in Lin's thesis is flatter and permits roughly $100\times$ larger steps, so its filter $g_i$ moves toward 1 faster across the spectrum. The question is whether that buys sharpness at equal compute while preserving calibration. This addresses Gap 4 of the research file with a concrete criterion.
Baselines
The naive reference point is the prior itself: the zero-iteration solver, which is trivially calibrated under the prior and maximally unsharp. Every method must beat it on interval width. Against the true posterior, it shows how much sharpness is at stake.
The strongest existing method for accuracy is exact or near-exact inference with preconditioned CG through blackbox matrix–matrix products, as in Exact Gaussian Processes on a Million Data Points. On Kin40K that paper reports a test RMSE of 0.099 for the exact GP against 0.273 for sparse SGPR. We will run CG in two ways: to tight tolerance as an approximate ground truth, and at matched wall-clock budgets with per-sample solves. The hypothesis is that budget-limited CG shows calibration errors the shared-operator solvers do not. Beating it means equal or better negative log-likelihood (NLL) and coverage at a fraction of its compute. We will not claim RMSE parity unless we observe it.
The strongest existing optimization-based sampler is SGD pathwise sampling Sampling from Gaussian Process Posteriors using Stochastic Gradient Descent. On HouseElectric it reports significantly better NLL than CG within the time budget, but the file gives no exact figure. For calibration error of early-stopped samplers in particular: no reported result found on Lacuna. Stochastic dual descent from Lin's thesis is the second strong competitor. Both will be run as published and with shared randomness across samples, using identical step-size grids, iteration budgets, minibatch sizes, random-feature counts, and hyperparameters fixed in advance by one common marginal-likelihood fit.
The key ablation isolates the proposal's main ingredient: whether the solver operator is shared and independent of the data. It compares the same SGD or dual solver with shared versus independent minibatch seeds, and CG at fixed $k$ versus at a residual tolerance. Everything else is held constant. If calibration does not differ between the shared and independent arms, the central mechanism is wrong.
Sparse variational GPs serve as an external reference for cheap uncertainty, run with matched compute.
Why not just…?
Why not just run the solver to convergence? That is the right answer when it is affordable, and our tolerance-CG arm measures exactly what it costs. Wang et al. need roughly two hours on 8 V100 GPUs for 1.3M points, and Lin et al. report CG failing to converge in low-noise regimes. The proposal's claim is conditional: if you must stop early, the choice of solver decides whether the resulting uncertainty can be trusted. The ill-conditioned, low-$\sigma^2$ experiments test whether this matters where it should.
Why not just recalibrate the variance on held-out data? This is a real threat. A single scale factor fitted on validation data is simple and might match our coverage numbers on average. It cannot, however, correct spatially varying miscalibration, such as CG being overconfident only in data-dense regions while fine elsewhere. It also uses data that our method does not need. We will report recalibrated CG and recalibrated independent-seed SGD alongside our method, broken down by region of input density. If global recalibration matches our results everywhere, the practical contribution narrows to the theory and the stopping rule, and we will say so.
Why not just apply Richardson–Romberg extrapolation across two step sizes, as in Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson–Romberg Extrapolation and Convergence of Noise-Free Sampling Algorithms with Regularized Wasserstein Proximals? The pathwise objective is quadratic. The leading constant-step bias that extrapolation cancels comes from third and higher derivatives, which a quadratic does not have, so the averaged iterate has no such bias to remove. What remains is truncation of the unresolved spectrum. Extrapolating two filters produces another polynomial filter that can leave $[0,2]$, losing the upper covariance bound while keeping calibration. We will include the extrapolated estimator as a variant to confirm that it changes sharpness only.
Why not just use plain diminishing step sizes? For a fixed iteration budget, any schedule is just another fixed polynomial, so it is covered by the theorem. The open question is only whether it is sharper. Iiduka's results (Appropriate Learning Rates of Adaptive Learning Rate Optimization Algorithms for Training Deep Neural Networks) and the inexact proximal analysis (A Tight Convergence Analysis of Inexact Stochastic Proximal Point Algorithm for Stochastic Composite Optimization Problems) suggest diminishing schedules pay a sublinear rate. We will include them in the step-size grid.
Proposed Experiments
The decisive test is synthetic and well specified. We draw functions from Matérn and squared-exponential GPs at $N$ from $10^4$ to $10^5$, with noise from $10^{-1}$ down to $10^{-6}$ to create ill-conditioning. For each solver arm and each iteration count, we compute the empirical distribution of the standardized error over many prior draws. The measures are coverage of 50% and 95% intervals and a Kolmogorov–Smirnov distance to $\mathcal{N}(0,1)$. Exact Cholesky posteriors serve as the reference at the smaller sizes.
The theory predicts flat, exact coverage at every $k$ for fixed-operator solvers. It predicts coverage errors for CG that grow with ill-conditioning and with tolerance-based stopping. It predicts a measurable gap that shrinks with $M$ for random-feature priors. Interval width, plotted against wall-clock time, then traces the sharpness–compute frontier. Comparing those frontiers for primal SGD and dual descent answers the primal–dual question.
On real data we use Kin40K, Song, and HouseElectric with standard splits, reporting RMSE, NLL, interval coverage and width, and wall-clock time. We also apply the residual adequacy check at each $k$ and test whether it predicts when under-coverage appears.
A downstream check uses the 8-dimensional Thompson-sampling benchmark of Lin et al. It asks whether shared-operator early-stopped samples reach equal regret with fewer iterations than CG-based samples. The idea is that well-calibrated, conservative exploration should not hurt optimization.
The proposal is falsified if shared-randomness SGD shows the same miscalibration as independent-seed SGD on synthetic draws. It is also falsified if budget-limited CG turns out to be as well calibrated as the fixed-operator solvers across the low-noise sweep.
References
- Pathwise Conditioning of Gaussian Processes
- Sampling from Gaussian Process Posteriors using Stochastic Gradient Descent
- Scalable Gaussian Processes: Advances in Iterative Methods and Pathwise Conditioning
- Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson–Romberg Extrapolation
- Exact Gaussian Processes on a Million Data Points
- Convergence of Noise-Free Sampling Algorithms with Regularized Wasserstein Proximals
- Appropriate Learning Rates of Adaptive Learning Rate Optimization Algorithms for Training Deep Neural Networks
- A Tight Convergence Analysis of Inexact Stochastic Proximal Point Algorithm for Stochastic Composite Optimization Problems