acceptodds
Under review as a conference paper at ICLR 2027

Blockwise Randomized Response: Theory and Algorithms for Label Differential Privacy

Abstract

In this paper, we introduce a novel block structure and apply it to randomized response-type algorithms, yielding the *BlockRR* framework for label differential privacy. Theoretically, we formulate an optimization problem whose optimal solution corresponds to the BlockRR mechanism. We illustrate that the introduction of is designed to enhance the influence of majority labels and mitigate the impact of minority labels and demonstrate the BlockRR mechanism serves as a general framework. In addition, we establish its -label DP guarantee and conduct a utility analysis by deriving bounds on the excess risk. Numerical results demonstrate that our method gets a better balance between test accuracy and the average of per-class accuracy in the high- and moderate-privacy regimes. In the low-privacy regime, our method reduces to standard RR.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
BlockRR, Label DP, RR-type, Block structure

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_FGbROpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes BlockRR, a randomized response (RR) mechanism for label DP that addresses class imbalance by using privatized estimated class priors to partition labels and adjust the perturbation probabilities. The authors provide optimality, privacy, and risk analysis.

Critical strengths
  • Label DP with class imbalance is an important and practical problem, and reporting both the overall and the average per-class accuracy is appropriate.

  • The block construction is intuitive, and the author provides a flexible way to adjust the label perturbation.

Critical weaknesses

Major comments

1. Weight. The objective ∑y,y~wyy~py~∣y\sum\limits_{y, \tilde y}w_{y\tilde y}p_{\tilde y \mid y} in Equation (4.1) is a prior-weighted surrogate. Since the relationship to classification risk or per-class accuracy is not established, it is unclear in what sense the proposed BlockRR is optimal in Theorem 4.1. And the proof in Appendix C does not explain how the weight wyy~w_{y\tilde y} enters the optimality argument.

2. Algorithm. Algorithm 1 randomizes individual labels given a partition, while Algorithm 2 estimates private priors from D1D_1 and constructs the privatized dataset from D2D_2. It is unclear what the protected object is in the two algorithms. Moreover, using the part of the original data D1D_1 to estimate the prior probability p=(p1,…,pK)⊤\boldsymbol{p} = (p_1, \ldots, p_K)^\top, although Algorithm 2 protects D1D_1 via the Laplace mechanism in Algorithm 3, the subsequent randomiztion of D2D_2 depends on the estimated prior. Please clarify how the labels in D1D_1 are protected and how the proof in Theorem 4.5 covers the full algorithm.

3. Theorem. Theorem 4.7 depends on the uncontrolled term Δ(x)=max⁡j∣gj(x)−sjη~j(x)∣\Delta(x) = \max_j|g_j(x) - s_j\tilde\eta_j(x)|, but the paper does not show how this term is controlled by the implemented training procedure. The experiment just uses cross-entropy training without specifying any rescaling or correction. Please explain how the bound applies to the implemented learner and what is established about the benefit of the proposed BlockRR over classical RR.

Minor comments

  • RR is repeatedly introduced, including around lines 32 and 135.

  • The abstract introduces T⊆S~1\mathcal T\subseteq \tilde {\mathcal S}_1 without explanation.

Questions for authors
  1. Why is the weighted objective in Equation (4.1) an appropriate measure for imbalanced classification? How do the weights affect the claimed optimal solution in Theorem 4.1?

  2. For y∈S2y\in \mathcal S_2 and y~∈S~1∖T\tilde y \in \tilde {\mathcal S}_1\setminus \mathcal T, Section 3.1 (line 162) assigns probability β\beta, whereas Algorithm 1 (line 225) assigns γ\gamma. Equation (3.1) also uses β\beta for this case. Which is correct, and which is used in the experiments?

  3. How were ll and σ\sigma selected for each privacy budget? Why did you not compare with other label DP methods discussed in the paper, such as ALIBI? It would also be better to provide additional simulations with different levels of class imbalance.

2 comments

[W1] The objective in Equation (4.1) maximizes the inner product between wyy~w_{y\tilde y} and py~∣yp_{\tilde y|y}, thereby concentrating the randomization mass on the entries where the weights are largest, subject to the row-sum and privacy constraints.

