Credit Attribution and Stable Compression

Authors: roi  livni
shay  moran
kobbi  nissim
chirag  pabbaraju
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 20:14:32

Abstract: Credit attribution is crucial across various fields. In academic research, proper citation acknowledges prior work and establishes original contributions. Similarly, in generative models, such as those trained on existing artworks or music, it is important to ensure that any generated content influenced by these works appropriately credits the original creators.

We study credit attribution by machine learning algorithms. We propose new definitions--relaxations of Differential Privacy--that weaken the stability guarantees for a designated subset of $k$ datapoints. These $k$ datapoints can be used non-stably with permission from their owners, potentially in exchange for compensation. Meanwhile, the remaining datapoints are guaranteed to have no significant influence on the algorithm's output.

Our framework extends well-studied notions of stability, including Differential Privacy ($k = 0$), differentially private learning with public data (where the $k$ public datapoints are fixed in advance),
and stable sample compression (where the $k$ datapoints are selected adaptively by the algorithm).
We examine the expressive power of these stability notions within the PAC learning framework, provide a comprehensive characterization of learnability for algorithms adhering to these principles, and propose directions and questions for future research.

Main paper: 
 introduction: 
 Many tasks that use machine learning algorithms require proper credit attribution. For example, consider a model trained on scientific papers that needs to reason about facts and figures based on existing literature. Most academic literature is protected under copyright licenses such as CC-BY 4.0 which allows adapting, remixing, transforming, and to copy and redistribute in any medium or format, as long as attribution is given to the creator. In another setting, a learner generating content, such as images or music, may benefit from creating derivative works from copyrighted materials without violating the creator's rights (either through proper attribution or monetary compensation, depending on the context and licensing).The increasing use of ML algorithms and the need for greater transparency is reflected by the recently implemented EU AI Act, which mandates the disclosure of training data [14] . However, disclosure of training data and proper attribution are not necessarily equivalent. In particular, mere transparency of the dataset does not reveal whether certain elements of certain content have been derived, nor does it provide proper attribution when particular content is heavily built upon. Therefore, there is a need to develop more nuanced notions and definitions that enable learning under the constraint that works are properly attributed. This paper focuses on this challenge, exploring theoretical models of credit attribution to provide rigorous and meaningful definitions for the task.Credit attribution is part of a much larger problem of learning under copyright constraints. Copyright issues in machine learning models are becoming increasingly prominent as these models are trained on vast amounts of data, often some of which is copyrighted. Consequently, the resulting models might contain content from copyrighted data in their training sets. Previous work suggests it may be mathematically challenging to capture algorithms that protect copyright. Specifically, attempts to regulate copyright often focus on protecting against substantial similarity between output content and training data by, for example, employing stable algorithms that are not sensitive to individual training points [9, 22, 24] . This is an important aspect of copyright; however, substantial similarity is only one piece of the puzzle.Another piece of the puzzle involves the use of original elements from copyrighted works in a legally permissible manner, such as through de minimis quotations, transformative use, and other types of fair uses, such as learning and research [13] . To fully utilize ML in many practical scenarios, it is desirable for learning models to be allowed to use original elements in a similar manner.To address this second piece, we focus on designing algorithms that, while allowed to use and be influenced by copyrighted material, must provide proper attribution. Such models would enable users to inspect these influences and verify that they conform to legal standards, or take necessary measures (such as monetary compensation or requesting permission). Despite credit attribution being narrower in scope than copyright protection in general, even this concept may be nuanced to be captured mathematically. Therefore, we focus on formalizing a specific (but arguably basic) aspect of itcounterfactual attribution:This principle asserts that any previous work that influenced the result should be credited. Counterfactually, if the creator of a work 𝑊 does not acknowledge another work 𝑊 ′ , they should be able to produce 𝑊 as if they had no knowledge of 𝑊 ′ .For example, an argument based on this principle in the extreme case when 𝑊 = 𝑊 ′ is found in a U.S. Supreme Court opinion: ". . . a work may be original even though it closely resembles other works, so long as the similarity is fortuitous, not the result of copying. To illustrate, assume that two poets, each ignorant of the other, compose identical poems. Neither work is novel, yet both are original. . . " -Feist Publications, Inc. v. Rural Telephone Service Company, Inc. 499 U.S. 340 (1991)  
