acceptodds
Under review as a conference paper at ICLR 2027

Distance-Corrected Private Prototypes for Long-Tailed Classification

Abstract

With a frozen public encoder, private prototype classification can use a single release of class sums and counts. Adding noise at the same scale to every class sum makes rare-class means less accurate and inflates squared distances to them. We introduce projected distance correction (PDC), which projects noisy class means onto the feature ball and corrects their distance scores to account for the added noise. When a fixed public feature bank is available, public-regularized distance correction (PRDC) instead retrieves features aligned with each released class sum and uses their mean to regularize each private prototype before correcting its score. Both methods preserve record-level differential privacy without additional privacy cost. Our analysis bounds deviations from non-private class scores and identifies when regularization preserves or changes the predicted class. It shows how accurate public means let PRDC reduce noise sensitivity while limiting the score changes caused by regularization. Experiments on three image datasets and two imbalance ratios show that, under the three strongest privacy settings, PDC improves balanced accuracy by an average of 20.0 percentage points over direct nearest-prototype classification. PRDC adds 3.0 points over PDC in this range, with positive average gains in five of six dataset-imbalance settings.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
differential privacy, long-tailed classification, prototype-based classification

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 2 reviews, above 85% of the others.
Reviewer_4piWOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies one-shot private prototype classification with a frozen public encoder. Class sums and counts are released once with Gaussian noise. Equal sum-noise scale hurts rare classes: noisy means are less accurate and squared distances are inflated. PDC projects noisy means onto the feature ball and corrects distance scores for sum noise.

Critical strengths
  1. Simple, practical fixes with no extra privacy cost. PDC and PRDC are post-processing of a single zCDP release, so they are easy to adopt and compatible with any frozen encoder.
  2. Strong empirical gains and careful ablations. The paper isolates projection, correction, public-mean retrieval, and score correction. Gains are large at small budgets and consistent across datasets and imbalance ratios.
Critical weaknesses
  1. Modest methodological novelty. Projection and distance correction are standard tools. PRDC is essentially shrinkage toward a retrieved public mean. No comparison to a simple James-Stein estimator or other shrinkage baselines.
  2. Public-bank dependence is a real limitation. PRDC can underperform PDC when the public source is mismatched. The paper shows this but does not offer a reliable way to detect mismatch or fall back safely. Experiments are limited to image features and two public banks.
Questions for authors
  1. How does PRDC behave when the top-K retrieved public features are irrelevant to the class? Is there a safeguard or diagnostic?
  2. How sensitive are results to the public development tasks used to select K, the count-budget share, and other hyperparameters?
5 comments

Thank you for your comments on the method and its evaluation. We believe that addressing the reviewers' comments has substantially improved the paper.

We have uploaded a revised manuscript incorporating the changes described in our responses. All equation, section, table, and figure numbers in our responses refer to this revision.

We welcome further questions or comments. If our responses resolve your concerns, we would be grateful if you could reconsider your score.

R3.1: methodological contribution. Our contribution is to couple prototype regularization and distance correction for classification under class-dependent privacy noise. Recent work continues to develop debiasing methods for functions of private releases [1, 2]. For imbalanced classification, correcting the expected distance penalty still leaves large score fluctuations for small classes, while regularization changes the correction required.

PDC constrains the noisy prototype to the feature ball and calibrates its score correction to the known DP noise scale and the projection factor. PRDC also sets its private–public weighting from the class-specific noise variance and scales the correction accordingly. Section 4 bounds the remaining sum/count fluctuations, separates them from the signed score shifts due to regularization, and gives conditions for preserving or changing the clean class decision. Figures 2 and 3 isolate the effects of regularization, correction, and their combination using the same private release. These simple updates improve classification without further private access or iterative training.

On CIFAR-100 and FOOD-101 at IR 100, averaged over all six budgets, PDC gives 51.1% and 55.9% BA, compared with 33.5% and 38.5% for Projection only and 19.1% and 26.3% for Correction only (Table 13).

The improvements are substantial against both private learning and shrinkage baselines. On CIFAR-10, CIFAR-100, and FOOD-101 at IR 100, averaged over ρ∈{.005,.02,.125}\rho\in\{.005,.02,.125\}, PRDC improves BA over DP-SGD+LA by 4.30–5.72 percentage points (Table 1). In the additional comparison in R3.2, PDC exceeds James–Stein by 10.64–12.17 points and soft thresholding by 16.18–19.69 points, with distance correction applied to both comparators. PRDC further improves PDC by 0.64–4.73 points in that comparison.