[W2] Privacy is guaranteed by Parallel Composition in Appendix E, Lemma E.1.

  • The prior, used for the partitions of those true and randomized sets, is estimated from D1D_1 protected via the Laplace mechanism in Algorithm 3, while the randomization of D2D_2 protected via Algorithm 1, which does NOT depend on the estimated prior (see Algorithm 1). Theorem 4.1 is just to explain our proposed mechanism corresponds to the optimal solution of the Linear programming problem in Theorem 4.1.

[W3] The term Δ(x)=max⁡j∣gj(x)−sjη~j(x)∣\Delta(\mathcal x)=\max_j|g_j(\mathcal x)-s_j\tilde\eta_j(\mathcal x)| appears only in the theoretical analysis.

In practice, the user who trains the model has access only to the randomized data, not to the randomization mechanism; consequently η~\tilde\eta (and hence Δ(x)\Delta(\mathcal x)) is unavailable at training time. It would therefore be unreasonable to include Δ(x)\Delta(\mathcal x) in the training procedure, and our algorithm does not: Δ(x)\Delta(\mathcal x) enters only the analysis, where it measures the deviation between the model output and the (unobservable) randomized label statistics.

[M1-2] We thank you for the comment. We have updated.

[Q1] I am sorry for any confusion.

  • The optimization problem is proposed for an explanation that our proposed mechanism corresponds to the optimal solution of this optimization problem.

  • For an practical problem, we will generally design an objective and give some constraints, which form an optimization problem. Here The objective in Equation (4.1) is the inner product between wyy~w_{y\tilde y} and py~∣yp_{\tilde y|y}. When we maximize this objective function, where wyy~w_{y\tilde y} contains an appropriate measure for imbalanced classification.

[Q2] In Equation (C.3), The fist two constraints must be tight ∑y~∈B(y)py~∣y+e−ϵ∑y~∈S~∖({B(y)}∪T)py~∣y~+∑y~∈Tpy~∣y≤1,∀y∈S2,\sum_{\tilde{y}\in B(y)}p_{\tilde{y} \mid y} + e^{-\epsilon} \sum_{\tilde{y} \in \tilde{\mathcal S} \setminus (\{B(y)\}\cup\mathcal T)} p_{\tilde{y} \mid \tilde{y}}+ \sum_{\tilde{y} \in\mathcal T} p_{\tilde{y} \mid y}\le1, \forall y\in \mathcal S_2, ∑y~∈B(y)py~∣y+e−ϵ∑y~∈S~∖{B(y)}py~∣y~+e−ϵ∑y~∈S2~py~∣y~≤1,∀y∈S1,\sum_{\tilde{y}\in B(y)}p_{\tilde{y} \mid y} + e^{-\epsilon} \sum_{\tilde{y} \in \tilde{\mathcal S} \setminus \{B(y)\}} p_{\tilde{y} \mid \tilde{y}}+ e^{-\epsilon}\sum_{\tilde{y} \in\tilde{\mathcal S_2}} p_{\tilde{y} \mid \tilde{y}}\le1,\forall y \in \mathcal S_1, since our objective ∑y∈S,y~∈S~wyy~py~∣y\sum_{y \in \mathcal S,\tilde{y}\in\tilde{\mathcal S}} w_{y\tilde{y}}p_{\tilde{y} \mid y} is maximized.

[Q3] The choices of ll and σ\sigma is manually, in the manner of a grid search.

  • This paper includes extensive experimental results on three datasets with four variants. We focus primarily on RR-type mechanisms; ALIBI is based on Bayes' formula and does not belong to this family, so it is outside the scope of the present study. We will add this comparison and the additional simulations with varying levels of class imbalance in a future version.

Thank you for the response and clarifications. I very appreciate the responses about W2 and Q1. I still think class imbalance is a quite important problem and the authors also used an imbalanced real dataset, but there no more explanation about this point and some additional numerical results about the choices of ll and σ\sigma. So I keep my score unless the authors can provide more details and clarifications.

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

