On Theoretical Limits of Learning with Label Differential Privacy

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 14:40:50

Abstract: Label differential privacy (DP) is designed for learning problems with private labels and public features. Although various methods have been proposed for learning under label DP, the theoretical limits remain unknown. The main challenge is to take infimum over all possible learners with arbitrary model complexity. In this paper, we investigate the fundamental limits of learning with label DP under both central and local models. To overcome the challenge above, we derive new lower bounds on testing errors that are adaptive to the model complexity. Our analyses indicate that $\epsilon$-local label DP only enlarges the sample complexity with respect to $\epsilon$, without affecting the convergence rate over the sample size $N$, except the case with heavy-tailed label. Under the central model, the performance loss due to the privacy mechanism is further weakened, such that the additional sample complexity becomes negligible. Overall, our analysis validates the promise of learning under the label DP from a theoretical perspective and shows that the learning performance can be significantly improved by weakening the DP definition to only labels.

Main paper: 
 introduction: 
 Many modern machine learning tasks require sensitive training samples that need to be protected from leakage [1] . As a standard approach for privacy protection, differential privacy (DP) [2] has been extensively studied [3] [4] [5] [6] [7] [8] [9] . However, the learning performances under original DP definition are usually far from satisfactory [10] [11] [12] [13] . Therefore, researchers attempt to design weakened DP requirements, under which the performances can be significantly improved, while still securing sensitive information. Under such background, label DP has emerged in recent years [14] , which regards features as public, while only labels are sensitive and need to be protected. Such setting is realistic in many applications, such as computational advertising [15] , recommendation systems [16] and medical diagnosis [17] . These tasks usually use some basic demographic information as features, which can be far less sensitive.Despite various approaches for learning with label DP [14, [18] [19] [20] [21] , the fundamental limits are still unknown. An interesting question is: By weakening the DP definitions to only labels, how much accuracy improvement is possible? From an information-theoretic perspective [22] , the underlying limits of statistical problems are characterized by the minimax lower bound, which takes the supremum over all possible distributions from a general class, and infimum over all learners.Deriving minimax lower bounds for learning under the label DP is challenging in two aspects. Firstly, under label DP, each sample has both public (i.e. the feature) and private (i.e. the label) components.Directly applying the methods for original DP [23] [24] [25] [26] [27] treats all components as private, and thus does not yield tight results. Secondly, the classical packing method [47] is only suitable for fixed model structures with fixed dimensionality. However, to establish lower bounds, one needs to take infimum over all possible learners with arbitrary model complexity. Table 1 : Minimax rate of convergence under label differential privacy. d is the dimension of features.In this paper, we investigate the theoretical limits of classification and regression problems under label DP. Our analysis involves both central and local models. For each problem, we derive the informationtheoretic minimax lower bound of the risk function over a wide class of distributions satisfying the β-Hölder smoothness and the γ-Tsybakov margin assumption [28] (see Assumption 1 for details).The general idea is to convert the problem to multiple hypothesis testing. To overcome the challenges above, we provide a bound of Kullback-Leibler divergence over joint distributions of private and public random variables, which is tighter than the bound between fully private variables. Moreover, under the central model, instead of using the packing method, we develop a new lower bound on the minimum testing error for each pair of hypotheses based on the group privacy property [4] , which is suitable for arbitrary model complexity. After deriving minimax lower bounds, we also propose algorithms with matching upper bounds to validate the tightness of our results.The results are shown in Table 1 , in which the third row refers to the bounds under the original local DP definition, while the fourth row lists the non-private baselines. To the best of our knowledge, minimax rates under central DP have not been established, and are thus not listed here. The main findings are summarized as follows.• Under ϵ-local label DP, for classification and regression with bounded label noise, the sample complexity is larger by a factor of O(1/ϵ 2 ). However, the convergence rate remains unaffected, which is in clear contrast with the original DP, under which the convergence rate is slower.• Under ϵ-local label DP constraint, for regression with heavy-tailed label noise, the convergence rate of risk over N becomes slower, indicating that heavy-tailed labels increase the difficulty of privacy protection.• Under ϵ-central label DP constraint, the performance loss caused by the privacy mechanism becomes further weakened. The risk only increases by a term that decays faster than the non-private rate, indicating that the additional sample complexity caused by the privacy mechanism becomes negligible with large N .In general, our analysis provides a theoretical perspective of understanding label DP. The result shows that by weakening the DP definition to protecting labels only, the learning performances can be significantly improved. 
related work: 
 Label DP. Under the local model, labels are randomized before training. The simplest method is randomized response [30] . An important improvement is proposed in [14] , called RRWithPrior, which incorporates prior distribution. [19] proposes ALIBI, which further improves randomized response by generating soft labels through Bayesian inference. There are also several methods for regression under label DP [18, 31] . Under central label DP, [20] proposes a clustering approach. [19] proposes private aggregation of teacher ensembles (PATE), which is then further improved in [21] .Minimax analysis for public data. Minimax theory provides a rigorous framework for the best possible performance of an algorithm given some assumptions. Classical methods include Le Cam [32] , Fano [33] and Assouad [34] . Using these methods, minimax lower bounds have been widely established for both classification and regression problems [28, 29, [35] [36] [37] [38] [39] [40] [41] . If the feature vector has bounded support, then the minimax rate of classification and regression are O(N -β(γ+1) 2β+d )and O(N -2β 2β+d ), respectively.Minimax analysis for private data. Under the local model, [42] finds the relation between label DP and stochastic query. [23] and [24] develop the variants of Le Cam, Fano, and Assouad's method under local DP. Lower bounds are then established for various statistical problems, such as mean estimation [43] [44] [45] [46] , classification [26] and regression [27] . Under central model, for pure DP, the standard approach is the packing method [47] , which is then used in hypothesis testing [48] , mean estimation [49, 50] , and learning of distributions [51] [52] [53] . There are also several works on approximate DP, such as [54, 55] .This work studies the theoretical limits of label DP, under which each sample is a mixture of public feature and private labels, thus existing methods can not be directly applied here. Under the central model, the minimax analysis becomes more challenging, since the packing method is only suitable for fixed model structures (i.e. the dimensionality of model output is fixed), while we need to find the minimum possible error over all possible learners with arbitrary output dimensions. As a result, the lower bounds of general classification and regression problems have not been established even under the original DP definition. To overcome such challenge, we develop a new approach to bound the error of hypothesis testing (see Lemma 1 in Appendix D).Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: It is explained at the end of conclusion section.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.• The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.• The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.• The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.• The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.• If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.• While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
preliminaries: 
 In this section, we show some necessary definitions, background information, and notations.To begin with, we review the definition of DP. Suppose the dataset consists of N samples (x i , y i ), i = 1, . . . , N , in which x i ∈ X is the feature vector, whileEQUATIONin which D and D ′ are adjacent if they differ only on a single sample, including both the feature vector and the label.In machine learning tasks, the output of A is the model parameters, while the input is the training dataset. Definition 1 requires that both features and labels are privatized. Consider that in some applications, the features may be much less sensitive, the notion of label DP is defined as follows. Compared with Definition 1, Definition 2 only requires the output to be insensitive to the replacement of a label. Therefore label DP is a weaker requirement. Correspondingly, the local label DP is defined as follows.EQUATIONDefinition 3 requires that each label is privatized locally before running any machine learning algorithms. It is straightforward to show that local label DP ensures central label DP. To be more precise, we have the following proposition.Proposition 1. Let z i = M (x i , y i ) for i = 1, . . . , N . If A is a function of (x i , z i ), i = 1, . . . , N , then A is ϵ-label DP.In supervised learning problems, given N samples (X i , Y i ), i = 1, . . . , N drawn from a common distribution, the task is to learn a function g : X → Y. For a loss function l : Y × Y → R, the goal is to minimize the risk function, which is defined as the expectation of loss function between the predicted value and the ground truth:EQUATIONThe minimum risk among all function g is called Bayes risk, i.e. R * = min g E[l(g(X, Y ))]. In practice, the sample distribution is unknown, and we need to learn g from samples. Therefore, the risk of any practical classifiers is larger than Bayes risk. The gap R -R * is called excess risk, and we hope that R -R * to be as small as possible. Now we discuss classification and regression problems separately.1) Classification. For classification problems, the size of Y is finite. For convenience, we denoteY = [K],in which [K] := {1, . . . , K}. In this paper, we use 0 -1 loss, i.e. l(Ŷ , Y ) = 1( Ŷ ̸ = Y ), then R = P( Ŷ ̸ = Y ).Define K functions η 1 , . . . , η K as the conditional class probabilities:EQUATIONUnder this setting, the Bayes optimal classifier and the corresponding Bayes risk isEQUATIONEQUATION2) Regression. Now we consider the case with Y having infinite size. We use ℓ 2 loss in this paper, i.e.l( Ŷ , Y ) = ( Ŷ -Y ) 2 .Then the Bayes risk isEQUATIONThen the following proposition gives a bound of the excess risk for classification and regression problems.Proposition 2. For any classifier c : X → [K], the excess risk of classification is bounded byEQUATIONFor any regression estimate η : X → Y, the excess risk of regression is bounded byEQUATIONThe proof of Proposition 2 is shown in Appendix A. Finally, we state some basic assumptions that will be used throughout this paper.Assumption 1. There exists some constants L, β, C T , γ, c, D and θ ∈ (0, 1] such that (a) For all j ∈ [K] and any x, x ′ , |η j (x) -η j (x ′ )| ≤ L ∥x -x ′ ∥ β ; (b) For any t > 0, P (0 < η * (X) -η s (X) < t) ≤ C T t γ , in which η s (x)is the second largest one among {η 1 (x), . . . , η K (x)};(c) The feature vector X has a probability density function (pdf) f which is bounded from below, i.e.f (x) ≥ c; (d) For all r < D, V r (x) ≥ θv d r d , in which V r (x) is the volume (Lebesgue measure) of B(x, r) ∩ X , v d is the volume of a unit ball.Assumption 1 (a) requires that all η j are Hölder continuous. This condition is common in literatures about nonparametric statistics [28] . (b) is generalized from the Tsybakov noise assumption for binary classification, which is commonly used in many existing works in the field of both nonparametric classification [29, 37, 40, 41] and differential privacy [26, 27] . If K = 2, then η * and η s refer to the larger and smaller class conditional probability, respectively. An intuitive understanding of (b) is that in the majority of the support, the maximum value among {η 1 (x), . . . , η K (x)} should have some gap to the second largest one. With sufficiently large sample size and model complexity, assumption (b) ensures that for test samples within the majority of the support X , the algorithm is highly likely to correctly identify the class with the maximum conditional probability. Therefore, in (b), we only care about η * (x) and η s (x), while other classes with small conditional probabilities can be ignored. (c) is usually called "strong density assumption" in existing works [39, 40] , which is quite strong. It is possible to relax this assumption so that the theoretical analysis becomes suitable for general cases.However, we do not focus on such generalization in this paper. Assumption (d) prevents the corner of the support X from being too sharp. In the remainder of this section, denote F cls as the set of all pairs (f, η) satisfying Assumption 1.In this section, we derive the upper and lower bounds of learning under central and local label DP, respectively.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [NA] Justification: This is a theoretical paper without experiments.Guidelines:• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details.• While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).• The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://nips.cc/public/guides/CodeSubmissionPolicy) for more details.• The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.• The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.• At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).• Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
