# Bias-Free Scalable Gaussian Processes via Randomized Truncations

arXiv: https://arxiv.org/abs/2102.06695 · HTML: https://mlsanity.com/paper/2102.06695/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 41 references that are in the map.
- First posted on arXiv 12 Feb 2021.

## Builds on (most cited first, 21 of 21)

- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Gaussian Processes for Big Data](https://mlsanity.com/paper/1309.6835/) (2013)
- [Residual Flows for Invertible Generative Modeling](https://mlsanity.com/paper/1906.02735/) (2019)
- [Efficiently Sampling Functions from Gaussian Process Posteriors](https://mlsanity.com/paper/2002.09309/) (2020)
- [Exact Gaussian Processes on a Million Data Points](https://mlsanity.com/paper/1903.08114/) (2019)
- [Distributed Gaussian Processes](https://mlsanity.com/paper/1502.02843/) (2015)
- [On the Error of Random Fourier Features](https://mlsanity.com/paper/1506.02785/) (2015)
- [Hierarchical Nearest-Neighbor Gaussian Process Models for Large Geostatistical Datasets](https://mlsanity.com/paper/1406.7343/) (2014)
- [Understanding Probabilistic Sparse Gaussian Process Approximations](https://mlsanity.com/paper/1606.04820/) (2016)
- [Generalized Product of Experts for Automatic and Principled Fusion of Gaussian Process Predictions](https://mlsanity.com/paper/1410.7827/) (2014)
- [A general framework for Vecchia approximations of Gaussian processes](https://mlsanity.com/paper/1708.06302/) (2017)
- [Rates of Convergence for Sparse Variational Gaussian Process Regression](https://mlsanity.com/paper/1903.03571/) (2019)
- [Constant-Time Predictive Distributions for Gaussian Processes](https://mlsanity.com/paper/1803.06058/) (2018)
- [Scalable Log Determinants for Gaussian Process Kernel Learning](https://mlsanity.com/paper/1711.03481/) (2017)
- [Preconditioning Kernel Matrices](https://mlsanity.com/paper/1602.06693/) (2016)
- [Randomized Automatic Differentiation](https://mlsanity.com/paper/2007.10412/) (2020)
- [On Russian Roulette Estimates for Bayesian Inference with Doubly-Intractable Likelihoods](https://mlsanity.com/paper/1306.4032/) (2013)
- [SUMO: Unbiased Estimation of Log Marginal Probability for Latent Variable Models](https://mlsanity.com/paper/2004.00353/) (2020)
- [Linear-time inference for Gaussian Processes on one dimension](https://mlsanity.com/paper/2003.05554/) (2020)
- [Efficient Optimization of Loops and Limits with Randomized Telescoping Sums](https://mlsanity.com/paper/1905.07006/) (2019)
- [Enabling scalable stochastic gradient-based inference for Gaussian processes by employing the Unbiased LInear System SolvEr (ULISSE)](https://mlsanity.com/paper/1501.05427/) (2015)

## Built on by (most cited first, 16 of 16)

- [Rectangular Flows for Manifold Learning](https://mlsanity.com/paper/2106.01413/) (2021)
- [Posterior and Computational Uncertainty in Gaussian Processes](https://mlsanity.com/paper/2205.15449/) (2022)
- [Preconditioning for Scalable Gaussian Process Hyperparameter Optimization](https://mlsanity.com/paper/2107.00243/) (2021)
- [When are Iterative Gaussian Processes Reliably Accurate?](https://mlsanity.com/paper/2112.15246/) (2021)
- [Large-Scale Gaussian Processes via Alternating Projection](https://mlsanity.com/paper/2310.17137/) (2023)
- [SKIing on Simplices: Kernel Interpolation on the Permutohedral Lattice for Scalable Gaussian Processes](https://mlsanity.com/paper/2106.06695/) (2021)
- [Computation-Aware Gaussian Processes: Model Selection And Linear-Time Inference](https://mlsanity.com/paper/2411.01036/) (2024)
- [Variational Nearest Neighbor Gaussian Process](https://mlsanity.com/paper/2202.01694/) (2022)
- [Neural Implicit Manifold Learning for Topology-Aware Density Estimation](https://mlsanity.com/paper/2206.11267/) (2022)
- [Multi-fidelity Monte Carlo: a pseudo-marginal approach](https://mlsanity.com/paper/2210.01534/) (2022)
- [Scaling Structured Inference with Randomization](https://mlsanity.com/paper/2112.03638/) (2021)
- [Recommendations for Baselines and Benchmarking Approximate Gaussian Processes](https://mlsanity.com/paper/2402.09849/) (2024)
- [Learning Hyperparameters via a Data-Emphasized Variational Objective](https://mlsanity.com/paper/2502.01861/) (2025)
- [Barely Biased Learning for Gaussian Process Regression](https://mlsanity.com/paper/2109.09417/) (2021)
- [Kernel Multigrid: Accelerate Back-fitting via Sparse Gaussian Process Regression](https://mlsanity.com/paper/2403.13300/) (2024)
- [Certifiable Safe Model-Based Reinforcement Learning with Control-Affine Dynamics Approximation](https://mlsanity.com/paper/2607.16501/) (2026)

## Abstract (arXiv)

Scalable Gaussian Process methods are computationally attractive, yet introduce modeling biases that require rigorous study. This paper analyzes two common techniques: early truncated conjugate gradients (CG) and random Fourier features (RFF). We find that both methods introduce a systematic bias on the learned hyperparameters: CG tends to underfit while RFF tends to overfit. We address these issues using randomized truncation estimators that eliminate bias in exchange for increased variance. In the case of RFF, we show that the bias-to-variance conversion is indeed a trade-off: the additional variance proves detrimental to optimization. However, in the case of CG, our unbiased learning procedure meaningfully outperforms its biased counterpart with minimal additional computation.