The paper proposes BlockRR, a label-DP mechanism that partitions the label space into majority and minority groups and applies different RR rules across the resulting blocks, and proves that it is the optimal solution of a certain optimization problem. The experiments on imbalanced variants of CIFAR-10, CIFAR-100, and MNIST investigate the tradeoff between overall accuracy and average per-class accuracy.

Critical strengths
  • The paper provides both theoretical analysis and experimental results.
  • The block structure provides an interpretable parameterization for adjusting the treatment of different label groups and connects existing RR mechanisms.
Critical weaknesses
  • The paper claims that blockRR achieves a better tradeoff between overall accuracy and per-class accuracy. But the current results are insufficient to supported this advantage. Tables 2-–5 report selected operating points, while the ablations of l (Table 6) and σ (Figure 2) report only overall accuracy. A joint analysis of overall and average per-class accuracy across parameter settings, at a fixed privacy budget, would be needed to demonstrate whether BlockRR improves the tradeoff. The current results show some exchanges between the two metrics, but do not convincingly establish the claimed superior balance relative to baselines.
  • Theorem 4.1 may fail for the optimization problem as written. Consider S=S~={1,2}S=\tilde{S}=\{1,2\}, prior p=(3/4,1/4)p=(3/4,1/4), ϵ=ln⁡2\epsilon=\ln 2, σ=1/ln⁡2\sigma=1/\ln 2, B(y)={y}B(y)=\{y\}, and l=0l=0. Equ (3.3) gives the prescribed partition S1={1}S_1=\{1\}, S2={2}S_2=\{2\}. BlockRR reduces to binary RR and attains objective value 5/65/6 in Equ (4.1). However, the input-independent mechanism that outputs labels with probabilities (3/4,1/4)(3/4,1/4) satisfies every stated constraint and attains 15/16>5/615/16>5/6. Thus, the optimality claim fails even when n1=n2=1n_1=n_2=1. In Appendix C, the existence of a boundary optimum does not justify the assertion ``inequalities in (C.1) and (C.2) must simultaneously be tight''.
  • Algorithm 1 is inconsistent with the mechanism defined in the text. For y∈S2y\in S_2 and y~∈S1~\T\tilde{y}\in\tilde{S_1}\backslash T, the text assigns probability β\beta, whereas Algorithm 1 assigns γ\gamma. Consequently, the pseudocode can produce probabilities that do not sum to 1, as its minority-label row sums to 1+(∣S1~∣−l)(γ−β)1+(|\tilde{S_1}|-l)(\gamma-\beta). I'm not sure whether it is a typo.
Questions for authors

Please address the weaknesses above.

1 comment

[W1] Ablation results of the parameter ll under different global privacy budgets ϵ\epsilon (overall and per-class test accuracies %)