local label dp: 
 1) Lower bound. The following theorem shows the minimax lower bound, which characterizes the theoretical limit.Theorem 1. Denote M ϵ as the set of all privacy mechanisms satisfying ϵ-local label DP (Definition 3). ThenEQUATION)Proof. (Outline) It suffices to derive (10) with K = 2. We convert the problem into multiple binary hypothesis testing problems. In particular, we divide the support into G bins. For some of them, we construct two opposite hypotheses such that they are statistically not distinguishable. Our proof uses some techniques in local DP [24] and some classical minimax theory [28] . The detailed proof is shown in Appendix B.In Theorem 1, (10) takes supremum over all joint distributions of (X, Y ), and infimum over all classifiers and privacy mechanisms satisfying ϵ-local label DP.2) Upper bound. We then show that the bound (10) is achievable. Let the privacy mechanism M (x, y) outputs a K dimensional vector, with each component being either 0 or 1, such thatEQUATIONand P(M (x, y)(j) = 0) = 1 -P(M (x, y)(j) = 1), in which M (x, y)(j) is the j-th component of M (x, y). For N random training samples (X i , Y i ), let Z i = M (X i , Y i ), and correspondingly, Z i (j)is the j-th component of Z i .Divide the support X into G bins, named B 1 , . . . , B G , such that the length of each bin is h. B 1 , . . . , B G are disjoint, and these bins form a covering of X , i.e. X ⊂ ∪ G l=1 B l . Then calculateEQUATIONThe classification within the l-th bin isEQUATIONsuch that the the prediction given x is c(x) = c l for all x ∈ B l . The next theorem shows the privacy guarantee, as well as the bound of the excess risk.Theorem 2. The privacy mechanism M is ϵ-local label DP. Moreover, under Assumption 1, withh ∼ N (ϵ 2 ∧ 1)/ ln K -12β+d , the excess risk of the classifier described above can be upper bounded as follows:EQUATION)Proof. (Outline) For privacy guarantee, we need to show that (11) is ϵ-local label DP:EQUATION)According to Definition 3, M is ϵ-local label DP. For the performance guarantee (14) , according to Proposition 2, we need to bound η * (x) -E[η c(x) (x)] for each x. If η * (x) -η s (x) is large, then with high probability, c(x) = c * (x), and then η * (x) = η c(x) (x). Thus we mainly consider the case with small η * (x) -η s (x). The details of proof are shown in Appendix C.The lower bound (10) non-privatized samples in terms of performance.2) Comparison with local DP that protects both features and labels. In this case, the optimal excess risk is (N ϵ 2 ) -β(γ+1)/(2β+2d) ∨ N -β(γ+1)/(2β+d) , which is worse than the right hand side of (10) . Such result indicates that compared with classical DP, label DP incurs significantly weaker performance loss.3) Comparison with other baseline methods. If we use the randomized response method instead of the privacy mechanism (11) , then the performance decreases sharply with the number of classes K. Several methods have been proposed to improve the randomized response method, such as RRWithPrior [14] and ALIBI [19] . However, these methods are not guaranteed in theory. ThenEQUATIONProof. (Outline) Lower bounds under central DP are usually constructed by packing method [47] ,which works for fixed output dimensions. However, to achieve a desirable bias and variance tradeoff, the model complexity needs to increase with N . In our proof, we still divide the support into G bins and construct two hypotheses for each bin, but we develop a new tool (see Lemma 1) to give a lower bound of the minimum error of hypothesis testing. We then use the group privacy property [4] to get the overall lower bound. The details can be found in Appendix D.2) Upper bound. Now we show that ( 16) is achievable. Similar to the local label DP problem, now divide the support into G bins, such that the length of each bin is h. Now the classification within the l-th bin follows a exponential mechanism [56] : EQUATION)in which n lj = N i=1 1(X i ∈ B l , Y i = j). Then let c(x) = c l for x ∈ B l .h ∼ (ln K/ϵN ) 1 β+d + (ln K/N ) 1 2β+d, then the excess risk can be bounded as follows:EQUATION)Proof. (Outline) The privacy guarantee of the exponential mechanism has been analyzed in [4] .Following these existing analyses, it can be shown that ( 17) is ϵ-label DP. It remains to show (18) .Note that if η * (x) -η s (x) is large, then the difference between the largest and the second largest one from {n lj |j = 1, . . . , K} will also be large. From (17) , the following inequality holds with high probability: c l = arg max j n lj = arg max j η j (x) = c * (x), which means that the classifier makes optimal prediction. Hence we mainly consider the case with small η * (x) -η s (x). The details of the proof can be found in Appendix E.The upper and lower bounds match up to logarithmic factors. In (18) , the first term is just the non-private convergence rate, while the second term (ϵN ) -β(γ+1) β+d can be regarded as the additional risk caused by the privacy mechanism. It decays faster with N compared with the first term, thus the additional performance loss caused by the privacy mechanism becomes negligible as N increases.This result is crucially different from the local model, under which the privacy mechanism always induces higher sample complexity by a factor of O(1/(ϵ 2 ∧ 1)). 
