betaFeedback

WorksComputer Science

Should We Combine Our Data? Algorithms and Limits for Privately Assessing Data Sharing

Abstract

In this paper, we study when two parties should pool their data to train a machine learning model. Two agents, Alice and Bob, each hold a sensitive labeled dataset and want to train a classifier from a given hypothesis class H\mathcal{H}. Even when each party's dataset can be perfectly classified on its own, the two parties may follow conflicting labeling standards or have selection biases that affect their features and label sets, such that no single classifier in H\mathcal{H} fits their combined data. Before committing to data sharing, Alice and Bob therefore want to test whether a single classifier in H\mathcal{H} can jointly fit both datasets—without revealing their individual data points to one another. We formalize this problem from a learning-theoretic viewpoint via opt⁡H\operatorname{opt}_\mathcal{H}, the minimum number of mistakes made by any hypothesis in H\mathcal{H} on their pooled data. Through interactive communication, the agents must distinguish opt⁡H=0\operatorname{opt}_\mathcal{H}=0 (compatible datasets) from opt⁡H≥t\operatorname{opt}_\mathcal{H}\geq t (conflicting datasets) under pure ε\varepsilon-two-party differential privacy. A trusted curator could do this with t=O(1/ε)t=O(1/\varepsilon), and we ask how small tt can be without one. For thresholds on the real line over a domain of size mm, we show that the optimal tt is Θ~(log⁡log⁡m/ε)\tildeΘ(\log\log m/\varepsilon), exponentially smaller than the Θ(log⁡m/ε)Θ(\log m/\varepsilon) samples needed to privately learn thresholds, even with a curator. For halfspaces in Rd\mathbb{R}^d, the dependence on mm jumps to log⁡(m)\log(m): we give a protocol with t=O~(d3log⁡m/ε)t=\tilde{O}(d^3\log m/\varepsilon) and show that some domains require t=Ω(dlog⁡(m/d)/ε)t=Ω(d\log(m/d)/\varepsilon).

Introduction

Institutions often hold complementary datasets that capture different aspects of the same downstream learning task. For example, a breast screening clinic may hold primarily negative cases, while a specialized diagnostic center may hold a much higher proportion of confirmed cancer cases [35, 43]. Similarly, organizations trying to detect cybersecurity incidents frequently share data to provide a comprehensive view of the cybersecurity landscape, as attackers may target different organizations with different exploits at different times [13]. In such settings, pooling data may enable institutions to learn a useful classifier that no entity could learn on its own. Indeed, this potential was highlighted and analyzed in early theoretical works on distributed machine learning [3]. Realizing the potential benefit of collaboration, however, often requires institutions to commit resources upfront through legal agreements, financial compensation, governance approvals, and dedicated infrastructure. Before incurring these costs, institutions need to assess the utility of combining their datasets: will pooling improve model accuracy or other downstream metrics enough to justify the collaboration? Yet this assessment depends on joint properties of the datasets, generally hidden from each institution’s local view. Institutions face a circular dilemma: they must judge whether collaboration is worthwhile before committing, yet doing so may require the very data sharing whose value they seek to assess.

Privacy requirements further complicate this dilemma. Hospitals, for example, must protect sensitive patient records even when sharing them would help evaluate a collaboration. Institutions may also hesitate to disclose valuable data to a prospective partner who could use them independently and decline to collaborate. When no trusted third party is available, each party must therefore assess whether collaboration is promising while limiting what it reveals about its data. This tension between the need to preserve data privacy while enabling agents to assess the utility of collaboration motivates the main conceptual question of this paper: How can agents estimate whether it is beneficial to combine their datasets while preserving the privacy of individual records? What algorithms can achieve this goal, and what are their fundamental limits?

How to Assess the Benefits of Data Sharing?

In this section, we propose a learning-theoretic notion that agents can use to assess the value of data sharing and provide two real-world scenarios in which it can inform the decision to collaborate. Our focus throughout the paper is on binary classification on a data space (or feature space) X⊆Rd\mathcal{X} \subseteq\mathbb{R}^{d} of size mm for some d≥1d \ge1 and a fixed publicly known hypothesis class H⊆{±1}X\mathcal{H} \subseteq\{\pm1\}^{\mathcal{X}}. We consider a setting with two agents, Alice (AA) and Bob (BB) who respectively hold a labeled dataset SA,SB∈(X×{±1})nS_A, S_B \in(\mathcal{X} \times\{\pm1\})^n of size n∈Nn \in\mathbb{N}.

