User-Level Differential Privacy With Few Examples Per User

Summary

This work designs a generic algorithm that transforms an item-level DP algorithm into a user-level DP one with $\sqrt{m}$ improvement in user complexity. It recovers previous user complexity bounds on various learning tasks, and the transformation works in the example sparse setting, i.e. does not require sufficient number of samples per user.

Strengths

1. Compared to Ghazi et.al. 2021 which requires sufficient number of samples per user, the generic transformation from item-level to user-level DP in this work applies to the example scarce setting. The authors derive new bounds in the example-scarce setting for PAC learning. 2. The authors recover the $\sqrt{m}$ factor in many known bounds for various learning tasks through a generic algorithm. 3. The writing is clear and easy to follow.

Weaknesses

1. The proposed algorithm is not computationally efficient. 2. Although $\sqrt{m}$ matches the tight bounds for a variety of problems, it seems that the lower bound is not addressed in this work. 3. In Theorem 16, it might be helpful to be specific about how sufficiently small should $\varepsilon', \delta'$ be. Minor issues: 1. In Lemma 4, I feel that it should be $A\simeq C$ instead of $B$ at the end of the line. 2. In line 242, it appears that the $\delta'$ inside the big O should be $\delta''$, and there should be a factor of $(1+e^{\varepsilon''})$ for the $\delta''$ term according to Lemma 4 (even though it does not affect the final bound on $\delta'$).

Questions

1. I wonder if it is possible show a $\Omega(\sqrt{m})$ lower bound as well under some non-trivial conditions? 2. In Theorem 16, how sufficiently small are $\varepsilon', \delta'$? Is it for some fixed small constant, or some expression that depends on other parameters?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

4 excellent

Limitations

Limitations and potential impacts are adequately addressed.

Summary

This paper studies the problem of user-level differential privacy, giving a generic conversion for any item-level approx DP algorithm to a user-level approx DP algorithm, and a clipped scoring function that allows application of the exponential mechanism to obtain user-level privacy. All results are applicable in the few-samples-per-user setting, significantly extending results beyond the case in which users have enough samples to solve a task independently.

Strengths

This work significantly improves our understanding of when user-level privacy is achievable, though it is unfortunate the transformation from item-level to user-level privacy isn't computationally efficient. The intermediate result that approx DP => sample perfect generalization is also a meaningful contribution to our understanding of the relationships between useful algorithmic stability notions.

Weaknesses

In terms of substance, I think this work is very strong, but the clarity of presentation could maybe be improved a little. That said, I do think the authors did a good job overall of assisting the reader with interpretation of their results. Notes: The first paragraph of the technical overview for the approximate DP result was a bit confusing. Page 4: “it is sufficient get new user-level pure-DP” Page 6: “For example, g is not Lipschitz everywhere anyway anymore”

Questions

There's a related result from BGHILPSS23 showing that approx DP implies perfect generalization, following from the connections approx DP => one-way perfect generalization, one-way perfect generalization => replicability, replicability => perfect generalization. However, my understanding is that their result is weaker than the one given in this work because it 1) requires correlated sampling and is therefore not necessarily computationally efficient and 2) the transformation from replicability to perfect generalization changes the output distribution of the DP algorithm, whereas the result in this work proves perfect generalization for the same approx DP algorithm A. Is this a correct comparison of these results, or is there any notable distinction between the resulting PG parameters obtained from both results? It would be very interesting to understand whether the computational inefficiency is in fact necessary.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

4 excellent

Limitations

Yes, the authors adequately address societal impact of their work.

Summary

This paper establishes new generic conversions from item-level DP algorithms to user-level DP algorithms, continuing a line of work initiated by Ghazi, Kumar, and Manurangsi. Previous state-of-the-art due to BGHILPSS '23 shows that any item-level $(\varepsilon, \delta)$-DP algorithm using N samples can be converted to a user-level DP algorithm with $n = O(\log(1/\delta)/\varepsilon$ users and $m \approx N^2$ samples per user. The present submission observes that this previous result is just one end of a spectrum of possible item-to-user-level conversions, and generalizes it to hold for the full range of $1 \le m \le N^2$. That is, the main result (somewhat simplifying) shows a conversion from any item-level DP algorithm to a user-level DP algorithm with $n \approx (N/\sqrt{m}) \cdot \log^{O(1)} ({1/\delta})/\varepsilon^2$ users and $m$ samples per user. In addition to generalizing the conversions of GKM'21 and BGHILPSS'23 to the regime of few examples per user, this result unifies previous work on specific problems such as mean estimation, stcochastic convex optimization, and discrete distribution learning for which a $n \propto 1/\sqrt{m}$ dependence was previously observed. As an auxiliary result, the paper also gives a tight characterization of the sample complexity of user-level pure $(\varepsilon, 0)$-differentially private PAC learning in terms of the probabilistic representation dimension.