Recent work uses public data to improve differentially private learning [3, 4]. Access to a public bank is thus a realistic assumption for PRDC. To address accuracy loss from a mismatched source, we additionally select between PDC and PRDC using the public bank and released statistics, without additional privacy cost (R3.3, Appendix D.8). Across three datasets, both public sources, and IRs 10 and 100 at the above budgets, this rule retains 95.8% of PRDC's gains and removes 97.7% of its losses relative to PDC.

R3.2: shrinkage comparison. The submitted ablation already includes projection-based shrinkage (Projection only). We added comparisons with James–Stein and coordinatewise soft thresholding [5]. All methods share new draws of privacy noise on the training sets of Table 1, with public banks screened as in Appendix C.2. We apply distance correction to both baselines and select the soft-thresholding parameter on public data. BA (%) averaged over ρ∈{.005,.02,.125}\rho\in\{.005,.02,.125\} is:

DatasetIRJames–SteinSoft thresholdingPDCPRDC
CIFAR-101093.3790.5293.4093.30
CIFAR-1010074.8166.8085.4586.09
CIFAR-1001043.9633.8958.6363.58
CIFAR-10010024.9820.6236.8041.53
FOOD-1011051.5736.1765.4068.11
FOOD-10110029.7822.2641.9546.40

PDC and PRDC outperform both baselines at IR 100. Appendix D.2 provides the full results and experimental details.

References

[1] Flavio Calmon et al. Debiasing Functions of Private Statistics in Postprocessing. FORC, 2025.

[2] Quentin Hillebrand et al. Privacy by Postprocessing the Discrete Laplace Mechanism. NeurIPS, 2026.

[3] Adam Block et al. Oracle-Efficient Differentially Private Learning with Public Data. NeurIPS, 2024.

[4] Jinseong Park, Yujin Choi, and Jaewook Lee. In-distribution Public Data Synthesis with Diffusion Models for Differentially Private Image Classification. CVPR, 2024.

[5] David L. Donoho. De-noising by soft-thresholding. IEEE Transactions on Information Theory, 1995.

R3.3: a criterion from public information and the release. We select between PDC and PRDC using only the public bank and released statistics, without additional privacy cost (Appendix D.8). Gaussian data fission [1] postprocesses the existing release into two observations with independent noise. We construct both classifiers from one observation and evaluate how often each assigns the class aggregates in the other to their own classes.

Let Δ^\widehat\Delta denote PRDC's average proxy accuracy minus PDC's. We choose

