Credit Attribution and Stable Compression

Thank you so much for reading our paper, and for your comments.

With regards to the weaknesses you bring up:

1. The paper motivates the contributions using generative models but presents results only for PAC learnable classes. Showing how credit attribution could be applied to generative models would enhance the paper.

2. Even for classification problems, the paper does not provide examples of credit attribution on common tasks such as image and text classification. Some examples of applications of CCA would significantly improve the impact of this work.

Our definitions for credit attribution (CCA and DP sample compression schemes) apply verbatim to any mechanisms in general, including generative models producing text/images. As such, they merely formalize the requirement that a mechanism satisfy the principle of counterfactual attribution.

3. The paper could benefit from connecting its contributions to existing literature. Adding a section on related work and positioning the contributions within the broader literature would provide valuable context.

We have elaborated on the many connections of our work (along with ample references) to the existing literature on differential privacy, stable compression schemes, private learning with public data, as well as copyright management throughout the Introduction and Definitions sections (Sections 1 and 2). If there are concrete examples of references that we missed, please let us know and we will be glad to incorporate those in the final manuscript.

4. The intuition behind semi-differentially private learning is not very clear. An explanation using a concrete example would be helpful.

Semi-differentially private learning is applicable in settings where it is conceivable to have access to a corpus of public data, in addition to some sensitive, private data. For example, many public surveys collecting data of some sort routinely have an option for users to “opt-in” to voluntarily allow the organization to use their data in a non-confidential manner. Users who do not care too much about the privacy of their data could choose to opt-in, while others that are more worried about privacy could choose not to. We can also imagine settings where a large corpus of unlabeled, public data is freely available (e.g., unlabeled images available online), but obtaining labeled data is expensive and necessitates preserving privacy. In such cases, where we have access to public data on which privacy constraints can be relaxed, it is reasonable to ask if we can design mechanisms that have better performance guarantees compared to the setting requiring full privacy. And as it turns out, this is indeed true—while simple function classes like thresholds on the unit interval cannot be efficiently learned under complete differential privacy, this task becomes much more efficient under semi-differential privacy. Further background about semi-differential privacy is provided in the works [1,2,3].

[1] Amos Beimel, Kobbi Nissim, and Uri Stemmer. Private learning and sanitization: Pure vs. approximate differential privacy.

[2] Amos Beimel, Kobbi Nissim, and Uri Stemmer. Learning privately with labeled and unlabeled examples.

[3] Noga Alon, Raef Bassily, and Shay Moran. Limits of private learning with access to public data.

With regards to your questions:

1. How could this framework be extended to generative models, such as text and image generators?

Thanks for this question, we should indeed add a discussion on the challenges in establishing for which classes generative learning is possible within our setup. In DP, there is a known close relationship between classes that are PAC learnable and classes that one can produce private synthetic data. There are certain challenges in proving a similar connection between PAC learning and synthetic data generation in our framework, and we believe this is an important future work. But overall, the first key step in understanding which classes one can generate synthetic data for is understanding what is PAC learnable.

2. How can the quality of the credit attributions be evaluated? Is there a risk that a credit attribution mechanism could mistakenly assign credit to creators who are unrelated to the generated content (along with the actual creators on which the generated content was based)?

Mechanisms satisfying our definitions are technically allowed to cite superfluous and possibly unrelated works; however, this is similar in spirit to the “Precision vs Recall” tradeoff. In the context of credit attribution, our definitions focus primarily on the “Recall” aspect of the problem—namely, an algorithm should not miss out on citing any work if its output derives heavily from it, even if it cites some extraneous works. To us, this seems like the more pressing objective of the two, owing to legality concerns: the owner of the work that the algorithm failed to acknowledge could sue in court. On the other hand, while the “Precision” problem of citing needless other works does seem like an issue, it appears to have less drastic implications. It is an interesting direction to further add the precision constraint in our definitions.

Please let us know if we can answer any more questions!

Thank you very much for reviewing our manuscript. We appreciate your feedback and would like to clarify the scope and objectives of our paper to facilitate a more accurate assessment. The paper aims to explore and propose notions of credit attribution. It does not cover topics such as copyright analysis or the study of SGD.