We focus on a basic question that arises before joint training: can a single classifier in a given hypothesis class explain both parties’ data? We formalize this question using their joint empirical loss defined as

opt⁡H(SA,SB):=min⁡h∈H∑U∈{A,B}∑(x,y)∈SU1{h(x)≠y}.(1)\operatorname{opt}_{\mathcal{H}}(S_A,S_B) := \min_{h \in\mathcal{H}} \sum_{U \in\{A,B\}} \sum_{(x,y) \in S_U} \mathbf{1}\{h(x) \ne y\}. \tag*{(1)}

We use opt⁡H(SA,SB)\operatorname{opt}_{\mathcal{H}}(S_A,S_B), the number of mistakes made on the pooled data by the best classifier in H\mathcal{H}, to assess the value of combining the data. It is zero when one hypothesis explains both datasets, and large when every hypothesis in H\mathcal{H} makes many mistakes on their union. A large joint loss may indicate conflicting labeling practices, selection biases causing missing features and labels, or that the hypothesis class is not complex enough to fit the combined data.

We therefore focus on distinguishing between the following:

opt⁡H(SA,SB)=0opt⁡H(SA,SB)≥t(2)\operatorname{opt}_{\mathcal{H}}(S_A,S_B) = 0 \qquad\qquad \operatorname{opt}_{\mathcal{H}}(S_A,S_B) \ge t \tag*{(2)}

for some t>0t > 0. When opt⁡H(SA,SB)=0\operatorname{opt}_{\mathcal{H}}(S_A,S_B) = 0, Alice and Bob agree to collaborate. When opt⁡H(SA,SB)≥t\operatorname{opt}_{\mathcal{H}}(S_A,S_B) \ge t, Alice and Bob must reassess2. Finally, if 0<opt⁡H(SA,SB)<t0 < \operatorname{opt}_{\mathcal{H}}(S_A,S_B) < t, we make no claims, as is standard in distribution testing. We now present two examples that further motivate the property-testing problem in (2).

Example 1 (Learning from disparate label sets). Suppose Alice is a screening clinician and Bob is a diagnostician. They want to develop a classifier to determine whether a patient in a target population should be referred for further diagnostic testing. Their datasets reflect different stages of care: Alice’s screening dataset SAS_A mainly contains records of patients who were not referred, whereas Bob’s diagnostic dataset SBS_B contains only records of patients who were referred and received more thorough testing [24]. Since the records contain sensitive patient information, neither agent is willing to disclose individual records to assess a possible collaboration, and no trusted third party is available. To isolate this selection bias, suppose Alice’s labels are all −1-1, and Bob’s are all +1+1. Then, neither can train a useful model alone; they must assess opt⁡H(SA,SB)\operatorname{opt}_{\mathcal{H}}(S_A,S_B) to determine whether they can train a low-error model on their joint data.

Example 2 (Identifying conflicting labeling practices). Now suppose Alice has labeled spam and non-spam emails in her dataset. However, her data may be limited or imbalanced, so she wants to augment it with Bob’s curated, labeled email dataset. The challenge is that Bob may have a different view of what constitutes spam, so his labels could conflict with Alice’s data [29]. For example, Alice may label unsolicited promotional emails as spam, while Bob uses that label for fraudulent or malicious messages. Before joint training, Alice wants to know whether a single classifier can achieve a sufficiently low test error under both labeling policies. To isolate conflicting labeling practices, suppose the agents encounter the same distribution of emails but may assign different labels to the same email. In this case, opt⁡H(SA,SB)=0\operatorname{opt}_{\mathcal{H}}(S_A,S_B)=0 indicates that, under the hypothesis class HH, Alice’s and Bob’s labeling practices are compatible, implying a collaboration may be worthwhile. On the other end, opt⁡H(SA,SB)≥t\operatorname{opt}_{\mathcal{H}}(S_A,S_B)\ge t points to differing labeling practices.

Remark 1.1 (From in-sample to in-population error). Note that our insights extend beyond the in-sample case and hold when considering generalization error over the underlying population distributions. We provide more details using standard arguments in Appendix § 7.