regression with bounded noise: 
 Now we analyze the theoretical limits of regression problems under local and central label DP.Throughout this section, we assume that the label is restricted within a bounded interval.Assumption 2. Given any x ∈ X , P(|Y | < T |X = x) = 1.Assumption 1 remains the same here. In the remainder of this section, denote F reg1 as the set of (f, η) that satisfies Assumption 1 and 2.1) Lower bound. Theorem 5 shows the minimax lower bound.Theorem 5. Denote M ϵ as the set of all privacy mechanisms satisfying ϵ-label DP. ThenEQUATIONThe proof of Theorem 5 is similar to that of Theorem 1, except for some details in hypotheses construction and the final bound of excess risk. The details are shown in Appendix F.2) Upper bound. The privacy mechanism is Z = Y + W , in which W ∼ Lap(2T /ϵ). Then the privacy mechanism satisfies ϵ-label DP. In this case, the real regression function η(x) can be estimated using the nearest neighbor approach. LetEQUATIONin which N k (x) is the set of k nearest neighbors of x among X 1 , . . . , X N .Theorem 6. The method described above is ϵ-local label DP. Moreover, with k ∼ N2β d+2β (ϵ∧1) -2d d+2β ,then under Assumption 1 and 2,EQUATION) Proof. (Outline) Since |Y | < T , W ∼ Lap(2T /ϵ), it is obvious that Z = Y + W is ϵ-local label DP.For the performance (21) , the bias can be bounded by the k nearest neighbor distances based on Assumption 1(a). The variance of η(x) scales inversely with k. An appropriate k can be selected to achieve a good tradeoff between bias and variance. The details are shown in Appendix G.From standard minimax analysis on regression problems, the non-private convergence rate is d+2β) . From Theorem 5 and 6, the privatization process makes sample complexity larger by a O(1/ϵ 2 ) factor.N -2β/(1) Lower bound. The following theorem shows the minimax lower bound.Theorem 7. Let A ϵ be the set of all algorithms satisfying ϵ-central DP. ThenEQUATION)2) Upper bound. For each bin B l , letEQUATIONin which W l ∼ Lap(2/(n l ϵ)). If n l = 0, i.e. no sample falls in B l , then just let ηl = 0. For allx ∈ B l , let η(x) = ηl . The excess risk can be bounded with the following theorem.Theorem 8. ( 23) is ϵ-label DP. Moreover, under Assumption 1 and 2, if h scales as h ∼ N -1 2β+d + (ϵN ) -1 d+β , then the excess risk is bounded byEQUATION)The upper and lower bounds match, indicating that the results are tight. Again, the second term in (24) converges faster than the first one with respect to N , the performance loss caused by privacy constraints becomes negligible as N increases. 