definitions and examples: 
 In this section, we introduce the two main definitions we study.We first recall some standard notation from learning theory and differential privacy. Let Z be an input data domain and C denote an output space. We denote by Z ★ the set of all finite sequences with elements from Z. Two sequences 𝑆 ′ , 𝑆 ′′ ∈ X ★ are called neighbors if they have the same length |𝑆 ′ | = |𝑆 ′′ | and there is a unique index 𝑖 such that 𝑆 ′ 𝑖 ≠ 𝑆 ′′ 𝑖 . Let ε, δ > 0 and let 𝑝, 𝑞 be probability distributions defined over the same space. We let 𝑝 ≈ ε,δ 𝑞 denote the following relation: 𝑝(𝐸) ≤ exp(ε) • 𝑞(𝐸) + δ and 𝑞(𝐸) ≤ exp(ε) • 𝑝(𝐸) + δ for every event 𝐸.Algorithms with Credit Attribution. Consider a mechanism 𝑀 : Z ★ → C × Z ★ that, for every possible input sequence 𝑆 = (𝑧 1 , . . . , 𝑧 𝑛 ), outputs a pair (𝑐, 𝑅), where 𝑐 ∈ C and 𝑅 ∈ Z ★ . Intuitively, 𝑅 is the list of inputs being credited by the mechanism, and 𝑐 is the model/content produced by the mechanism. Thus, we require that each data point 𝑧 𝑖 ∈ 𝑅 is also an input data point 𝑧 𝑖 ∈ 𝑆. For such a mechanism 𝑀 and an input sequence 𝑆, we let 𝑀 (𝑆) denote the probability distribution over outputs of 𝑀 given 𝑆 as input, where the probability is induced by the internal randomness of the mechanism. For example, if 𝑀 is deterministic, then 𝑀 (𝑆) is a Dirac distribution (i.e., it assigns probability 1 to the deterministic output of 𝑀 on 𝑆).The definition below uses the following notation: for a sequence 𝑆 = (𝑧 1 , . . . , 𝑧 𝑛 ) and an index 𝑖 ∈ [𝑛], we let 𝑆 -𝑖 denote the subsequence of 𝑆 obtained by omitting 𝑧 𝑖 . Let 𝑧 𝑖 ∈ 𝑆 be a data point such that Pr (𝑐,𝑅)∼𝑀 (𝑆) [𝑧 𝑖 ∈ 𝑅] < 1. That is, there is a positive probability that 𝑧 𝑖 is not credited Example: Support Vector Machine Figure 1 : Support Vector Machine (SVM) as an (ε = δ = 0)-counterfactual credit attributor: The SVM algorithm identifies a maximum-margin separating hyperplane, which is defined by the subsample of the support vectors. Any input point which is not a support vector does not influence the output: even if it is removed from the input sample, the output hyperplane does not change.by 𝑀 when executed on 𝑆. In this case, we let 𝑀 (𝑆 -𝑖 ) denote the distribution of 𝑀 (𝑆) conditioned on the event that 𝑧 𝑖 ∉ 𝑅. We are now ready to present our first definition5 of counterfactual credit attribution. ). Let ε, δ > 0. A mechanism 𝑀 : Z ★ → C × Z ★ is called an (ε, δ)-counterfactual∈ 𝑅] = 1, or 𝑀 (𝑆 -𝑖 ) ≈ ε,δ 𝑀 (𝑆 -𝑖 ), where 𝑀 (𝑆 -𝑖 ) is the output distribution on the dataset 𝑆 -𝑖 = 𝑆 \ {𝑧 𝑖 }, and 𝑀 (𝑆 -𝑖 ) is the output distribution on the dataset 𝑆, conditioned on 𝑧 𝑖 ∉ 𝑅.To emphasize, in Definition 1 the conditional output distribution 𝑀 (𝑆 -𝑖 ) models the condition "if data-point 𝑧 𝑖 is not credited by 𝑀," whereas the output distribution 𝑀 (𝑆 -𝑖 ) represents the counterfactual scenario "had the data-point 𝑧 𝑖 not been seen by 𝑀." [8, 20] ). A mechanism 𝐴 : Z ★ → C is a stable sample compression scheme of size 𝑘 if for every input sequence 𝑆 = (𝑧 1 , . . . , 𝑧 𝑛 ) there is a subsequence κ(𝑆) ⊆ 𝑆 of size |κ(𝑆)| ≤ 𝑘 such that 𝐴(𝑆) = 𝐴(𝑇) for every intermediate subsequence κ(𝑆) ⊆ 𝑇 ⊆ 𝑆. See Figure 1 for an example. Each stable compression scheme corresponds to an (ε = 0, δ = 0)-CCA which credits the datapoints in κ(𝑆). That is, 𝑀 (𝑆) = ( 𝐴(𝑆), κ(𝑆)). Stable sample compression thus provides something stronger: group-counterfactuality, meaning any subset of datapoints that is not selected does not influence the output. Definition 1 not only relaxes stable sample compression, but also extends the concept of differential privacy with public data, known as semi-private learning. In semi-private learning, the learner's input includes public examples (which can be processed non-stably) and private examples (for which the algorithm must satisfy differential privacy guarantees). Semi-private learning [1, 4] has been extensively studied in recent years [19] , for example, in the context of query release [3, 18] , distribution learning [5, 6] , computational efficiency [7, 21] , as well as in other contexts.Definition 2 (Semi-Differentially Private Mechanism). Let ε, δ > 0; an (ε, δ)-semi differentially private (semi-DP) mechanism is a mapping 𝑀 : Z ★ × Z ★ → C such that for every 𝑆 pub ∈ Z ★ and every pair of neighboring sequences , 𝑆 ′ priv , 𝑆 ′′ priv :6𝑀 (𝑆 pub , 𝑆 ′ priv ) ≈ ε,δ 𝑀 (𝑆 pub , 𝑆 ′′ priv ).5In analogy to the variant of differential privacy where the unit of protection is the addition or removal of a data point, our definition uses omissions of data points. This aligns with our motivation for counterfactual credit attribution: if a non-credited data point is omitted (rather than replaced), the output does not change. Omission is crucial here, as replacing a non-credited data point with a credited one could drastically alter the output.6Note that the special case of 𝑆 pub = ∅ gives a DP mechanism. Then, for every input sequence 𝑆:𝑀 (𝑆) = ρ(𝑆| κ(𝑆 ) , 𝑆| ¬κ(𝑆) ),where 𝑆| κ(𝑆 ) = (𝑆 𝑖 ) 𝑖 ∈κ(𝑆) and 𝑆| ¬κ(𝑆) = (𝑆 𝑖 ) 𝑖∉κ(𝑆) .Note that the compression function κ selects the indices of the compressed subsample (rather than the subsample itself, as in classical sample compression). This technical difference allows us to pose the requirement of differential privacy on the compression function κ. Going back to the analogy with active learning, Definition 2 also imposes stability of the labeling function (i.e. the function that decides which labels to query). Example 2.2 (Randomized Response). We next describe a simple task which can be performed by sample DP-compression schemes, but not by semi-DP mechanisms. Imagine that the data is drawn from a distribution where each datapoint is useful with probability 0.1 and is otherwise garbage with probability 0.9. The goal is to select 𝑘 datapoints while maximizing the number of useful datapoints that are selected. If we select datapoints obliviously, for example by simply taking the first 𝑘 examples, we would expect that only about 10% of them will be useful. However, by using a mechanism compliant with Definition 3, we can increase the proportion of useful examples.This mechanism is based on randomized response and operates as follows: each example is independently assigned a random label in {0, 1}, where a useful example is assigned a label of 1 with probability 𝑝 > 1/2, and each garbage example is assigned a label of 1 with probability 1 -𝑝 < 1/2. The value of 𝑝 is set as a function of the privacy parameter ε.7 Then, the compression function κ selects the first 𝑘 indices whose label is 1. This way, the fraction of useful points among the points labeled 1 is ≈ 0.1 𝑝 0.1 𝑝+0.9(1-𝑝) = 1 9/ 𝑝-8 > 0.1 (the last inequality holds for 𝑝 > 1/2). See Appendix B for a more detailed argument.Theorem 2 implies a stark dichotomy: either a class C can be learned by a DP algorithm (equivalently, a sample DP-compression of size 𝑘 = 0), or it is impossible to learn it unless 𝑘 = Ω(1/α). Notice that with 𝑘 = 𝑂 (𝑑/α), public examples are sufficient to learn without any private examples. Theorem 2 generalizes a result by [1, Theorem 4.2] who proved it in the special case of semi-DP learning. In our setting though, we need to crucially handle scenarios where the credited (or rather, public) datapoints are chosen adaptively as a function of the full dataset. This is not the case in semi-DP learning, and requires us to use novel technical tools (like Theorem 3 ahead).Thus, in the PAC setting, sample DP-compression schemes do not offer any advantage over semi-DP learners. However, Example 2.2 demonstrates that using sample DP-compression, it is possible to select the 𝑘 points in the compression set so that the frequency of 'useful' examples among these 𝑘 points is boosted.Our next theorem addresses the limits of handpicking 𝑘 points by sample DP-compression. We formalize this task as follows: given a distribution 𝐷 over Z and an event 𝐸 of 'good' points, the goal is to design a DP-compression function κ : Z 𝑛 → [𝑛] 𝑘 that maximizes the number of selected data points that belong to 𝐸. That is, the goal is to maximize∑︁ 𝑖 ∈κ(𝑆) 1[𝑧 𝑖 ∈ 𝐸].Example 2.2 illustrates a method that selects roughly exp(ε) • 𝑘 • 𝐷 (𝐸) points from 𝐸 by an (ε ≥ 0, δ = 0)-compression function. This is a factor of exp(ε) better than obliviously selecting the 𝑘 points, which yields 𝑘 • 𝐷 (𝐸) points from 𝐸. Is this factor of exp(ε) optimal? Can one do better, possibly by increasing δ? The following result shows that exp(ε) is asymptotically optimal. Theorem 3. Let 𝑀 be an (ε, δ) sample DP-compression scheme, let D be a distribution over Z, and let 𝐸 ⊆ Z be any event, with 𝑝 = D(𝐸). For an input sample 𝑆 = (𝑧 1 , . . . , 𝑧 𝑛 ) ∼ D 𝑛 , define 𝑍 = 𝑍 (𝑆) as the random variable denoting the fraction of selected indices in κ(𝑆) whose corresponding data points belong to 𝐸. That is, 𝑍 =EQUATION)Indeed, since by convention δ = δ(𝑛) ≪ 1/𝑛, the above theorem implies that exp(ε) is asymptotically optimal. We note that Theorem 3 is also key in the proof of Theorem 2. We elaborate on this in Section 4.2.Generalization. Definition 1 and Definition 3 can also be examined from a learning theoretic perspective as notions of algorithmic stability. Algorithmic stability is particularly useful in the context of generalization because, roughly speaking, stable algorithms typically generalize well. We note in passing that this is indeed the case for Definition 1 and Definition 3: any learning rule adhering to either definition satisfies that its empirical error and population error are typically close.One natural way to prove this is by following the argument that shows sample compression schemes generalize. In a nutshell, the argument proceeds as follows: first, if we fix the selected 𝑘-tuple, the obtained hypothesis generalizes well. Then, we apply a union bound over all possible 𝑛 𝑘 choices of 𝑘-tuples from the input sample.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: We are upfront about the nuances involved in credit attribution and copyright protection (e.g., in the introduction as well as conclusion), in the sense that a single definition is likely not going to be all-purpose. We are also candid about our assumptions throughout the paper, and identify various open directions and loose ends.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. 
