It's My Data Too: Private ML for Datasets with Multi-User Training Examples

Thanks for your support of the paper, and for the editing suggestions which we plan to incorporate. Here we respond to some of the reviewer’s questions. As space permits, we will plan to include more detailed explanations along these lines in the revision:

• “X_i cannot be repeated in e_i”: We believe this question is asking whether two different edges can have examples with the same content. Our definition does not restrict the values of different x_i, even in relation to each other. This is in line with other DP definitions such as example-level DP or user-level DP in the single attribution model, which do not make any assumptions on the contents of examples in relation to each other.
• “Doesn’t some e_i change when changing x_i”: Here we are decoupling the edge (i.e. users associated with an example) and the content of the example. e.g. For edge-data adjacent datasets D, D’, in D Alice might send Bob the email “how was your surgery?” and in D’ Alice might send the email “are you free for lunch tomorrow?”. In both cases e_i = {Alice, Bob}, but the content x_i has changed (and for edge-data adjacency, the rest of the graph is unchanged).
• “duplicates allows for a larger dataset which reduces DP noise…”: We apologize for not elaborating further in the paper. As a simple example, suppose our users are {A, B, C, D} and our examples are associated with hyperedges {{A}, {A, B}, {A, C}, {B, C}, {A, D}}. If we use k = 3, without duplicates we can get a dataset of size at most 4, since we have to discard one of the examples including A. However, with duplicates we can use the dataset, e.g. {{A}, {A, B}, {A, D}, {B, C}, {B, C}} which includes 5 examples and still satisfies the bound k = 3. That is, we can use duplication (equivalently, upweighting of some examples) to even out users’ contributions and make full use of each user’s allocation.
• “more users will have <k examples than for the regular graph and then the dataset will be smaller.”: For simplicity let’s focus on 2-uniform graphs, i.e. the usual graphs where every edge has two users. Consider the 2-regular graph {{A, B}, {B, C}, {C, D}, {D, E}, {E, F}}. For contribution bound k = 2, by including all edges, every user saturates their contribution bound and we get 6 edges. In contrast, consider the graph {{A, B}, {B, C}, {C, A}, {A, D}, {B, E}, {C, F}}. The number of users/edges is the same, and the average degree is still 2, but half the users have degree 1 and half have degree 3. So under a contribution bound of 2, the best we can do is to include 4 edges (e.g. {{A, B}, {A, D}, {B, E}, {C, F}}. In short, some of the users don’t have enough edges to saturate their contribution bound, and others have too many edges and must discard some, so we can include fewer edges than if the graph were perfectly regular.

Thanks to the reviewer for their support of the paper. We want to respond to the two gaps raised by the reviewer.

• Gap 1: We agree that the graph structure can be a privacy risk. We do not advocate that every algorithm that achieves fixed-graph-DP is appropriate for ML settings, and do not advocate for actually publishing the graph in practice. While we do not formally protect the graph structure in a DP manner, as discussed at the end of Section 2, the structure of our algorithms (which discard the graph information during training) means they resist straightforward attacks (with non-pathological data). Part of our goal with this work is to invite future research on this problem, including designing attacks on our two-phase algorithms in practical settings.
• Gap 2: We agree such a comparison could be useful. However, to the best of our knowledge, the only setting where batch gradient queries with node DP would be readily applicable and feasible at scale is when the hypergraph is already bounded-degree, in which case contribution bounding is a no-op and fixed-graph DP/the comparison are unnecessary. While reductions (by truncating some nodes) to bounded degree graphs are known, these reductions are only understood for “2-uniform” graphs (that is, the usual graphs, where edges involve only two nodes, as opposed to hypergraphs, which are the focus of our work).

Thanks for your support of the paper. We respond to a few points below:

• "The greedy algorithms are somewhat simple.”: We agree the algorithms are simple, and we have framed them as baselines to emphasize this. We note that our empirical results, which demonstrate the baseline algorithms are quite competitive, suggest developing much more complicated algorithms may be unnecessary in practice (but may still be an interesting research direction). We also agree that part of the goal of this paper is to encourage more work on the multi-attribution setting.
• “epsilon larger than 10 does not make too much sense. It is nearly non-private.”: We agree that in practice epsilons larger than 10 may not give meaningful privacy guarantees. Our goal with studying large epsilons was mainly to extend our empirical understanding to low-noise regimes. We also note that e.g. an epsilon of 64 in one setting can correspond to a much smaller epsilon in a different setting with the same noise multiplier and batch size but e.g. a different dataset size or graph structure, so studying these low-noise regimes may provide useful insights even if one does not believe that the corresponding epsilon is meaningful in practice.
• “Potentially harming algorithmic fairness”: This is an interesting point. Note that contribution bounding also makes the contributions of different users more uniform, so even without differential privacy one might expect contribution bounding to actually increase fairness in this dimension. One could summarize the impact on fairness as, contribution bounding favors examples with fewer users and users with fewer examples. We expect that whether this leads to an overall positive or negative impact on fairness will be highly subjective and context-dependent, depending on what properties of the dataset these quantities (examples per user and users per example) align with.

Thanks to the reviewer for their feedback. We agree that broadly, there is much more work to be done to fully understand the multi-attribution model, and part of our goal with this work is to motivate future research into this setting. Below we respond to individual points we disagree with in the review:

• W1:
  • “no claim is made about any suboptimality bounds”: As mentioned in Appendix B.2, theoretically the problem is known to be hard to approximate to within large factors, even in some very simple settings. So while one could attempt to prove positive theoretical results, these would be overly pessimistic and not give meaningful guidance in practice.
  • Q1/“add baselines”: We use the checkpoint available here as our initialization, which achieves a test loss of 4.955 for arXiv, i.e. is not competitive with DP fine-tuning even at small epsilons. We will state this as a reference point for the empirical results in the revision. Since we introduce fixed-graph DP (and as we discuss in our response to reviewer gGTR, the node-graph DP algorithms are not readily applicable except in trivial settings), besides the not-fine-tuned checkpoint and some other baselines we already included in the paper, we do not feel there are obvious and meaningful baselines to compare our greedy baseline to. However, we are open to suggestions from the reviewer for other baselines to consider adding in the revision.
• W2:
  • We are glad the reviewer raised the question of appropriate DP formulations; in fact, one of the main goals for our paper is to provide a better framework for such discussions. Node-DP is not well known in the ML community currently, and hopefully our paper will provide a clear critique to simply applying example-level or user-level DP to settings where examples contain information from multiple users.
  • At the same time, we also agree that the fixed-graph DP is not as strong as one ideally would want. We spent considerable time looking for ways to scale node-DP, and nevertheless this approach seems very far from being feasible for large-scale ML applications. Given the explosion of GenAI, there is a pressing need for practical approaches in this space that can be offered now.
  • We do not advocate that every algorithm that achieves fixed-graph-DP is appropriate for ML settings. Our algorithm carefully decouples the use of the graph from the use of the training data. This decoupling excludes the most obvious problematic algorithms (i.e., ones that publish the graph). In fact, despite considerable effort, we were unable to design any realistic attack to exploit our algorithms. At the same time, we also lack a fully satisfactory guarantee. (For example, one can prove statements assuming independence of the training data from the graph structure; but such independence does not hold in practice and we find it unsatisfactory.)
  • Hence, we propose an approach here that is practical and provides significantly better privacy than the naive application of existing DP ML solutions. Equally importantly, we hope our work highlights the problem, and stimulates future research. We do not advocate for our approach as a complete solution, but feel it is a valuable starting point that already highlights nontrivial choices and phenomena.
• W3:
  • On lacking novelty: While our greedy algorithms are not very complicated, we believe the fixed-graph DP definition and the contribution bounding framework are meaningful contributions, and we believe our empirical results developing a better understanding of the greedy baseline raise and study non-trivial questions about contribution bounding.
  • On tailoring to multi-attribution: While the greedy algorithm retrieves the trivial strategy maximizing |S| in the single-attribution case, most of our empirical results answer questions which do not make sense to ask in the single-attribution case (e.g. in the single-attribution case, there is no difference from the ILP, no bias towards examples with fewer users). Furthermore, designing a more complicated method tailored to the multi-attribution case is unnecessary if the greedy algorithm is competitive with strong baselines like the ILP solver, which our empirical results provide evidence for.