Tuning Private Gaussian Processes on Subsamples Priced in Privacy

Choosing the settings of a privately trained model is itself a privacy leak. In differential privacy (a guarantee that the output barely changes whether or not any one person's record is used), every tuning trial that touches the sensitive data spends part of a fixed privacy budget. Practitioners either ignore this cost or pay for a handful of full-data trials. There is a cheaper option that nobody has used deliberately. If a trial runs on a random subsample in which each record is included with probability $q$, the trial's privacy cost shrinks sharply, because an attacker cannot tell whether a target record was even used. This effect is called privacy amplification by subsampling. Small-$q$ trials are therefore cheap proxies for the full-data model, and their price is counted in privacy rather than compute. That turns private tuning into a multi-fidelity optimization problem: a search that mixes many cheap, approximate evaluations with a few expensive, accurate ones.

The complication is that under privacy, the cheap proxy is not simply a blurrier copy of the expensive one. The noise a private model needs depends on how much data it sees. So the best settings, such as the number of inducing points in a sparse Gaussian process, can move as $q$ changes. We propose a tuner for private sparse Gaussian processes whose surrogate models this movement explicitly. The tuner spends privacy according to measured value per unit of privacy, and it abandons small subsamples once their agreement with the full-data model falls below a known break-even point. The tuner may also find that no subsample is worth its price, and we treat that as a valid outcome.

Core Claim

The claim has three parts, each testable separately. First, the subsampling rate $q$ acts as a fidelity knob whose cost is privacy. Under the Sampled Gaussian Mechanism analysis of Mironov et al., the Rényi privacy cost of a subsampled Gaussian step falls roughly quadratically in $q$ when $q$ is small. For a trial that uses a subsample for its whole run, the tight accounting tools of Balle, Barthe & Gaboardi bound the whole trial as a subsampled mechanism. The result is that a 5% trial can cost far less than 5% of a full trial.

Second, the fidelity is non-monotone and drifts. Among good configurations, the rank agreement between a subsample trial and the full-data trial is expected to be much weaker than the global agreement. This is the failure Klein et al. found for ordinary proxies, and we predict privacy makes it worse near the optimum. The mechanism is visible in Smith, Álvarez & Lawrence: private sparse Gaussian process accuracy on downsampled MNIST peaked at about 21 inducing points, and more points raised sensitivity and therefore noise. Where that peak sits should depend on sample size, so it should move with $q$.

Third, a surrogate that models this drift, together with a stopping rule based on the critical correlation threshold of Zaytsev & Burnaev, should reach better final utility at a fixed total privacy budget than single-fidelity private tuning. That threshold result proves that below a certain cross-fidelity correlation, the minimax-optimal policy discards low-fidelity data entirely.

What Exists and What Does Not

Three strands of prior work define the space. The first privatizes Gaussian processes. Smith et al. 2021 route private labels through inducing points to bound sensitivity, and they select hyperparameters with the exponential mechanism. Honkela privatizes the sufficient statistics that link data to fixed inducing points, and adds a noise-aware update that keeps the covariance matrix valid. Neither uses subsampling amplification, and neither treats tuning as a budgeted search. We reuse both as the model being tuned.

The second strand trains Bayesian models privately on subsamples. DPVI combines mini-batch subsampling, gradient clipping and moments accounting, but only for parametric models. It explicitly leaves open how to tune the subsampling rate without spending privacy, and that open problem is the one we target.

The third strand does private Bayesian optimization. Kusner et al. privatize only the released optimum. DP-GIBO and MoMA-GP-UCB are single-fidelity methods, the latter under the much noisier local privacy model. On the multi-fidelity side, MF-GP-UCB and CAMO assume that fidelity improves monotonically toward the target and that cost means compute. Our setting violates both assumptions, and no paper in the file combines fidelity selection with privacy accounting.

Research Program

The model being tuned is a private sparse variational Gaussian process: a Gaussian process compressed to $m$ inducing points (a small set of summary locations that carry the model's information), trained with per-example clipping and Poisson mini-batches in the style of DPVI. It uses Honkela's noise-aware covariance update for stability, and inducing points placed on public inputs as in Smith et al. Subsampled training is also what makes this model scale. Citi Bike, with 1.46 million trips, is out of reach for exact $\mathcal{O}(n^3)$ inference.

A tuning trial draws a secret Poisson subsample at rate $q$ and trains with hyperparameter vector $h$. The vector $h$ covers the inducing-point count $m$, lengthscale, clipping threshold, and the noise split between training and evaluation. The trial then reports a privatized validation score. Its privacy cost $c(q,h)$ is computed exactly with subsampled Rényi accounting. The entire tuning run plus the final release is composed into one end-to-end guarantee.

The surrogate is a Gaussian process over $(h, \log q)$. Its kernel is a product of a hyperparameter kernel and a fidelity kernel, plus one structured term: a learned shift $\mu(\log q)$ in the location of the optimum along the privacy-sensitive coordinates $m$ and the noise split. This lets the model represent "good at 5% means $m$ should be larger at 100%" rather than "good at 5% means good at 100%."

Queries maximize information gain about the full-data optimum per unit privacy spent:

$$ a(h,q) = \frac{\mathrm{IG}\big(h^\star_{q=1};\, y(h,q)\big)}{c(q,h)}, $$

where $\mathrm{IG}$ is the expected reduction in entropy of the full-data optimizer $h^\star_{q=1}$ from observing the noisy score $y(h,q)$.

A switch rule accompanies the acquisition. The surrogate's posterior estimate of cross-fidelity correlation among the current top candidates is compared with the Zaytsev–Burnaev threshold, and fidelities below it are removed from the query set. This estimate is computed only from already-privatized scores, so it adds no privacy cost.

We will also report a measurement study that stands on its own. It traces rank correlation against $q$, both globally and within the top decile of configurations, alongside the privacy cost against $q$. The study will show whether Gap 1 in the file is real at all.

Baselines

The naive reference is non-private tuning followed by private training, which quietly spends no tuning budget. Smith et al. 2018 (Differentially Private Regression with Gaussian Processes) report 14.3 cm RMSE on !Kung with non-private tuning, versus 17.4 cm with private selection. We report this reference as an upper bound on what honest methods can reach, not as a competitor.

The strongest existing honest method is the exponential-mechanism hyperparameter selection of Smith et al. 2021, which reports 19.02 cm RMSE on !Kung. We rerun it on the same candidate grid, the same private model, and the same total privacy budget. Beating it means lower final test RMSE at matched total $(\epsilon, \delta)$ across at least five budget levels, with confidence intervals over 20 seeds.

We also run single-fidelity private Bayesian optimization in the style of Kusner et al., with every trial at $q=1$ and privacy accounted per trial. Next is a fixed-subsample version that runs all trials at one tuned $q$. Last is private successive halving over $q$: many random configurations at small $q$, with survivors promoted, following the Hyperband-style schedulers that HPOBench shows are strong in the non-private setting. Every method receives the same total privacy budget, the same number of trainings of the private model, and the same search space.

Three ablations isolate the proposal's ingredients. The first removes the optimum-drift term, leaving a standard multi-fidelity kernel. The second removes the threshold switch. The third prices trials by compute instead of privacy.

Why not just…?

Why not just tune on public or synthetic proxy data for free? This is a real threat whenever a distributionally similar public dataset exists, and in that case it should win. Our setting is the one where no such dataset exists: the private labels (height, trip duration, clinical outcomes) are what make the data valuable. We will include a public-proxy baseline wherever one can be built, for example a held-out city borough for Citi Bike, and report where it wins.

Why not just run private successive halving over $q$ and skip the Gaussian process surrogate? This is the most serious competitor, because promotion schedules are simple and robust. They do, however, assume that a configuration's rank at small $q$ predicts its rank at full $q$. If the measurement study shows that optima drift with $q$, promotion will discard the configurations that become best at full data, while a surrogate with a drift term can extrapolate to them. If the study shows no drift, we expect successive halving to match us. In that case we will report that the surrogate buys nothing and narrow the claim to accounting alone.

Why not just pick one small $q$ and tune there? Zaytsev & Burnaev show that fixed heuristic allocations fall short of minimax-optimal blending, and Klein et al. show that single-proxy tuning lands on misleading optima. The fixed-$q$ baseline tests directly whether either result carries over to the private case.

Why not just use the exponential mechanism as Smith et al. do? It scores every candidate on the full data, so its cost grows with grid size and it cannot exploit amplification. Our comparison at matched budget measures how much the cheap subsample trials save.

Proposed Experiments

We use !Kung (1D and 2D) and the Citi Bike duration task as the main regression benchmarks. Citi Bike is the one that forces the scalable subsampled model. UCI Adult serves as a classification check. HPOBench's subsample-fidelity families provide a non-private sanity check that our correlation measurements reproduce known proxy behaviour.

The metrics are final test RMSE, or accuracy for Adult, against total privacy spent. We also report the rank correlation between subsample and full-data trials within the top decile, plus calibration of predictive intervals.

Three results would decide the proposal. The first is whether top-decile rank correlation at small $q$ is markedly lower under privacy than without it, with the same data and subsample. The second is whether the best $m$ measurably shifts with $q$, extending the peak at about 21 inducing points reported by Smith et al. The third is whether the full method beats both the Smith et al. exponential mechanism and private successive halving at matched budget. If the first two results fail, the drift-aware surrogate is unnecessary and the contribution reduces to privacy-priced accounting for subsampled trials. We would report that outcome as a finding.