On Theoretical Limits of Learning with Label Differential Privacy

Summary

This paper investigates the theoretical boundaries of learning with Label Differential Privacy (Label-DP) in both central and local models. Label-DP is a weakening of standard differential privacy, where only the privacy of the "label" of each example is to be protected (an example is a pair (feature vector, label)). The key contributions of the paper are to establish min-max optimal rates for excess error in the settings of: * (multi-class) classification, * regression with bounded labels, * regression with unbounded labels (but under a bounded moment condition). The min-max rates are over the class of data distributions that satisfy $\beta$-Holder smoothness, admits a lower bound on probability density that is bounded away from zero, assumes that there are no “sharp corners” in the input space, and a $\gamma$-margin assumption (in case of classification), or bounded label range or bounded label moments (in case of regression). These min-max rates are then compared against the previously known min-max rates for learning under “full” local-DP (that protects both features and labels), as well as non-private learning. The key takeaways are: * Local-DP vs Non-Private: * For classification and regression with bounded labels, the sample complexity under Local-DP increases by a factor of $1/\varepsilon^2$, but has the same rate in terms of desired excess error. This is unlike “Full Local-DP”, where the sample complexity is larger even in terms of the desired excess error. * For regression with unbounded labels, the dependence of sample complexity on desired excess error is worse than the non-private setting. * Central-DP vs Non-Private: * The excess error is the sum of the non-private excess error and an additional term that decays faster in the number of samples, so the additional sample complexity due to privacy is negligible for very small excess error.

Strengths

The paper provides a comprehensive study of the min-max rates for learning under label differential privacy, in both local and central models of DP, and for both classification and regression. This complements prior literature on min-max rates for learning (non-privately) and for learning under (full) differential privacy. The rates highlight the precise cost of _label_ differential privacy and the sample complexity benefits over full differential privacy.

Weaknesses

While there are many results in the paper, I think the proof techniques in both lower and upper bounds use mostly standard tools (This is not necessarily a weakness!). The paper writing could be improved at several places though. Some comments are listed below under "Questions".

Questions

I don't have any significant questions. Some suggestions about writing are listed below: * Table 1: I understood that the last two rows of Table 1 are prior work, and the first two rows are the new contributions in this paper. But it would be good to include appropriate citations prominently, e.g. in the caption for Table 1. * Line 122: $\mathbb{E}[l(g(X, Y))]$ should be $\mathbb{E}[l(g(X), Y)]$. * Line 135 (Eq 8): I think $\eta^*(x) = \max_k \eta_k(x)$, but it is not formally defined anywhere? * Line 137: Proof of Proposition 2 in Appendix A does not cover the regression setting. (It is quite standard, but might be good to include the proof for completeness.) * Line 139: Is Assumption 1 only about the classification setting? If so, maybe it makes sense to move it to Section 4? * Line 145: Assumption 1 (d): It is not explained until this point that $\mathcal{X} \subseteq \mathbb{R}^d$. I think this should be defined upfront if this is assumed throughout the paper. * Line 169: If I understand correctly, the $\inf_{\hat{Y}}$ refers to $\hat{Y}$ that is a function of the outputs of the mechanism on all inputs $(M(x_i, y_i))_i$. This notation is implicit, but would be good to spell out. * Line 202: Is there a reference for the bounds for “full” local DP, that protects both features and labels ? * Line 244: How is Assumption 1 relevant for regression? What is $\eta_j$ ? Only points (c) and (d) make sense. Maybe (a) also makes sense for $\eta$ instead of $\eta_j$ ? * Line 297: $Y_{Ti}$ notation is awkward to read. Might want to make it something like $Y^T_i$?

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

I do not see any potential negative societal impact of this work, as it is primarily theoretical.

Summary

This work studies the minimax rates for classification and regression under (pure) label differential privacy in both the local and central models. They prove that rates of convergence for classification and regression with bounded label noise in the local label DP model are comparable to those for the non-private tasks, except for the expected $1/\varepsilon^2$ dependence. This represents an improvement over rates for standard DP in both settings, where there is a worse dependence on the dimension of the covariates. They also prove, however, in the case of regression with unbounded label noise, the convergence rate improvements over “full” DP aren’t as meaningful.

Strengths

This work makes notable progress in our theoretical understanding of the costs of label DP relative to non-private and full DP algorithms for the same learning task.

Weaknesses

The presentation could be improved in several places. Admittedly, this is written from a statistical perspective that is different from the one I am most familiar with, so some of the perceived presentation issues may just be a matter of convention, but the following changes might make this work more understandable to the general NeurIPS community: Abstract: The main challenge and the techniques to overcome them as stated in the abstract aren’t clear to me as a reader at this point. It’s not yet stated that the subject of interest is minimax rates, and so there’s no context for the statement “take infimum over all possible learners” and why that would present a challenge. Generally, I did not have a good idea of what the contribution of this work was from the abstract. Introduction: “the learning performances” -> “the learning performance” “the label DP” -> “label DP” In Table 1, attribution for the full DP rates in the local DP setting as well as the rates in the non-private setting should be given in the table. Also, I think there’s an issue with the parentheses in the local label DP rates for regression with bounded label noise. Section 2: In the “Minimax analysis for private data” paragraph, KNLRS11 is attributed with finding the relation between label DP and stochastic queries. This is not accurate, this work characterizes local DP learning by the statistical query model. Section 3: “We hope that $R - R^*$ to be as small as possible” -> “we seek to minimize this risk” or something similar “the Bayes optimal classifier and the corresponding Bayes risk is” -> “the Bayes optimal classifier and the corresponding Bayes risk are” In Proposition 2, f(x) is used before it is defined. Section 4: I didn’t find the proof outline for Theorem 1 or Theorem 3 to be informative at all. It would be good to add more specifics if possible. “Let the privacy mechanism M(x,y) outputs” -> “Let the privacy mechanism M(x,y) output”

