Teaching Private Students to Say "I Don't Know": Unfamiliarity Votes in PATE

Private Aggregation of Teacher Ensembles (PATE) is a standard recipe for training on sensitive data without releasing it. The private data is split into disjoint pieces, one "teacher" model is trained on each piece, and the teachers vote on labels for unlabeled public examples. Noise is added to the vote counts so the released labels satisfy differential privacy, a formal guarantee that no single training record changes the output much. A fresh "student" model then learns from those noisy labels and is the only thing released. The weak point is the public data. In practice it contains images or records unlike anything in the private set. Deep networks tend to agree with one another, confidently and wrongly, on such inputs. PATE's confidence check reads that agreement as strong consensus and treats it as almost free in privacy cost. The result is that PATE spends its budget teaching the student confident wrong labels on exactly the inputs it should refuse.

We propose a simple change. Each teacher gets a (K+1)-th ballot option, "unfamiliar to me." The teacher casts it when its own uncertainty about the query exceeds a threshold that it sets on its own private held-out data. Each teacher still casts exactly one vote, so the sensitivity of the vote histogram stays at one and the standard PATE privacy analysis carries over unchanged. When "unfamiliar" wins the noisy vote, the student receives a hard "unknown" label and learns an explicit rejection class. Uncertainty information thus crosses the privacy boundary as a discrete vote rather than as soft probabilities or variances, both of which are costly or leaky to release. The open scientific question is which kind of teacher casts reliable unfamiliarity votes when it was trained on only a small slice of the data. A Bayesian teacher, whose weights are a distribution rather than a single setting, is the natural candidate. A known negative result, however, says it may be no better than an ordinary network, and we design the study around that risk.

Core Claim

The claim has two parts. The first, which we expect to hold, is that adding an unfamiliarity ballot to PATE reduces the confident wrong labels released on out-of-distribution (OOD) public queries, at no change in privacy sensitivity. It should also produce a student whose learned unknown class detects OOD inputs at deployment better than post-hoc fixes applied to a standard PATE student. The second, a hypothesis we will test rather than assume, is that teachers with probabilistic weights cast better unfamiliarity votes than deterministic teachers in PATE's small-data-per-teacher regime. If it holds, it should do so through their total or aleatoric uncertainty rather than their epistemic disagreement. If deterministic teachers thresholding their own softmax entropy match Bayesian teachers, then the contribution is the voting mechanism alone, and we will report it that way.

The aggregate that gets noised is the extended vote histogram

$$n_j(x) = \left|\{\, i : v_i(x) = j \,\}\right|, \qquad j \in \{1,\dots,K,\ \mathrm{unk}\},$$

Here $v_i(x)$ is teacher $i$'s vote: its predicted class if its uncertainty score $u_i(x)$ is below its threshold $\tau_i$, and "unk" otherwise. Each $\tau_i$ is chosen so that teacher $i$ keeps a fixed fraction, for example 95%, of its own held-out private examples. Each $\tau_i$ depends only on partition $i$, so changing one record still changes at most one teacher's vote, and the global sensitivity remains one.

Relation to Prior Work

The method builds on Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data, which introduced disjoint teachers, noisy argmax voting and student distillation. It also builds on Scalable Private Learning with PATE, which added Gaussian noisy max voting (GNMax) and the Confident Aggregator that abstains when consensus is weak. That check only measures agreement. Our change gives the teachers a way to express unfamiliarity, and makes "unknown" a label the student learns rather than a query that is silently dropped. Hot PATE coordinates teacher sampling so that diverse valid outputs survive the noise. It assumes the teachers are competent on the query, and coordination could even herd them onto a shared hallucination. We leave generation to future work but view the unfamiliarity ballot as its missing guard.

The motivation comes from From Risk to Uncertainty. That paper decomposes risk under proper scoring rules and finds that ensemble members often agree on hard OOD inputs, so their epistemic disagreement collapses. The aleatoric Bayes risk, by contrast, remains a strong detector, with roughly 91–96% AUROC on CIFAR-10 against several OOD sets. This finding also constrains our design. It tells us not to build the ballot from cross-teacher disagreement, and to score each teacher by its own total or aleatoric uncertainty.

On the probabilistic side, Feature Preserving Shrinkage on Bayesian Neural Networks via the R2D2 Prior reports that a Bayesian network with a heavy-tailed shrinkage prior reaches 92.85% AUROC for CIFAR-10 versus Fashion-MNIST, against 71.02% for deep ensembles. This motivates Bayesian teachers. The method was demonstrated on a single model trained on full data, and it is untested on the M/N-sized partitions PATE uses. Cooperative Variance Estimation and Bayesian Neural Networks shows that separating noise estimation from weight-posterior sampling keeps coverage under shift. It is regression-only, so we treat it as conceptual support rather than a component.

DomED is the closest work. It distills both the mean and the spread of a specialist ensemble into a student via a Dirichlet loss, but it is non-private. Releasing a continuous spread under differential privacy would require far more noise than releasing a vote, which is why we use a discrete ballot instead. Dataset Distillation for Memorized Data shows that soft labels can leak held-out teacher data. That constrains us to hard labels, which our K+1 scheme supplies. Learning Placeholders for Open-Set Recognition (PROSER) trains a dummy unknown class on synthetic manifold-mixup points. Our student uses the same kind of output head, but supervises it with real, privately sanitized teacher votes on real public inputs. Finally, Where are we with calibration under dataset shift finds that calibrating ensemble members individually beats calibrating the ensemble average. Per-teacher thresholds are the private analogue of that finding.

Research Program