\begin{cases} \mathrm{PRDC},&\widehat\Delta>0,\\ \mathrm{PDC},&\widehat\Delta\le0. \end{cases}$$ These comparisons use the same training sets as Table 1, with new draws of privacy noise shared across methods. At IR 100, with the 20,000-image banks of Appendix D.7, BA (%) averaged over $\rho\in\{.005,.02,.125\}$ is: | Target / public bank | PDC | PRDC | Selection | | --- | --- | --- | --- | | CIFAR-10 / ImageNet | 85.45 | 88.66 | 87.86 | | CIFAR-10 / UECFood | 85.45 | 75.55 | 85.43 | | CIFAR-100 / ImageNet | 36.80 | 41.60 | 41.60 | | CIFAR-100 / UECFood | 36.80 | 27.82 | 36.71 | | FOOD-101 / UECFood | 41.95 | 45.88 | 45.88 | | FOOD-101 / ImageNet | 41.95 | 35.65 | 41.55 | Across the three datasets, both public sources, and both IRs, selection retains 95.8% of PRDC's gains and removes 97.7% of its losses relative to PDC over these budgets. Table 24 reports the full results. On FOOD-101/ImageNet at IR 10 and $\rho=.005$, selection remains 1.17 points below PDC. Developing a more accurate fallback criterion is left to future work. **R3.4: additional tasks and public banks.** We added 20 Newsgroups for text classification, iNaturalist 2018 as a naturally imbalanced image task, and COCO as an additional public bank for CIFAR-10/100 and FOOD-101. The two new tasks support the gains of PDC and PRDC observed on the original datasets (Appendices D.10 and D.11). BA (%) averaged over $\rho\in\{.005,.02,.125\}$ is: | Task | Noisy mean | PDC | PRDC | | --- | --- | --- | --- | | 20 Newsgroups (IR 10) | 21.81 | 32.22 | 44.69 | | 20 Newsgroups (IR 100) | 13.81 | 17.60 | 29.90 | | iNaturalist 2018 | 2.73 | 7.05 | 9.91 | With COCO, PRDC also improves BA over PDC on all three datasets at IR 100, averaged over the same budgets: | Dataset | PDC | PRDC / COCO | | --- | --- | --- | | CIFAR-10 | 85.61 | 88.44 | | CIFAR-100 | 36.63 | 39.21 | | FOOD-101 | 41.93 | 42.84 | These gains support using a general-purpose public collection when retrieval provides examples relevant to the target classes (Appendix D.12). **R3.5: irrelevant neighbors.** PRDC can still outperform PDC after removing public classes matched by name to the target classes. We select 25%, 50%, 75%, or 100% of the target classes and remove all samples from the matched public classes. We compare against random removal of the same number of public samples (Appendix D.7). Results are averaged over $\rho\in\{.005,.02,.125\}$ at IR 100. For FOOD-101 with 50% of the target classes selected, class recall decreases by 1.49 points on the selected classes and 0.59 points on the remaining classes relative to random removal. The changes are smaller on CIFAR-10/100 (Table 23). **R3.6: public development and hyperparameters.** The original submission includes hyperparameter sensitivity results in Appendices D.5 and D.6. We choose $K$ on public development tasks and report the full $K\in\{16,64,256,2048\}$ sweep, with the public choices marked in Figure 7 of the revision. At IR 100, BA averaged over all six budgets varies by 1.25 percentage points across these four values on CIFAR-100 with ImageNet and by 2.84 points on FOOD-101 with UECFood-256. The publicly selected $K$ is within 0.71 and 0.49 points of the best value, respectively. The count-budget share follows Equation (4) and does not depend on the public development tasks. Appendix D.5 varies this share from half to twice its prescribed value while keeping the total privacy budget fixed. Across this range, mean BA changes by less than 0.4 percentage points for each method and dataset. The PRDC weight is determined by the noise variance and released count through Equation (10). **References** [1] James Leiner et al. Data Fission: Splitting a Single Data Point. Journal of the American Statistical Association, 2025.

Thank you again for your time and comments. We have posted our responses and uploaded the revised paper. Before the discussion closes, we would appreciate hearing whether our responses address your concerns and which points still need clarification. We would be happy to discuss further.

Reviewer_r8qDOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper handles DP prototype classification with a frozen public encoder on long-tailed data. This paper tackles the core problem that adding noise with the same scale for all class inflates the distance to rare class more. To address this problem, this paper proposes PDC and PRDC. Both are based on combination of prototype regulation (projection in PDC and interpolation with public top-k mean in PRDC) and distance correction. Experiments on the generated LT datasets based on CIFAR-10/100 and FOOD-101 show the effectiveness of the proposed methods in terms of BA and Macro-F1 on various privacy budgets.

Critical strengths
  • Through the Eq. (13), this paper introduces the core problem that the distance to a class with a small count is inflated more. And, combining regularizations (projection in PDC and interpolation with top-K mean in PRDC) with correction leads to clear performance gain.
  • The thorough experiments with ablations show clear effectiveness of PDC and PRDC compared with baseline methods.
Critical weaknesses
  • There are many notations and equations, which makes it hard to follow on a first read. It might be good to include notation table in Appendix and reduce notations if possible.
  • Fig. 1 (b) and (c) would be better if they include the intuitively different behaviors of dominant class and rare class. How do the noisy prototypes of dominant class and rare class move to regulated (projected or interpolated) prototypes.
  • The benchmark datasets are limited. Experiments with larger datasets could support the effectiveness of the proposed method. And, Fig. 4 shows that tail recall on CIFAR-100 and FOOD-101 remains low at small privacy budgets.
Questions for authors

Please refer the weakness

3 comments

Thank you for your comments on the presentation and evaluation of our work. We believe that addressing the reviewers' comments has substantially improved the paper.

We have uploaded a revised manuscript incorporating the changes described in our responses. All equation, section, table, and figure numbers in our responses refer to this revision.