regression with heavy-tailed noise: 
 In this section, we consider the case such that the noise has tails. We make the following assumption.Assumption 3. For all x ∈ X , E[|Y | p |X = x] ≤ M p for some p ≥ 2.Instead of requiring |Y | < T for some T , now we only assume that the p-th order moment is bounded.For non-private cases, given fixed noise variance, the tail does not affect the mean squared error of regression. As a result, as long as p ≥ 2, the convergence rate of regression risk is the same as the case with bounded noise. However, the label DP requires the output to be insensitive to the worst case replacement of labels, which can be harder if the noise has tails. To achieve ϵ-DP, the clipping radius decreases with ϵ, thus the noise strength needs to grow faster than O(1/ϵ). As a result, the convergence rate becomes slower than the non-private case. In the remainder of this section, denote F reg2 as the set of (f, η) that satisfies Assumption 1 and 3.1) Lower bound. In earlier sections about classification and regression with bounded noise, the impact of privacy mechanisms is only a polynomial factor on ϵ, while the convergence rate of excess risk with respect to N is not changed. However, this rule no longer holds when the noise has heavy tails.Theorem 9. Denote M ϵ as the set of all privacy mechanisms satisfying ϵ-label DP. Then for small ϵ,EQUATION2) Upper bound. Since now the noise has unbounded distribution, without preprocessing, the sensitivity is unbounded, thus simply adding noise to Y can no longer protect the privacy. Therefore, a solution is to clip Y into [-T, T ], and add noise proportional to T /ϵ to achieve ϵ-local label DP.Such truncation will inevitably introduce some bias. To achieve a tradeoff between clipping bias and sensitivity, the value of T needs to be tuned carefully. Based on such intuition, the method is precisely stated as follows.Let Z i = Y T i +W i , in which Y T i is the truncation of Y i , i.e. Y T i = (Y i ∧T )∨(-T ),and W ∼ Lap(2T /ϵ). The result is shown in the next theorem.Theorem 10. The method above is ϵ-local label DP. Moreover, with k ∼ (N ϵ 2 )2pβ 2pβ+d(p-1) ∨ N 2β 2β+d ,andT ∼ (kϵ 2 ) 1 2p, the risk is bounded byEQUATION)Proof. (Outline) It can be shown that the clipping bias scales as T EQUATION2) Upper bound. Now we derive the upper bound. To restrict the sensitivity, instead of estimating with (23) directly, now we calculate an average of clipped label values:EQUATIONin which W l ∼ Lap(2T /(n l ϵ)). Then for all x ∈ B l , let η(x) = ηl . The following theorem bounds the excess risk.Theorem 12. (28) is ϵ-label DP. Moreover, under Assumption 1 and 3, if h and T scales as h ∼ 1) , and T ∼ (ϵN h d ) 1/p , then the excess risk can be bounded byN -1 2β+d + (ϵN ) - 1 pβ+d(p-EQUATIONThe proof of Theorem 11 and 12 follow that of Theorem The theoretical analyses in this section are summarized as follows. In general, with fixed noise variance, if the label noise is heavy-tailed, while the non-private convergence rates remain unaffected, the additional risk caused by privacy mechanisms becomes significantly higher, indicating the difficulty of privacy protection for heavy-tailed distributions.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [NA] Justification: This is a theoretical paper without experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.• The full details can be provided either with the code, in appendix, or as supplemental material. 
conclusion: 
 In this paper, we have derived the minimax lower bounds of learning under label DP for both central and local models. Furthermore, we propose methods whose upper bounds match these lower bounds.The results indicate the theoretical limits of learning under the label DP. From these results, it is discovered that under local label DP constraints, the sample complexity blows up by a factor of at least O(1/ϵ 2 ). Under central label DP requirements, the additional error caused by privacy mechanisms is significantly smaller. Finally, it is shown that for regression problem with heavy-tailed label distribution, the additional risk induced by privacy requirement becomes inevitably higher.Limitations: The limitations of our work include the following aspects. Some assumptions can be weakened. For example, current analysis assumes that feature distributions have bounded supports, which may be extended to the unbounded case. One can let the bin splitting and nearest neighbor method be adaptive in the tails of features, such as [41] . Moreover, the bounds derived in this paper require that samples increase exponentially with dimensionality. However, in practice, the performance of learning under the label DP can be quite well even in high dimensions. The discrepancy can be explained by the fact that the minimax lower bound considers the worst-case distribution over a wide range of distributions. However, in most realistic cases, the distributions satisfy significantly better properties. A better modeling is to assume that these samples lie on a low dimensional manifold [57, 58] . In this case, it is possible to achieve a much better convergence rate.Finally, it is not sure whether approximate DP (i.e. (ϵ, δ)-DP) can improve the convergence rates.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [NA]Justification: No experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.• For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).• If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.• The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: Our paper does not violate code of ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.• The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This paper is foundational and theoretical research and not tied to particular applications.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.• The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.• If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This paper has no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.• Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.• We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: This paper does not use existing assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.• For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: From ( 5) and ( 6), the Bayes risk isEQUATIONThe risk of classifier c isEQUATIONFrom ( 31) and ( 6),EQUATION)The proof is complete.In this section, we prove the minimax lower bound of multi-class classification. The problem with K classes with K > 2 is inherently harder than that with K = 2. Therefore, we just need to prove the lower bound for binary classification, in which Y = {1, 2}. LetEQUATIONSince η 1 (x) + η 2 (x) = 1 always holds, we haveEQUATIONTherefore, η(x) captures the conditional distribution of Y given x.Find G disjoint cubes B 1 , . . . , B G ⊂ X , such that the length of each cube is h. Denote c 1 , . . . , c G as the centers of these cubes. Let ϕ(u) be some function supported at [-1/2, 1/2] d , such thatEQUATIONEQUATIONIt can be proved that if for some constant C M ,EQUATIONthen for any η = η v , η 1 and η 2 satisfies Assumption 1(b). DenoteEQUATION)Then the excess risk is bounded byEQUATIONIf vk ̸ = v k , then from (38) ,EQUATIONEQUATIONin which ρ H denotes the Hamming distance. ThenEQUATIONDefineEQUATIONin which P (X,Z) 1:N |v denotes the distribution of (X 1 , Z 1 ), . . . , (X N , Z N ) with η = η v . D KL denotes the Kullback-Leibler divergence. Then from [28] , Theorem 2.12(iv),EQUATION)It remains to bound δ. Without loss of generality, supposeEQUATIONIn (a), P X,Z|v denotes the distribution of a single sample with privatized label (X, Z), with η = η v .In (b), P Z|X=x,v denotes the conditional distribution of Z given X = x, with η = η v . (c) uses [24] ,Theorem 1. In (d), ∥ϕ∥EQUATIONFor (a), note that Z is generated from Y . From data processing inequality, (a) holds. For (b), without loss of generality, suppose that 35) and (36) ,EQUATION|η v (x)| ≤ 1/2. Therefore, -ln(1 -η v (x)) ≤ 2η v (x). Therefore (b) holds.From ( 46) and ( 47),EQUATIONLetEQUATIONThen δ ≲ 1. From (45) , with m ∼ h γβ-d ,EQUATIONHenceEQUATION)The proof is complete.DenoteEQUATIONand forEQUATIONas the number of training samples whose feature vectors fall in B l , andEQUATIONRecall ( 12) that defines S lj . From Hoeffding's inequality,EQUATIONin which X 1:N denotes X 1 , . . . , X N .DefineEQUATIONandEQUATIONNow we bound P(v * l -v lc l > t), in which c l is defined in (13) . c l can be viewed as the prediction at the l-th bin. We would like to show that the even if the prediction is wrong, the value (i.e. conditional probability) of the predicted class is close to the ground truth.v * l -v lc l > t only if ∃j, v * l -v lj > t,and S lj > S lc * l . Therefore either S lj -n l v lj > t/2 or S lc * l -n l v * l > t/2 holds. HenceEQUATION)DefineEQUATIONThenEQUATIONIn (a), we use the inequalityEQUATION)Now we bound the excess risk.EQUATIONWe need to boundB l η * (x) -E[η c(x) (x)] f (x)dx for each l.From Assumption 1(a), for anyx, x ′ ∈ B l , the distance is bounded by ∥x -x ′ ∥ ≤ √ dL. ThusEQUATIONin which L d is defined as 63) and ( 53),L d := L √ d. From (EQUATIONEQUATIONthenEQUATION)Take integration over cube B l , we getEQUATIONin which p(B l ) = P(X ∈ B l ) is the probability mass of B l . Moreover, defineEQUATIONandEQUATIONin which the ηs is the second largest value of ηj among j = 1, . . . , K, which follows the definition of η s .IfEQUATIONTake expectation over X 1:N , we getEQUATIONandEQUATION)From Assumption 1(c), p(B l ) ≥ cN h d . Therefore, from (67) and ( 71)EQUATIONIt remains to boundEQUATIONEQUATIONandEQUATIONEQUATIONThenEQUATION)ForEQUATION)It is obvious that there exists a finite constant C ′ < ∞ that depends on γ, such thatEQUATIONEQUATIONCombine ( 74), ( 79) and (82),EQUATION)To minimize the overall excess risk, letEQUATIONthenEQUATION)Compare to the simple random response method, the bin splitting avoids the polynomial decrease over K.We still divide the support as the local label DP setting, except that the value of h is different, which will be specified later in this section. Note that (42) still holds here. Let V takes values from {-1, 1} m randomly with equal probability, and V k is the k-th element. Then η V (x) is a random function. The corresponding random output of hypothesis testing is denoted as Vk , which is calculated by (38) . ThenEQUATIONin which the last step holds since Vk for different k are calculated independently.It remains to give a lower bound of P( Vk ̸ = V k ). Denote n k as the number of samples falling in B k , Ȳk as the average label values in B k :EQUATIONEQUATIONMoreover, defineEQUATIONin which the last step comes from (36) . ThenEQUATIONin which X 1:N means X 1 , . . . , X N . We then show the following lemma.Lemma 1. If 0 ≤ t ≤ ln 2/(ϵn k ), and n k t is an integer, thenEQUATIONProof. Construct D ′ by changing the label values of l = n k t items from these n k samples falling in B k , from -1 to 1. Then the average label values in B k is denoted as Ȳ ′ k after such replacement. Vk also becomes V ′ k . Then from the ϵ-label DP requirement, Gaussian distribution with mean a k . To be more rigorous, by Berry-Esseen theorem [?], for someEQUATIONEQUATION)Similarly,EQUATION)We first analyze cubes withEQUATION)Under condition (96), the right hand side of ( 94) and ( 95) are at least 1/4. ThereforeEQUATIONFrom (86),EQUATION)From ( 35), ( 89) and (87), a k ≤ h β . ThereforeEQUATION)Recall that each cube has probability mass ch d . Select h such thatEQUATION)From Chernoff inequality, 16C 2 E < n k < ln 2/(ϵh β ) holds with high probability. (100) yieldsEQUATION)Recall the bound of m in (37) . Let m ∼ h γβ-d , then (99) becomesEQUATION)Moreover, the standard lower bound for classification [28] isEQUATIONEQUATION)DenoteEQUATIONEQUATION)For all j such that n * l -n lj > t,EQUATIONEQUATIONHenceEQUATIONDefineEQUATIONthenE[n lj |X 1:N ] = n l v lj .(111) From Hoeffding's inequality,EQUATIONin which the last step uses the inequalitEQUATION)By Hölder continuity assumption (Assumption 1(a)), for x ∈ B l ,EQUATIONEQUATION)Now take integration over B l . 117) is the central label DP counterpart of (67). The remainder of the proof follows arguments of the local label DP. We omit detailed steps. The result isEQUATION) in which p(B l ) = P(X ∈ B l ) = B l f (x)dx. (EQUATIONEQUATIONEQUATION)The proof is complete.Find G cubes in the support and the length of each cube is h. Let ϕ(u) be the same as the classificationEQUATION) Let P(Y = 1|x) = (1 + η v (x))/2, P(Y = -1|x) = (1 -η v (x)), then η(x) = E[Y |x] = η v (x).The overall volume of the support is bounded. Thus, we haveG ≤ C G h -d (122)for some constant C G .EQUATIONthen the excess risk is bounded byEQUATIONEQUATIONEQUATIONSimilar to the classification problem analyzed in Appendix B, letEQUATIONthen δ ≲ 1, andEQUATIONThusEQUATIONAccording to Assumption 2, |Y | < T with probability 1, thus Var[Y |x] ≤ T 2 for any x. A Laplacian distribution with parameter λ has variance 2λ 2 , thusEQUATIONHenceEQUATION)Now we analyze the bias first.EQUATIONThusEQUATIONfor some constant C 1 .It remains to bound the variance.EQUATIONFor the first term in (135),EQUATION)For the second term in (135),EQUATIONTherefore (135) becomesEQUATIONCombine the analysis of bias and variance,EQUATIONTherefore the overall risk is bounded byEQUATIONThe optimal growth rate of k over N isEQUATIONThen the convergence rate of the overall risk becomesEQUATIONH Proof of Theorem 7From (127),EQUATIONFollow the analysis of lower bounds of classification in Appendix D, let h scales as (101), thenEQUATIONMoreover, note that the non-private lower bound of regression isEQUATIONCombine ( 144) and (145),EQUATIONI Proof of Theorem 81) Analysis of bias. Note thatEQUATIONTherefore, for all x ∈ B l ,EQUATIONTherefore for all x ∈ B l ,EQUATION2) Analysis of variance.EQUATIONEQUATIONSimilarly,EQUATION)The mean squared error can then be bounded by the bounds of bias and variance.EQUATIONEQUATIONEQUATIONJ Proof of Theorem 9Now we prove the minimax lower bound of nonparametric regression under label DP constraint. We focus on the case in which ϵ is small.Similar to the steps of the proof of Theorem 5 in Appendix F, we find B cubes in the support. The definition of η v , vk are also the same as (121) and (123). Compared with the case with bounded noise, now Y can take values in R.For given x, letEQUATIONIn Appendix F about the case with bounded noise, T is a fixed constant. However, here T is not fixed and will change over N . It is straightforward to show that the distribution of Y in (156) satisfies Assumption 3:EQUATIONMoreover, by taking expectation over Y , it can be shown that η v is still the regression function:EQUATIONLetEQUATIONHere we still defineEQUATIONEQUATIONLetEQUATIONEQUATIONK Proof of Theorem 10EQUATIONThenEQUATIONThereforeEQUATIONNow we bound I 1 , I 2 and I 3 separately.Bound of I 1 . We show the following lemma (which will also be used later).Lemma 2.EQUATIONProof. Firstly, we decompose η T (x) and η(x):EQUATIONEQUATIONThe first term is the same between (168) and (169). Therefore we only need to compare the second and the third term.EQUATIONEQUATIONSimilarly,EQUATIONA Combination of these two inequalities yields the (167).With Lemma 2,EQUATION)Bound of I 2 . Follow the steps in (134),EQUATION)Bound of I 3 . We decompose Var[η(x)] as following:EQUATIONFor the first term in (175), from Assumption 3,EQUATIONRecall (20) , we haveEQUATION)For the second term in (175), (137) still holds, thusEQUATIONandEQUATIONPlug ( 173), ( 174) and ( 179) into (166), and take expectations, we getEQUATIONEQUATIONEQUATIONLet Y be distributed as (156). Recall Lemma 1 for the problem of classification and regression with bounded noise. Now we show the corresponding lemma for regression with unbounded noise.Lemma 3. If 0 ≤ t ≤ T ln 2/(ϵn k ), and n k t/T is an integer, thenEQUATION)Here we briefly explain the condition n k t is an integer. Recall the definition of Ȳk in (88). Now since Y take values in {-T, 0, T }, n k Ȳk /T must be an integer. Therefore, in Lemma 3, we only need to consider the case such that n k t/T is an integer.Proof. The proof follows the proof of Lemma 1 closely. We provide the proof here for completeness.Construct D ′ by changing the label values of l = n k t/T items from these n k samples falling in B k , from -T to T . Then the average label values in B k is denoted as Ȳ ′ k after such replacement. Vk also becomes V ′ k . Then from the ϵ-label DP requirement, We then follow the proof of Theorem 3 in Appendix D. (101) becomesEQUATIONEQUATIONIn (156), note that P(Y = T ) ≥ 0 and P(Y = -T ) ≥ 0. Therefore M p /T p ≥ η v (x)/T . ThisEQUATIONi.e.h ∼ (ϵN ) -p-1 pβ+d(p-1) .Combine with standard minimax rate, the lower bound of regression with unbounded noise isEQUATIONM Proof of Theorem 121) Analysis of bias. Note that Lemma 2 still holds here. Moreover, recall (149). Therefore|E[η l ] -η(x)| ≤ |E[η l -η T (x)]| + |η T (x) -η(x)| ≤ L d h β + M p p -1 T 1-p . (190)2) Analysis of variance. Similar to (151), it can be shown thatEQUATIONMoreover, the noise variance can be bounded byEQUATION)The mean squared error is then bounded byEQUATIONEQUATION)To minimize (194), let Justification: The main contribution (i.e. proposing a new Huber loss minimization approach which is more suitable to realistic cases, and providing theoretical analysis) has been made clear in the abstract and introduction.EQUATIONGuidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper.• The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.• The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.• It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 