ll0123456
overallper-classoverallper-classoverallper-classoverallper-classoverallper-classoverallper-classoverallper-class
ϵ=0.6\epsilon=0.642.52±1.8842.52 \pm 1.8827.5527.5542.78±2.4742.78 \pm 2.4727.2727.2743.48±1.98\mathbf{43.48 \pm 1.98}27.82\mathbf{27.82}41.52±2.4641.52 \pm 2.4626.4626.4643.22±1.5143.22 \pm 1.5127.5527.5542.95±1.4842.95 \pm 1.4827.4527.4542.34±1.6242.34 \pm 1.6227.0027.00
ϵ=0.8\epsilon=0.848.88±1.9448.88 \pm 1.9432.3732.3748.79±1.9848.79 \pm 1.9832.2332.2349.91±1.9049.91 \pm 1.9032.5232.5249.90±2.9349.90 \pm 2.9332.0832.0849.44±2.3149.44 \pm 2.3131.7931.7948.80±1.8048.80 \pm 1.8031.2431.2451.01±1.29\mathbf{51.01 \pm 1.29}33.24\mathbf{33.24}
ϵ=1.0\epsilon=1.055.58±1.9155.58 \pm 1.9137.5537.5555.65±1.2555.65 \pm 1.2536.7936.7957.10±1.9157.10 \pm 1.9137.5337.5356.40±1.5956.40 \pm 1.5936.3636.3656.04±1.7156.04 \pm 1.7136.0536.0558.26±1.67\mathbf{58.26 \pm 1.67}43.30\mathbf{43.30}56.92±2.8556.92 \pm 2.8536.7536.75
ϵ=2.0\epsilon=2.079.03±0.7979.03 \pm 0.7968.69\mathbf{68.69}78.61±0.6778.61 \pm 0.6765.5065.5078.76±0.7878.76 \pm 0.7863.7763.7778.77±0.9278.77 \pm 0.9263.1763.1778.54±0.7478.54 \pm 0.7461.4061.4078.72±1.0578.72 \pm 1.0560.8960.8979.14±0.44\mathbf{79.14 \pm 0.44}60.0960.09
ϵ=3.0\epsilon=3.087.18±0.30\mathbf{87.18 \pm 0.30}80.90\mathbf{80.90}87.05±0.3387.05 \pm 0.3379.6379.6386.99±0.4886.99 \pm 0.4878.2278.2286.78±0.4286.78 \pm 0.4276.7976.7986.59±0.3986.59 \pm 0.3974.9274.9286.09±0.4486.09 \pm 0.4472.4272.4285.94±0.3585.94 \pm 0.3569.9269.92
ϵ=4.0\epsilon=4.090.36±0.32\mathbf{90.36 \pm 0.32}86.01\mathbf{86.01}90.09±0.4290.09 \pm 0.4284.7784.7789.99±0.2789.99 \pm 0.2784.0684.0689.85±0.6089.85 \pm 0.6082.6982.69$89.62 \pm 0.38 $80.4980.4988.96±0.3588.96 \pm 0.3578.1278.1288.78±0.5388.78 \pm 0.5376.4476.44

Ablation results of the parameter σ\sigma under different global privacy budgets ϵ\epsilon (overall and per-class test accuracies %)

σ\sigma0.20.40.60.81.01.21.41.6
overallper-classoverallper-classoverallper-classoverallper-classoverallper-classoverallper-classoverallper-classoverallper-class
ϵ=0.6\epsilon=0.643.28±2.08\mathbf{43.28\pm2.08}27.85\mathbf{27.85}42.48±3.1942.48\pm3.1927.4627.4641.32±2.1941.32\pm2.1926.5126.5143.48±1.96\mathbf{43.48\pm1.96}27.8227.8242.73±1.7142.73\pm1.7127.3127.3143.48±1.98\mathbf{43.48\pm1.98}27.7927.7942.68±2.0142.68\pm2.0127.2227.2241.66±1.9941.66\pm1.9926.5626.56
ϵ=0.8\epsilon=0.847.05±2.5347.05\pm2.5331.4331.4348.76±1.7848.76\pm1.7832.1032.1049.62±1.5649.62\pm1.5631.8531.8549.63±1.6949.63\pm1.6931.9531.9548.79±2.4848.79\pm2.4831.5431.5451.01±1.29\mathbf{51.01\pm1.29}33.24\mathbf{33.24}49.50±1.8549.50\pm1.8532.9432.9450.15±0.9150.15\pm0.9132.1232.12
ϵ=1.0\epsilon=1.055.17±2.0155.17\pm2.0137.2037.2055.55±2.1255.55\pm2.1236.3636.3654.69±1.3654.69\pm1.3635.0935.0956.76±2.5956.76\pm2.5936.8136.8155.57±2.2855.57\pm2.2835.7235.7258.26±1.67\mathbf{58.26\pm1.67}43.30\mathbf{43.30}57.22±2.3057.22\pm2.3037.0437.0457.94±2.2757.94\pm2.2737.2937.29
ϵ=2.0\epsilon=2.077.71±2.4177.71\pm2.4167.37\mathbf{67.37}78.41±0.9578.41\pm0.9562.8162.8178.23±0.6578.23\pm0.6558.2458.2479.14±0.44\mathbf{79.14\pm0.44}60.0960.0978.23±1.0978.23\pm1.0957.5057.5078.19±0.7178.19\pm0.7157.3957.3978.24±0.8278.24\pm0.8257.6157.6178.25±0.7878.25\pm0.7857.8057.80
ϵ=3.0\epsilon=3.087.32±0.37\mathbf{87.32\pm0.37}81.04\mathbf{81.04}87.20±0.4587.20\pm0.4580.1580.1587.21±0.4287.21\pm0.4279.3579.3587.05±0.3387.05\pm0.3379.4079.4087.31±0.28\mathbf{87.31\pm0.28}79.5879.5887.19±0.3087.19\pm0.3079.6879.6886.91±0.4286.91\pm0.4278.9078.9087.32±0.40\mathbf{87.32\pm0.40}80.1280.12
ϵ=4.0\epsilon=4.090.08±0.4190.08\pm0.4185.98\mathbf{85.98}90.02±0.3190.02\pm0.3185.0385.0390.14±0.3090.14\pm0.3084.6884.6889.97±0.3689.97\pm0.3684.1484.1490.10±0.2790.10\pm0.2784.4184.4190.15±0.24\mathbf{90.15\pm0.24}84.6784.6790.07±0.3490.07\pm0.3484.9784.9790.12±0.4590.12\pm0.4584.4184.41

