Progress-Aware Greedy Block Solvers for Gradient-Observing Gaussian Processes

A Gaussian process (GP) is a Bayesian regression model that returns both a prediction and a calibrated error bar. It is the default surrogate model in Bayesian optimization and in many scientific simulators. Fitting one exactly means solving a dense linear system whose size equals the number of observations. When the training data include gradients as well as function values, as they do whenever the simulator is differentiable, each point contributes $d+1$ unknowns instead of one. The system grows to $n(d+1)$ and becomes badly conditioned, so that exact Cholesky factorization costs $\mathcal{O}(n^3 d^3)$ and conjugate gradients stalls. The most promising modern exact solver solves the system a few hundred unknowns at a time. It repeatedly picks one block of unknowns and solves that block exactly, a method called alternating projection or block coordinate descent (Large-Scale Gaussian Processes via Alternating Projection). It picks the block whose residual is largest. That rule ignores how much a block's solve will actually reduce the error, and the gap matters most in the gradient setting, where value and derivative unknowns live on very different scales.

We propose replacing the residual-size rule with the exact one-step progress of each candidate block. This quantity can be read off at little extra cost because the solver already stores a small Cholesky factor for every block. We also propose a block design for gradient-observing GPs that groups each point's value and partial derivatives with those of its spatial neighbours. In two sentences: greedy block solvers for GPs currently pick blocks by "largest error", but "largest guaranteed decrease" is nearly free to compute and accounts for within-block correlation and scale. For derivative-informed GPs, where correlation and scale mismatch are severe, this should turn an impractical exact solve into a practical one.

Core Claim

Write the GP training system as $A\alpha = y$, with $A = K + \sigma^2 I$ the kernel matrix plus noise, $\alpha$ the unknown weights, and $r = y - A\alpha$ the current residual. Exactly solving for the block of unknowns $I$, with the others held fixed, lowers the dual quadratic objective $\tfrac12\alpha^\top A\alpha - \alpha^\top y$ by exactly

$$\Delta_I = \tfrac12\, r_I^\top A_{II}^{-1} r_I ,$$

where $r_I$ is the residual restricted to block $I$ and $A_{II}$ is the corresponding diagonal sub-block. This is the Gauss-Southwell-Quadratic rule proposed for general block coordinate descent in Let's Make Block Coordinate Descent Converge Faster. That paper supplies the method. Large-Scale Gaussian Processes via Alternating Projection instead scores blocks by $\|r_I\|_2$, which equals $\Delta_I$ only when $A_{II}$ is a multiple of the identity. Their method already caches a Cholesky factor of every $A_{II}$, so scoring all $n/b$ blocks of size $b$ costs $\mathcal{O}(nb)$ triangular-solve work. This is the same order as the residual update each iteration already pays.

Our claim is that the progress-aware rule matters little on smooth scalar GPs but matters a great deal on derivative-informed GPs. There, three things make the residual norm a misleading score. First, derivative entries of the kernel scale as the inverse squared lengthscale, so value and derivative residuals are not comparable. Second, nearby points' derivatives are strongly correlated. Third, for stationary kernels a point's value and its own gradient are uncorrelated, so the useful coupling runs between neighbours rather than within a point. The new contribution is the combination of an exact, progress-scored greedy block solver with a neighbourhood block structure for the $n(d+1)$ system, and the evidence of when the scoring matters.

Research Program

The first component is the solver. It is the alternating-projection solver of Wu et al. with three changes. It scores blocks by $\Delta_I$. It optionally down-weights blocks updated in the last few steps, to limit the redundancy that Bo and Sminchisescu identified. It uses blocks built for gradient data. We will compare three block designs: per-point blocks, which hold all $d+1$ unknowns of a set of $k$-means-clustered neighbouring points; per-type blocks, which hold values only or one derivative direction only; and random partitions. All three keep the $\mathcal{O}(n)$-memory, kernel-recomputed-on-the-fly property of the original method.

The second component is analysis. Applying the linear-rate argument of Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection blockwise gives a rate controlled by a block analogue of their $\ell_1$ strong-convexity constant. We will compute this constant, and the corresponding constant for the residual-norm rule, numerically on small derivative-GP systems. The goal is to predict in advance on which kernels, lengthscales and dimensions the new rule should win.