We now address your concerns:

In the introduction, the authors discussed the applications of credit attribution, particularly in copyright analysis. However, in the rest of the paper, they did not mention any applications of the proposed credit attribution notion (Definition 1). In fact, I am quite curious about the connection between Definition 1 and copyright analysis (such as in Section 2 of "On Provable Copyright Protection for Generative Models").

Please notice that, while we see the problem of credit attribution as part of the larger problem of copyright, we explicitly state that the paper does not deal with the copyright question as a whole but only with a particular aspect. Therefore, providing any copyright analysis is not within the scope of this paper, and we ask that the paper be judged by its merits and not by objectives that the paper doesn’t presume to tackle.

To me, it is necessary to establish a solid mathematical connection between Definition 1 (or Definition 3) and existing widely used copyright notions to convince readers that the proposed notion is truly useful. If not, an empirical study of the proposed Definition 1 or 3 in real-world algorithms, such as how to achieve the proposed definition by modifying SGD (just like DP-SGD, which is a DP counterpart of SGD), is necessary.

We are also explicit that the notion of credit attribution that we consider is essentially orthogonal to previous work and existing copyright notions –-- while their focus is on the question of substantial similarity, we focus on algorithms that are allowed to be influenced by previous work (and may even be substantially similar), but must attribute credit. Summarily, these are two different tasks.

As to the analysis of SGD, in this paper we suggest a general framework for credit attribution, and as such, we intentionally do not focus on a specific algorithm or a specific use-case of the notion. While designing an SGD version for our algorithm may be an interesting future work, it is not within the scope of the current paper.

The authors claimed that Definition 1 extends the semi-DP notion in Definition 2. However, this extension is not clearly stated in the current version. Specifically, I was confused about how to convert a special case of Definition 1 to Definition 2 (which part is public in Definition 1). Moreover, why is Definition 2 a stronger notion than Definition 1, as claimed by the authors?

Thanks, we will add a detailed proof to how a semi-DP can be turned into a CCA mechansim in the final version. Roughly, every semi-DP mechanism $M$ with $k$ public datapoints defines a CCA mechanism $A$ as follows:

For a dataset $S$, the CCA mechanism $A$ outputs $(h, R)$, where $R$ is the first $k$ datapoints in $S$. The function $h = M(S_{\leq k}, S_{>k})$ is obtained by applying $M$ using the first $k$ examples in $S$ as public data and the remaining examples as private datapoints. Please let us know if further details are needed.

We hope that our response addresses your concerns. Please let us know if we can answer any more questions!

Thank you so much for reading our paper, and for your comments.

With regards to addressing the weaknesses/questions:

Examples that satisfy Definition 1 could be further discussed. Could the authors clarify examples of $(\varepsilon>0,\delta)$-counterfactual credit attributor (Definition 1) which are not ($\varepsilon=0,\delta=0$)-CAA?

Example 2.1 shows that any stable sample compression scheme satisfies Definition 1 with $\varepsilon=0, \delta=0$. In particular, Figure 1 shows that SVM satisfies $\varepsilon=0, \delta=0$. Furthermore, as we mention in the proof of Theorem 1, a slight variant of AdaBoost also satisfies this condition. This shows that even simple and well-known algorithms satisfy (a more restrictive version of) Definition 1.

In terms of algorithms satisfying Definition 1 with $\varepsilon > 0$: any DP algorithm satisfies this condition, with $R=\emptyset$. Any semi-DP algorithm satisfies this condition, with $R \neq \emptyset$, but chosen non-adaptively (i.e., $R$ does not depend on the input). It would be interesting to construct examples of mechanisms that choose $R \neq \emptyset$ adaptively, and also satisfy Definition 1 with $\varepsilon > 0$. Note that we leave open (line 153) the question of constructing a PAC learner satisfying Definition 1 with $|R|=k=O(1)$, and conceivably, the first thing to try here might be to consider both $\varepsilon > 0$ and $R$ chosen adaptively.