We welcome further questions or comments. If our responses resolve your concerns, we would be grateful if you could reconsider your score.

R1.1: notation. We reviewed the notation and retained the symbols needed for the method and analysis. We added a notation table in Appendix E to help readers.

R1.2: prototype movement. Class frequency affects regularization indirectly through prototype noise and the released count. Dominant classes have less noisy means that tend to remain inside or near the feature ball, so PDC leaves them unchanged or moves them only slightly. Rare-class means can lie far outside the ball. PDC projects these means onto the ball, addressing the large perturbations that motivate the method.

In PRDC, larger released counts give more weight to the noisy private mean μ~c\widetilde\mu_c, while smaller counts give more weight to the public mean bcb_c. Dominant classes therefore tend to move less from their noisy means, whereas rare classes move more toward the public mean. We revised Figure 1 to illustrate these behaviors.

R1.3: larger natural data. We added experiments on iNaturalist 2018, a naturally imbalanced dataset containing 437,513 training images from 8,142 classes. The mean BA (%) over ρ∈{.005,.02,.125}\rho\in\{.005,.02,.125\} is shown below, with full results in Appendix D.10.

Noisy meanPDCPRDCDPPL-PublicDP-SGD+LA
2.737.059.913.106.28

R1.4: tail recall at small budgets. Figure 4 now enlarges ρ=.005\rho=.005 and .02.02 in its CIFAR-100 and FOOD-101 tail panels. The values on those original curves are:

Datasetρ\rhoNoisy meanPDCPRDC
CIFAR-100.0050.000.271.24
CIFAR-100.020.000.842.89
FOOD-101.0050.000.402.43
FOOD-101.020.001.857.51

At IR 100, these tail classes contain only 5–23 and 7–34 training examples, respectively. With unit-length features, the Gaussian sum and count noise have standard deviations 10.18 and 53.58 at ρ=.005\rho=.005, and 5.09 and 26.79 at .02.02. Section 5.4 relates these scales to the limited tail samples. The enlarged curves show the gains within this low-recall range.

Thank you for the detailed responses and the revised manuscript. The revision addresses my comments well, and the paper is now easier to follow. The notation table and the revised Figure 1 make it clearer how the noisy prototypes of dominant and rare classes are regularized differently by PDC and PRDC. The additional experiments on iNaturalist 2018 further support the effectiveness of the proposed methods on a larger, naturally imbalanced dataset. For tail recall at small privacy budgets, the enlarged curves and the explanation of the noise scales relative to the very limited number of tail-class samples clarify both the gains and the inherent difficulty of this regime. Overall, my concerns have been addressed, and I will maintain my rating of weak acceptance.

Thank you for your careful review and for considering our responses. We appreciate your constructive comments, which helped us improve the presentation and evaluation of the paper.

Comments on the paper

3 comments

Thank you for your detailed comments and suggestions. We believe that addressing the reviewers' comments has substantially improved the paper.

We have uploaded a revised manuscript incorporating the changes described in our responses. All equation, section, table, and figure numbers in our responses refer to this revision.

We welcome further questions or comments. If our responses resolve your concerns, we would be grateful if you could reconsider your score.

R2.1: public-bank relevance. PRDC's gains depend on the relevance of the public examples it retrieves. Appendix D.7 examines this dependence by swapping object and food sources at a fixed bank size. The losses in this controlled comparison do not by themselves imply similarly poor performance with a broad public collection.

We added COCO as a single public source for CIFAR-10/100 and FOOD-101 (Appendix D.12). At IR 100, BA (%) averaged over ρ∈{.005,.02,.125}\rho\in\{.005,.02,.125\} is:

DatasetPDCPRDC / COCO
CIFAR-1085.6188.44
CIFAR-10036.6339.21
FOOD-10141.9342.84

These gains show that PRDC can benefit from a general-purpose collection when retrieval supplies examples relevant to the target classes.

We also provide a criterion for selecting between PDC and PRDC using only the public bank and released statistics, without additional privacy cost (R2.5, Appendix D.8). It falls back to PDC when the estimated proxy accuracy does not favor PRDC.