Problem Formalization

In this section, we formalize our problem and state our main technical question. We first consider the disjoint-label setting as in Example 1, where Alice holds only negatively labeled examples, and Bob holds only positively labeled ones. Since the labels are fixed by the party holding each record, we suppress them and write SA,SB∈XnS_A, S_B \in\mathcal{X}^n. This setting isolates the joint aspect of the problem: when H\mathcal{H} contains the constant predictors, each local dataset is perfectly realizable, but their union need not be. Thus, the local optimal errors alone do not determine whether a common classifier can explain both datasets. For our algorithms, we later show that they extend to datasets with arbitrary label mixtures (see Corollaries 4.8 and 3.13).

The definition of opt⁡H\operatorname{opt}_{\mathcal{H}} in Equation (1) in the disjoint-label setting can be rewritten as

opt⁡H(SA,SB)≜min⁡h∈H{∑xA∈SA1{h(xA)≠−1}+∑xB∈SB1{h(xB)≠+1}}.(3)\operatorname{opt}_{\mathcal{H}}(S_A,S_B) \triangleq\min_{h\in\mathcal{H}}\left\{\sum_{x_A\in S_A}\mathbf{1}\{h(x_A)\ne-1\}+\sum_{x_B\in S_B}\mathbf{1}\{h(x_B)\ne+1\}\right\}. \tag*{(3)}

To assess a potential collaboration, the agents first agree on an error threshold t∈[2n]t\in[2n]. They seek a private assessment algorithm that rejects with high probability when every classifier in H\mathcal{H} makes at least tt mistakes on the pooled data, i.e., opt⁡H(SA,SB)≥t\operatorname{opt}_{\mathcal{H}}(S_A,S_B)\ge t. We call this requirement soundness. However, a trivial algorithm that always rejects also satisfies soundness. We therefore also require the algorithm to accept with high probability when the pooled data are jointly realizable, i.e., opt⁡H(SA,SB)=0\operatorname{opt}_{\mathcal{H}}(S_A,S_B)=0, a requirement we call completeness. Finally, to protect the privacy of individual records throughout the interaction, we use differential privacy [17] in its two-party form [8, 37], which requires each agent’s view to be differentially private with respect to the other agent’s dataset (see Definition 2.1). We combine these pieces and formally define the two-party algorithm for dataset valuation as follows:

Definition 1.2 (ε\varepsilon-DP tester with resolution tt). Fix a data space X\mathcal{X}, a hypothesis class H⊂{±1}X\mathcal{H} \subset\{\pm1\}^{\mathcal{X}}, a dataset size n∈Nn \in\mathbb{N}, a privacy parameter ε>0\varepsilon> 0, and t∈[2n]t \in[2n]. Let Π\Pi be an almost-surely terminating interactive two-party protocol on all pairs of finite multisets over X\mathcal{X}, with common output in {Match,Far}\{\mathrm{Match}, \mathrm{Far}\}. We interpret these outputs as acceptance or rejection of the proposed collaboration at this preliminary stage, respectively. We call Π\Pi an ε\varepsilon-private tester with resolution tt for H\mathcal{H} at dataset size nn if it satisfies the following requirements:

  1. Privacy. Π\Pi satisfies ε\varepsilon-two-party differential privacy as in Definition 2.1 for every input SA,SB∈XnS_A, S_B \in\mathcal{X}^n

  2. Soundness. For every SA,SB∈XnS_A, S_B \in\mathcal{X}^n s.t. opt⁡H(SA,SB)≥t\operatorname{opt}_{\mathcal{H}}(S_A, S_B) \ge t, we have Pr⁡[Π(SA,SB)=Far]≥0.9\Pr[\Pi(S_A, S_B) = \mathrm{Far}] \ge0.9.

  3. Completeness. For every SA,SB∈XnS_A, S_B \in\mathcal{X}^n, s.t. opt⁡H(SA,SB)=0\operatorname{opt}_{\mathcal{H}}(S_A, S_B) = 0, we have Pr⁡[Π(SA,SB)=Match]≥0.9\Pr[\Pi(S_A, S_B) = \mathrm{Match}] \ge0.9.