[W2] We are sorry for any confusion. It is impossible of the input-independent mechanism, since we must satisfy the ϵ\epsilon label dp condition.

In Equation (C.3), The fist two constraints must be tight ∑y~∈B(y)py~∣y+e−ϵ∑y~∈S~∖({B(y)}∪T)py~∣y~+∑y~∈Tpy~∣y≤1,∀y∈S2,\sum_{\tilde{y}\in B(y)}p_{\tilde{y} \mid y} + e^{-\epsilon} \sum_{\tilde{y} \in \tilde{\mathcal S} \setminus (\{B(y)\}\cup\mathcal T)} p_{\tilde{y} \mid \tilde{y}}+ \sum_{\tilde{y} \in\mathcal T} p_{\tilde{y} \mid y}\le1, \forall y\in \mathcal S_2, ∑y~∈B(y)py~∣y+e−ϵ∑y~∈S~∖{B(y)}py~∣y~+e−ϵ∑y~∈S2~py~∣y~≤1,∀y∈S1,\sum_{\tilde{y}\in B(y)}p_{\tilde{y} \mid y} + e^{-\epsilon} \sum_{\tilde{y} \in \tilde{\mathcal S} \setminus \{B(y)\}} p_{\tilde{y} \mid \tilde{y}}+ e^{-\epsilon}\sum_{\tilde{y} \in\tilde{\mathcal S_2}} p_{\tilde{y} \mid \tilde{y}}\le1,\forall y \in \mathcal S_1, since our objective ∑y∈S,y~∈S~wyy~py~∣y\sum_{y \in \mathcal S,\tilde{y}\in\tilde{\mathcal S}} w_{y\tilde{y}}p_{\tilde{y} \mid y} is maximized.

[W3] We thank the reviewer for the comment. The correct expression is in Lines 116--168. We correct this inconsistency in Algorithm 1.

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

The paper introduces BlockRR, a block-structured randomized-response framework for label differential privacy in classification with imbalanced classes. It partitions labels into majority and minority groups and applies different perturbation rules within and across groups, encompassing standard randomized response and RRWithPrior as special cases. The authors formulate a constrained optimization characterization, establish an ϵ\epsilon-label differential privacy guarantee, and derive an excess-risk bound under singleton-block assumptions. Experiments on imbalanced CIFAR-10, CIFAR-100, and MNIST variants show competitive overall accuracy and generally better average per-class accuracy than RRWithPrior, while improvements over standard randomized response vary across settings.

Critical strengths
  1. Unified and flexible framework: BlockRR incorporates class-prior information through configurable label partitions and perturbation rules, recovering standard randomized response and RRWithPrior as special cases.

  2. Theoretical analysis: The paper provides an optimization characterization, label differential privacy analysis, and an excess-risk bound under singleton-block assumptions.

  3. Evaluation accounting for class imbalance: Experiments across CIFAR-10, CIFAR-100, and MNIST variants assess both overall and average per-class accuracy, demonstrating competitive performance and generally improved per-class accuracy relative to RRWithPrior.

