Active learning trains a model with fewer labels by repeatedly asking an annotator to label the examples the model is least sure about. When the pool of unlabeled examples is itself private, for instance patient scans that a hospital will not release, the choice of which example to label leaks information about individuals. The standard fix is differential privacy, a guarantee that the output barely changes when any one person's record is added or removed. Current practice adds noise to each candidate's uncertainty score separately. At realistic privacy levels that noise swamps the signal, and active learning degrades toward random sampling. We propose to privatize the choice at the level of regions of the input space instead. The pool is partitioned into cells using fixed anchors that depend only on public information. Each cell gets a score equal to the summed, clipped uncertainty of its members. A differentially private mechanism picks the cells, and the example to label is drawn from inside the chosen cell. One record can change only one cell's sum, and only by a bounded amount. So the noise stays fixed while the signal grows with the number of uncertain points in a region.
In two sentences, the idea is this. Per-example private selection pays full noise for a signal carried by one example. Region-level selection pays the same noise for a signal carried by many examples. We expect this to recover most of the gains of non-private active learning at privacy budgets where per-example selection currently fails. The mechanism has a testable signature: its advantage should grow with pool size, while per-example selection should not benefit from a bigger pool.
Core Claim
The closest work is Differentially Private Active Learning: Balancing Effective Data Selection and Privacy. It sets up the right threat model, in which both the training data and the unlabeled pool are private. It privatizes selection by clipping each candidate's predictive entropy and adding Laplace noise, and it reuses early labels efficiently through "step amplification" across rounds. That paper also supplies the motivating negative result. Privatized selection roughly halves the benefit of active learning, and below $\epsilon \approx 3$ the noise drowns out the informativeness signal. It also constrains our design, because it finds that diversity-based selection such as CoreSet spends the privacy budget too fast to be practical.
Our claim is that the failure comes from the level at which noise is applied, and that uncertainty itself remains a good signal under privacy. Write $u_i \in [0, C]$ for the clipped uncertainty of candidate $i$, computed by the current privately trained model. Write $A_j$ for the set of candidates whose embedding falls closest to public anchor $j$. The cell score is
$$S_j = \sum_{i \in A_j} u_i ,$$
and the mechanism selects cell $j$ with probability proportional to $\exp(\epsilon S_j / 2C)$. This is the exponential mechanism, a standard way to privately pick the best option from a list. Adding or removing one record changes exactly one $S_j$ by at most $C$, so the sensitivity is $C$ however large the pool is. Suppose one region holds many moderately uncertain points and another holds few. The gap between their scores scales with how many points each contains, while the noise does not. That is the source of the predicted pool-size scaling.
The partition is free in privacy terms because the anchors come from public data. The pooled scores are post-processing of the private model applied to each record separately. We borrow this idea of public-anchored grouping from Clustering and Median Aggregation Improve Differentially Private Inference. That paper anchors private text embeddings to public DBPedia centroids so that batches are homogeneous for private text rewriting. We apply the grouping to acquisition decisions rather than to generation, and our cells are scored by the model's uncertainty rather than being static.
Why aggregation is the right lever here
The aggregation literature shows that grouping records before adding noise reduces the noise needed. Publishing Differentially Private Datasets via Stable Microaggregation proves that if a partition is "stable" (changing one record alters at most two groups), sensitivity falls to $2/k$ for groups of size $k$. Machine Learning with Differentially Private Labels: Mechanisms and Frameworks clusters features and adds noise only to per-cluster vote counts, keeping sensitivity at $\sqrt{2}$ independent of dataset size. It reports 94.6% on CIFAR-10 at $\epsilon = 0.5$. Both of these supply the method. Both apply aggregation to passive release or passive training, and neither applies it to the query function of an active learner. Label differential privacy via clustering constrains our choice of cell size. It proves that clusters that are too small relative to the number of classes cannot preserve utility, and heterogeneous large clusters dilute the signal. We expect the same "Goldilocks" tradeoff in cell count, and we measure it directly.
Summed scores also bring two side benefits, which we treat as hypotheses to test. First, a single corrupted or inherently ambiguous example cannot dominate a cell the way it dominates a per-example ranking. Privacy-preserving and Uncertainty-aware Federated Trajectory Prediction for Connected Autonomous Vehicles shows that selecting at median aleatoric uncertainty beats selecting at maximum uncertainty, where aleatoric uncertainty means noise in the data itself that no amount of training removes. That paper motivates our second clipping variant, described below. Second, spreading picks across cells yields some batch diversity without the costly private geometry that sank CoreSet in the DP-AL study.
Research Program
We will build the mechanism inside the DP-AL pipeline. Each round has four steps. The model is trained with DP-SGD (stochastic gradient descent with per-example clipping and Gaussian noise). Uncertainties are computed on the private pool. $b$ cells are selected by the exponential mechanism. One example per selected cell is drawn uniformly at random and sent to the annotator. Privacy accounting composes the selection mechanism with DP-SGD through a Rényi-DP accountant and reuses DP-AL's step amplification schedule. Leakage to the trusted annotator is handled as in DP-AL.
Anchors come from k-means on public-encoder embeddings of a public dataset. For the medical sets, the public encoder is a generically pretrained image encoder. Where no suitable public anchors exist, we substitute an S-MDAV-style stable partition computed on private embeddings. This doubles the sensitivity to $2C$ and lets us check whether public anchors are essential.
The analysis has three parts. First, we will prove the sensitivity bound. We will also derive the expected probability of choosing the most uncertain region as a function of cell occupancy, $\epsilon$, and $C$, and from it predict at what pool size region selection overtakes per-example selection. Second, we will study the granularity tradeoff empirically by sweeping the number of anchors. Third, we will test a two-sided clipping variant. It caps each $u_i$ below maximum entropy, so the most ambiguous points contribute no more than moderately uncertain ones. This is the private analogue of median aleatoric selection. We use capping rather than a true median because the median's global sensitivity is poor, and we do not want to lean on local-sensitivity arguments that would weaken the formal guarantee.
Baselines
The naive reference point is uniform random acquisition with DP-SGD under the identical total privacy budget and label budget. Selection then leaks nothing and costs no budget. The file reports 74.54% on RetinalOCT for random sampling under DP (Differentially Private Active Learning: Balancing Effective Data Selection and Privacy).
The strongest existing method is DP-AL's privatized entropy selection, which clips per-example scores, adds Laplace noise, and uses step amplification. The same paper reports 78.00% accuracy on RetinalOCT for it. The file does not state the $\epsilon$ for that figure, so we will rerun it rather than rely on the reported number. We will run it with the authors' accounting, the same DP-SGD configuration, the same label budget per round, and the same hyperparameter search budget as our method, including a search over its clipping constant. Beating it means higher final accuracy at matched total $\epsilon$ and labels, averaged over at least five seeds. We are especially interested in $\epsilon \le 3$, where that paper reports failure, and a win there would matter most. For CIFAR-10, BloodCell, CheXpert and SNLI, no reported result was found on Lacuna for DP-AL, so all numbers there come from our reruns.
We add a stronger per-example competitor that DP-AL does not report. It uses the exponential mechanism, or report-noisy-max (add noise to every score and take the largest), directly over individual clipped scores. This isolates whether any gain comes from aggregation or merely from a better selection mechanism. The key ablation holds everything fixed and varies only the granularity. At one extreme each cell holds one example, which recovers per-example selection. At the other there is a single cell, which recovers random sampling. The intermediate anchor counts in between are the proposal.
A non-private uncertainty sampler serves as the ceiling. We report what fraction of its gain over random each private method recovers, since that ratio is the quantity DP-AL found to be halved.
Why not just…?
Why not just use a better per-example mechanism, like report-noisy-max, instead of cells? This is the real threat. For picking a single winner, report-noisy-max adds noise of scale $C/\epsilon$ regardless of pool size, so it is much better than independent Laplace on every score. Still, the score gap it must resolve lies between individual examples and is at most $C$. Across many rounds, per-round $\epsilon$ shrinks under composition and that gap disappears into noise. The cell sum makes the gap grow with occupancy. Our experiment settles this directly. We run both mechanisms at matched budgets while growing the pool, subsampling CIFAR-10 and SNLI pools from 5k to the full set. If per-example noisy-max matches us at every pool size, the aggregation claim is false and we will say so.
Why not just select from a public pool, where selection is free? Improving Differentially Private Models with Active Learning does exactly this with DIVERSEPUBLIC. It lifts SVHN from 75% to 85% at zero extra privacy cost. Its own NEARPRIVATE extension, however, shows that polluted public data forces spending private budget anyway. For medical tasks like RetinalOCT and CheXpert, matching public pools largely do not exist. We will still run DIVERSEPUBLIC wherever a plausible public pool exists, for example CIFAR-10 with a polluted CINIC-style public set. In domains that have clean public data it may simply win, and we will report that honestly.
Why not just sample at random with DP-SGD and benefit from subsampling amplification? Random sampling spends nothing on selection, which is its real advantage at very small $\epsilon$. DP-AL's gap (78.00% versus 74.54% on RetinalOCT) shows that a selection signal is worth paying for on imbalanced data. We need to show that the gap survives and widens below $\epsilon = 3$. The one-cell end of our granularity ablation is exactly this baseline, so the comparison is built in.
Why not just use private diversity or CoreSet selection? DP-AL found CoreSet impractical under privacy because its geometric sensitivity burns the budget, and Computational Hardness of Private Coreset documents hardness barriers. Our cells give coverage across regions with sensitivity $C$ per round and no private geometry at all. We measure the resulting diversity, as the number of distinct classes and cells covered per batch, against non-private CoreSet as a reference.
Proposed Experiments
We will use the DP-AL benchmark suite: RetinalOCT, BloodCell and CheXpert (imbalanced medical imaging, the motivating case), CIFAR-10, and SNLI for text. We sweep total $\epsilon \in \{0.5, 1, 3, 8\}$ with fixed $\delta$ and fixed label budgets. Metrics are test accuracy (AUC for CheXpert), the fraction of non-private active learning gain recovered, and a membership-inference attack on the final model as an empirical privacy check alongside the formal accounting.
Three checks decide whether the proposal is right. First, at $\epsilon \le 3$ our method should beat both DP-AL entropy selection and per-example noisy-max at matched budgets. Second, the gap over per-example selection should widen as pool size grows, as the sensitivity argument predicts. If it does not, the mechanism is not doing what we claim. Third, accuracy should trace an interior optimum across anchor counts, because the one-cell and one-per-example extremes reduce to the two baselines. A monotone curve would mean aggregation is not what drives the result.
A secondary experiment injects label noise into 10% of RetinalOCT and CIFAR-10. It tests whether two-sided clipping of cell sums avoids the corrupted examples that per-example uncertainty preferentially picks, using the fraction of corrupted examples acquired as the measure.
References
- Differentially Private Active Learning: Balancing Effective Data Selection and Privacy
- Clustering Improves Differentially Private Inference
- Publishing Differentially Private Datasets via Stable Microaggregation
- Machine Learning with Differentially Private Labels: Mechanisms and Frameworks
- Label differential privacy via clustering
- Privacy-Preserving and Uncertainty-Aware Federated Trajectory Prediction for Connected Autonomous Vehicles
- Improving Differentially Private Models with Active Learning
- Computational Hardness of Private Coreset