Strengths

- This is a nice contribution to the emerging general theory around user-level DP learning, in particular, building a bridge between one thread of work on general item-level vs. user-level connections and another on understanding the sample complexity of user-level DP for specific problems. - As part of their analysis, the authors more carefully investigate the connection between DP and perfect generalization, in particular giving a clean solution to an old open question of CNLRW'16 that is likely to have further applications.

Weaknesses

- The main technical ideas going into the algorithms and their analysis appeared in prior work on this topic. (E.g., the passage from DP to perfect generalization appears in GKM'21/BGHILPSS'23, and a similar PTR-based argument appeared in KL'21/GKKMMZ'23). This paper's technical contribution is to carefully refine each of these steps and piece them together in the right way. - Neither of the paper's new algorithms is computationally efficient in general, even if the task admits a computationally efficient item-level DP learner. Note that this is the case for previous general item-to-user-level conversions as well. - The final main result (Theorem 9) is somewhat messy to state and potentially suboptimal in its dependence on $\log(1/\delta)$ and $\varepsilon$. This is likely in part due to stacking various generic tools (DP => PG, amplification by subsampling, PTR) that could potentially be avoided with a simpler algorithm.

Questions

- The prior work of BBGHLISS'23 also claims to have resolved the open question of CLNRW'16 on DP vs. perfect generalization, but I believe they did so in a weaker sense. Namely, they only showed that every DP algorithm admits a PG algorithm solving the same problem; whereas this submission shows that the original DP algorithm itself perfectly generalizes. This is an important distinction that I think is worth highlighting. - I wasn't really able to match the informal description of the proof of Lemma 13 (lines 214-226) to the formal proof in appendix B. In particular, the new contribution of the formal proof seems to be to apply a nice symmetrization argument to the previous results of RRST'16/BGHILPSS'23 that held for a one-sided version of the DP -> PG connection. Does the informal argument in the main body of the text reflect what's going on under the hood of these prior results? And if so, does it suggest a simpler / more direct argument that doesn't go through max-information etc.? - I'd suggest renaming "local deletion DP" (Definition 15) to something else due to the (unfortunate) naming collision that may suggest this definition has to do with local DP. Maybe something like "pointwise deletion DP"?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

Limitations (overlapping with points identified as weaknesses) are nicely described as directions for future work in the conclusion.

Summary

This work develops novel generic algorithms that convert algorithms under item-level differential privacy (DP) to user-level DP in the low user sample regime, where each user holds a small number of samples, and obtains new results for user sample complexity (aka., min # users to achieve a certain utility of the algorithm). Based on a novel observation that connects sample perfect generalization to local deletion DP, the proposed algorithm under approximate-DP leads to tight user sample complexity bound for several privacy-preserving machine learning applications. The proposed algorithm under pure-DP is based on the exponential mechanism with a new score function and it also leads to tight and improved user sample complexity bounds for several applications.

Strengths

The improved user sample complexity results and proposed algorithms under both approximate DP and pure DP are interesting and are widely applicable to several important privacy preserving machine learning tasks. The paper is well presented and intriguing to read. The notations are well-defined throughout the paper. Problems and results are well defined and clearly stated. The contribution and overview of techniques are well summarized. The paper tries hard to give the readers intuition on the techniques developed and does a good job explaining the observations. The paper also explains well its difference from the previous works, especially why the techniques from previous works do not apply when the number of samples per user is low.

Weaknesses

The only places that might need a bit more explanation is why local deletion DP is natural to consider based on sample perfect generalization results, and how local deletion DP is then converted to user level DP?

Questions

This might be a stupid question. How is the randomness of the private algorithms considered in this work? Do we assume that a random seed is given? Is line 9 in Algorithm 1 for removing the polylog dependence on $n$ users in the proof? What are the major differences between pure DP and approximate DP in changing from item-level DP to user-level DP? What are the challenges that make the techniques to convert from item-level DP to user-level DP for approximate DP not applicable to pure DP? In which applications/problems is the user sample complexity bound from this work not tight? Minor issues: $x_{1, n}$ in line 31 $\Rightarrow$ $x_{1, m}$. $\mathbf{x}_{T}$ in line 265 $\Rightarrow$ $\mathbf{x}_{-T}$. Might be clearer to add “for some chosen constant $\kappa$” to the end of line 272.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

Limitations (esp. the runtime of the proposed algorithm) are well discussed in the paper.