Decision: This paper studies the classification and regression under label differential privacy (label DP) under the minimax framework. Here, we are given labeled samples $(X_1, Y_1), \\dots, (X_n, Y_n)$ drawn from some unknown distribution $D$ and the goal is to build a classification or regression model that minimizes the expected loss w.r.t. $D$. The samples $X_1, \\dots, X_n$ here are assumed to be public while the labels $Y_1, \\dots, Y_n$ are assumed to be private, i.e. the neighboring notion for label DP is changing a single label. The main contribution of the paper is to, under standard assumptions (e.g. that the underlying label probability is Holder continuous), give tight minimax bounds for classification and regression with label DP both under local DP and central DP. For central DP, there is almost no cost for label DP (compared to no privacy constraint) as long as $\\epsilon$ is not very small. Meanwhile, there is a cost of local label DP as long as $\\epsilon \ll 1$.

**Strengths:**
- This paper gives tight minimax bounds for classification and regression with label DP under standard assumptions.

**Weaknesses:**
- Although the bounds are nice, it is very hard to tell from the main body what the novel ideas are. More specifically, the "proof outlines" for the lower bounds essentially contain no information. Meanwhile, the upper bounds simply use binning together with standard DP algorithms, i.e. RAPPOR in equation (11), Exponential Mechanism in equation (17) and Laplace mechanism (for regressions).