The probabilities are over the protocol’s private and public randomness.

We seek the smallest achievable resolution tt, since smaller values let agents enforce stricter error tolerances. Without privacy constraints, the agents can exchange their datasets and compute opt⁡H(SA,SB)\operatorname{opt}_{\mathcal{H}}(S_A, S_B) exactly, achieving t=1t = 1, the best possible resolution. A trusted curator could also ensure differential privacy by releasing opt⁡H(SA,SB)+Lap⁡(1/ε)\operatorname{opt}_{\mathcal{H}}(S_A, S_B) + \operatorname{Lap}(1/\varepsilon), since the joint loss has sensitivity one. This gives a tester with resolution tcentral=O(1/ε)t_{\mathrm{central}} = O(1/\varepsilon), independent of the dimension and hypothesis class. However, we require information-theoretic two-party differential privacy without a trusted curator. This motivates the main technical question that our paper seeks to answer:

For fixed H\mathcal{H} and ε\varepsilon, what is the smallest resolution tt that an ε\varepsilon-DP private tester can guarantee?

Our Results

We answer the above technical question for two fundamental classes of hypotheses: thresholds on the real line and half-spaces in Rd\mathbb{R}^d. For each class, we establish both upper and lower bounds on the optimal resolution tt of any ε\varepsilon-private tester (summarized in Table 1). Notably, our main interactive protocols achieve a resolution tt that is *completely independent of the dataset size nn, and all of our upper bounds extend immediately from the disjoint-label setting to arbitrary mixed-label datasets (see Corollaries 4.8 and 3.13).

ClassUpper boundLower bound
Thresholds in R\mathbb{R}log⁡log⁡mεlog⁡(log⁡log⁡mε)\frac{\log\log m}{\varepsilon}\log\left(\frac{\log\log m}{\varepsilon}\right)log⁡log⁡mε\frac{\log\log m}{\varepsilon}
Halfspaces in Rd\mathbb{R}^{d}min⁡{d2log⁡(2m)ε(d+log⁡(log⁡(2m))),(n2dlog⁡(2m)ε)1/3,n}\min\left\{\frac{d^{2}\log(2m)}{\varepsilon}(d+\log(\log(2m))),\left(\frac{n^{2}d\log(2m)}{\varepsilon}\right)^{1/3},n\right\}min⁡{d,nε}εlog⁡(2+min⁡{md,nεd2})\frac{\min\{d,\sqrt{n\varepsilon}\}}{\varepsilon}\log\left(2+\min\left\{\frac{m}{d},\frac{n\varepsilon}{d^{2}}\right\}\right)†

Table 1. Bounds on the error gap tt for pure ε\varepsilon-two-party DP testing with success probability at least 0.9, up to universal constant factors. † The halfspace lower bound holds for some input domains, d≥d0d \ge d_{0}, m≳dm \gtrsim d, and sufficiently small ε\varepsilon.

Thresholds on Real Line

We start with the simplest nontrivial class, thresholds on the real line, where each hypothesis labels a point positive exactly when it lies at or above a cutoff θ\theta:

Hthr={hθ:R→{±1}∣∃θ∈R s.t. hθ(x)=1 for x≥θ and hθ(x)=−1 for x<θ}.(4)\mathcal{H}_{\mathrm{thr}} = \{h_\theta: \mathbb{R} \to\{\pm1\} \mid\exists\theta\in\mathbb{R}\ \text{s.t.}\ h_\theta(x) = 1\ \text{for}\ x \ge\theta\ \text{and}\ h_\theta(x) = -1\ \text{for}\ x < \theta\}. \tag*{(4)}

Our main result for this class is as follows:

Theorem 1.3 (Informal Version of Theorems 3.1 and 3.12). Fix m,n∈Nm, n \in\mathbb{N} and ε∈(0,1]\varepsilon\in(0, 1]. For every domain X⊂R\mathcal{X} \subset\mathbb{R} with ∣X∣=m|\mathcal{X}| = m, provided n,t≳log⁡log⁡mεlog⁡(log⁡log⁡mε)n, t \gtrsim\frac{\log\log m}{\varepsilon}\log\left(\frac{\log\log m}{\varepsilon}\right), there exists an interactive, randomized, and polynomial-time algorithm that is an ε\varepsilon-DP tester with resolution tt for Hthr\mathcal{H}_{\mathrm{thr}}. Moreover, for every domain X⊂R\mathcal{X} \subset\mathbb{R} with ∣X∣=m|\mathcal{X}| = m, every ε\varepsilon-DP tester with resolution t∈[n]t \in[n] for Hthr\mathcal{H}_{\mathrm{thr}} requires t≳log⁡log⁡mεt \gtrsim\frac{\log\log m}{\varepsilon}.