The third component integrates the solver into hyperparameter learning, the outer loop that Bo and Sminchisescu left open. The solver is warm-started across marginal-likelihood gradient steps, and the block scores are re-ranked after each kernel update.

Baselines

The naive reference point is exact Cholesky on the full $n(d+1)$ system, run where it fits in memory. It gives ground-truth weights and the error floor every iterative method is measured against. Above that size we use a long-run, tight-tolerance solve as reference.

The strongest existing exact solver is alternating projection with residual-norm block selection, from Large-Scale Gaussian Processes via Alternating Projection. That paper reports up to 27× faster training and 72× faster inference than conjugate gradients, and 84.5 hours on a single GPU for 4.1 million scalar points. We run it unchanged on the same $n(d+1)$ system, with the same block partitions, block size, GPU and stopping tolerance. The comparison then isolates the scoring rule. Beating it means reaching the same relative residual and test error in at least 2× less wall-clock time on the derivative benchmarks, without being slower on scalar benchmarks. No reported result was found on Lacuna for this method on derivative-observing GPs, so the baseline numbers will be produced here.

The second strong competitor is preconditioned conjugate gradients with batched kernel multiplies and a pivoted-Cholesky preconditioner, from Exact Gaussian Processes on a Million Data Points. That paper reports an exact-GP RMSE of 0.099 on Kin40K against 0.273 for the best sparse approximation. It gets the same preconditioner rank budget and the same memory budget as our method.

The third competitor is the incremental greedy block builder of Greedy Block Coordinate Descent for Large Scale Gaussian Process Regression, which reports 59× faster convergence than conjugate gradients on Sarcos. It is the closest prior method that also scores by objective decrease. It does so one coordinate at a time with Woodbury updates on the CPU, so we run it at the sizes where it is feasible.

Random and cyclic block selection serve as lower anchors. The key ablations hold everything fixed except the score: residual norm, Jacobi-rescaled residual norm, and $\Delta_I$. They are crossed with the three block designs.

Why not just…?

Why not just run Wu et al.'s solver on the derivative system as is? This is the real threat, and it is the main experiment. If residual-norm and $\Delta_I$ selection converge at the same speed on derivative GPs, the scoring rule adds nothing and the contribution reduces to the block design. We will report that outcome plainly. Our expectation that they differ rests on the scale and correlation structure of derivative kernels, which the numerically computed rate constants will confirm or refute before the large runs.

Why not just rescale coordinates by the kernel diagonal and keep the residual-norm rule? Diagonal (Jacobi) rescaling makes Gauss-Southwell equivalent to the Gauss-Southwell-Lipschitz rule of Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection. It fixes the value-versus-derivative scale mismatch but not the correlation between neighbouring points inside a block. It is therefore an ablation arm. If it captures most of the gain, we will say so and recommend it as the simpler method.

Why not just use preconditioned conjugate gradients? It parallelizes well. However, Wu et al. show its residual spikes and stalls under small noise, and derivative kernels are more ill-conditioned still. We will sweep noise and lengthscale to locate where, if anywhere, it remains competitive.

Why not just drop most derivatives, as d-KG does? Bayesian Optimization with Gradients keeps one directional derivative per point to cut cost. We include that model as an accuracy comparison: if the full-gradient GP predicts no better, exact solving is unnecessary.

Proposed Experiments

The derivative benchmarks are the synthetic Bayesian-optimization functions in the file: Branin, Rosenbrock, Ackley, Levy, Hartmann 6D and Cosine Mixture. For each we draw values and gradients at $n$ points up to the size where $n(d+1)$ reaches several hundred thousand unknowns. For Hartmann 6D that is roughly 50,000 points. Scalar controls are Kin40K, 3D Road and HouseElectric, checked against the conditions reported in the cited papers.

Metrics are relative residual and dual objective against wall-clock time and against kernel entries evaluated, iterations to a fixed tolerance, test RMSE and negative log-likelihood on held-out values and gradients, and the error in marginal-likelihood gradients during hyperparameter learning.

The decisive checks are three. First, on derivative benchmarks, $\Delta_I$ selection should reach tolerance substantially faster than residual-norm selection. It should also beat Jacobi-rescaled selection, especially at small noise and short lengthscales. Second, on scalar benchmarks it should match residual-norm selection within noise, showing the extra scoring cost is negligible. Third, the size of the gap across settings should track the numerically computed rate constants, so the theory predicts when the method helps rather than merely describing it afterwards.