main theorems: 
 In this section, we present our main theorems that characterize the expressivity of learning rules satisfying our proposed definitions. We focus on the PAC (Probably Approximately Correct) learning model [23] and employ its standard definitions (explicitly provided in Section 4). Question (Guiding Question). Is learnability subject to counterfactual credit attribution (Definition 1) more restricted than unconstrained learnability? Is learnability subject to sample DPcompression (Definition 3) more restricted than unconstrained learnability? How do these restrictions compare to differentially private learning? Note that with respect to both Definition 1 and Definition 3, it is clear that if 𝑘, the number of credited points, is sufficiently large, then it is possible to learn any PAC-learnable class C. Indeed, if 𝑘 equals the PAC sample complexity of C, then an oblivious selection, such as the first 𝑘 points, will suffice. Therefore, the above question is particularly interesting for values of 𝑘 that are significantly smaller than the PAC sample complexity of C.Our first theorem demonstrates that every PAC-learnable class can be learned using an (ε = 0, δ = 0)counterfactual credit attribution learning rule, which selects at most a logarithmic number of sample points for attribution. Remarkably, this can be achieved using the AdaBoost algorithm. We leave as an open question whether 𝑘 can be made independent of 𝑛, possibly by allowing ε and δ to be positive. Note that an affirmative answer to this question might also shed light on the sample compression conjecture [17, 25] .Our second theorem establishes a limitation for sample DP-compression schemes, showing that they do not offer more expressivity than differentially private PAC learning [15] .1. C is learnable by a DP-learner. 
