A Gaussian process (GP) is a regression model that returns a prediction together with a calibrated error bar. Exact training on $n$ points requires solving an $n \times n$ linear system. Two families of methods scale this up. The first splits the data across machines, fits an independent small GP on each shard, and averages the shard predictions; these are called committee machines. They need one round of communication, but they never recover the exact answer. The second keeps the model exact and solves the full system iteratively with conjugate gradients (CG). CG needs a synchronization across all machines at every iteration, often hundreds of them.
This note proposes a method between the two. A committee's average is the first step of a distributed optimizer from the federated-learning literature, one that exploits how similar the machines' local problems are. Taking a few more corrected steps converges to the exact GP. When data are split at random, each shard's local problem is a close stand-in for the global one. A shard is large enough when it exceeds the number of kernel directions the full posterior can resolve above the noise. In that regime, the number of communication rounds should be set by that closeness rather than by the conditioning of the full kernel matrix, and it should stay nearly flat as $n$ grows.
Core Claim
The posterior mean of a GP with Gaussian noise minimizes a strongly convex quadratic, a regularized least-squares fit in the kernel's function space. That objective splits into a sum over shards. Each shard term has its own curvature, given by that shard's scaled kernel covariance plus the prior.
Function-similarity theory shows that proximal methods in the DANE family pay communication rounds according to how close the local curvatures are to the global one, not according to global smoothness. Tian et al. phrase this as a relative condition number. With $H$ the global curvature operator and $H_i$ shard $i$'s curvature rescaled by the number of shards, the relevant condition is
$$(1-\delta)\,H_i \preceq H \preceq (1+\delta)\,H_i .$$
Under this condition a local-solve-then-average iteration shrinks the error by roughly a factor $\delta$ per round, because on a quadratic it is a Richardson iteration preconditioned by $H_i^{-1}$.
The GP-specific claim is that under random partitioning $\delta$ shrinks roughly like $\sqrt{d_{\text{eff}}\log n_i / n_i}$. Here $n_i$ is the shard size and $d_{\text{eff}}$ is the kernel's effective dimension at the noise level, meaning the number of eigen-directions of the kernel above the noise. This rate is what matrix concentration gives for sampled covariance operators. The consequence is that exact-GP solves across $M$ machines need about $\log(1/\epsilon)/\log(1/\delta)$ rounds, independent of $n$ once shards exceed $d_{\text{eff}}$.
The robust Bayesian committee machine (rBCM) of Distributed Gaussian Processes closely resembles round one of this iteration without the similarity correction. That explains why it works well and why it plateaus.
Relation to Prior Work
The GP-scaling papers motivate the problem. Exact Gaussian Processes on a Million Data Points runs CG with pivoted-Cholesky preconditioning and on-the-fly kernel blocks. It reaches test RMSE 0.099 on Kin40K versus 0.273 for sparse GP regression, which shows that exactness matters. It is, however, a single-node multi-GPU method: every CG iteration is a global matrix-vector product.
rBCM (Distributed Gaussian Processes) takes the opposite trade. It uses one communication round and entropy-weighted aggregation. It scales to 17 million points but reaches RMSE 35.5 on the Airline delay data, against 33.0 for a variational sparse GP (Gaussian Processes for Big Data) trained on a subset. We keep rBCM's shard-local Cholesky factorizations and reuse them as the local solver inside an iterative scheme. We do not treat them as the final answer.
The similarity literature supplies the method. The stabilized proximal-point method S-DANE (Stabilized Proximal-Point Methods for Federated Optimization) tolerates inexact local solves by moving the center of the proximal term. Its accelerated variant replaces $\delta$ with $\sqrt{\delta}$. Optimal gradient sliding (Optimal Gradient Sliding and its Application to Optimal Distributed Optimization Under Similarity) gives the matching lower-bound rate. These papers analyze generic strongly convex losses. None identifies what controls $\delta$ for kernel objectives, or observes that GP noise makes the posterior-mean problem strongly convex by construction.
The research file flags a tension: the GP marginal likelihood is nonconvex, while similarity guarantees assume strong convexity. We resolve it by applying the guarantees only to the inner linear solves, which are convex. Hyperparameters are learned in an outer loop that makes no convergence claim.
Two existing works constrain the design. Federated Gaussian Process: Convergence, Automatic Personalization and Multi-Fidelity Modeling trains a shared GP prior with federated averaging and leaves length-scale convergence open. We do not address privacy-constrained federated GPs. Our setting is a data-parallel cluster in which inputs can be exchanged but synchronization is expensive. Asynchronous Distributed Gaussian Process Regression and Differentially Private Federated Bayesian Optimization with Distributed Exploration argue for spatial partitioning, whereas rBCM finds random partitioning works well. Our theory predicts exactly this split. Spatial shards make local models sharp but inflate $\delta$, so the iteration slows or diverges. That makes the choice of partition a measurable trade-off instead of a matter of taste.
Research Program
We will build a solver that keeps one Cholesky factor per shard, computed once for that shard's $n_i \times n_i$ kernel matrix. Each round proceeds in four steps. The workers exchange the current coefficient vector. Each worker evaluates the global residual on its own points, which costs $O(n\,n_i)$ kernel evaluations computed on the fly as in BBMM. Each worker then applies its shard-local inverse through the cached factor. Finally, the corrections are averaged.
The inexact variant follows S-DANE and replaces the exact local solve with a few local CG steps. The accelerated variant adds momentum. The solver handles many right-hand sides at once, meaning $\mathbf{y}$ plus the random probe vectors that BBMM uses to estimate the log-determinant gradient. This lets the same machinery drive marginal-likelihood hyperparameter learning, warm-started across outer steps.
The analysis has three parts. First, we will prove the relative-similarity bound in terms of $d_{\text{eff}}$ and shard size, for random partitions. Second, we will derive round complexity for the exact, inexact, and accelerated variants. Third, we will characterize how $\delta$ degrades under spatial or label-skewed partitions. We will also estimate $\delta$ empirically at run time from a few power iterations on $H_i^{-1}H - I$, so that the solver can report in advance whether a given partition will converge fast.
Baselines
The naive reference point is rBCM (Distributed Gaussian Processes) on the same shards and the same hyperparameters. It is round one of our method in spirit, so any accuracy it leaves on the table is exactly what extra rounds must recover. Beating it means lower test RMSE and negative log predictive density at a stated round budget. Its reported Airline RMSE is 35.5.
The strongest existing exact method is BBMM with pivoted-Cholesky-preconditioned CG (Exact Gaussian Processes on a Million Data Points). We will distribute it across the same $M$ nodes with row-sharded matrix-vector products, the same kernel, the same hyperparameters, and the same tolerance on the relative residual. Its reported figures are Kin40K RMSE 0.099 and HouseElectric (1.3 million points) trained in under two hours on 8 V100s. Beating it means reaching the same residual, and matching its RMSE to within noise, with at least five times fewer synchronizations. Total floating-point work must be no more than about twice BBMM's, and wall-clock time must be lower once inter-node latency is non-negligible.
The accuracy-matched cheap competitor is a variational sparse GP (Gaussian Processes for Big Data) given the same wall-clock budget and a tuned number of inducing points. Its reported Airline RMSE is 33.0.
The ablation that isolates our key ingredient is CG preconditioned by the averaged shard-local inverses. This uses the same preconditioner but none of the proximal, stabilized, or accelerated machinery, and all methods share one tuning budget for step sizes and restart rules.
Why not just…?
Why not just put the shard-local inverses inside CG as a block preconditioner? This is the serious threat, because on a quadratic our iteration is closely related to additive-Schwarz preconditioning. The ablation above settles it. If preconditioned CG matches our round counts, the contribution reduces to two things. One is a similarity-based theory of when shard-local preconditioning works for GPs, tied to $d_{\text{eff}}$ and to the partitioning scheme. The other is the observation that committee machines are its first iterate. We would report that honestly and adopt the CG form.
We expect the proximal form to still win in two places. The first is inexact local solves, where S-DANE's analysis tolerates cheap local work and a fixed preconditioner inside CG must be applied exactly. The second is the anytime property: each round yields a valid predictor that improves on rBCM.
Why not just use rBCM, as it already scales to 17 million points? Its Airline RMSE of 35.5 trails a variational sparse GP's 33.0, and it cannot approach the exact answer at all. Our round-versus-RMSE curves will show whether two or three extra rounds close that gap.
Why not just use a sparse variational GP? Sparse approximations saturate as data grow: 0.273 versus 0.099 on Kin40K (Exact Gaussian Processes on a Million Data Points). They also smooth away sharp local structure (Approximation-Aware Bayesian Optimization). We include them at equal wall-clock budget so that the accuracy cost of approximation is visible, not assumed.
Why not just learn hyperparameters on a subset and skip the distributed outer loop? This is plausibly adequate. BBMM itself pretrains on 10,000 points, so we make subset pretraining our default initialization. The distributed outer loop is scored only by the likelihood and RMSE it adds after pretraining. If that gain is negligible, we will drop the loop and present the method as a solver.
Proposed Experiments
We will use Kin40K, UK Housing, HouseElectric, and Airline delays at 2 to 5 million points, with $M$ from 4 to 64 nodes on an ordinary Ethernet cluster. Because wall-clock time depends on hardware, we will also report hardware-independent counts: synchronization rounds, bytes moved, and kernel evaluations. We will sweep shard size across the estimated $d_{\text{eff}}$ of each dataset.
The first decisive check tests the scaling prediction. With random shards held above $d_{\text{eff}}$, rounds to a fixed residual should stay nearly flat as $n$ grows by a factor of ten, while distributed BBMM's iteration count grows. If rounds instead track the kernel condition number, the central claim fails.
The second check tests the partition trade-off. As we move from random to KD-tree partitions, the measured $\delta$ and the round count should rise together, and rBCM's one-round accuracy should change in the direction reported by Distributed Gaussian Processes versus Asynchronous Distributed Gaussian Process Regression. That would turn a disagreement between the two papers into a predicted curve.
The third check is the preconditioned-CG ablation described above. It determines whether the similarity machinery or only the shard preconditioner accounts for the gains.
References
- Acceleration in Distributed Optimization under Similarity
- Distributed Gaussian Processes
- Exact Gaussian Processes on a Million Data Points
- Gaussian Processes for Big Data
- Stabilized Proximal-Point Methods for Federated Optimization
- Optimal Gradient Sliding and its Application to Optimal Distributed Optimization Under Similarity
- Federated Gaussian Process: Convergence, Automatic Personalization and Multi-fidelity Modeling
- Asynchronous Distributed Gaussian Process Regression
- Differentially Private Federated Bayesian Optimization with Distributed Exploration
- Approximation-Aware Bayesian Optimization