A Gaussian process (GP) is a regression model that returns both a prediction and an honest error bar. It is the default tool for guiding expensive searches such as Bayesian optimization. Exact GPs cost cubic time in the number of data points, so practitioners use sparse GPs, which summarize the data through a small set of $m$ "inducing points", virtual anchor locations that carry the fit. Sparse GPs are also unusually fragile to corrupted data. With so few anchors, a cluster of bad measurements can pull the fit toward itself and then be reported with high confidence. Iteratively reweighted least squares (IRLS) is the classical cure for bad measurements in simpler models. It fits the model, gives each point a weight that shrinks as its error grows, refits with those weights, and repeats. So far IRLS has been applied to kernel models only with the full, cubic-cost kernel matrix.
This note proposes putting IRLS inside the sparse GP. The claim is that the combination works well because of structure, not just because both pieces are present. For fixed weights, the best sparse GP has a closed form built from weighted sums over data points. Those sums can be accumulated one mini-batch at a time, so each reweighting sweep costs $O(nm^2)$ and never needs the whole dataset in memory. On top of this loop we add two things. The first is annealing: the robust loss starts nearly quadratic and is sharpened gradually. The second is weight-aware choice of inducing points, so that corrupted points neither pull the fit nor use up the model's limited set of anchors.
Core Claim
A sparse GP trained by annealed IRLS has three properties. It recovers the clean function at contamination levels, around 50–80%, where likelihood-based robust sparse GPs fail. It does so in streaming mini-batches rather than the full batches that current robust methods require. And its uncertainty stays calibrated, because the learned weights enter the model as per-point noise inflation rather than being discarded.
The part that would be new is that the reweighting loop controls two things at once, the fitted function and the placement of the $m$ inducing points. Existing robust sparse GPs do neither of these through an iterated residual loop.
Relation to Prior Work
Four papers motivate the gap.
- Kernel Cauchy ridge regression. On the Robustness of Kernel Ridge Regression Using the Cauchy Loss Function solves Cauchy-loss kernel ridge regression by IRLS with weights $w_i \propto 1/(\sigma^2 + r_i^2)$. It is strong under Pareto noise, but it factors the full $n\times n$ matrix at every iteration and returns no posterior variance. We keep its weight function and remove both limitations.
- Robust computation-aware GPs (RCaGP). Robust and Computation-Aware Gaussian Processes reports that low-rank approximations make outlier sensitivity worse. Its fix down-weights each point once, by distance from a fixed prior mean, and needs full-batch training. Our weights are recomputed from the model's own residuals and accumulate over mini-batches.
- Robust scalable GP regression. Robust and Scalable Gaussian Process Regression and Its Applications is the closest method. It combines a Gaussian-plus-uniform mixture likelihood with stochastic variational inference over inducing points. Its responsibilities do act as soft weights, but they come from a uniform outlier model that the authors call a weak assumption for structured corruption. It also has no annealing, and its inducing points are placed by the ordinary evidence bound.
- Approximation-aware Bayesian optimization. Approximation-Aware Bayesian Optimization shows that the inducing budget should be steered toward the regions that matter. Its steering signal takes observed values at face value, so a spuriously high outlier would attract the budget.
Two papers supply the method.
- Graduated non-convexity (GNC). Graduated Non-Convexity for Robust Spatial Perception supplies the Black-Rangarajan duality. The duality says a robust loss equals a weighted least squares problem with auxiliary weights. The same paper supplies the annealing schedule that tolerates 70–95% outliers without an initial guess. It was only ever applied to geometric problems.
- IRLS convergence theory. Global Linear and Local Superlinear Convergence of IRLS for Non-Smooth Robust Regression gives the convergence theory we will try to extend to the sparse kernel case.
Two further papers are set aside or used for contrast.
- Iteratively reweighted kernel machines efficiently learn sparse functions reweights input coordinates rather than observations. It is orthogonal to this proposal and not used.
- GPnn, from Leveraging Locality and Robustness to Achieve Massively Scalable Gaussian Process Regression, is robust to a mis-specified model but has no defense when an outlier lands among a test point's neighbors.
Research Program
The weighted sparse posterior. Let $K_{mm}$ be the kernel among the inducing points and $k_i$ the kernel vector between point $x_i$ and the inducing points. Let $\sigma^2$ be the noise variance and $w_i\in(0,1]$ the current weight on point $i$. Treat each point as having noise variance $\sigma^2/w_i$. The optimal Gaussian posterior over the inducing values $u$ then has precision and mean
$$\Sigma_u^{-1} = K_{mm}^{-1} + K_{mm}^{-1}\Big(\tfrac{1}{\sigma^2}\sum_i w_i k_i k_i^\top\Big)K_{mm}^{-1},\qquad \mu_u = \Sigma_u K_{mm}^{-1}\tfrac{1}{\sigma^2}\sum_i w_i k_i y_i .$$
This is the standard collapsed sparse-GP solution with heteroscedastic noise. It depends on the data only through two sums, an $m\times m$ matrix and an $m$-vector. A sweep therefore streams over mini-batches, updating the weights from the current residuals and adding each batch's contribution to the sums. The closed-form solve at the end of the sweep costs $O(m^3)$.
This design sidesteps the known instability of naive mini-batch IRLS. Within a sweep the model is frozen, so every batch's weights are computed against the same fit. As an option, the sums can be computed from exponentially averaged statistics to support true streaming.
Annealing. The weight function follows the GNC continuation for Geman-McClure or truncated least squares losses. A parameter $\mu$ starts large, where the loss is nearly quadratic and all weights are close to 1. It shrinks across sweeps until the target robust loss is reached. The robust scale is tied to a median-absolute-deviation estimate of the residuals, to reduce the scale-tuning sensitivity that the KCRR paper reports.
Weight-aware inducing points. Between sweeps, inducing locations are re-selected by a pivoted Cholesky factorization of the kernel restricted to points with weight above a threshold, with each candidate's leverage multiplied by $w_i$. Points the model has decided are outliers can then no longer claim anchors. Kernel hyperparameters are updated by gradient steps on the weighted collapsed bound.
Uncertainty. Predictive variance comes directly from $\Sigma_u$. Because weights shrink the effective sample size, variance should widen automatically in regions dominated by down-weighted points. A GPnn-style post-hoc noise recalibration on a held-out split is included as a separate component so that we can measure what it adds.
Theory. We will try to show that the annealed loop is a majorize-minimize scheme on the weighted collapsed objective, which would guarantee monotone descent at each fixed $\mu$. We also want to characterize when inducing re-selection preserves that descent.
Baselines
Naive reference points. The first is a standard sparse variational GP with a Gaussian likelihood, trained by mini-batch variational inference with the same $m$ and the same optimizer budget. It shows how much damage contamination does. The second is the exact robust reference, KCRR run by full-matrix IRLS on datasets small enough to allow it. It tells us what our sparse approximation costs. The KCRR paper reports MAE 0.3984 on Yacht under Pareto noise, against 1.0794 for the MCCR baseline. Our sparse variant should come within a small margin of 0.3984 at modest $m$.
Strongest robust sparse competitor. This is the Gaussian-uniform mixture sparse GP from Robust and Scalable Gaussian Process Regression and Its Applications. It is the most direct rival: robust, scalable, trained by mini-batch variational inference, with soft outlier assignments. It reports MAE 0.03 on the Neal 1D benchmark with 80% outliers, against 0.76 for the standard variational free energy baseline. Because that number is close to saturated, Neal alone cannot separate the methods. Beating this baseline means matching it on Neal and the uniform-outlier Friedman settings, and clearly lower MAE and NLL under structured corruption (clustered or offset outliers). Both methods get the same inducing count, the same mini-batch size, the same wall-clock limit, and equal hyperparameter search budgets.
Robust baseline for Bayesian optimization. RCaGP from Robust and Computation-Aware Gaussian Processes is the robust baseline for optimization loops. It is run full-batch with the authors' prior-mean construction, at the problem sizes where it fits in memory. The paper reports that it wins on contaminated UCI tasks and on Lasso DNA with 25% outliers, but no reported result found on Lacuna for its numeric MAE, NLL, or objective values. We will therefore rerun it ourselves.
Large-n baseline. GPnn is the fast large-$n$ baseline. Its reported timing is about 30 seconds for $n=1.6\times10^6$ on HouseElectric.
Ablations. Three ablations isolate the key ingredients: IRLS without annealing (fixed $\mu$), IRLS with ordinary inducing placement, and full-batch versus streamed statistics.
Why not just…?
Why not just use a Student-t likelihood in a standard sparse variational GP? This is the most serious alternative, because a Student-t likelihood is a scale mixture of Gaussians and its variational updates are an implicit reweighting. It has no annealing, though, and its heavy-tail parameter is usually learned. At high contamination the likelihood can explain the outliers by fattening its tails instead of rejecting them. It is included as a baseline under the same budget. If it matches our method at 50–80% structured contamination, the contribution shrinks to speed and streaming, and we will say so.
Why not just fit once, delete the largest residuals, and refit? This is hard, two-step IRLS. It fails when the initial non-robust fit is already dragged toward a dense outlier cluster, which is exactly the situation GNC was designed for. We run it with a threshold tuned on validation data. The Friedman sweep over contamination rates will show where it breaks down.
Why not just use nearest-neighbor GPs with a robust local estimate? In low-dimensional, very large-$n$ problems a local median over neighbors may be competitive and faster. We treat that as a real threat on HouseElectric-scale data. It should degrade in 60–180 dimensional optimization, where GPnn notes that neighbor search slows down, and where scattered outliers still contaminate small neighborhoods.
Proposed Experiments
Synthetic contamination sweep. We use Neal 1D and Friedman 10D with contamination from 0 to 80% under three outlier types: uniform, clustered with an offset, and heavy-tailed Cauchy or Pareto noise. We report test MAE, NLL, 95% interval coverage, and the fraction of inducing points sited within a lengthscale of an outlier cluster. The last metric directly tests the claim about protecting the anchor budget.
Scaling on UCI. On Protein, Song and HouseElectric with injected contamination, we report the same metrics plus peak GPU memory and wall-clock time. The goal is to show that the streamed version matches full-batch accuracy while its memory stays roughly flat as $n$ grows.
Bayesian optimization. On Lasso DNA (180D) with a 25% outlier rate, including spuriously high values, we compare best true objective found against RCaGP and an approximation-aware sparse GP. The reference point is that Approximation-Aware Bayesian Optimization reports up to 10x fewer evaluations than the standard evidence-bound baseline, measured on clean objectives.
Qualitative check. On the 2013 Dow Jones flash-crash series, the method should hold a stable estimate through the anomaly while its error bars widen over it.
Decisive result. The decisive result is the clustered-outlier Friedman setting at 50% or more contamination. If annealed, weight-aware IRLS does not beat both the mixture-likelihood sparse GP and the Student-t sparse GP there on MAE and coverage, the central claim fails.
References
- On the Robustness of Kernel Ridge Regression Using the Cauchy Loss Function
- Robust and Computation-Aware Gaussian Processes
- Robust and Scalable Gaussian Process Regression and Its Applications
- Approximation-Aware Bayesian Optimization
- Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejection
- Global Linear and Local Superlinear Convergence of IRLS for Non-Smooth Robust Regression
- Iteratively reweighted kernel machines efficiently learn sparse functions
- Leveraging Locality and Robustness to Achieve Massively Scalable Gaussian Process Regression