Next, we mention a few implications of this result:

  • Minimal overhead compared to the centralized/non-private setting: Recall that a trusted curator achieves resolution O(1/ε)O(1/\varepsilon) for every hypothesis class. In comparison, two-party differential privacy introduces only an O~(log⁡log⁡m)\widetilde{O}(\log\log m) dependence on the domain size mm, negligible in most practical settings.

References

  1. [1]H. J. Asghar, Z. Lu, Z. Zhao, and D. Kaafar. “Practical, private assurance of the value of collaboration via fully homomorphic encryption”. arXiv preprint arXiv:2310.02563 (2023).arxiv.org/abs/2310.02563
  2. [2]M.-F. Balcan, E. Blais, A. Blum, and L. Yang. “Active property testing”. In: 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science. IEEE. 2012, pp. 21–30.
  3. [3]M. F. Balcan, A. Blum, S. Fine, and Y. Mansour. “Distributed learning, communication complexity and privacy”. In: Conference on Learning Theory. JMLR Workshop and Conference Proceedings. 2012, pp. 26–1.arxiv.org/abs/1204.3514
  4. [4]O. Bousquet, S. Boucheron, and G. Lugosi. “Introduction to statistical learning theory”. In: Summer school on machine learning. Springer, 2003, pp. 169–207.DOI
  5. [5]A. Blum and L. Hu. “Active tolerant testing”. In: Conference On Learning Theory. PMLR. 2018, pp. 474–497.arxiv.org/abs/1711.00388
  6. [6]M. Braverman, G. Kol, S. Moran, and R. R. Saxena. “Convex set disjointness, distributed learning of halfspaces, and LP feasibility”. arXiv preprint arXiv:1909.03547 (2019).arxiv.org/abs/1909.03547
  7. [7]A. Blum, K. Ligett, and A. Roth. “A learning theory approach to noninteractive database privacy”. Journal of the ACM (JACM) 60.2 (2013), pp. 1–25.DOI
  8. [8]A. Beimel, K. Nissim, and E. Omri. “Distributed private data analysis: Simultaneously solving how and what”. In: Annual International Cryptology Conference. Springer. 2008, pp. 451–468.DOI
  9. [9]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. Springer. 2013, pp. 363–378.arxiv.org/abs/1407.2674
  10. [10]M. Braverman and O. Weinstein. “A Discrepancy Lower Bound for Information Complexity”. CoRR abs/1112.2000 (2011).arxiv.org/abs/1112.2000
  11. [11]C. Carathéodory. “Über den Variabilitätsbereich der Koeffiziente von Kraftwerkreihen, die gegebene Werte nicht nehmen”. Mathematical Annals 64.1 (1907), pp. 95–115.DOI
  12. [13]K. Chang and H. Huang. “Exploring the management of multi-sectoral cybersecurity information-sharing networks”. Government Information Quarterly 40.4 (2023), p. 101870.DOI
  13. [14]R. B. Christensen, S. R. Pandey, and P. Popovski. “Semi-Private Computation of Data Similarity with Applications to Data Valuation and Pricing”. IEEE Transactions on Information Forensics and Security 18 (2023), pp. 1978–1988.DOI
  14. [15]R. Compton, L. Zhang, A. Puli, and R. Ranganath. “When More is Less: Incorporating Additional Datasets Can Hurt Performance By Introducing Spurious Correlations”. In: Proceedings of the 8th Machine Learning for Healthcare Conference. Vol. 219. Proceedings of Machine Learning Research. PMLR, 2023, pp. 110–127.arxiv.org/abs/2308.04431
  15. [16]K. Dutta, A. Ghosh, and S. Moran. “Uniform Brackets, Containers, and Combinatorial Macbeath Regions”. In: 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Ed. by M. Braverman. Vol. 215. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, 59:1–59:10. ISBN: 978-3-95977-217-4.arxiv.org/abs/2111.10048
  16. [17]C. Dwork, F. McSherry, K. Nissim, and A. Smith. “Calibrating noise to sensitivity in private data analysis”. In: Theory of cryptography conference. Springer. 2006, pp. 265–284.
  17. [18]J. Feldman, T. Malkin, R. A. Servedio, C. Stein, and M. J. Wainwright. “LP decoding corrects a constant fraction of errors”. IEEE Transactions on Information Theory 53.1 (2007), pp. 82–89.
  18. [19]M. F. Flanagan, V. Skachek, E. Byrne, and M. Greferath. “Linear-programming decoding of nonbinary linear codes”. IEEE Transactions on Information Theory 55.9 (2009), pp. 4134–4154.arxiv.org/abs/0707.4360
  19. [20]Y. Fu, T. Wang, and V. Chandrasekaran. “Challenges in Enabling Private Data Valuation”. arXiv preprint arXiv:2603.00342 (2026).arxiv.org/abs/2603.00342
  20. [21]J. Feldman, M. J. Wainwright, and D. R. Karger. “Using linear programming to decode binary linear codes”. IEEE Transactions on Information Theory 51.3 (2005), pp. 954–972.
  21. [22]V. Feldman and D. Xiao. “Sample complexity bounds on differentially private learning via communication complexity”. In: Conference on Learning Theory. PMLR. 2014, pp. 1000–1019.arxiv.org/abs/1402.6278
  22. [23]K. Fuentes, M. Xu, and I. Y. Chen. “Dataset-to-Dataset Evaluation Before (and Without) Sharing Data”. In: Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society. Vol. 8. 1. 2025, pp. 963–977.DOI
  23. [24]J. A. de Groot, P. M. Bossuyt, J. B. Reitsma, A. W. Rutjes, N. Dendukuri, K. J. Janssen, and K. G. Moons. “Verification problems in diagnostic accuracy studies: consequences and solutions”. Bmj 343 (2011).DOI
  24. [25]F. Garrido-Lucero, B. Heymann, M. Vono, P. Loiseau, and V. Perchet. “DU-Shapley: A Shapley Value Proxy for Efficient Dataset Valuation”. In: Advances in Neural Information Processing Systems. Vol. 37. 2024.
  25. [26]A. Ghorbani and J. Zou. “Data Shapley: Equitable Valuation of Data for Machine Learning”. In: Proceedings of the 36th International Conference on Machine Learning. Vol. 97. Proceedings of Machine Learning Research. PMLR, 2019, pp. 2242–2251.arxiv.org/abs/1904.02868
  26. [27]R. Jia, D. Dao, B. Wang, F. A. Hubis, N. Hynes, N. M. Gürel, B. Li, C. Zhang, D. Song, and C. J. Spanos. “Towards Efficient Data Valuation Based on the Shapley Value”. In: Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics. Vol. 89. Proceedings of Machine Learning Research. PMLR, 2019, pp. 1167–1176.arxiv.org/abs/1902.10275
  27. [29]J.-C. Klie, R. E. d. Castilho, and I. Gurevych. “Analyzing dataset annotation quality management in the wild”. Computational Linguistics 50.3 (2024), pp. 817–866.arxiv.org/abs/2307.08153
  28. [30]P. W. Koh and P. Liang. “Understanding Black-box Predictions via Influence Functions”. In: Proceedings of the 34th International Conference on Machine Learning. Vol. 70. Proceedings of Machine Learning Research. PMLR, 2017, pp. 1885–1894.arxiv.org/abs/1703.04730
  29. [31]D. Kane, R. Livni, S. Moran, and A. Yehudayoff. “On communication complexity of classification problems”. In: Conference on Learning Theory. PMLR. 2019, pp. 1903–1943.
  30. [32]P. Kothari, A. Nayyeri, R. O’Donnell, and C. Wu. “Testing surface area”. In: Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. SIAM. 2014, pp. 1204–1214.
  31. [33]M. Kearns and D. Ron. “Testing Problems with Sublearning Sample Complexity”. Journal of Computer and System Sciences 61.3 (2000), pp. 428–456.DOI
  32. [34]W. Kong and G. Valiant. “Estimating learnability in the sublinear data regime”. Advances in Neural Information Processing Systems 31 (2018).arxiv.org/abs/1805.01626
  33. [35]C. D. Lehman, R. F. Arao, B. L. Sprague, J. M. Lee, D. S. M. Buist, K. Kerlikowske, L. M. Henderson, T. Onega, A. N. A. Tosteson, G. H. Rauscher, and D. L. Miglioretti. “National Performance Benchmarks for Modern Screening Digital Mammography: Update from the Breast Cancer Surveillance Consortium”. Radiology 283.1 (2017), pp. 49–58.DOI
  34. [36]P. McMullen. “The maximum numbers of faces of a convex polytope”. Mathematika 17.2 (1970), pp. 179–184.DOI
  35. [37]A. McGregor, I. Mironov, T. Pitassi, O. Reingold, K. Talwar, and S. Vadhan. “The Limits of Two-Party Differential Privacy”. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science. 2010, pp. 81–90.
  36. [38]F. McSherry and K. Talwar. “Mechanism design via differential privacy”. In: 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07). IEEE. 2007, pp. 94–103.
  37. [39]P. Nakkiran, G. Kaplun, Y. Bansal, T. Yang, B. Barak, and I. Sutskever. “Deep Double Descent: Where Bigger Models and More Data Hurt”. In: International Conference on Learning Representations. 2020.arxiv.org/abs/1912.02292
  38. [40]K. K. Patel, S. P. Karimireddy, R. C. Fernandez, and M. Zampetakis. “Limits and Potential of Score-Based Data Valuation: Redundancy, Complementarity, and Non-Monotonicity”. In: Advances in Neural Information Processing Systems. Accepted. 2026.
  39. [41]T. Richardson and R. Urbanke. Modern Coding Theory. Cambridge: Cambridge University Press, 2008.DOI
  40. [42]A. Rao and A. Yehudayoff. Communication Complexity and Applications. Cambridge University Press, 2020.
  41. [43]B. L. Sprague, R. F. Arao, D. L. Miglioretti, L. M. Henderson, D. S. M. Buist, T. Onega, G. H. Rauscher, J. M. Lee, A. N. A. Tosteson, K. Kerlikowske, C. D. Lehman, and Breast Cancer Surveillance Consortium. “National Performance Benchmarks for Modern Diagnostic Digital Mammography: Update from the Breast Cancer Surveillance Consortium”. Radiology 283.1 (2017), pp. 59–69.DOI
  42. [44]N. Sauer. “On the density of families of sets”. Journal of Combinatorial Theory, Series A 13.1 (1972), pp. 145–147.DOI
  43. [45]S. Shelah. “A combinatorial problem; stability and order for models and theories in infinitary languages”. Pacific Journal of Mathematics 41.1 (1972), pp. 247–261.DOI
  44. [46]Z. Tian, J. Liu, J. Li, X. Cao, R. Jia, J. Kong, M. Liu, and K. Ren. “Private Data Valuation and Fair Payment in Data Marketplaces”. arXiv preprint arXiv:2210.08723 (2022).arxiv.org/abs/2210.08723
  45. [47]E. Viola. “The communication complexity of addition”. Combinatorica 35.6 (2015), pp. 703–747.
  46. [48]J. T. Wang, T. Yang, J. Zou, Y. Kwon, and R. Jia. “Rethinking Data Shapley for Data Selection Tasks: Misleads and Merits”. In: Proceedings of the 41st International Conference on Machine Learning. Vol. 235. Proceedings of Machine Learning Research. PMLR, 2024, pp. 52033–52063.arxiv.org/abs/2405.03875
  47. [49]J. T. Wang, Y. Zhu, Y.-X. Wang, R. Jia, and P. Mittal. “A Privacy-Friendly Approach to Data Valuation”. In: Advances in Neural Information Processing Systems. Vol. 36. 2023.DOI
  48. [50]X. Xu, A. Hannun, and L. Van Der Maaten. “Data appraisal without data sharing”. In: International Conference on Artificial Intelligence and Statistics. PMLR. 2022, pp. 11422–11437.

Paper details

vlnc:W_bz3r8ja8
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-5, GPT-6, GPT (multiple versions)

View statement
Looking for related papers…
Contents