Questions

Do you have a sense of how the rates would change for approximate label DP?

Rating

7

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

Yes, the authors address the limitations.

Summary

The paper considers the problems of classification and regression under the constraint of local/central pure label DP. The authors derive upper and lower bounds on the excess risk (compared to the non-private Bayes classifier/regression) for these problems, under somewhat standard assumptions on the 'ground truth' randomized label function $\eta$. For regression, both the case where the labels are bounded and have bounded moments are considered. For the lower bounds, the authors develop extensions of techniques from minimax estimation to label DP. For upper bounds, authors propose some algorithms combining 'binning' different examples with a privacy mechanism chosen according to the problem setting. The upper/lower bounds are matching in each setting up to logarithmic factors. For local label DP, the authors show the minimax excess risk with $N$ samples matches the non-private bounds using $N \min\{\epsilon^2, 1\}$ samples. In other words, with $\epsilon = \Omega(1)$ the minimax risk asymptotically matches the non-private risk, and otherwise there is an inherent separation. For central label DP, the minimax bound is one that approaches the non-private bound as $N \rightarrow \infty$ for any fixed $\epsilon$, showing a qualitative difference. For local "full" DP, i.e. the features are also private, even for $\epsilon = \Omega(1)$ and large $N$ one cannot achieve the non-private rate.

Strengths

* Derives optimal (up to log factors) upper and lower bounds for several different variants of classification/regression under label DP. * To derive these bounds, introduces some new technical tools for minimax analysis of DP algorithms that might be useful in future work. * Label DP is a variant of DP that is seeing attention in practice, and classification/regression are fundamental problems, so the results in the paper can have a practical impact easily. * The authors do a good job making clear the comparison between the results in different settings. e.g. Table 1 is a very concise summary that allows one to draw all the essential comparisons between the different settings, and there are discussions like Remark 1 that give qualitative interpretations of the quantitative results, and also discuss other baselines to compare to.

Weaknesses

The main issue is with the presentation. Specifically, the presentation does a great job explaining what the final results are and helping the reader contextualizing them, but at some points the techniques used to obtain the result are discussed at a very high level in the main body and why they work remains obscure even after reading the proof outlines in the main body multiple times. There are some cases where the authors do a good job concisely describing a proof, e.g. Theorem 6's proof outline is very concise but it still gives a good idea what the proof looks like, even if they would have to check the appendix for details. But for others, like Theorems 1/2/3, the proof outline is not very informative. See Questions for more details. I understand the authors are constrained by space requirements, but I think the allocation of space in the main body can be better thought out. For example, I think it might be better to try to give the reader a very good understanding of classification and/or bounded label regression (e.g., Lemma 1 from the Appendix could be brought to the main body without its proof, and the authors could explain how it is used), and omit all but the top-level points on bounded label moment regression, rather than giving a sparse understanding of all three.

Questions

These are some examples of points I think are not clear from the main body which a reader interested in these problems might be able to understand better if the presentation were improved. * What techniques from local DP / minimax theory does Theorem 1 use / how would it vary from e.g. the proof for the corresponding non-private lower bound? Saying you use techniques from certain areas/papers without specifying what they are is not particularly informative to a reader. (even giving a high-level summary of the technique would be ok) * How do you decide the number of bins in your upper bound for Theorem 2? Presumably by optimizing some tradeoff b/t the number of examples per bin and having narrower bins where $\eta$ cannot vary too much within a bin, but I'm not confident about this from reading the main body. * $\mathcal{X}$ is a vector space, what does "a bin of length $h$" mean for bins defined over a vector space? I believe it means something like each bin has radius at most $h$ in some appropriate norm, but not sure. * In Theorem 3, the proof outline's first and second halves seem disconnected. The authors mention the model complexity needs to increase with $N$, how does the second half of the proof outline address this necessity?

Rating

5

Confidence

3

Soundness

4

Presentation

2

Contribution

3

Limitations

Yes

Summary

This paper investigates the minimax risks of classification and regression (with both bounded and heavy-tailed noise) under label differential privacy (DP) in both central and local models.

Strengths

The paper provides a comprehensive analysis by considering both upper and lower bounds for the minimax risks. It explores both central and local DP models and different settings, covering a broad spectrum of scenarios.

Weaknesses

The writing quality needs improvement to meet publication standards. Several sections are challenging to understand. Specific issues include: (1) Around line 178, the output of the mechanism for classification is unclear. Why is it not a one-hot vector, or at least why is the L1 norm not equal to 1? (2) Some notations are overused. For example, "c" refers to the lower bound of the density function in Assumption 1 and also denotes the classifier in line 186 and subsequent proofs. (3) The description of the algorithm before Theorem 2 is vague and lacks clarity. (4) The proofs in the appendix are hard to follow without explanations or discussions. For instance, how is $\phi$ defined in Equation (35), and what purpose does it serve? Why does the construction satisfy the assumptions? There seem to be some typos or missing elements in Equations (39) and (40).

Questions

The paper discusses non-private baselines. Are there citations provided for these baselines?

Rating

4

Confidence

2

Soundness

2

Presentation

2

Contribution

2

Limitations

See weaknesses and questions.

Response to Rebuttal

I would like to thank the author(s) for their response. The proposed changes sound good to me, and I will keep my rating.