technical background and proofs: 
 We study our main definitions in the context of PAC learning. Concretely, we assume that the input data domain Z in Section 2 is X × Y, for an input space X and label space Y. For our purposes, Y = {0, 1}. Learning rules are mechanisms A : Remark 2. Note that if 𝑘 = 0 above, we recover the standard definition of an (α, β, ε, δ)-DP PAC learner (where α is the error, β is the failure probability, and ε, δ are the privacy parameters) [15] .Z * → C × Z * ,Our CCA learning rule crucially uses the notion of a randomized stable sample compression scheme, which is a generalization of stable sample compression schemes (Example 2.1) and was developed in a recent work by [12] . We use the notation 𝑆 ′ ⊑ 𝑆 for sequences 𝑆, 𝑆 ′ ∈ (X × Y) * that satisfy: (∀(𝑥, 𝑦)) : (𝑥, 𝑦) ∈ 𝑆 ′ =⇒ (𝑥, 𝑦) ∈ 𝑆.• For any 𝑆 ∈ (X × Y) * realizable by H, if κ(𝑆) = 𝑆 ′ , then 𝑆 ′ ⊑ 𝑆.• For any 𝑆 ∈ (X × Y) * realizable by H,EQUATION)A randomized sample compression scheme (D κ , ρ) for H is stable if for any 𝑆 ∈ (X × Y) * realizable by H and 𝑆 ′ ⊑ 𝑆, the distribution of κ(𝑆 ′ ) is the same as the distribution of κ(𝑆) conditioned on κ(𝑆) ⊑ 𝑆 ′ . The size 𝑠(𝑛) of the compression scheme is the supremum over 𝑆 ∈ (X × Y) 𝑛 (realizable by H) and κ in the supportt of D κ of the number of distinct elements in κ(𝑆). [12] show that stable randomized compression schemes imply generalization. 𝑅 D (ρ(κ(𝑆))) ≤ 𝑂 𝑠(𝑛) + log(1/β) 𝑛 .Furthermore, they also show that there exists a stable randomized compression scheme for any hypothesis class H having finite VC dimension 𝑑. This compression scheme is based on a simple variant of AdaBoost (Algorithm 1 in [12] ). The following is contained in their work:9Lemma 4.2 ([12] ). For any hypothesis class H with VC dimension 𝑑, there exists a stable randomized sample compression scheme (based on AdaBoost) having failure probability ξ of sizeEQUATIONWe are now equipped with the necessary tools required to prove Theorem 1.Proof of Theorem 1. Let D be any distribution realizable by H, and let 𝑆 be a sample of size 𝑛 drawn from D 𝑛 . Given β, fix ξ = β/3. From Lemma 4.2, we know that there exists a stable randomized compression scheme (D κ , ρ) for H of size 𝑠(𝑛) = 𝑂 (𝑑 log(𝑛/β)), and failure probability ξ. Then, since β > 2ξ, from Lemma 4.1, we know that with probability at least 1β over 𝑆 and κ ∼ D κ ,𝑅 D (ρ(κ(𝑆))) ≤ 𝑂 𝑑 log(𝑛/β) 𝑛 .For the right-hand size above to be at most α, it suffices to have𝑛 = 𝑂 𝑑 log(𝑑/α)+𝑑 log(1/β) α .Let A be the learning rule, which when given a sample 𝑆 ∼ D 𝑛 as input, runs the stable randomized compression scheme from above on 𝑆 to obtain 𝑆 ′ of size 𝑘 = 𝑂 (𝑑 log(𝑛/β)). The learner then outputs (ρ(𝑆 ′ ), 𝑆 ′ ). By the reasoning above, ρ(𝑆 ′ ) has error at most α with probability at least 1β.It remains to argue that A is a valid CCA mechanism. This follows by virtue of (D κ , ρ) being a stable randomized compression scheme. Namely, for any 𝑖, 𝑆 -𝑖 ⊑ 𝑆, and hence by Definition 6, the distribution of κ(𝑆 -𝑖 ) is identical to the distribution of κ(𝑆) conditioned on 𝑆 𝑖 ∉ κ(𝑆). Finally, since ρ is a deterministic function of its argument, A satisfies Definition 1 with ε = δ = 0. ■Towards proving Theorem 2, we first show that a sample DP-compression scheme for the class of thresholds can be used to construct a DP learner for it. This lemma has a similar flavor to the public data reduction lemma (Lemma 4.4) in [1] . For a set 𝑆 = {𝑥 1 , . Proof. Let D be any distribution over {𝑥 1 , . . . , 𝑥 𝑚-1 } × {0, 1} realizable by H 𝑚-1 . Given a sample 𝑆 ∼ D 𝑛 , the private learner A does the following. First, it constructs a sample S, also of size 𝑛, as follows. Initialize 𝑗 = 1. For each 𝑖 = 1, 2, . . . , 𝑛, toss a coin (independently of the data, and other coins) that lands heads with probability 𝑝, for 𝑝 to be appropriately chosen later. If the coin lands heads, S(𝑖) = 𝑆( 𝑗), and 𝑗 is incremented by 1. If the coin lands tails, S(𝑖) is set to the designated dummy example (𝑥 𝑚 , 1). In this way, S is a sample of size 𝑛 drawn from the mixture distributionD = 𝑝 • D + (1 -𝑝) • 1 ( 𝑥 𝑚 ,1), where 1 ( 𝑥 𝑚 ,1) is a point mass on (𝑥 𝑚 , 1). Note that since all the thresholds in H 𝑚 label 𝑥 𝑚 as 1, D is realizable by H 𝑚 .The learner A now invokes the sample DP-compression scheme Ã on S. If any of the 𝑘 examples in the compression set constructed by Ã is a non-dummy element, A outputs a constant hypothesis that labels all points in {𝑥 1 , . . . , 𝑥 𝑚-1 } as 1. On the other hand, if all of the 𝑘 examples in the compression set are dummies, then A outputs the hypothesis that Ã outputs (restricted to {𝑥 1 , . . . , 𝑥 𝑚-1 }).We first claim that the output of A is (2ε, 3δ)-private with respect to its input 𝑆.). A is (2ε, 3δ)-DP.The proof of this claim is given in Appendix A. At a high level, the privacy parameter deteriorates to 2ε because of the two-step process of compressing S to 𝑘 points in an ε-DP way, and then obtaining an ε-DP learner thereafter.Next, we claim that on average, there will be a lot of dummies in the compression set selected by Ã. This step crucially hinges on Theorem 3, where we substitute the event 𝐸 in the statement of the theorem to be the event that a non-dummy element is selected (i.e., 𝐸 is the support of the distribution D). In particular, we get that the expected number of non-dummy elements is at most 𝑘 𝑝𝑒 ε + δ𝑘𝑛, which is at most 1 32 , if we set 𝑝 = 1 64𝑘ε 2 , and use that 𝑘 ≤ 𝑛, δ ≤ 1 64𝑛 2 . We can now reason about the error and failure probability parameters of A. Because Ã is an (ε, δ) sample DP-compression scheme that successfully learns H 𝑚 with error α and failure probability 1 32 , with probability at least 1 -1 32 over the draw of S and the randomness of Ã, the hypothesis it outputs has error at most α. Furthermore, since the expected number of non-dummy elements chosen in the compression set is at most 1 32 , Markov's inequality gives that with probability at least 1 -1 32 over the draw of S and the randomness of Ã, all the 𝑘 examples chosen by Ã in the compression set are dummies. By a union bound, with probability at least 1 -1 16 over the draw of S and the randomness of Ã, all the examples chosen to be in the compression set by Ã are dummies and the hypothesis it outputs has error (with respect to D) less than α.But recall that the distribution D on S is induced by the distribution D on 𝑆, and that whenever all the examples chosen by Ã in the compression set are dummies, A returns Ã's output. This implies that with probability at least 1 -1 16 over the draw of 𝑆 from D 𝑛 and the randomness of A, the hypothesis output by A has error at most α with respect to D. But since D is a mixture distribution,𝑅 D (A(𝑆)) ≥ 𝑝 • 𝑅 D (A(𝑆)),and hence we have that with probability at least 1 - 1 16 , the error of A(𝑆) with respect to D is at most α 𝑝 ≤ 64𝑘𝑒 ε α. Thus, A is a 64𝑘𝑒 ε α, 1 16 , 2ε, 3δ -DP learner for H 𝑚-1 as required. ■We next state a lower bound on the sample complexity of DP learners for thresholds [2, 10] .Theorem 4 (Theorem 1 in [2] ). Let H 𝑚 be the class of thresholds on {𝑥 1 , . . . , 𝑥 𝑚 }. Let A be a By Theorem 4, it must be that 𝑛 ≥ Ω(log * 𝑚). Since we can find H 𝑚 ⊆ H for any 𝑚 ≥ 1, this would mean that 𝑛 = ∞, which is a contradiction. Thus, it must be the case that 𝑘 ≤ 1 68α . ■We prove a simplified form of Theorem 3 (with slightly tighter bounds), where we consider the input to be a bit string. Theorem 3 as stated in terms of a general event can be immediately obtained as a corollory by interpreting the bits in the string as indicators for the event (details in Appendix A). EQUATION= 𝑖|𝑋 𝑖 = 0] = Pr[𝑋 𝑖 = 0 ∧ 𝐼 𝑗 = 𝑖] Pr[𝑋 𝑖 = 0] = 𝑥 ∈ {0,1} 𝑛 ,𝑥 𝑖 =0 Pr[𝑥] Pr[𝐼 𝑗 = 𝑖|𝑥] 1 -𝑝 = 𝑥 ∈ {0,1} 𝑛 , 𝑥 𝑖 =1 Pr[𝑥 ⊗𝑖 ] Pr[𝐼 𝑗 = 𝑖|𝑥 ⊗𝑖 ] 1 -𝑝 ≤ 𝑥 ∈ {0,1} 𝑛 ,𝑥 𝑖 =1 Pr[𝑥] • (𝑒 ε Pr[𝐼 𝑗 = 𝑖|𝑥] + δ) 𝑝 = 𝑒 ε 𝑥 ∈ {0,1} 𝑛 , 𝑥 𝑖 =1 Pr[𝑥] Pr[𝐼 𝑗 = 𝑖|𝑥] 𝑝 + δ = 𝑒 ε • Pr[𝐼 𝑗 = 𝑖|𝑋 𝑖 = 1] + δ,where in the fourth inequality, we used that for 𝑥 having 𝑥 𝑖 = 1, Pr D [𝑥 ⊗𝑖 ] = 1-𝑝 𝑝 • Pr[𝑥], 