- Although this paper seems to be the first to study classification / regression under Assumption 1, there were numerous previous works that derive theoretical (lower and upper) bounds for classification / regression under label DP before. For example, the paper [14] provides upper & lower bounds for label-DP convex optimization; a much earlier paper [A] also gave PAC-style bounds for learning. A more comprehensive discussion is required to distinguish the current work from previous works.

- The paper only deals with pure-DP and does not consider approximate-DP.

**Recommendation** The paper would benefit from a significant revision to highlight the novelty, and to provide comparisons to previous work. Due to this, we recommend rejection for the current version of the paper.

**References:**

[A] Kamalika Chaudhuri, Daniel J. Hsu: Sample Complexity Bounds for Differentially Private Learning. COLT 2011: 155-186

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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: questions: The paper discusses non-private baselines. Are there citations provided for these baselines?
limitations: limitations: See weaknesses and questions.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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?
limitations: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: questions: Do you have a sense of how the rates would change for approximate label DP?
limitations: limitations: Yes, the authors address the limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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$?
limitations: limitations: I do not see any potential negative societal impact of this work, as it is primarily theoretical.

Comments: title: Response to Rebuttal
Thanks for your reply
comment: Thank you very much for your response. We are glad that you maintain the score. Please let us know if you have any further questions or comments.
Thank you to the authors for addressing my concerns and committing to improving the presentation of the paper. My positive score was motivated by the technical contribution and the assumption that presentation issues would be addressed during the review process and so I will keep my score.
Thank you very much for raising the score! Although other reviewers also raise some detailed issues, from their comments, we think that they have understood most of the paper well. We will definitely revise the details of presentations according to these comments. Moreover, in the final version, an additional page is allowed, thus we can add more discussions about the intuitions.