The conditional distribution in Definition 1 might make the definition challenging to verify. It would enhance the paper if the authors could provide case studies of $(\varepsilon, \delta)$-CAA applied to classical problems with varying parameters $\varepsilon,\delta$ controlling the privacy-utility tradeoff.

This is true, however this caveat is also true for DP and cryptographic security. It is not clear to us if there exists a verifiable definition in this context, but, like with DP, verifying Definition 1 will require an a priori proof by the algorithm designer.

Could the authors explain the difference or connection between Definition 3 and adaptive composition + post-processing in DP?

Recall that the reconstruction function in Definition 3 is a semi-DP mechanism, and post-processing a semi-DP mechanism is also semi-DP. But if we compose a mechanism satisfying Definition 3, since the reconstruction function is a function of the $k$ compressed examples, privacy is foregone for these examples. For the points that do not get compressed, privacy decays as in advanced composition in DP.

We hope our response addresses your concerns. Please let us know if we can answer any further questions!

Thank you so much for reading our paper, and for your comments. We are glad you liked our paper!

With regards to the points you bring up:

The notion of the privacy parameter $\varepsilon$ in standard DP has some interpretability in simple contexts like that of linear queries via lower bounds on the number of $\varepsilon$-private queries needed before reconstruction attacks become viable. The definition of credit attribution via DP necessitates some more thought into what a reasonable parameter choice looks like.

This is a good point. We did not think much about the problem of credit attribution in terms of an indistinguishability test that the algorithm should pass under private queries; however, semantically mapping intuitions and interpretations from the now well-established theory on differential privacy to the setting of credit attribution seems like an excellent avenue for future research.

I feel strongly that the label 'DP Sample Compression Scheme' needs to be changed. To recall, in this paper's terms a DP Sample Compression Scheme is a mechanism $M:\mathcal{Z}^n \to \mathcal{C}$ such that $\mathcal{M}(S)=\rho(S_{\kappa(S)},S_{\neg \kappa(S)})$ where $\kappa$ (the Compression function) is a $\varepsilon$-DP sampler from $S$, and $\rho$ (the Reconstruction function) is semi-DP (i.e. only DP with respect to its second component, the subset of points which were not sampled by $\kappa$). This is a good definition and makes sense, but I feel any label along the lines of DP <> where <> is a mechanism taking as input data sets suggests that it is in fact differentially private. This mechanism is clearly not DP (nor does it need to be for the purposes of this paper), because in particular any point sampled by $\kappa$ can be released in the clear (which is fine for the purposes of credit attribution). I understand that the subsampler is what is DP here, so maybe something along the lines of 'Sample Compression Scheme with DP compression or 'semi-DP sample compression scheme' might be a better descriptor, or whatever else the authors prefer. One of the reasons I feel this is important is that we rely all the time on the post-processing properties of DP algorithms, and it is not unlikely that someone who did not read this definition properly mistakes this for a DP subroutine and uses it incorrectly as a DP blackbox in a larger DP algorithm. Any such instance would be that person's fault, but if we can reduce its likelihood/any sources of confusion that would be a good thing.

This is a good point. We indeed mean that the compression function is DP but not further. We will consider the names Sample DP-Compression Scheme or Sample Compression Scheme with DP compression as suggested.

In the introduction you describe DP using swap DP but then later on use add-drop DP when defining credit attribution - perhaps you could just stick to add-drop DP throughout?

Thanks, we will make this change.

I think there might be an interesting link between user-level DP and appropriately attributing the works of an artist/data source, as opposed to any particular artwork/data point. I'm just curious if you have given this much thought, I might have missed it in the paper if so.

This is a great idea! If we understand your suggestion correctly, the principle of counterfactual attribution could also be stated at a per-user level, instead of a per-artwork level i.e., if in creating a work $W$, a mechanism does not cite/acknowledge any of the works $W_A$ by an author $A$, then the mechanism should be able to create $W$ as if it had not seen $W_A$ at all. This is a totally reasonable granularity to instantiate the definition, and constitutes an interesting formulation for future study.

Please let us know if we can help answer any more questions!