We will build PATE with GNMax and the Confident Aggregator, and add the K+1 ballot. We compare four teacher types at matched partition sizes:

  1. Deterministic networks scored by softmax entropy.
  2. Deterministic networks with entropy regularization and label smoothing, following the shift-calibration study.
  3. Bayesian teachers via stochastic-gradient Langevin sampling, scored three ways: total predictive entropy, expected entropy (aleatoric), and mutual information (epistemic).
  4. R2D2-prior Bayesian teachers, where compute allows.

Each teacher's threshold is set on its own private held-out split. The student is a (K+1)-way classifier trained on the released hard labels.

The analysis has three parts. First, we measure, per teacher type, how often an OOD public query yields a released confident in-distribution label. This is the PATE-specific version of the hard-OOD paradox. Second, we measure how much privacy budget is spent on such queries. Third, we trace how the student's accuracy on in-distribution data trades against OOD rejection as the per-teacher retention fraction and the number of teachers vary. Fewer samples per teacher should increase spurious "unfamiliar" votes on rare in-distribution classes. We will report that cost explicitly, broken down by class, because on imbalanced data it could erode accuracy on minority classes.

Baselines

The naive reference is unmodified Confident-GNMax PATE from Scalable Private Learning with PATE, with a K-way student scored by maximum softmax probability for OOD detection. It shows what happens when nothing is done about contaminated public data. Its reported clean-data operating points are 98.5% student accuracy on MNIST at ε=1.97 and 73.2% on Glyph at ε=0.837. The original PATE reports 90.66% on SVHN at ε=8.19. We run it on exactly the same partitions, public pools and ε as our method. Beating it means equal or better clean accuracy at equal ε, with higher student OOD AUROC and fewer confident wrong labels released on OOD queries. Lacuna has no reported result for PATE students' OOD detection or calibration, so all of these comparisons are new measurements.

The strongest competitor that leaves the private side untouched is standard PATE plus public-side fixes. One version applies temperature scaling to the student on in-distribution validation data. The other trains the student with PROSER-style mixup placeholders on the public pool. Both are free in privacy cost. PROSER reports 89.1% open-set AUC on CIFAR-10 in the non-private setting. We give these baselines the same student architecture, the same public data and the same hyperparameter search budget as our student.

The non-private reference is a full-data deep ensemble scored by Bayes risk, the configuration in From Risk to Uncertainty (~91–96% AUROC), together with the R2D2 single model at 92.85% on CIFAR-10 versus Fashion-MNIST. These are ceilings, not targets.

Two ablations isolate the key ingredient. The first, filter-only, drops queries where "unfamiliar" wins instead of teaching an unknown class. It separates the benefit of saving budget from the benefit of the student learning rejection. The second is the deterministic-versus-Bayesian teacher comparison above, scored by each uncertainty measure. It decides whether probabilistic weights earn their cost.

Why not just…?

Why not just calibrate the student with temperature scaling? Temperature scaling rescales logits without moving decision boundaries. The shift-calibration study found that calibration fitted on in-distribution data degrades under shift. The deeper problem is upstream: the student was trained on confident wrong labels for OOD-like inputs, and no rescaling removes that. Our temperature-scaled baseline measures this directly.

Why not just use teacher disagreement, which PATE already measures? The risk-decomposition results show that independently trained networks agree on hard OOD inputs, so disagreement is weakest exactly where it is needed. The Confident Aggregator's behavior on contaminated pools is our first measurement. We expect it to release many confident wrong labels there.

Why not just have deterministic teachers threshold their own softmax entropy? This is a real threat to the Bayesian half of the proposal. Bayes risk computed from ordinary networks already works well in the risk-decomposition paper. Deterministic entropy thresholding is therefore a full arm of the study, not a strawman. If it matches Bayesian teachers, we drop the Bayesian claim and keep the voting mechanism.

Why not just filter the public pool with a public OOD detector, or train the student with outlier exposure? A public detector has no access to what the private distribution looks like, and that is the information the teachers hold. PROSER-style placeholders cover only the space near interpolation paths, and outlier exposure can worsen in-distribution calibration for ensembles according to the shift-calibration study. Both are run as baselines. If they match our student, the private ballot is unnecessary.

Why not just train one model with differentially private SGD (DP-SGD)? DP-SGD adds noise at every gradient step, which costs accuracy. PATE reported 98.00% on MNIST at ε=2.04 against 97% at ε=8.0 for prior DP-SGD work. Combining Langevin sampling with DP gradient noise compounds the distortion further. We include DP-SGD only as a secondary reference on MNIST.

Proposed Experiments

The private and public splits come from the PATE benchmarks. MNIST and SVHN serve as private data. CIFAR-10 is added as a harder private set, with its public pool built from held-out CIFAR-10 images contaminated at fractions from 0% to 50% with SVHN, CIFAR-100 and Fashion-MNIST. Contamination is applied both to the pool the teachers label and, independently, to the deployment test set. For a medical setting we use Diabetic Retinopathy Detection, where R2D2-Net reports 71.04% OOD AUROC as a single non-private model. Glyph, with its 150 imbalanced classes, tests the cost on rare classes.

The metrics are student accuracy at fixed ε, the fraction of OOD queries released with a confident in-distribution label, the privacy budget spent on OOD queries, student OOD AUROC, and expected calibration error (ECE). A membership-inference attack on the student confirms that hard labels do not reopen soft-label leakage.

The decisive check has three conditions. At 20% contamination on CIFAR-10 with equal ε, the K+1 student must beat both public-side fixes on OOD AUROC. It must also lose no more than one point of clean accuracy against standard PATE, a tolerance we set in advance. Finally, the filter-only ablation must fall in between, showing that teaching rejection matters beyond saving budget. The Bayesian-versus-deterministic contrast, broken down by uncertainty measure, settles the second claim either way.