Credit Attribution and Stable Compression
Authors: Roi Livni
Shay Moran
Kobbi Nissim
Chirag Pabbaraju
Venue: NeurIPS 2024 poster (2024)
Keywords: Credit Attribution
Algorithmic Stability
Stable Sample Compression
Primary area: learning_theory
TL;DR: We study credit attribution by machine learning algorithms via new relaxations of Differential Privacy that specifically weaken the stability guarantees for a designated subset of $k$ datapoints.

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.

Credit Attribution and Stable Compression
Roi Livni' Shay Moran
Kobbi Nissim
Chirag Pabbaraju
Abstract
Credit attribution is crucial across various fields. In academic research, proper citation acknowledges prior work and establishes original contributions. Simi- larly, in generative models, such those trained 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-relaxationss of Differential Privacy-that weaken the stability guarantees for a designated subset of k datapoints. These & datapoints can be used non-stably with permission from their owners, potentially in exchange for compensation. Mcanwhile, each of the remaining datapoints is guaranteed to have no significant influence on the algorithm's output.
Our framework extends well-studied notions of stability, including Differential Privacy 0), differentially private learning with public data (where the k public datapoints are fixed in advance), and stable sample compression (where the & 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 these principles, and propose directions and questions for future research.
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. learner generating content, such as images without violating the creator's s rights (either through proper attribution or monetary compensation, depending on the context and licensing).
music, may benefit from creating derivative works from copyrighted materials
The increasing use of ML algorithms and the need for greater transparency 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 necessarily equivalent. 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 heavily built upon. Therefore, there is 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 provide rigorous and meaningful definitions for the task.
"Tel Aviv University. rlivni clivni@tauex. tau. tau.ac.ii ic. Technion and Google Research. smoran@technion. ac.il.
&Goorgetown University and Google Research. kobbi. wwwsiiimgeorgetooo..e. 8 Stanford University. cpabbara@cs. stanford. edu.
38th Conference on Neural Information Processing Systems (NeurIPS 2024).

---

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 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 MI. many practical scenarios, desirable for learning models to be allowed to use original elements in 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 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 be captured mathematically. Therefore, we focus on formalizing specific (but arguably basic) aspect of it counterfactual attribution:
This principle asserts that any previous work that influenced the result should be credited. Counterfactually, the creator of a work W does not acknowledge another work W", they should be able to produce W as if they had no knowledge of W"
For example, an argument based this principle in the extreme case when W W is found in 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. Rural Telephone Service Company, Inc 499 U.S. 340 (1991)
2 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 e denote an output space. We denote by 2* the set of all finite sequences with elements from Z. Two sequences S", e X* are called neighbors if they have the same length [.5'| |S"I and there is unique index i such that S # Sy- Let E, > Ó and let p. q be probability distributions defined over the same space. We let p =2, q denote the following relation: p(E)= s exp(e) q(E)+ + 5 and (E) z exp(E) p(E) + 8 for every event E.
Algorithms with Credit Attribution. Consider a mechanism M 2* - C 2* that, for every possible input sequence itively, R is the list of inputs being credited by the mechanism, and c is the model/content produced by the mechanism. Thus, we require that each data point z E R is also an input data point , e S. For such a mechanism M and an input sequence S, we let MSS) denote the probability distribution over outputs of M given as input, where the probability is induced by the internal randomness of the mechanism. For example, if M is deterministic. then (S) is a Dirac distribution (i.e., it assigns probability to the deterministic output of M on S).
(ZI.....Zn), outputs a pair R), where c E e and R E 2+. Intu-
The definition below uses the following notation: for sequence S (Zı...., an) and an index [n], we let S-, denote the subsequence of S obtained by omitting z,. Let z E be a data point such that (s e R] < 1. That is, there is positive probability that is not credited

---

