Exact Gaussian processes (GPs, probabilistic regression models whose predictions come with calibrated error bars) now scale to millions of points. That progress came from replacing the cubic-cost matrix factorization with iterative solvers that need only matrix-vector products. Training such a GP still requires a practitioner to set three coupled knobs by hand. The first is the learning rate of the outer optimizer that fits the kernel hyperparameters. The second is how accurately the inner linear solve must converge at each outer step. The third is how much artificial "jitter" to add to the diagonal so the arithmetic does not break. A single run can take 84.5 hours on 4.1 million points (Large-Scale Gaussian Processes via Alternating Projection), so tuning these knobs by grid search is out of reach. The knobs fail together in one regime: when observation noise is tiny, as in deterministic simulators and high-precision spatial data. There the kernel matrix becomes nearly singular, gradients with respect to the noise level blow up, and single-precision factorizations crash.
We propose one training loop with no hand-set step size and no hand-set solver tolerance. The outer optimizer estimates local curvature from consecutive gradients and grows its step geometrically, in the style of Accelerated GRAAL. The inner solver is greedy block coordinate descent. Its residual gives a cheap, provable bound on how wrong the current gradient is. The outer optimizer asks the inner solver for exactly as much accuracy as its own curvature estimate needs, and no more. Low noise and finite precision are not side issues in this design. They are the stress test it is built for.
Core Claim
The key fact is that, for the GP system $(K+\sigma^2 I)w = y$, the solve error is certified cheaply. Here $K$ is the $n\times n$ kernel matrix, $\sigma^2$ the observation noise, $y$ the targets, and $w$ the representer weights. The smallest eigenvalue of $K+\sigma^2 I$ is at least $\sigma^2$, so for any iterate $w_t$ with residual $r_t = y-(K+\sigma^2 I)w_t$:
$$\|w_t - w^\ast\| \le \|r_t\|/\sigma^2 .$$
A greedy block solver drives $\|r_t\|$ down near-monotonically, which Wu et al. observed in contrast to conjugate gradients' early spikes. This bound therefore becomes a usable stopping signal. Conjugate gradients cannot offer one, because its residual oscillates.
The outer optimizer works on log-hyperparameters $\theta$. It estimates local smoothness as $\hat L_k = \|g_k - g_{k-1}\|/\|\theta_k-\theta_{k-1}\|$ from successive gradient estimates $g_k$. An error of size $\epsilon$ in each gradient corrupts $\hat L_k$ by up to $2\epsilon/\|\theta_k-\theta_{k-1}\|$. So the inner solve is stopped once the certified gradient error falls below
$$\epsilon_k \le \rho\, \hat L_{k-1}\,\|\theta_k-\theta_{k-1}\|,$$
where $\rho<1$ is a fixed safety fraction. With this rule the curvature estimate measures the function and not the solver. The rule is loose early, when steps are small and curvature barely matters, and tight near convergence. The claim is that this coupling removes the step-size and tolerance knobs without losing wall-clock time or accuracy against tuned pipelines. It should also keep training stable as $\sigma^2$ falls toward single-precision limits, where tuned Adam pipelines need jitter or diverge.
Research Program
Outer loop. Borodich and Kovalev's Accelerated GRAAL (Nesterov Finds GRAAL) supplies the step-size mechanism. It estimates curvature from consecutive points and lets the step grow geometrically from a tiny start. Its guarantees cover convex and $(L_0,L_1)$-smooth functions. $(L_0,L_1)$-smoothness means curvature that grows with the gradient norm, which is qualitatively what happens to the marginal likelihood as $\log\sigma^2$ decreases. The GP marginal likelihood is nonconvex, however. We therefore claim no global guarantee. We test whether the method behaves well inside the basin it starts in, and we compare against AdaGrad-norm step sizes, which do carry nonconvex guarantees (Kavis et al.; SGD with AdaGrad Stepsizes).
Probe noise. The log-determinant gradient is estimated with random probe vectors, following the trace estimation of Scalable Log Determinants for Gaussian Process Kernel Learning. That probe noise is exactly what the parameter-free literature identifies as corrupting finite-difference curvature estimates. Our remedy is to reuse the same probes for the two gradients whose difference forms $\hat L_k$, and to redraw them only between curvature measurements. Probe variance then cancels in the difference. The probe solves are certified by the same residual bound.
Inner solve. We start from Wu et al.'s alternating projection, which is Gauss-Southwell block coordinate descent with cached block factorizations. We change one thing: the rule for choosing which block to update. Wu et al. pick the block with the largest residual norm $\|r_I\|$. Bo and Sminchisescu showed that gradient-magnitude rules waste effort on correlated, redundant points (Greedy Block Coordinate Descent for Large Scale Gaussian Process Regression). The quantity that actually measures progress is the exact decrease from minimizing over block $I$, $r_I^\top K_{II}^{-1} r_I$, written here with $K_{II}$ for the noisy diagonal block $(K+\sigma^2 I)_{II}$. With the block Cholesky factors already cached, scoring all $n/b$ blocks of size $b$ costs $O(nb)$, the same order as the residual update itself. Bo and Sminchisescu's rule needed $O(m^3)$ incremental inverses over random candidates. Ours pays no extra asymptotic cost, because it scores fixed blocks rather than building blocks one point at a time. This rule plays a supporting role in the proposal, and it is ablated separately.
Precision. Only the small diagonal blocks are factorized, so we factor them in FP64. The kernel products and residuals stay in FP32, which is where GPU throughput lies (Exact Gaussian Processes on a Million Data Points). The aim is to drive the added jitter to zero rather than to a hand-chosen $10^{-6}$, since jitter biases uncertainty. Log-space arithmetic is used only where it belongs. Hyperparameters are kept as logarithms, and the log-determinant is accumulated as a sum of log-eigenvalues of small tridiagonal matrices. We do not attempt log-space linear algebra on signed residuals: the research file notes that signed subtraction defeats it.
Baselines
The naive reference point is the standard exact-GP pipeline of Wang et al.: conjugate gradients with pivoted-Cholesky preconditioning and batched kernel products, paired with Adam at a default learning rate and default solver tolerance and jitter. It represents what a practitioner gets without tuning. Wang et al. report RMSE 0.099 on Kin40k, against 0.273 for sparse SGPR. We reproduce it on the same data splits and hardware, with Adam's learning rate fixed at its default.
The strongest competitor on speed at scale is Wu et al.'s alternating projection with Adam. They report training speedups of up to 27x over conjugate gradients, and 84.5 hours on Gas Sensors where conjugate gradients would need over a month. For fairness we give this baseline a grid over learning rate and solver tolerance on the mid-sized datasets and report its best configuration. We charge the grid's total compute against it in a separate "including tuning" column. Our method gets no grid.
The strongest competitor on tuning-freeness is Wenger et al.'s preconditioned L-BFGS with line search (Preconditioning for Scalable Gaussian Process Hyperparameter Optimization). They report up to a 12x training speedup and fewer line-search evaluations. Line search already removes the step size, so this is the comparison that decides whether our coupling adds anything. We run it with its published preconditioner settings and the same probe count.
Beating these baselines means one of two outcomes. Either we match the tuned alternating-projection configuration's test RMSE and negative log-likelihood within run-to-run noise at no more wall-clock time than its single best run. Or we beat it outright once tuning cost is counted. In addition, we must remain stable at noise levels where the baselines need jitter.
Three ablations isolate the ingredients:
- The same GRAAL outer loop with a fixed solver tolerance tests the inexactness coupling.
- The same coupled loop with Wu et al.'s residual-norm block rule tests the exact-decrease rule.
- The same loop with AdaGrad-norm in place of GRAAL tests whether geometric step growth matters.
Why not just…?
Why not just use L-BFGS with a line search, which is already free of a step size? This is the most serious threat. Line search needs repeated objective values, and each objective value includes a stochastic log-determinant. Wenger et al. had to precondition specifically to make those values reliable. Our loop needs only gradients, and it controls their error explicitly. If preconditioned L-BFGS matches us in wall-clock time and stability at low noise on 3D Road and House Electric, the coupling's value reduces to the inner-solver choice, and we will report it that way.
Why not just tune Adam once on a subset and reuse the setting? Tuned settings do not transfer along the axis we care about. As the fitted noise shrinks, the gradient in $\log\sigma^2$ grows and the solve becomes harder. A learning rate tuned at moderate noise can therefore diverge at low noise. The experiment that settles this transfers tuned Adam settings from Kin40k to the noise-free simulators and to 3D Road with low noise enforced. We then measure divergence rate and final likelihood.
Why not just run everything in FP64? This is a real alternative on small problems, and we include an FP64 run of every baseline up to Kin40k and Sarcos scale. At millions of points, FP64 kernel products halve memory capacity and cut GPU throughput, which is why Wang et al. work in single precision. Our design confines FP64 to the small block factorizations. The test is whether mixed precision matches FP64 accuracy at near-FP32 cost.
Why not just use AdaGrad-norm step sizes, which have nonconvex guarantees? It is simpler, and it is an ablation arm of this study. Accumulated-gradient step sizes only shrink. They pay for early large gradients for the rest of the run, which is exactly what low-noise fits produce. GRAAL-style steps can grow back. If AdaGrad-norm matches GRAAL within the coupled loop, we adopt it and keep the coupling, which is the actual contribution.
Proposed Experiments
Datasets follow the file's benchmark suite: Kin40k, Sarcos, 3D Road, House Electric and Gas Sensors for scale. For the low-noise stress test we use the noise-free simulators from Chen et al. (Borehole, OTL Circuit, Wing Weight), where the true noise is zero and current pipelines rely on jitter. Metrics are test RMSE and negative log-likelihood, wall-clock time to a fixed training likelihood, total compute including any tuning, and failure rate across five seeds. Failure means divergence or Cholesky breakdown.
The first decisive check is a noise sweep on 3D Road. We fix $\sigma^2$ at decreasing values down to $10^{-6}$ relative to signal variance with zero jitter, and record which methods still train and how calibrated their predictive variances remain. The second check is the coupling itself. We plot requested tolerance against outer iteration, and gradient error against the bound, to confirm that the certified bound is tight enough to be useful. A bound off by orders of magnitude would make the solver over-solve and erase the speed advantage. The third check compares block rules: inner iterations to a fixed residual under the exact-decrease rule versus the residual-norm rule on clustered spatial data. Bo and Sminchisescu found redundancy hurts most on such data, with greedy selection 10x faster than cyclic on Sarcos. The full Gas Sensors run is attempted last and only if the mid-scale results favor the method. The comparison there is against Wu et al.'s reported 84.5 hours.
References
- Large-Scale Gaussian Processes via Alternating Projection
- Nesterov Finds GRAAL: Optimal and Adaptive Gradient Method for Convex Optimization
- High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize
- SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variance
- Scalable Log Determinants for Gaussian Process Kernel Learning
- Greedy Block Coordinate Descent for Large Scale Gaussian Process Regression
- Exact Gaussian Processes on a Million Data Points
- Preconditioning for Scalable Gaussian Process Hyperparameter Optimization
- Gaussian Process Parameter Estimation Using Mini-batch Stochastic Gradient Descent: Convergence Guarantees and Empirical Benefits