conclusion: 
 We study two natural definitions for algorithms satisfying credit attribution. In the context of PAC learning, we provide a characterization of learnability for algorithms that respect these definitions.Our work motivates the further study of these and other related definitions for credit attribution, and opens up interesting technical directions to pursue. However, as mentioned earlier, credit attribution is only part of the much more nuanced problem of copyright protection, and hence, our definitions only capture subtleties involved in the problem in part. With further exploration, and other suitable definitions, we will hopefully be able to ensure that algorithms (especially generative models) appropriately credit the work that they draw upon.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: The paper does not include experiments requiring code.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 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: The paper does not include experiments. 
experiment statistical significance: 
 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: The paper does not include 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. 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: [Yes] Justification: Our work suggests definitions for credit attribution in machine learning algorithms. The hope is that models adhering to these definitions (particularly generative AI models) will not be able to get away with generating content that is heavily influenced from existing (possibly copyrighted) artwork without properly citing it. We do not anticipate any negative societal impact due to our work. 
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: The paper poses no such risks. 
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: The paper is theoretical and 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. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [NA] Justification: The paper does not release any new assets. Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: Proof of Claim 4.4. Consider any 2 neighboring datasets 𝑆 = (𝑧 1 , . . . , 𝑧 𝑖 , . . . , 𝑧 𝑛 ) and 𝑆 ′ = (𝑧 1 , . . . , 𝑧 ′ 𝑖 , . . . , 𝑧 𝑛 ) that differ at index 𝑖. Here, we are using the shorthand 𝑧 𝑖 = (𝑥 𝑖 , 𝑦 𝑖 ). We want to argue that the distribution of A(𝑆) = 2ε,3δ A(𝑆 ′ ). Let 𝑂 be any subset of the output space of A. Recall that A first constructs the sample S from 𝑆 and then passes it to the semi-private learner Ã. Then,Pr[A(𝑆) ∈ 𝑂] = Pr[A(𝑆) ∈ 𝑂|𝑧 𝑖 ∈ S] Pr[𝑧 𝑖 ∈ S] + Pr[A(𝑆) ∈ 𝑂|𝑧 𝑖 ∉ S] Pr[𝑧 𝑖 ∉ S] = Pr[A(𝑆) ∈ 𝑂|𝑧 𝑖 ∈ S] Pr[𝑧 ′ 𝑖 ∈ S′ ] + Pr[A(𝑆 ′ ) ∈ 𝑂|𝑧 ′ 𝑖 ∉ S′ ] Pr[𝑧 ′ 𝑖 ∉ S′ ] (5)where we used that the coins that deterine whether 𝑧 𝑖 ∈ 𝑆 (or 𝑧 ′ 𝑖 ∈ S′ ) are tossed independently of the data, and that the distribution of S′ conditioned on 𝑧 ′ 𝑖 ∉ S′ , is identical to the distribution of S conditioned on 𝑧 𝑖 ∉ S. Hence, we focus on the term Pr[A(𝑆) ∈ 𝑂|𝑧 𝑖 ∈ S] in (5) . We can decompose this asEQUATIONHere, for every term in the summation, s′ differs from s at exactly one index 𝑖, and we again used that the coins used to construct S and S′ are independent of the data. Let 𝐸 ( s) be the event that all the 𝑘 samples chosen by the semi-private learner Ã when it is given s as input are dummies. Since s and s′ differ in exactly one element, because of the special property of the selection mechanism of Ã, we have that 7) and ( 9), we getEQUATIONEQUATION)Now, observe that if 𝐸 ( s) does not occur (and correspondingly if 𝐸 ( s′ ) does not occur), then we deterministically out the constant hypothesis in either case, and henceEQUATIONCombining ( 8) and ( 11), we getPr[A(𝑆) ∈ 𝑂|𝑧 𝑖 ∈ S, S = s, ¬𝐸 ( s)] • Pr[¬𝐸 ( s)|𝑧 𝑖 ∈ S, S = s] ≤ 𝑒 ε • Pr[A(𝑆 ′ ) ∈ 𝑂|𝑧 ′ 𝑖 ∈ S′ , S′ = s′ , ¬𝐸 ( s′ )] • Pr[¬𝐸 ( s′ )|𝑧 ′ 𝑖 ∈ S′ , S′ = s′ ] + δ (12)Altogether, (10) and (12) give thatPr[A(𝑆) ∈ 𝑂|𝑧 𝑖 ∈ S, S = s] ≤ 𝑒 2ε • Pr[A(𝑆 ′ ) ∈ 𝑂|𝑧 ′ 𝑖 ∈ S′ , S′ = s′ ] + 3δ.Substituting in ( 6), we getPr[A(𝑆) ∈ 𝑂|𝑧 𝑖 ∈ S] ≤ ∑︁ s′ :𝑧 ′ 𝑖 ∈ s′ Pr[A(𝑆) ∈ 𝑂|𝑧 𝑖 ∈ S, S = s] Pr[ S′ = s′ |𝑧 ′ 𝑖 ∈ S′ ] ≤ ∑︁ s′ :𝑧 ′ 𝑖 ∈ s′ 𝑒 2ε • Pr[A(𝑆 ′ ) ∈ 𝑂|𝑧 ′ 𝑖 ∈ S′ , S′ = s′ ] + 3δ Pr[ S′ = s′ |𝑧 ′ 𝑖 ∈ S′ ] ≤ 3δ + 𝑒 2ε ∑︁ s′ :𝑧 ′ 𝑖 ∈ s′ Pr[A(𝑆 ′ ) ∈ 𝑂|𝑧 ′ 𝑖 ∈ S′ , S′ = s′ ] Pr[ S′ = s′ |𝑧 ′ 𝑖 ∈ S′ ] = 𝑒 2ε • Pr[A(𝑆 ′ ) ∈ 𝑂|𝑧 ′ 𝑖 ∈ S′ ] + 3δ. Finally, substituting back in (5), we get Pr[A(𝑆) ∈ 𝑂] ≤ 𝑒 2ε • Pr[A(𝑆 ′ ) ∈ 𝑂|𝑧 ′ 𝑖 ∈ S′ ] + 3δ Pr[𝑧 ′ 𝑖 ∈ S′ ] + Pr[A(𝑆 ′ ) ∈ 𝑂|𝑧 ′ 𝑖 ∉ S′ ] Pr[𝑧 ′ 𝑖 ∉ S′ ] ≤ 𝑒 2ε • Pr[A(𝑆 ′ ) ∈ 𝑂|𝑧 ′ 𝑖 ∈ S′ ] Pr[𝑧 ′ 𝑖 ∈ S′ ] + Pr[A(𝑆 ′ ) ∈ 𝑂|𝑧 ′ 𝑖 ∉ S′ ] Pr[𝑧 ′ 𝑖 ∉ S′ ] + 3δ = 𝑒 2ε • Pr[A(𝑆 ′ ) ∈ 𝑂] + 3δ.[A(𝑆 ′ ) ∈ 𝑂] ≤ 𝑒 2ε • Pr[A(𝑆) ∈ 𝑂] + 3δ, completing the proof. ■ Proof of Lemma 4.5. Let A(𝑋) = 𝐼 = (𝐼 1 , 𝐼 2 , . . . , 𝐼 𝑘 ). Note that 𝑍 = 1 𝑘 𝑘 ∑︁ 𝑗=1 𝑛 ∑︁ 𝑖=1 1[𝐼 𝑗 = 𝑖 ∧ 𝑋 𝑖 = 1],and henceEQUATION)Now, for any 𝑥 ∈ {0, 1} 𝑛 , let 𝑥 ⊗𝑖 denote 𝑥 with its 𝑖 th bit flipped. Then, observe thatPr[𝐼 𝑗 = 𝑖|𝑋 𝑖 = 0] = Pr[𝑋 𝑖 = 0 ∧ 𝐼 𝑗 = 𝑖] Pr[𝑋 𝑖 = 0] = 𝑥 ∈ {0,1} 𝑛 ,𝑥 𝑖 =0 Pr[𝑥] Pr[𝐼 𝑗 = 𝑖|𝑥] 1 -𝑝 = 𝑥 ∈ {0,1} 𝑛 , 𝑥 𝑖 =1 Pr[𝑥 ⊗𝑖 ] Pr[𝐼 𝑗 = 𝑖|𝑥 ⊗𝑖 ] 1 -𝑝 ≤ 𝑥 ∈ {0,1} 𝑛 ,𝑥 𝑖 =1 Pr[𝑥] • (𝑒 ε Pr[𝐼 𝑗 = 𝑖|𝑥] + δ) 𝑝 = 𝑒 ε 𝑥 ∈ {0,1} 𝑛 , 𝑥 𝑖 =1 Pr[𝑥] Pr[𝐼 𝑗 = 𝑖|𝑥] 𝑝 + δ = 𝑒 ε • Pr[𝐼 𝑗 = 𝑖|𝑋 𝑖 = 1] + δ,where in the fourth inequality, we used that for 𝑥 having𝑥 𝑖 = 1, Pr D [𝑥 ⊗𝑖 ] = 1-𝑝 𝑝 • Pr[𝑥], and that A is an (ε, δ)-DP mechanism. Hence, we have thatEQUATION)Substituting ( 15) in ( 13), we getEQUATION)Finally, note that 𝑛 𝑖=1 Pr[𝐼 𝑗 = 𝑖] = 1 for any 𝑗. Substituting in ( 16), we have shown the desired lower boundE[𝑍] ≥ 𝑝 -𝑛𝑝(1 -𝑝)δ 𝑝 + 𝑒 ε (1 -𝑝).For the upper bound, we repeat the above analysis with𝑍 ′ = 1 𝑘 𝑗 ∈A(𝑋) 1[𝑋 𝑗 = 0], to obtain E[𝑍 ′ ] ≥ (1 -𝑝) -𝑛𝑝(1 -𝑝)δ 1 -𝑝 + 𝑝𝑒 ε .But note that 𝑍 ′ = 1 -𝑍, and henceE[𝑍] = 1 -E[𝑍 ′ ] ≤ 𝑝𝑒 ε + 𝑛𝑝(1 -𝑝)δ 1 -𝑝 + 𝑝𝑒 ε .Proof of Theorem 3. Recall that 𝐸 ⊆ Z is an event satisfying D(𝐸) = 𝑝 for the given distribution D over Z. Let D|𝐸 denote the distribution D conditioned on the event 𝐸, and let D|¬𝐸 denote the distribution D conditioned on the complement of event 𝐸. Assume for the sake of contradiction that eitherE[𝑍] > 𝑝𝑒 ε +𝑛 𝑝 (1-𝑝)δ 1-𝑝+ 𝑝𝑒 ε or E[𝑍] < 𝑝+𝑛 𝑝 (1-𝑝)δ 𝑝+(1-𝑝)𝑒 ε .Then, consider an algorithm B, that takes as input a bit string 𝑌 from a product distribution on {0, 1} 𝑛 , where each bit is independently set to 1 with probability 𝑝. Given such an input string 𝑌 , the algorithm constructs a sequence 𝑆 = {𝑧 1 , . . . , 𝑧 𝑛 }, where 𝑧 𝑖 ∼ D|𝐸 if 𝑌 𝑖 = 1, and 𝑧 𝑖 ∼ D|¬𝐸 otherwise. Thus, 𝑆 is exactly distributed as 𝐷 𝑛 . B then passes 𝑆 to the DP sample compression scheme 𝑀, which selects a compression set κ(𝑆) = (𝑖 1 , . . . , 𝑖 𝑘 )-this is the tuple of indices that B outputs too. Note that because the compression function κ is an (ε, δ)-DP mechanism, B is also an (ε, δ)-DP mechanism with respect to its input. To see this, consider two neighboring bit strings 𝑦, 𝑦 ′ , such that 𝑦 𝑖 = 1 and 𝑦 ′ 𝑖 = 0. We will show that Pr[B(𝑦) ∈ 𝑂] ≤ 𝑒 ε • Pr[B(𝑦 ′ ) ∈ 𝑂] + δ, and the same calculations will give the bound with 𝑦, 𝑦 ′ swapped.EQUATIONNow, for any 𝑧 ′ 𝑖 ∈ ¬𝐸, we know (since κ is anEQUATION)Substituting ( 18) in (17) gives thatPr[B(𝑦) ∈ 𝑂] ≤ 𝑒 ε • ∑︁ 𝑧 -𝑖 Pr[𝑧 -𝑖 ] ∑︁ 𝑧 ′ 𝑖 ∈¬𝐸 Pr[𝑧 ′ 𝑖 |¬𝐸] Pr[A(𝑧 -𝑖 • 𝑧 ′ 𝑖 ) ∈ 𝑂] + δ = 𝑒 ε • Pr[B(𝑦 ′ ) ∈ 𝑂] + δ.Now, by our assumption, either Claim B.1 (RR boosts empirical measure optimally). In the setting of Lemma 4.5, let δ = 0 and let A be the randomized response mechanism RR (Definition 7) . Then,E[𝑍] > 𝑝𝑒 ε +𝑛 𝑝 (1-𝑝)δ 1-𝑝+ 𝑝𝑒 ε or E[𝑍] < 𝑝+𝑛 𝑝 (1-𝑝)δ 𝑝+(1-𝑝)𝑒 ε . But this means that either E 𝑘 𝑗=1 1[𝑌 𝑖 𝑗 = 1] > 𝑝𝑒 ε +𝑛 𝑝 (1-𝑝)δ 1-𝑝+ 𝑝𝑒 ε or E 𝑘 𝑗=1 1[𝑌 𝑖 𝑗 = 1] < 𝑝+𝑛 𝑝 (1-𝑝)δ 𝑝+(1-𝑝)𝑒 ε . Thus, B is an (ε,EQUATIONRemark 3. Observe that when 𝑘 = 𝑜 𝑛 log 𝑛 and 𝑛 gets large, the expression in the parentheses approaches 1. Thus, we can conclude that randomized response attains the upper bound from Lemma 4.5 when δ = 0.Proof. Recall that for 𝑋 ∼ D, randomized response first constructs 𝑌 by flipping each bit of 𝑋 with probability 1 1+𝑒 ε . That is, the distribution of 𝑌 is the product distribution where each 𝑌 𝑖 is 1 with probability 𝑝• 𝑒 ε 1+𝑒 ε + (1 -𝑝) • 1 1+𝑒 ε = 1-𝑝+ 𝑝𝑒 ε 1+𝑒 ε := α. Let 𝑆 = {𝑖 ∈ [𝑛] : 𝑌 𝑖 = 1}.We first claim that with high probability, |𝑆| ≥ 𝑘.To see this, note thatPr[|𝑆| ≥ 𝑘] = 1 -Pr[|𝑆| < 𝑘] = 1 -Pr[∃𝑆 ′ ∈ [𝑛] : |𝑆 ′ | > 𝑛 -𝑘, 𝑌 𝑖 = 0 ∀𝑖 ∈ 𝑆 ′ ] ≥ 1 -Pr[∃𝑆 ′ ∈ [𝑛] : |𝑆 ′ | = 𝑛 -𝑘 + 1, 𝑌 𝑖 = 0 ∀𝑖 ∈ 𝑆 ′ ] ≥ 1 - 𝑛 𝑘 -1 (1 -α) 𝑛-𝑘+1 ≥ 1 -𝑛 𝑘 • 𝑒 -α(𝑛-𝑘 ) :=β, where we denote the tail probability by β. Note that since we assume 𝑘 = 𝑜 𝑛 log 𝑛 , β = 𝑜(1). Let 𝐼 be the tuple of 𝑘 indices that RR outputs (note that all these indices are always distinct). Recall that, if |𝑆| ≥ 𝑘, then 𝑌 𝑖 = 1 for all 𝑖 ∈ 𝐼.Let 𝑍 1 = 𝑖 ∈𝐼 1[𝑌 𝑖 = 1] and 𝑍 0 = 𝑖 ∈ 𝐼 1[𝑌 𝑖 = 0]. Then we have that E[𝑍 1 ] ≥ 𝑘 • Pr[|𝑆| ≥ 𝑘] ≥ 𝑘 (1 -β) =⇒ E[𝑍 0 ] ≤ 𝑘β.Markov's inequality then gives us that Pr[𝑍 0 ≥ 1] ≤ 𝑘β. Thus, with probability at least 1 -𝑘β, we have that 𝑌 𝑖 = 1 for all (distinct) indices output by RR: let 𝐺 denote this event.Finally, let 𝑍 = 1𝑘 𝑖 ∈ 𝐼 1[𝑋 𝑖 = 1]. Then, we have thatEQUATIONBut observe thatE[𝑍 |𝐺, 𝐼 = {𝑖 1 , . . . , 𝑖 𝑘 }] = 1 𝑘 ∑︁ 𝑗 ∈ {𝑖 1 ,...,𝑖 𝑘 } Pr[𝑋 𝑗 = 1|𝑌 𝑗 = 1] = 1 𝑘 ∑︁ 𝑗 ∈ {𝑖 1 ,...,𝑖 𝑘 } Pr[𝑋 𝑗 = 1 ∧ 𝑌 𝑗 = 1] Pr[𝑌 𝑗 = 1] = 1 𝑘 ∑︁ 𝑗 ∈ {𝑖 1 ,...,𝑖 𝑘 } 𝑝 • 𝑒 ε 1+𝑒 ε 𝑝 • 𝑒 ε 1+𝑒 ε + (1 -𝑝) • 1 1+𝑒 ε = 𝑝𝑒 ε 1 -𝑝 + 𝑝𝑒 ε .Substituting in (20) and plugging in the expression for β, we get the desired boundE[𝑍] ≥ 1 -𝑘𝑛 𝑘 • exp (𝑘 -𝑛) (1 -𝑝 + 𝑝𝑒 ε ) 1 + 𝑒 ε • 𝑝𝑒 ε 1 -𝑝 + 𝑝𝑒 ε . ■ NeurIPS Paper Checklist 1.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: We claim to study credit attribution in machine learning algorithms in the abstract, and our main results (Definitions 1, 3 and Theorems 1, 2) are precisely about this.• 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.• 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.• 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).• 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.8It seems interesting to possibly consider randomized reconstruction functions as well; for our purposes, deterministic reconstruction functions suffice.9In more detail, this follows by setting the weak learning parameter γ to a constant (e.g., 1/8) in Algorithm 1 in[12], and noting that such a weak learner can be found via empirical risk minimization. 


Decision: The authors did a good job addressing the reviewers' questions and comments.  All reviewers are supportive. For this reason, I recommend accept.  

Meanwhile, I do have some comments that the authors can consider.  

First, on the technical level, the results appear to resemble the "semi-private learning" result very strongly. "Public data <=> data attribute credits to". Note that the most intriguing result on the dichotomy seems directly inherited from the ABM NeurIPS'19 paper. The discussion w.r.t. this line of work is somewhat ambiguous.

Secondly, it is philosophically and ethically a bit uneasy for me to accept that the protection of Definition 1 is sufficient. In the SVM example, sure, only the support vectors matter, but if you do not have the collection of all the other data points, how would you know that these data points that you are crediting are support vectors?

To drive the point home, let's say the company training this model is only providing monetary compensation to the support vectors, then seems very unfair to other data points that the algorithm actually used for training, and are very close to being the support vectors. I think the idea of conditioning on the output and finding a sparse number of data points that contribute to the output is a very broken paradigm for "credit attribution".

Reviews: review: paper_summary: paper_summary: This paper studies the problem of credit attribution in machine learning tasks. Motivated by the moral and legal need to appropriately credit input data points when they significantly influence the output of a learning or generative model, the authors develop a characterization of reasonable credit attribution algorithms. Similar to how in differential privacy an individual is considered protected if keeping or omitting their data in the input data set leads to at most a limited $(\varepsilon,\delta)$ bounded shift in max-divergence of the output distribution, this work considers an individual to be safely not credited if omitting their data would have lead to a bounded shift in this sense. 

The authors link the notion of generating a not-too-long list of samples to be credited (since a trivial solution is to credit everyone) to the notion of stable sample compression schemes of size $k$, which allow identification of a subsequence of size $k$ for every input data set such that restricting the input to any input subset containing that subsequence leads to the same output. This is stronger than the notion of credit attribution they are considering, so they consider a relaxation using semi-differentially private algorithms, which only need to have a bounded shift in the output distribution when a sample is added or dropped from a `private' subset of the input data. This relaxation is called a DP Sample Compression Scheme.

The authors give an example showing that their definition is not vacuous and go on to state three theorems:
1. PAC learnable classes with VC dimension $d$ admit solutions with valid credit attribution and only $O(d\log n)$ many samples.
2. If a concept class is not DP learnable (in which case it would have been automatically a valid credit attribution algorithm without having to credit any point), then it must credit at least $k=\Omega(1/\alpha)$ many points.
3. The additional number of points one is allowed to pick by relaxing from random subsampling of $k$ points (and crediting the whole sample) to a valid credit attribution algorithm allows one to pick at most an $\exp(\epsilon)$ factor many more samples.
strength_weakness: strength_weakness: 1. 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.
2. 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 $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.
questions: questions: If you can address the points I have raised in the Weaknesses section that would suffice for most of the questions I would like to have answered. In particular the second point is a bit concerning to me, although maybe I have misunderstood the definition. If my understanding is correct and if you feel strongly that the label/name ought to stay as it is and you can point to other important instances which violate the principle I described I would be happy to be corrected.

Additional questions/notes: 
1. 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?
2. 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.
limitations: limitations: Yes, limitations have been adequately discussed.
paper_summary: paper_summary: This paper addresses the challenge of credit attribution within the context of machine learning algorithms. It proposes new definitions that relax the stability of a subset of data points. The framework extends established notions of stability, such as Differential Privacy, differentially private learning with public data, and stable sample compression, within the PAC learning framework. The authors provide a characterization of learnability for algorithms adhering to these stability principles and suggest future research directions.
strength_weakness: strength_weakness: 1. Examples that satisfy Definition 1 could be further discussed. Could the authors clarify examples of  (ε>0,δ)-counterfactual credit attributor (Definition 1) which are not (ε=0,δ=0)-CAA?
2. 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 (ε, δ)-CAA applied to classical problems with varying parameters ε,δ controlling the privacy-utility tradeoff.
questions: questions: 1. See weaknesses
2. Could the authors explain the difference or connection between Definition 3 and adaptive composition + post-processing in DP?
limitations: limitations: NA
paper_summary: paper_summary: The authors propose a new notion of credit attribution, which is a relaxation of differential privacy (DP). They discuss the relationship between the proposed notion, semi-differential privacy where part of the data records are public, and a DP sample compression scheme. PAC learning theory under these notions is investigated.
strength_weakness: strength_weakness: Even though the proposed new definition of credit attribution may provide a new perspective on copyright and privacy, the current content may not support this strongly due to the following weaknesses:

1. 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").


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.

2. 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?

It would be a significant enhancement if the authors could establish a solid mathematical relationship between these three definitions.
questions: questions: Please clarify my concerns in the weaknesses section. Additionally, please point out if I made any mistakes in the review.

I believe this paper has the potential to be accepted as it might provide a new perspective on copyright and privacy analysis. However, for the current version, I would not suggest accepting it due to the weaknesses I listed.
limitations: limitations: Yes
paper_summary: paper_summary: This paper studies credit attribution and stable compression. Credit attribution aims to assign recognition to the original creators of content generated by machine learning models. The authors propose formal definitions for credit attribution and connect it to differential privacy (DP). The proposed framework extends notions of stability, such as stable sample compression. The paper uses the PAC learning framework to study the learnability of machine-learning problems under the constraints of counterfactual credit attribution (CCA) and stable sample compression.
strength_weakness: strength_weakness: 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.
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.
4. The intuition behind semi-differentially private learning is not very clear. An explanation using a concrete example would be helpful.

Minor Correction: Sec 2, Line 71: X* -> Z*
questions: questions: 1. How could this framework be extended to generative models, such as text and image generators?
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)?
limitations: limitations: Yes, the authors have addressed the limitations of their work at different points in the paper, but not in a separate "Limitations" section, as encouraged in the guidelines.

Comments: title: Response to rebuttal
Response to comment by Reviwer ariQ
Thanks
comment: Thank you for your efforts in the rebuttal! I will maintain my original score.
Thank you for the rebuttal, I think all of my questions and concerns have been addressed for now. My only main concern was about the term 'DP Sample Compression Scheme', and I'm sure that any term that you would like to use (not necessarily the ones I mentioned) should work well as long as it doesn't imply that the algorithm as a whole is DP.
Thank you again for your response. We really appreciate your time in engaging in this discussion!
1) We would like to clarify again that our definitions are valid for any mechanisms in general, **including generative models**. More explicitly, we can think of a generative model as a CCA mechanism $M: Z^*\to C \times Z^*$ satisfying Definition 1, where the input $Z^*$ is the training data that the model sees (e.g., existing artworks), and the output $C$ is the new content it generates (e.g., new artwork) and $Z^*$ is the artworks that it cites. In this sense, the definition is general and *is* effective for credit attribution in the context of generative models (it is just a criterion that the model must satisfy). Perhaps it also helps to keep in mind how Differential Privacy is a definition applicable to mechanisms in general, has a well-established theory in the PAC learning setting, and at the same time is also applied in practice for many other types of algorithms. Please let us know of an example if there is something more specific that you are looking for!
2) SVM is just an example of a learning algorithm that (conveniently) already satisfies the definition that we propose for credit attribution. In general, modern ML algorithms like CNNs and Transformers, by themselves do not satisfy our definitions. It is also well-agreed at this point that these models significantly outperform SVMs on benchmark tasks (e.g., image classification). One of our motivations behind proposing the definitions that we do (which, again are general criterions) is that the community can start to modify and suitably adapt modern ML algorithms like CNNs so that they adhere to the credit attribution criterion.
3) We agree that it is always trivially possible to get full recall, by just citing the entire training dataset. However, the objective is to cite only a small-sized, relevant portion of the training data. In this sense, our PAC learning algorithm that satisfies CCA (Theorem 1) obtains meaningful bounds---even in the **worst case**, it cites only $k=O(d\log{n})$ examples, upon seeing a training dataset of $n$ examples labeled by a hypothesis class of VC dimension $d$. As we state, it would be an interesting future direction to obtain optimal, distribution dependent bounds that possibly also factor in precision.
I would like to thank the authors for their responses to my comments and questions. While some of my concerns have been addressed, my main concerns still remain.

1. The proposed framework for credit attribution does not seem directly applicable to the generative models discussed in the abstract and introduction as a motivation for this work. If the framework is indeed applicable to such models, it would be beneficial to include a clear example demonstrating this. If not, it might be advisable to reduce the emphasis on generative models in the early sections of the paper. Otherwise, this emphasis could potentially mislead readers into believing that the framework is effective for credit attribution in the context of generative models.
2. As I understand it, the paper examines the proposed framework for support vector machines in the context of classification. While this contribution is valuable, it would be even more impactful to demonstrate credit attribution for modern machine learning models, such as convolutional neural networks used for image classification. If the framework does not apply to such models, it would be helpful to include a comparison between the performance of state-of-the-art classification models and those that support credit attribution. This would provide valuable insights into the performance trade-offs associated with incorporating credit attribution into classification tasks.
3. While it is understandable to prioritize recall in the context of credit attribution, it is equally important to ensure that precision remains at a reasonable level. If precision is allowed to be too low, it would be trivial to achieve perfect recall simply by attributing credit to all training samples. An empirical analysis of the trade-off between recall and precision within the proposed framework would be highly beneficial.
Dear Reviewer nyTY,

It seems that this comment may have been posted under the wrong rebuttal. Could you please review and respond to the correct one?

Thank you for your attention to this matter.

Best regards,
Reviewer ariQ
Thank you! Just a quick reminder to raise the score when you can.
Thank you for the clarification. I would change my rating and suggest acceptance of the paper.