A Gaussian process (GP) is a probabilistic model that predicts with calibrated uncertainty. To run on large datasets, it is usually compressed onto a small set of "inducing points": a few hundred learned anchor locations that summarize the whole function. These anchors are placed wherever they most improve total fit. The total is dominated by the largest demographic group, so the anchors should drift toward that group's region of feature space and leave small groups with a coarse, low-resolution model. We propose to test whether this happens and, if it does, to fix it at the source. The fix trains the sparse GP under an explicit fairness constraint, solved as a constrained optimization problem in which the anchor locations themselves respond to the constraint. The alternative is to bolt a fairness penalty onto a model whose capacity has already been spent.
The claim in two sentences is this. Part of the unfairness of scalable GP classifiers is a capacity-allocation failure, not only a decision-rule failure. A fixed budget of inducing points, moved by the dual variables of a fairness constraint, should reach a better accuracy–fairness trade-off and more reliable test-time fairness than the same constraint applied with anchors frozen where the ordinary objective put them. The idea is cheap to state and cheap to falsify, which is why it is worth doing first.
Core Claim and Relation to Prior Work
Two lines of evidence motivate the proposal. Approximation-Aware Bayesian Optimization shows that a sparse variational GP has a finite "representational budget." Training with the standard evidence lower bound spreads inducing points by global fit and blurs the regions that matter downstream, and redirecting them toward a task utility gives up to 10× fewer evaluations in optimization. That work never looks at demographic groups. Maximin Relative Improvement documents differential predictability: 73% of 400 US census configurations show moderate-to-extreme asymmetry in how predictable groups are. Taken together, these suggest that a group that is both small and hard to predict gets penalized twice by a sparse GP: it has few samples and few anchors.
The method comes from two sources. The model is the sparse variational GP classifier of Scalable Variational Gaussian Process Classification (inducing points, mini-batch training, 97.8% on MNIST with 200 inducing points), building on Gaussian Processes for Big Data. The solver is an augmented Lagrangian, which adds a quadratic penalty to the usual multiplier method. AL-CoLe shows this removes the oscillations and duality gaps of plain dual ascent in non-convex learning. Benchmarking Stochastic Approximation Algorithms for Fairness-Constrained Training finds that its smoothed stochastic variant (SSL-ALM) gives the best fairness–accuracy compromise for mini-batch deep networks.
The closest existing work differs in specific ways. Fair Kernel Regression through Cross-Covariance Operators solves fair kernel regression in closed form with independence operators. It needs full $n\times n$ inversion, does not scale, and gives no posterior uncertainty; it only sketches a GP extension. Fair Bayesian Optimization uses exact GPs as surrogates to tune a black-box learner's hyperparameters, so the GP never is the fair predictor. A Fair Bayesian Inference through Matched Gibbs Posterior shows that deterministic fair training ruins calibration and builds a fair posterior by sampling. It uses parametric models, sampling, and a fixed penalty weight, whereas we use a non-parametric variational model and a hard tolerance. None of these works treats the compression step itself as a place where unfairness enters, or makes the compressed representation a decision variable of the fairness problem.
A GP also offers a technical convenience that deep models lack. Group selection rates and true-positive rates are step functions with zero gradient almost everywhere, which forces the surrogate-and-buffer heuristics of Balancing Act. A probit GP instead gives a smooth posterior predictive probability $p_i = \Phi\big(\mu_i/\sqrt{1+\sigma_i^2}\big)$. Here $\mu_i$ and $\sigma_i^2$ are the posterior mean and variance of the latent function at input $i$, and $\Phi$ is the standard normal cumulative distribution function. Averaging $p_i$ over group-$g$ positives gives a differentiable expected true-positive rate $\widetilde{\mathrm{TPR}}_g$, and it automatically discounts points where the model is uncertain.
The problem we solve is
$$\max_{\;q(u),\,Z,\,\theta}\ \mathcal{L}_{\text{ELBO}}(q(u), Z, \theta)\quad \text{s.t.}\quad \big|\widetilde{\mathrm{TPR}}_g - \widetilde{\mathrm{TPR}}_{\text{all}}\big| \le \epsilon \ \ \text{for every group } g,$$
where $q(u)$ is the Gaussian variational distribution over inducing values, $Z$ the inducing locations, $\theta$ the kernel hyperparameters, and $\epsilon$ a disparity tolerance in rate units (for example 0.02). The analogous false-positive constraint gives full equalized odds. The key design choice is that $Z$ receives gradients from the constraint terms weighted by the multipliers, so anchors move toward groups whose constraints are binding.
Research Program
The first stage is diagnostic. We train ordinary sparse GP classifiers across a sweep of inducing-point counts $m$ and measure three things per group: the share of kernel "responsibility" each group receives from the anchors, relative to its population share; its average posterior variance; and its error. If the starvation story is right, minority-group error and variance should shrink faster with $m$ than majority-group error, and the gap should be largest when $m$ is small relative to the number of groups. This matters most for intersectional subgroups on census data, where the number of groups can rival $m$.
The second stage builds the constrained trainer. It uses per-group augmented Lagrangian updates in the SSL-ALM style, with natural-gradient steps on $q(u)$, ordinary gradient steps on $Z$ and $\theta$, and multiplier updates computed from running group-level estimates of the smooth rates. Because the rates are smooth expectations, we expect to need smaller buffers than Balancing Act. Whether that holds will be measured, not assumed.
The third stage asks whether the GP's uncertainty helps with the fairness generalization gap. The benchmarking paper and Balancing Act both report this gap: near-zero violation on training data and substantial violation on test data. We test two things. First, whether constraints on posterior-discounted rates transfer better than constraints on a deep network's hard rates. Second, whether per-group posterior variance on training data predicts which groups will violate at test time. If the second holds, it gives practitioners a warning signal that no deterministic method provides.
Baselines
The naive reference point is an unconstrained sparse GP classifier trained on the ordinary objective, as in Scalable Variational Gaussian Process Classification. We also report it with per-group post-hoc thresholds, which is what most practitioners would do first. It uses the same $m$, kernel, and optimizer steps as our method. Beating it means lower test equalized-odds gap at matched or better accuracy and expected calibration error.
The strongest existing competitor for constrained fair classification at scale is a deep network trained with SSL-ALM through the benchmark of Benchmarking Stochastic Approximation Algorithms. The file reports no specific table values for that paper, so our comparison number will come from rerunning its released toolkit. We run it on the identical Folktables splits, with the same $\epsilon$, the same group definitions, and a matched hyperparameter-search budget measured in trials and wall-clock time. We also run AL-CoLe on COMPAS. The only reported number there is a counterfactual gender-flip prediction-change rate: 7.6% unconstrained versus 1.5% with AL-CoLe. We will report that same metric so the comparison is direct. Beating these deep constrained methods means a smaller test-time violation at the same training tolerance, together with lower calibration error, at comparable accuracy. Matching them on accuracy is not required.
For kernel methods specifically, FACIL and NFACIL from Fair Kernel Regression are run exactly on subsamples small enough to invert. This shows how much the sparse model gives up relative to exact kernel fairness. No reported numeric result was found on Lacuna for FACIL, so all values will be produced here. The MMD logit penalty of Toward Fairness via MMD Regularization on Logits is attached to the same sparse GP as a soft-penalty competitor, with its weight swept over a grid of the same size as our $\epsilon$ sweep.
The ablations that isolate the key ingredient all share the same constrained trainer and differ only in how anchors are handled. In the first, anchors are learned by the ordinary objective and then frozen while the constrained problem is solved. In the second, anchors are initialized by per-group k-means in proportion to group size, or equally across groups, and left free to move without constraint. In the third, the ordinary objective is reweighted by fixed inverse group frequencies. In the fourth, the unconstrained model gets double the number of anchors. The proposal's central claim survives only if constraint-driven anchor movement beats all four at equal $m$.
Why not just…?
Why not just threshold an unconstrained sparse GP per group? Learning Non-Discriminatory Predictors proves that post-hoc correction of an accuracy-maximizing model is suboptimal outside linear-Gaussian settings, because information the model never learned cannot be recovered by moving thresholds. In a sparse GP that lost information has a physical location: regions with no anchors. The diagnostic stage tests this directly. If thresholded unconstrained models already match our trade-off curve, the capacity story is wrong and we will report that.
Why not just reweight minority groups in the objective, or add a soft fairness penalty? This is the most serious threat, because fixed reweighting also pulls anchors toward small groups. The difference is that multipliers find the weights needed to meet a stated tolerance $\epsilon$, and they adapt to differential predictability. Maximin Relative Improvement shows that uniform subsidies for hard groups can harm easy groups badly, with a 74% error increase in its North Dakota case. The reweighted and MMD-penalty ablations settle the question empirically. If a well-tuned reweighting matches us at equal tuning budget, the contribution shrinks to interpretability of $\epsilon$, and we will say so.
Why not just add more inducing points or initialize them per group? More anchors cost $O(m^3)$ per step, and with thousands of intersectional subgroups a per-group allocation is unaffordable. Still, for a handful of binary groups this may be enough. The doubled-$m$ and stratified-initialization ablations measure how many extra anchors the constrained method is worth. We expect the advantage to be concentrated in the regime where groups outnumber the budget, and to vanish for coarse binary partitions.
Why not just use a deep network with SSL-ALM and skip GPs? For raw accuracy on large tabular data that may well win. The proposal's bet is on calibration and test-time fairness, where A Fair Bayesian Inference through Matched Gibbs Posterior shows deterministic fair models degrade. The head-to-head on Folktables measures both the test-time violation and the expected calibration error, so a loss on either would be visible.
Proposed Experiments
We start on the two-dimensional banana dataset from Scalable Variational Gaussian Process Classification, adding a synthetic minority group placed in a sparse region. This lets us visualize where anchors go with and without constraints. The main benchmark is Folktables ACSIncome across the 400 state, partition, and feature-set configurations of Maximin Relative Improvement, including intersectional sex×race subgroups. It is complemented by Adult, COMPAS, and Communities and Crime for comparability with Fair Kernel Regression and Fair Bayesian Optimization. The metrics are test accuracy, per-group error, the train and test equalized-odds gap (and their difference), the fraction of groups violating $\epsilon$ at test time, expected calibration error, Brier score, and wall-clock time. For census configurations we also report worst-group relative improvement.
Three checks decide the proposal. The first is whether the minority–majority error gap in unconstrained sparse GPs shrinks with $m$. If it is flat, capacity is not the mechanism, and the work reduces to a constrained sparse GP. The second is whether moving anchors beats frozen anchors, stratified initialization, reweighting, and doubled $m$ at equal budget. Of the four, reweighting is the one that could sink the claim. The third is whether training-time posterior variance per group correlates with test-time fairness violation across the 400 configurations, and whether our test-time violation is below that of SSL-ALM deep networks at the same tolerance. A positive result on all three would show that in scalable probabilistic models, fairness has to be enforced where the model decides what to remember, not only where it decides what to predict.
References
- Approximation-Aware Bayesian Optimization
- Maximin Relative Improvement: Fair Learning as a Bargaining Problem
- Scalable Variational Gaussian Process Classification
- Gaussian Processes for Big Data
- AL-CoLe: Augmented Lagrangian for Constrained Learning
- Benchmarking Stochastic Approximation Algorithms for Fairness-Constrained Training of Deep Neural Networks
- Fair Kernel Regression through Cross-Covariance Operators
- Fair Bayesian Optimization
- A Fair Bayesian Inference through Matched Gibbs Posterior
- Balancing Act: Constraining Disparate Impact in Sparse Models
- Toward Fairness via Maximum Mean Discrepancy Regularization on Logits Space
- Learning Non-Discriminatory Predictors