- 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 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 enters the optimality argument.
2. Algorithm. Algorithm 1 randomizes individual labels given a partition, while Algorithm 2 estimates private priors from and constructs the privatized dataset from . It is unclear what the protected object is in the two algorithms. Moreover, using the part of the original data to estimate the prior probability , although Algorithm 2 protects via the Laplace mechanism in Algorithm 3, the subsequent randomiztion of depends on the estimated prior. Please clarify how the labels in are protected and how the proof in Theorem 4.5 covers the full algorithm.
3. Theorem. Theorem 4.7 depends on the uncontrolled term , 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 without explanation.
Questions for authors
-
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?
-
For and , Section 3.1 (line 162) assigns probability , whereas Algorithm 1 (line 225) assigns . Equation (3.1) also uses for this case. Which is correct, and which is used in the experiments?
-
How were and 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
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 and . So I keep my score unless the authors can provide more details and clarifications.
[W1] The objective in Equation (4.1) maximizes the inner product between wyy~ and py~∣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.
[W3] The term Δ(x)=maxj∣gj(x)−sjη~j(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 η~ (and hence Δ(x)) is unavailable at training time. It would therefore be unreasonable to include Δ(x) in the training procedure, and our algorithm does not: Δ(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~ and py~∣y. When we maximize this objective function, where wyy~ 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, ∑y~∈B(y)py~∣y+e−ϵ∑y~∈S~∖{B(y)}py~∣y~+e−ϵ∑y~∈S2~py~∣y~≤1,∀y∈S1, since our objective ∑y∈S,y~∈S~wyy~py~∣y is maximized.
[Q3] The choices of l and σ is manually, in the manner of a grid search.