R2.2: natural imbalance. We added experiments on the full iNaturalist 2018 training set, preserving its naturally imbalanced class frequencies. It contains 437,513 images from 8,142 classes, with 2–1,000 images per class. Averaged over ρ∈{.005,.02,.125}\rho\in\{.005,.02,.125\}, BA is 7.05% for PDC and 9.91% for PRDC. Appendix D.10 reports the full results.

R2.3: another encoder. We extended the ResNet-18 evaluation to CIFAR-100 and FOOD-101 (Appendix D.9). At IR 100, PRDC improves the strong-budget mean BA over PDC from 18.53% to 21.62% on CIFAR-100 and from 17.65% to 20.70% on FOOD-101.

R2.4: overlap between public and benchmark images. We checked the public banks against the full benchmark training and test sets for exact and near-duplicate images, including resized, cropped, and reflected copies. We conservatively removed all candidate public images (Appendix C.2):

Public sourceImages consideredImages removed
ImageNet1,281,16710,360
UECFood-25631,395195
iNaturalist 2021100,0005,561

Across CIFAR-10, CIFAR-100, and FOOD-101 at IR 10 and 100, removing these candidates changes the strong-budget mean PRDC BA by at most 0.019 percentage points (Table 6, Appendix C.2).

R2.5: a criterion from public information and the release. We select between PDC and PRDC using only the public bank and released statistics, without additional privacy cost (Appendix D.8). Gaussian data fission [1] postprocesses the existing release into two observations with independent noise. We construct both classifiers from one observation and evaluate how often each assigns the class aggregates in the other to their own classes.

Let Δ^\widehat\Delta denote PRDC's average proxy accuracy minus PDC's. We choose

\begin{cases} \mathrm{PRDC},&\widehat\Delta>0,\\ \mathrm{PDC},&\widehat\Delta\le0. \end{cases}$$ These comparisons use the same training sets as Table 1, with new draws of privacy noise shared across methods. At IR 100, with the 20,000-image banks of Appendix D.7, BA (%) averaged over $\rho\in\{.005,.02,.125\}$ is: | Target / public bank | PDC | PRDC | Selection | | --- | --- | --- | --- | | CIFAR-10 / ImageNet | 85.45 | 88.66 | 87.86 | | CIFAR-10 / UECFood | 85.45 | 75.55 | 85.43 | | CIFAR-100 / ImageNet | 36.80 | 41.60 | 41.60 | | CIFAR-100 / UECFood | 36.80 | 27.82 | 36.71 | | FOOD-101 / UECFood | 41.95 | 45.88 | 45.88 | | FOOD-101 / ImageNet | 41.95 | 35.65 | 41.55 | Across the three datasets, both public sources, and both IRs, selection retains 95.8% of PRDC's gains and removes 97.7% of its losses relative to PDC over these budgets. Table 24 reports the full results. On FOOD-101/ImageNet at IR 10 and $\rho=.005$, selection remains 1.17 points below PDC. Developing a more accurate fallback criterion is left to future work. **References** [1] James Leiner et al. Data Fission: Splitting a Single Data Point. Journal of the American Statistical Association, 2025.
Reviewer_FG9jOpenReview ↗

Overall, the response and revision have substantially addressed my main concerns. I therefore maintain my positive recommendation and my score of 3 (weak acceptance).

Thank you for the detailed response and the substantial additions to the revised manuscript. The new experiment on the full iNaturalist 2018 dataset addresses my concern about evaluating only on synthetically constructed long-tailed data. The expanded ResNet-18 results also provide useful evidence that the observed improvement is not specific to one encoder or dataset.

The duplicate-screening analysis adequately addresses my concern about possible overlap between the public banks and the benchmark data. In particular, the negligible change after removing all candidate matches makes it unlikely that the reported gains are driven by image overlap.

Most importantly, the proposed data-fission-based selection rule is a meaningful response to my main concern about public-bank mismatch. The reported results suggest that it preserves most of PRDC’s gains while avoiding nearly all of its losses, without incurring additional privacy cost. The remaining failure case on FOOD-101/ImageNet shows that the fallback criterion is not completely reliable, but this limitation is clearly acknowledged and appears relatively narrow.

Overall, the response and revision have substantially addressed my main concerns. I therefore maintain my positive recommendation and my score of 3 (weak acceptance).

Thank you for your careful review and for considering our responses. We appreciate your constructive comments, which helped us improve the presentation and evaluation of the paper.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.