Please let us know if you have any further concerns.
Thank you for your response. The other reviewers indeed provided valuable feedback, indicating a better understanding of the paper. I feel that my difficulty in understanding some aspects may partially stem from my unfamiliarity with the related work. In response, I’ve decided to raise my score and moderately lower my confidence level. However, I believe that the presentation issues should be addressed in the revision to improve readability.
Thanks for your response. As the final version allows one additional page, there will be enough space for us to provide more detailed and informative outlines for each theorem. Please kindly let us know if you have further questions or comments. We will add all the new results and discussions to the final paper. Thank you very much!
Thanks for the response. I am hopeful that the authors can incorporate the ideas presented in the rebuttal to improve the presentation. At this point, I agree with the sentiment of Reviewer kpNG - I do not oppose accepting the paper, though a round of reviews to help validate that the presentation has improved may be good. So I am keeping my score.
Thank you very much again for your feedback and for engaging in this discussion. If you have any remaining questions, please do let us know.
I would like to thank the author(s) for their response. The proposed changes sound good to me, and I will keep my rating.
Thanks for your prompt response. Our feeling is that in general, reviewers raise good comments, indicating that they understand our paper well. The issues in presentation do not affect the readability significantly. We will definitely fix these issues in our revision.
Thank you to the authors for the detailed response. After reviewing other comments, it appears that many reviewers share concerns about the presentation, which makes the paper difficult to read, especially for those unfamiliar with the existing literature. There are discussions in the paper whose correctness I am unable to verify or appreciate due to my unfamiliarity with the existing literature and the poor presentation. If the consensus is that these flaws do not overshadow the merits of the content, I would not oppose its acceptance. However, I also support the idea of rejecting this version to allow for further refinement and improvement in a future submission.