Critical weaknesses
  1. Inconsistent mechanism specification: Algorithm 1 assigns γ\gamma to minority-to-majority transitions outside TT, whereas the mechanism definition and privacy proof require β\beta. Consequently, the sampling probabilities can fail to sum to one as written.

  2. Insufficient justification of optimality: Appendix C assumes that selected linear-program constraints are tight and that probabilities are symmetric within each group, without adequately establishing these properties under unequal prior weights.

  3. Limited empirical advantage and coverage: Improvements over standard RR are modest and inconsistent, with average per-class accuracy often lower on the CIFAR-10 variants. Comparisons cover only two RR baselines and artificially imbalanced image datasets, limiting evidence of broader effectiveness.

Questions for authors

What is the key methodological improvement of BlockRR over standard RR and RRWithPrior, and under which privacy budgets and class-imbalance conditions does its block structure provide a clear advantage in overall or per-class accuracy?

1 comment

[W1] We thank the reviewer for this comment. The correct expression appears in Lines 116–168. We have corrected this inconsistency in Algorithm 1.

[W2] In Equation (C.3), The fist two constraints must be tight ∑y~∈B(y)py~∣y+e−ϵ∑y~∈S~∖({B(y)}∪T)py~∣y~+∑y~∈Tpy~∣y≤1,∀y∈S2,\sum_{\tilde{y}\in B(y)}p_{\tilde{y} \mid y} + e^{-\epsilon} \sum_{\tilde{y} \in \tilde{\mathcal S} \setminus (\{B(y)\}\cup\mathcal T)} p_{\tilde{y} \mid \tilde{y}}+ \sum_{\tilde{y} \in\mathcal T} p_{\tilde{y} \mid y}\le1, \forall y\in \mathcal S_2,

∑y~∈B(y)py~∣y+e−ϵ∑y~∈S~∖{B(y)}py~∣y~+e−ϵ∑y~∈S2~py~∣y~≤1,∀y∈S1,\sum_{\tilde y\in B(y)}p_{\tilde y \mid y} + e^{-\epsilon} \sum_{\tilde y \in \tilde{\mathcal S} \setminus \{B(y)\}} p_{\tilde y |\tilde y}+ e^{-\epsilon}\sum_{\tilde y \in\tilde{\mathcal S_2}} p_{\tilde y |\tilde y}\le1,\forall y \in \mathcal S_1,

since our objective ∑y∈S,y~∈S~wyy~py~∣y\sum_{y \in \mathcal S,\tilde{y}\in\tilde{\mathcal S}} w_{y\tilde{y}}p_{\tilde{y} \mid y} is maximized.

We appreciate the comment on the symmetry of the probabilities, we should add.

[W3] The two RR baselines are not arbitrary: they are the most competitive representative of the same family in the RR-type mechanisms.

Standard RR applies a one-size-fits-all perturbation to all labels, ignoring dataset-specific structure during randomization, while RRWithPrior avoids this by discarding minority labels, at the cost of removing the very classes it is meant to protect. BlockRR instead constructs a block structure derived from the dataset's own structure and perturbs each block separately. This lets it handle the majority and minority labels with separate randomization strategies rather than a single global one.

[Q1-1] Standard RR applies a one-size-fits-all perturbation to all labels, ignoring dataset-specific structure during randomization, while RRWithPrior avoids this by discarding minority labels, at the cost of removing the very classes it is meant to protect. BlockRR instead constructs a block structure derived from the dataset's own structure and perturbs each block separately. This lets it handle the majority and minority labels with separate randomization strategies rather than a single global one. The key methodological improvement is thus a structure-aware partition of the label space: by randomizing the majority and minority separately, BlockRR counteracts the majority's dominance over the randomization process without discarding minority labels as RRWithPrior does.

[Q1-2] BlockRR's advantage is largest in the low ϵ\epsilon regime (ϵ<1\epsilon<1), where label randomization is strong and a uniform strategy perturbs minority and majority labels alike. As ϵ\epsilon increases, the gap narrows and largely vanishes by ϵ>=4\epsilon>=4.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.