Example: Support Vector Machine
Figure 1: Support Vector Machine (SVM) as an (c = O)-counterfactual credit attributor: The SVM algorithm identifics maximum-marght separating hyperplane, which is defined by the subsample of the support vectors. Any input point which is not support vector does not influence the output: even if it is removed from the input sample, the output hyperplane does not change.
by M when executed on In this case, we let ((S denote the distribution of M conditioned on the event that 2 R. We are now ready to present our first definition of counterfactual credit attribution.
Definition 1 (Counterfactual Credit Attribution). Let E, > mechanism M 2* @ x Z* is called an (e, cocontterrala credit attributor (CCA) if for every input sequence S = (ZI...., 2n) and every index i E [n] the following holds: either P)(c. 12i E R] = 1, or
M(S Re,8 M(S-i),
where (S-+) is the output distribution on the dataset S-i = S (zi), and M(S-1) is the output distribution on the dataset S, conditioned on R.
To emphasize, in Definition 1 the conditional output distribution M(S models the condition "if data-point 2i is not credited by M," whereas the output distribution ((-,)) represents the counterfactual scenario "had the data-point not been seen by M."
Example 2.1 (Stable Sample Compression [8, 20]). A mechanism A 2* - e is stable sample
compression scheme of size & if for every input sequence (Z)...., 2n) there subsequence x(S) C of size (xS k such that A(S) A(T) for every intermediate subsequence xSS) C T S. See Figure for an example.
Each stable compression scheme corresponds to an (E = 0, = 0)-CCA which credits the datapoints in xS). That is, M(S) (A(S),x($)) Stable sample compression thus provides something stronger: group-counterfactuulity. meaning any subset of datapoints that is not selected does not influence the output.
Definition I not only relaxes stable sample compression, but also extends the concept of differential privacy with public data, known semi-private learning. In semi-privare learning, the learner's 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 Diffi--Diferretialll Private Mechanism). Let 5 > O; an (e, 8)-semi differentially Z** x Z* - e such that for every Spub E 2* and S "pri""
private (semi-DP) mechanism is a mapping every pair of neighboring sequences St Spriv'
M (Spub Spriv) Re M (Spubb- priv).
'In analogy to variant of differential privacy where the unit of protection the addition or removal of data point, our definition uses omissions data points. This aligns with our motivation counterfactual credit attribution: if non-credited data point is omitted (rather than replaced), the output does not change. Omission is crucial here, replacing non-credited data point with a credited one could drastically alter the output. Note that the special case of Spub = gives DP mechanism.

---

Remark 1. Any semi-DP mechanism M that uses k public points can be turned into a CCA mechanism as follows: on an input sequence S, the CCA mechanism outputs (c, R), where R Sgk= and (S.. That is, M uses the first k points in S as public data, and the rest are private.
Private learning with public data is sometimes likened to semi-supervised learning, where private data corresponds to unlabeled data and public data to labeled data. In both scenarios, the learner accesses many less informative examples (unlabeled private) and fewer more informative examples (labeled or public). Expanding on this analogy, Definition is akin to active learning, where the learner adaptively chooses which data points credit, similar selecting which data points to label in active learning.
Semi-differential privacy (Definition 2) provides stronger stability guarantees than counterfactual credit attribution (Definition 1), including for the selection process. In contrast, Definition allows for highly non-stable selection process (e.g., SVM). This leads us consider a more direct hybrid of semi-DP and sample compression, suggesting the following definition:
Definition& 3 (Sample DP-Compression Scheme). Let e, 6 O and k s n. An (E. 8) sample differentially private (n - k) -compression scheme a mechanism 2n" which consists of two functions:
1. Compression: an (E, DDD mechanism K 2" - [n]*, called the compression function, and
2. Reconstruction: an (e, () Semi-DP mechanism p 2* x 2* e called the recon- struction function.
Then, for every input sequence S:
(S) (1-xx(s)),S-x(())
where S)x(S) = (Si)tex(S) and S) = (Si)ie(())
Note that the compression function x 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 x. 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 data drawn from 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 selected. If 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 inde- pendently assigned a random label in {0. 1}. where a useful example is assigned label of 1 with probability p > 1/2, and each garbage example assigned a label of with probability 1-p p < 1/2. The value of p is set as function of the privacy parameter e.? Then, the compression function selects the first indices whose label This way, the fraction of useful points among the points
labeled is x 0.1p40.9(1-p) 9/p-8 > 0.1 (the last inequality holds for p > 1/2). See Appendix B for a more detailed argument.
0.1p
Main Theorems
In this section, present 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 (cxplicitly provided in Section 4).
We get E = In P and 6 = O. [--p)

---

Question (Guiding Question). Is learnability subject to counterfactual credit attribution (Defini- tion 1) more restricted than unconstrained learnability? learnability subject to sample DP- compression (Definition 3) more restricted than unconstrained learnability? How do these restrictions compare to differentially private learning?
Note that with respect to both Definition and Definition is clear that if k, 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 e, then an oblivious selection, such as the first k points, will suffice. Therefore, the above question is particularly interesting for values of k 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 (e = 0, 0)- counterfactual credit attribution learning rule, which selects at most logarithmic number of sample points for attribution. Remarkably, this can be achieved using the AdaBoost algorithm.
Theorem (PAC Learning with Credit Attribution = PAC Learning). Let e be concept class with VC dimension VC( E) = d < co, and let a. f denote the error and confidence parameters. Then, there exists an (E 0, 5 = 0)-CCA learning rule M that learns e with sample complexity d llogid/ +d (1/()
n n= 0
while selecting only O(d log n) examples for attribution.
We leave as open question whether & can be made independent of n. possibly by allowing and 6 to be positive. Note that an affirmative answer to this question might also shed light on the sample compression conjecture 25].
Our second theorem establishes limitation for sample DP-oompression schemes, showing that they do not offer more expressivity than differentially private PAC learning [15].
DPpprresssssnDD-P-P-oeP Theorem 2 (Sublinear Sample DP OP-Compression = Learninng) Every class e satisfies exactly one of the following:
1. e is learnable by DP-learner.
2. Any sample DP-compression scheme that learns e has size at least k = Q(1/a).
Theorem implies stark dichotomy: either a class C can be learned by a DP algorithm (equivalently size & 0), or it impossible to learn it unless with & O(d/a) a). public examples are sufficient to learn without any private examples. Theorem 2 generalizes a result by [1, Theorem 4.2) who proved it 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 the full dataset. This is not the case in semi-DP lcarning, and requires us use novel technical tools (like Theorem 3 ahead).
a sample DP-compression
Q(1/a). Notice that
Thus, 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 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 theorem addresses the limits of handpicking & points by sample DP-compression. We formalize this task as follows: given a distribution /) over 2, and an event E of 'good' points, the goal is to design a DP-compression function k 2 - [m]* that maximizes the number of selected data points that belong to E. That is, the goal is to maximize
Σ 1| EJ. TEK(S)
Example 2.2 illustrates a method that selects roughly exp(e) D(E) points from E by an (e 2 0, coooopprsnoonn function. This is a factor of exp(E) better than obliviously selecting the k points, which yields D(E) points from E. Is this factor of exp(e) optimal? Can one do better, possibly by increasing 5? The following result shows that exp(E) is asymptotically optimal.
5

---

Theorem 3. Let M be an (e, 6) sample DP-compression scheme, let 'D be a distribution over Z, and let Z. be any event, with p DE), For an input sample S == (Z)...., Zn) D", define Z = Z(S) as the random variable denoling the fraction of selected indices in K(S) whose corresponding data points belong to E. That is, Z
]K[S]] - Liex(s) 1zz EJ. Then,
pe - ōn S E|Z] S pe + Ön.
(1)
Indeed, since by convention 8 8(n) < 1 1/n, the above theorem implies that exp(E) 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 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 I and Definition 3: any learning rule adhering to either definition satisfies that its empirical error and population error 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 k k-tuple, the obtained hypothesis generalizes well. Then, we apply a union bound over all possible n² choices of k-tuples from the input sample.
Technical Background and Proofs
We study our main definitions in the context of PAC learning. Concretely, we assume that the input data domain 2 in Section 2 is X x y, for an input space X and label space y. For our purposes, == {0, 1). Learning rules are mechanisms A 2 e x 2", where e is the set of all functions mapping X to y, denoted as y We say that a distribution D over Z is realizable by a hypothesis class H c yx if for every finite sequence (x1, y1)....... (xn. drawn i.i.d from D, there exists some hypothesis h H. that satisfies h(x;)= yi. Vi E [n]. For any hypothesis h e y*, we denote its risk with respect to a distribution D by RD (h) Pr(x)) [h(x) # y].
Definition (CCA PAC learning rule). mechanism
a CCA PAC PAC learning rule a hypothesis class H. if A satisfies Definition! I, and for any distribution D realizable by H, for any a, B > 0, there exists a finite n A (a, ß), such that with probability at least 1 1 over a sample S DD" and the randomness of A, the hypothesis h in the output (h,S") of A on S satisfies (h) S
Definition 5 (Sample DP-Compression learning rule). An (E, 8) sample differentially private (n - k) compression scheme M learns a hypothesis class K s yx for any distribution D realizable by H, for any a. B > O, with probability at least 1 1 B over a sample S ~ Dn' and the randomness of M, the hypothesis (S) output by the reconstruction function in M satisfies RD(M (M() $ a.
Remark 2. Note that = 0 above, we recover the standard definition of an (a. B, e, 8)-D PAC learner (where a is the error, ß is the failure probability, and e, ö are the privacy parameters) [15].
4.1 Upper Bound: PAC learnability implies (e 6 = coountterfata credit attribution learning
Our CCA learning rule erucially 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 recent work by [12]. We use the notation S' t S for sequences S' (X x y)* that satisfy: (V(x,)) y)): (x E S = (x E S.
Definition 6 (Stable Randomized Sample Compression Scheme). A randomized sample compression scheme (Dxr p) for a class H. having failure probability & comprises of a distribution DDx over (deterministic) compression functions x : (X x x))" - (X x y)" and deterministic reconstruction function 8 p= (X x 4)* y². The compression functions x in the support Dx must satisfy
*It seems interesting to possibly consider randomized reconstruction functions as well; for our purposes, deterministic reconstruction functions suffice.

---

For any S E (X x 8)* realizable by H. if x(S) = S", then S' = S.
The reconstruction function p must satisfy
For any S (X 4)* realizable by H.
Pre-D, [3(x,)) S: p()()))())) # y) S.
randomized sample compression scheme (Dxx p) for H is stable for any S E (Xxxy)' realizable by H and S' E S, the distribution of ((S) is the same as the distribution of x(S) conditioned on ((S) S' The size s(n) of the compression scheme the supremum over E (X 8)" (realizable
by HC and in the supportt of 'Dx of the number of distinct elements in x(S).
[12] show that stable randomized compression schemes imply generalization.
Lemma 4.1 (Theorem 1.2 in [12]). Let (Dx, p) a stable randomized compression scheme for H of size snn) and failure probability &. Let D be any distribution over X x y realizable by H. For any n and β 26, with probability at least - over S D" and K ~ Dx. holds that
R>)((<((S)) & s(n) + +lg(11/))
Furthermore, they also show that there exists a stable randomized compression scheme for any hypothesis class H having finite VC dimension d. This compression scheme is based on a simple variant of AdaBoost (Algorithm in [12]). The following is contained in their work:?
Lemma 4.2 ([12)). For any hypothesis class H with VC dimension d, there exists stable randomized sample compression scheme (based AdaBoost) having failure probability & of size
snn = O (d ldg(//EE))
We are now equipped with the necessary tools required prove Theorem 1.
Proof of Theorem 1. Let 2 be any distribution realizable by H, and let S be a sample of size n drawn from D Given B. fix & B/3. From Lemma 4.2, we know that there exists a stable randomized compression scheme (D for H[ of size s(n) (d log(n/ (gg()))), and failure probability Ç. Then, since 6 22, from Lemma 4. we know that with probability least 1 f over S and k 'x.
d (og((n
R (p)((((S))) s
For the right-hand size above to be at most a, suffices to have (logld/a)+d
a
Let A be the learning rule, which when given a sample S ~ Dn as input, runs the stable randomized compression scheme from above on to obtain S' of size & (og(n))) The learner then outputs (p(S"),')) S'). By the reasoning above, p(S") has error at most with probability at least 1 - -B.
remains to argue that A is valid CCA mechanism. This follows by virtue of (Dx, being stable randomized compression scheme. Namely, for any i, S-z E S, and hence by Definition 6, the distribution of x(S,,) is identical to the distribution of (S) conditioned S; x(S). Finally, since is deterministic function of its argument, A satisfies Definition with = 5 = 0.
4.2 Lower Bound: A dichotomy for sample DP- DP-compression
Towards proving Theorem 2, we first show that a sample DP-compression scheme for the class of thresholds can be used construct DP learner for it. This lemma has a similar flavor to the public data reduction lemma (Lemma 4.4) in [1]. For a set S = Xm)), the class of thresholds over comprises of functions hi... hm such that (x,x)
íl. Vi. j [m].
9In more detail, this follows by setting the weak learning parameter a constant (e.g., 1/8) in Algorithm I in [12], and noting that such weak learner be found via empirical risk minimization.
7

---

Lemma 4.3 (Reduction from DP learner to sample DP-compression scheme). Let Km be the class of thresholds over Xxm). Suppose there exists an (ε.8) sample coooprsssoii scheme A that learns Hm with error and failure probability B = 52. and has sample complexity and - Then, there exists a (6Ake" a, to 2e, 36) - learner for
compression size k S n. Let 8 S
GAn
Hm-1 where Hm-1 is the class of thresholds over (X1.....Nmm1), with sample complexity n.
Proof. Let DD be any distribution over (x), (x] 1 x {0, 13 realizable by Hm= Given a sample S ~ 'D,, the private learner A does the following. First, it constructs sample S, also of size as follows. Initialize j = For each == ..2......!! n, toss coin (independently of the data, and other coins) that lands heads with probability p. for p to be appropriately chosen later. If the coin lands heads, 5(i = S(),, and j is incremented by 1. If the coin lands tails, 5i) is set to the designated dummy example (Xm. 1). In this way. $ is sample of size drawn from the mixture distribution δ = p. D + (1 - p)- 1 (xm..)) where (xxm.)) is a point mass on (Xm. 1). Note that since all the thresholds in Hm label xm as 1, D is realizable by Hmm
The learner A now invokes the sample DP-oompression scheme A on S. If any of the examples in the compression set constructed by Á is non-dummy element, A outputs constant hypothesis that labels all points in Km.. 1 as 1. On the other hand, all of the k examples the compression set are dummies, then A outputs the hypothesis that À outputs (restricted to .........mm.)..
We first claim that the output of A is (2c, (-:3)8ppprvvaa with respect its input S.
Claim 4.4 (A is private). A (2x, -DP.
The proof of this claim is given in Appendix A. At a high level, the privacy parameter deteriorates to 2e because of the two-step process of compressing Š to k points in an e-DP way, and then obtaining an e-DP learner thereafter.
Next, we claim that on average, there will be a lot of dummies in the compression set selected by A. This step crucially hinges on Theorem 3, where substitute the event E in the statement of the theorem to be the event that non-dummy element is selected (i.c., E is the support of the distribution D). In particular, we get that the expected number of non-dummy elements is at most kpe ōkn, which is at most 32 if we set p न and use that k 5 64n
We can now reason about the error and failure probability parameters of A. Because À is (E, 6) sample DP DP-compression scheme that successfully learns HCm with error and failure probability म.. with probability at least 5/2 over the draw of Š and the randomness of Ā, the hypothesis outputs has error at most a. Furthermore, since the expected number of non-dummy elements chosen in the compression set is at most . Markov's 's inequality gives that with probability at least - 32 over the draw of S and the randomness of Ā, all the & examples chosen by Á in the compression set dummies. By union bound, with probability at least To over the draw of $ and the randomness of A, all the examples chosen to be in the compression set by Á are dummies and the hypothesis outputs has error (with respect to 1) less than a.
But recall that the distribution D on Š is induced by the distribution D on S, 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 I over the draw of S from 1"" and the randomness of A, the hypothesis output by A has error at most a with respect to D. But since is mixture distribution,
To
(A())) 2 p (A())))
and hence we have that with probability at least 1. the error of A(S) with respect to D is at most I 64ke*a a. Thus, A is a (64ke" a, -/2 2e, 36) -DP learner for H as required.
We next state a lower bound on the sample complexity of DP learners for thresholds [2, 10). Theorem 4 (Theorem in [2]). Let Hm be the class of thresholds on (m). Let A be a 1. 0.1, 1000 log -DP learner for Kmm with sample complexity n. Then n 2 2logg m).
To T6
8

---

We are now ready prove Theorem 5, which shows that non-Littlestone [16] classes cannot be learnt by sublinear sample Dooomppessio schemes. Theorem follows from Theorem since classes that are DP-learnable are exactly the classes with finite Littlestone dimension [11].
Theorem 5. Let H be hypothesis class over X that has infinite Liulestone dimension. For E 0.05, = 3000m logn' let A be an (e,5) sample differentially private (n + k) compression scheme that learns H. with error a and failure probability 32- Then k 2 688
Proof. Because H has infinite Littlestone dimension, for any m 2 1, there exist ( .m and Hm H such that Hm is the class of thresholds over (xi.-..,
12, Theorem 3]. Now, A is an (n - k) sample DP-compression scheme that learns H:; in particular, this means that A has sample complexity n < co, and also that A learns Hmn with the same parameters and sample complexity. By Lemma 4.3, we know that there then exists a (68ka, 16. 0. 1000n² logn private learner for HCm with sample complexity n. Assume for the sake of contradiction that 68a This means that there exists a a, 16
1 1 0.1, 10000 log private learner for Hmm with sample complexity n. By Theorem 4, it
must be that n 2 Q2log" m). Since we can find Hm S H for any m 2 1, this would mean that n = co, which is a contradiction. Thus, it must be the case that s 68a
4.3 Bounded boosting of empirical measure
We prove a simplified form of Theorem 3 (with slightly tighter bounds), where we consider the input to be bit string. Theorem 3 as stated 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).
Lemma 4.5 (Bounded Boosting of Empirical Measure). Let A {0, 1)" - [n] be an (E, 6) selection mechanism. Let D be the product distribution on {0, 13" where each bit is set to 1 with probability p. For X ~ DD let Z denote the fraction of indices in A(X) at which X is I, ie.. Z= ; [je(() 1[X; 1]. Then, we have that
p 1-np(1-ph) + (1 111-ph p)
pe + +np(1-pp)
I E[Z] S
(4)
1 pet
Proof Sketch. Let A(X) / (4,, .2..... 1A) be the tuple of indices selected by the DP mechanism on input X. We first write = Σ Σ²= I11, = ii = 1]. Thereafter, the main step of the proof
uses that the mechanism is private order to relate the conditional probability Pr[!, i i|x; 1] to Pr[li = i|x; = 0] for any j [k]. Concretely, observe that
Pr[X; O =
Σ Ixc Pr[x] Pr[ = i|x]
Pr[ly = i| 0]
Pr[X| = 0]
1-p
Exc(0,1)
Pr[ of
Pr[1; = 1|.
E Exe(0.1)
Pr[x] (e Pr[ = i[x] +)
1-p
p
e <'Eee10.1
Pr[x] Prl i|x]
+ + e Pr[1y= =|x; = 1] +
where in the fourth inequality, we used that for x having x; = 1, [x 1- Pr[x], and that A is an O)D mechanism. This relation lets us express the joint probability term Pr[1; i X, = 1] in the expression E E[Z] = _ ) Σn Pr[l, = =i X; = 1] simply in terms of Pr[1, r]. Thereafter, noticing that Σn Pr[ = i = yields the result. The complete details are provided in Appendix A.
5 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.
Acknowledgements Shay Moran is a Robert J. Shillman Fellow; he acknowledges support by ISF grant 1225/20, by BSF grant 201 by Azrieli Faculty Fellowship, by Israel PBC-VATAT, by the Technion Center for Machine Learning and Intelligent Systems (MLIS), and by the the European Union (ERC, GENERALIZATIIN 101116258), as well as an ISF Grant (2188) 20). Chirag Pabbaraju is supported by Moses Charikar and Gregory Valiant's Simons Investigator Awards. Work of Kobbi Nissim was supported by NSF Grant No. CCF2217678 "DASS: Co-design of law and computer science for privacy in sociotechnical software systems" and gift to Georgetown University.
101039692). Roi Livni is supported by ERC grant (FOG,
Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
References
[1] N. Alon, R. Bassily, and S. Moran. Limits of private learning with access to public data. Advances neural information processing systems, 32, 2019. 2, 3, 4.2
[2] N. Alon, R. Livni, M. Malliaris, and S. Moran. Private pac learning implies finite littlestone di- mension. In Proceedings of the 51 Annual ACM SIGACT Symposium on Theory of Computing. pages 852-860, 2019, 4.2, 4, 4.2
[3] R. Bassily, A. Cheu, S. Moran, A. Nikolov, J. Ullman, and S. Wu. Private query release assisted by public data. In International Conference Machine Learning, pages 695-703. PMLR, 2020.
[4] A. Beimel, K. Nissim, and U. Stemmer. Private learning and sanitization: Pure vs. approximate differential privacy. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 363-378. Springer, 2013.
[5] S. Benn-Dvid, A. Bie, C. L. Canonne, G. Kamath, and V. Singhal. Private distribution learn- ing with public data: The view from sample compression. Advances in Neural Information Processing Systems, 36, 2024. 2
[6] A. Bie, G. Kamath, and V. Singhal. Private estimation with public data. Advances in neural information processing systems, 35:18653-18666, 2022. 2
[7] A. Block, M. Bun, R. Desai, A. Sheuty, and S. Wu. Oracle-efficient differentially private learning with public data. arXiv preprint arXiv:2402.09488. 2024. 2
[8] O. Bousquet, S. Hanneke, S. Moran, and N. Zhivotovskiy. Proper learning. helly number, and an optimal svm bound. In Conference on Learning Theory, pages 582-609. PMLR, 2020. 2.1
[9] O. Bousquet, R. Livni, and S. Moran. Synthetic data generatoon--squuenial and private. Advances in Neural Information Processing Systems, 33:7114-7122 2020.
[10] M. Bun, Nissim, U. Stemmer, and P. Vadhan. Differentially private release and learning of threshold functions. In V. Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science. FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 634 649. IEFE Computer Society, 2015. doi: 10. 209/FFCS.2005..55 URL https://doi org/10.
1109/FOCS. 2015 45. 4.2
[11] M. Bun, R. Livni, and S. Moran. An equivalence between private classification and online prediction. In 2020 JEEE Annual Symposium on Foundations of Computer Science Science (FOCS), pages 382-402, IEFF, 2020. 4.2
10

---

[12] A. da Cunha, K. G. Larsen, and M. Ritzert. Boosting, voting classifiers and randomized sample
compression schemes. arXiv preprint arXiv:2402.02976, 2024. 4.1, 4.1, 4.1, 4.2, 9
[13] N. Elkin-Koren, U. Hacohen, R. Livni, and S. Moran. Can copyright be reduced to privacy? arXiv preprint arXiv:2305. 14822, 2023. 1
[14] Institute for Information Law (IViR). Generative ai, copyright and the ai act. Kluwer Copy- right Blog, May 2023. URL https://cooyrrighbbloog. .ww.ioog.lllueee kluweriplaw com/ 20////222/0/0//////////
innerativeaai-opyrtte -twphhhtt-n------eeeeeeeee and-the-ai-acee Retrieved March 6, 2024. 1
[15] S. P. Kasiviswanathan, H. K. Lee, K. Nissim, Raskhodnikova, and A. Smith. What can learn privately? SIAM Journal on Computing, 40(3):793-826, 2011. 3,
[16] N. Littlestone. Learning quickly when irrelevant attributes abound: A new Innear-hreehold algorithm. Machine learning, 2:285-318, 1988. 4.2
[17] N. Littlestone and M. Warmuth. Relating data compression and learnability, 1986.
[18] T. Liu, G. Vietri, T. Steinke, J. Ullman, and Wu. Leveraging public data for practical private query release. In International Conference Machine Learning, pages 2021. 2
PMLR,
[19] A. Lowy. Z. Li. T. Huang, and M. Razaviyayn. Optimal differentially private learning with public data, arXiv preprint arXiv:2306. 15056, 2023. 2
[20] Z. Nikita. Optimal learning via local entropies and sample compression. In Conference on Learning Theory, pages 2023-2065. PMLR, 2017. 2.1
[21] F. Pinto, Y. Hu, F. Yang, and A. Sanyal. Pillar: How to make semi-private learning more effective. In 2024 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML), pages 110-139. IEEE, 2024. 2
[22] S. Scheffler, E. Tromer, and M. Varia. Formalizing human ingenuity: A quantitative framework for copyright law's ss substantial similarity. In Proceedings of the 2022 Symposium on Computer Science and Law, pages 37-49, 2022.
[23] L. G. Valiant. A theory of the learnable. Communications of the ACM, 23441111 1984.
[24] N. Vyas, S. M. Kakade, and B. Barak. On provable copyright protection for generative models.
In International Conference on Machine Learning, pages 35277-35299, PMLR, 2023.
[25] M. K. Warmuth. Compressing to ve dimension many points. In COLT, volume pages 743-744. Springer, 2003. 3

---

A Supplementary Proofs
Proof of Claim 4.4. Consider any neighboring datasets = (Z)...... ., 2i.....2n ........n) 2n) and
S' = (Z)..... 2,..... 2n) that differ at index i. Here, we using the shorthand ž, (x). We want to argue that the distribution of A(S) 22. A(S'), Let be any subset of the output space of where we used that the coins that deterine whether z; E S (or z/ St) are tossed independently of the data, and that the distribution of S conditioned on 2 & St identical to the distribution of conditioned on & E Hence, we focus on the term ( E Olai E S) in (5). We can decompose this as
A. Recall that A first constructs the sample S from and then passes to the semi-private learner
A. Then,
Pr(A(S) 0] = Pr[A(S) E Olz E Pr[zz E $1+ Pr(A(S) E Olz Pr] & $] = (r) E Olz E Pr|z/ E 5'] Pr(AA(S) E 01 & S'J Pr(z, E S1 (5)
Pr( E Olz S
Σ Pr(A(()) E Olz E S,S = 3] Pr[$ ड|2 e S]
Pr(A(S) OZ, S,5 Pr[S' 5 e S'). 8'
(6)
Here, for every term in the summation, 3' differs from 3 at exactly one index i, and we again used that the coins used to construct $ and 5' are independent of the data. Let E(3) be the event that all the k samples chosen by the semi-private learner Á when it is given 3 as input are dummies. Since 3 and 5 differ in exactly one element, because of the special property of the selection mechanism of A, we have that
Pr| Pr( e S,S e Pr(E(F))EE E =') Pr(-E(3)la, e $,5= e e" Pr(-E(3)1kk E $t 55] + +6
(7)
(8)
But note that the set of public examples is exactly the same, if (3) and E(3') respectively occur- hence, the learner in Á (which is a function of the set of public examples) that operates on the private examples in either case is identical. Furthermore, the sets of private examples themselves differ in exactly one element; we can thus use the privacy guarantees of the learner in Å to claim that
Pr[A(S) O|z E 5.5 3, E(3) & min (1,ef Pr(A(S)) e Ol4 ... = =,,) + (9)
Combining (7) and (9), we get
Pr[A(S) E Olz e S. = 3, Pr[E()) e = (min ef Pr[A(()) min -P(AA(S) 01z/ $ (r](()) e 5,5 =35=3]+6
+ Pr(E()) e $ =
min (1,e² -P(AA(S)) S' E()))( (ef- Pr[E(3') S = +8
2e Pr[A(S') E 012 e 5",5"= 3 ((")] PT(E(3) e $²,5' = =3]
(10)
Now, observe that if (3) does not occur (and correspondingly if E(3') does not occur), then we deterministically out the constant hypothesis in either case, and hence
Pr(A(S) Olz Š. 3. [3]] Pr[A(S') Ol4 S' -3.-=88EE((3))
(11)
Combining (8) and (1I), we get
Pr(A(S) E Ol2 5. = Ee Pr(A E O|2; $ S' - S (12)
5
Altogether, (10) and (12) give that
Pr(A(() E Ol2 E S, 5- =5=5] s 2t Pr(A(S)) E Ok2 E 55.5"" - 53.
12

---

Substituting in (6), we get
Pr[A(() 012 E $]
Pr(A(()) 0k S,5 3J Pr[ 5 e ST
E Pr(A((s) E = Pr[s' = 3' 51
57
8i2/68
$ 38 2
Σ Pr[A(S)) E 01 E E =" 31 e S1
= 2 Pr((((S) P 0kly E 5 36.
Finally, substituting back in (5), we get
Pr[A(() 0]
$ s(c² (P(A(()) E Ol2 E 8'1 36) Pr[z, E S'1 + Pr(A(() E Olz, $ Pr[2 e $1
S seae. (PT(AP(( Ol2 e S Pr[z/ e (1) Pr(A(S)) Ol4 $ S' Pr[z & 8']) + +
=P²-P((A(S))) 0] + 38.
By the same calculations, we also get the bound Pr[A(S)) E OJ S e² Pr(.A(S) E 0] + +6, completing the proof.
Proof of Lemma 4.5. Let A(X) = I = (11, 11.12...... 1R). Note that
%. E=
and hence
k a
EE[Z]
Prx =
Pr[x: = 1] Pr[ = =||;;
k
/=1
=p
P
Pr[l, =| 1].
(13)
k
j=l
Now, for any x E (0, 1)", let si denote x with its 7t bit flipped. Then, observe that
Pr[X: = 0 = Exe(o.1) Pr[x] Pr[Z, i|x]
Pr[l; = i| 0]
Pr 0]
1-p
Exe Pr o0 Pr[l) = 81
E Exe(0,1) Pr[x] (ef Pr[l, = :|x] + 8)
e Exxe((.))=x Pr[x] Pr[1, i|x]
+ +5= Pr[1, = i|X; = 1] + +
where in the fourth inequality, we used that for x having x; 1, Pro [x 1-2 Pr[x], and that A an (E, DDP mechanism. Hence, we have that
PIx.All, = Pr[X, = 0] Pr[l, i|X, = 0] + Pr = 1] Pr[1, = i
Xr 0] (e" Pr[1, = i|X; + Pr 1 Pr[l, i|
= (p + e (1 p)) Pr[1, (1-
(14)
Pr[l, i (1
Pr[ly = 1| 1]
(15)
p e p)
Substituting (15) in (13), we get
E 4
p k(p e1 p))
Pr[l = - (1))
(16)
j=l
13

---

Finally, note that -y= Pr[1 i] 1 for any j. Substituting in (16), we have shown the desired
lower bound
P 2-np(1-pi)
E|Z]
p+
For the upper bound, we repeat the above analysis with 7.' Lja(()) 1[x; 0J, to obtain
(1 (1- np(1 p)6
E
p + pe
But note that Z' =1 11 Z. and hence
pe + +np(1 -P)
E[Z] 11z]=1-F[[ E[Z <
1 p pe
Proof of Theorem 3. Recall that E 2 is an event satisfying D(E) = p for the given distribution D over Z. Let DIE denote the distribution D conditioned on the event E, and let DI-E denote the distribution D conditioned on the complement of event E. Assume for the sake of contradiction that either [[[Z] >
pe-tmp(l-p18 or E[Z] ptnpil-p16
p+(I-ple** Then, consider an algorithm B, that takes as input bit string Y from product distribution on {0, 1)", where each bit is independently set with probability p. Given such an input string Y, the algorithm constructs sequence S = [Zi..... Znt. where 2; 'DEE Y; = 1, and zi - otherwise. Thus, S is exactly distributed as D then passes S to the DP sample compression scheme M, which selects a compression set x(S)
I-p+pe"
is the tuple of indices that B outputs too. Note that because the compression function x is an (e, 6>-D mechanism, B is also an (e, DDD mechanism with respect to its input. To see this, consider two neighboring bit strings y.y', such that y; I and y O. We will show that Pr(2(y) E 0] s ef Pr([(yy) E 0] 6, and the same calculations will give the bound with y,y' swapped.
Pr( E] = EPIlZ-) Σ Pr[z Pr((cc) 0
Priz-il
(17)
Now, for any o E -E, we know (since is an (E, DD mechanism) that
+ 6 Pr[A(z)12z) Ols e Pr[A(zz o z/) e 0]+
and hence
(1 o +
(18)
E
Substituting (18) in (17) gives that
Pr[B(y) E 0] S e
[pIizil
Pr[z-1l Σ Prle//EE) 2/) E 0)
EEE-E
= =e (r(By' E 00) 6.
Now, by our assumption, either [E[Z] > p=--np(1-
or Z < p-np(1-p)ō But this means that
1-pape- ド 1[Y = 1]
pe(l-p)er
either E Σ 1[Y,, = =1]] pé<+np(1-p) E
ptmp(1-p16
p+(1-pie* Thus, B is an
1-p+ppe
(e, DDP selection mechanism that violates the bounds in Lemma 4.5, and hence our assumption is false.
B A DP sample compression scheme based on Randomized Response
Definition (Randomized response). LetRR {0, 13" - [n]* be the randomized response selection
mechanism defined as follows. Givenx E (0, 13"", RR flips each bit ofx independently with probability
The to obtain x. Let S = (i E [n] K 1) and S' [m] \ S. Further, let |S] = If 2 then RR oulputs uniformly random subset of k indices from S, ordered arbitrarily. Otherwise, it arbitrarily orders S, and outputs S T, where a uniformly random subset of indices chosen from S' (and ordered arbitrarily), and denotes concatenation.
14

---

Claim B.1 (RR boosts empirical measure optimally), In the setting of Lemma 4.5, let ő = 0 and let be the randomized response mechanism RR (Definition 7). Then,
(k n) p pe²)
pe
E|Z] 1 kn
exp
(19)
1+e e
1 p pe
and n 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.
Remark 3. Observe that when k
log
Proof. Recall that for X D, randomized response first constructs Y by flipping each bit of X with probability T4e7 That is, the distribution of Y is the product distribution where each Y; is 1 with 1-ptpe"
probability p. Ltpt + (1 - p) 14e I+e == Let = (i E [n] Y, = =1). We first claim that with high probability, [S] k.
To see this, note that
Pr[[S] 2 k] = 1 Pr[[S] < <k
= Pr[3S' E [n] =1)== S']
2 | PS' E [n]
2 1 (1-a)
2 n -a(nkk)
=0
where we denote the tail probability by B. Note that since we assume k = oo
logn ( B o(1.
Let I be the tuple of indices that RR outputs (note that all these indices are always distinct). Recall that, if [S] 2 k, then Y; = 1 for all i E 1. Let Zi Liez [V; = 1] and Zo = Liel [[; = O]. Then have that
E[ 2 k Pr[[S] 2 2
E [o] S kB.
Markov's 's inequality then gives that Pr[Zo 2 1] S kB. Thus, with probability least 1 kB, have that Y, = for all (distinct) indices output by RR: let G denote this event.
Finally, let Z 1 iir 1[x; 1]. Then, have that
[[Z] 2 Pr[G] G
2 (1 - kp) E[Z|G]
kB) Σ
Pr[l (4..... [HG] E[ZIG (h..... ..4..
(20)
But observe that
E E| 1= (h..... ix)l
Σ
Pr[X; 1|,, 1]
Pr[x, = 1 1AYY=11
Pr[Y,
Jell
Σ
p Tto
je(
P.
loer
(1 p) Ite
pet
P + pe
15

---

Substituting in (20) and plugging in the expression for B, we get the desired bound
(k n1 + p+))
))
pe
E [2] z
1 kn exp
1 e
1- p pe
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: claim to study credit attribution in machine learning algorithms in the abstract, and our main results (Definitions 1, and Theorems 2) are precisely about this.
Guidelines:
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.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
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 single definition is likely not going to be all- 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 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 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 thors 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance the approach. For example, 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 provide closed captions for online lectures because it fails 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, 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 impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
17

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
We state all the assumptions in our theorems, and also provide complete
proofs/references.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed reproduce the main perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reprodueibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions provide some reasonable avenue for reproducibility, which may depend the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (c.g., with an open-souree dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path reproducing verifying the results.
18

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
wwt.SSbwwisssooooooioooooooooooe iy) for more details.
While we encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips. cc/ hts//ublic/gguu hetee/guideeeeeeee / wwtsSuuuiiisiiiiiii ssissssoooo ssionPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
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, confi-
dence intervals, statistical significance tests, 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 with given experimental conditions).
19

---

The method for calculating the error bars should be explained (closed form formula, call 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.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
Our work conforms to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations 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 algo- rithms. The hope 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 work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
20

---

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 spe- cific 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse 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 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
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 dataset.
The authors should state which version of the asset used and, possible, include 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.
21

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. cww datastsss has curated licenses for some datasets. Their licensing guide can help determine the license of 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 available online, the authors encouraged reach out the asset's creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release any assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our work does not entail crowdsourcing experiments research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material fine, but if the main contri- bution of the paper involves human subjects, then much detail possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Not applicable for the same reason as above.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
22

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere 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.
23


Reviews:
[{"review_id": "UPwnvxGJwc", "reviewer": "Reviewer_JBKH", "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. \n\nThe 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.\n\nThe authors give an example showing that their definition is not vacuous and go on to state three theorems:\n1. PAC learnable classes with VC dimension $d$ admit solutions with valid credit attribution and only $O(d\\log n)$ many samples.\n2. 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.\n3. 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.", "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.\n\nAdditional questions/notes: \n1. 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?\n2. 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": "Yes, limitations have been adequately discussed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. This paper considers an important problem and comes up with a very reasonable definition to address it. Basing their notion of indistinguishability on that which is used in DP has found some mainstream and legal acceptance as well as far as I know, so in principle this might turn out to be quite viable.\n2. The directions of inquiry (comparison with random subsampling, sample complexity, checking for potential vacuousity) are all good.", "weaknesses": "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.\n2. 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.\nOne 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for reading our paper, and for your comments. We are glad you liked our paper!\n\nWith regards to the points you bring up:\n> 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.\n\nThis 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.\n> 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.\n\nThis 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.\n> 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?\n\nThanks, we will make this change.\n> 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.\n\nThis 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.\n\n---\nPlease let us know if we can help answer any more questions!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EzMu0eZn6L", "reviewer": "Reviewer_jYet", "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.", "questions": "1. See weaknesses\n2. Could the authors explain the difference or connection between Definition 3 and adaptive composition + post-processing in DP?", "limitations": "NA", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper introduces novel definitions of stability that allow weaker stability of the designed subset of the data points.\n2. This framework extends notions of stability, including Differential Privacy, differentially private learning with public data, and stable sample compression.", "weaknesses": "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?\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for reading our paper, and for your comments.\n\nWith regards to addressing the weaknesses/questions:\n\n> 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?\n\nExample 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.\n\nIn 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.\n\n> 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.\n\nThis 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.\n\n> Could the authors explain the difference or connection between Definition 3 and adaptive composition + post-processing in DP?\n\nRecall 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.\n\n---\nWe hope our response addresses your concerns. Please let us know if we can answer any further questions!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8BT2WnHxeF", "reviewer": "Reviewer_nyTY", "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.", "questions": "Please clarify my concerns in the weaknesses section. Additionally, please point out if I made any mistakes in the review.\n\nI 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": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The proposed credit attribution notion is interesting, and the established relationship between this notion, semi-differential privacy, and stable sample compression is intriguing. The PAC learning part seems correct, and the results intuitively make sense, even though I haven't read the detailed proof.", "weaknesses": "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:\n\n1. 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\").\n\n\nTo 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.\n\n2. 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?\n\nIt would be a significant enhancement if the authors could establish a solid mathematical relationship between these three definitions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nWe now address your concerns:\n\n> 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\").\n\nPlease 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.\n\n> 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.\n\nWe 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. \n\nAs 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. \n\n> 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?\n\n\nThanks, we will add a detailed proof to how a semi-DP can be turned into a CCA mechansim in the final version.\nRoughly, every semi-DP mechanism $M$ with $k$ public datapoints defines a CCA mechanism $A$ as follows:\n\nFor a dataset $S$, the CCA mechanism $A$ outputs $(h, R)$, where $R$ is the first $k$ datapoints in  $S$.\nThe 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. \n\n---\nWe hope that our response addresses your concerns. Please let us know if we can answer any more questions!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tZaffWhSd3", "reviewer": "Reviewer_ariQ", "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.", "questions": "1. How could this framework be extended to generative models, such as text and image generators?\n2. 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": "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.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper proposes formal definitions for credit attribution.\n2. It shows that every PAC learnable class can also be learned using a CCA learning rule.\n3. It connects CCA and sample compression to differential privacy.\n4. It characterizes the expressive power of different learning rules, such as CCA, sample compression, and differentially private learning, using the PAC learning framework.", "weaknesses": "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.\n2. 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.\n3. 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.\n4. The intuition behind semi-differentially private learning is not very clear. An explanation using a concrete example would be helpful.\n\nMinor Correction: Sec 2, Line 71: X* -> Z*", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for reading our paper, and for your comments.\n\nWith regards to the weaknesses you bring up:\n> 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. \n2. 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.\n\nOur 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. \n\n> 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.\n\nWe 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. \n\n> 4. The intuition behind semi-differentially private learning is not very clear. An explanation using a concrete example would be helpful.\n\nSemi-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].\n\n[1] Amos Beimel, Kobbi Nissim, and Uri Stemmer. Private learning and sanitization: Pure vs. approximate differential privacy.\n\n[2] Amos Beimel, Kobbi Nissim, and Uri Stemmer. Learning privately with labeled and unlabeled examples.\n\n[3] Noga Alon, Raef Bassily, and Shay Moran. Limits of private learning with access to public data.\n\n---\nWith regards to your questions:\n\n> 1. How could this framework be extended to generative models, such as text and image generators?\n\nThanks 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.\n\n> 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)?\n\nMechanisms 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.\n\n---\nPlease let us know if we can answer any more questions!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank the reviewers for taking the time to read the manuscript. We would like to reiterate that in this work, we present a first candidate notion of learning with credit attribution as well as provide a first characterization of PAC learnability under credit attribution. **This should be regarded as the scope of the current work.**

The reviewers have suggested several interesting and important open problems as well as future directions of research which we find all to be of great interest. We do want to emphasize, though, that while these suggestions highlight the potential of further study of credit attribution, our work is focused on presenting a model for credit attribution and initiates basic research of this model. We ask the reviewers to take this into account, and focus their assessment of our work as much as possible on the scope of this work and not on future study.

Meta-review: 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".
Decision: Accept (poster)