Blockwise Randomized Response: Theory and Algorithms for Label Differential Privacy

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 $\mathcal{T}\subseteq {\tilde{\mathcal{S}}}_1$ 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.