Pith. sign in

REVIEW 5 minor 52 references

Despite its combinatorial definition, the Shapley value of a fixed data owner is asymptotically captured by a simple first-order leading term of order (log I)/I.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-12 02:55 UTC pith:VA3NFOT7

load-bearing objection Clean first asymptotic for dataset-level Shapley under smooth RKHS utilities: exact φ_i^I is O(1/I)-close to an explicit first-order term of scale (log I)/I, with usable estimator consequences.

arxiv 2607.03374 v1 pith:VA3NFOT7 submitted 2026-07-03 cs.GT

An Asymptotic Analysis of the Shapley Value for Dataset Valuation

M\'elissa Tamine , Benjamin Heymann , Maxime Vono , Patrick Loiseau This is my paper
classification cs.GT
keywords Shapley valuedataset valuationasymptotic analysisRKHS mean embeddingsleading termdata valuationcooperative games
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

When many independent data owners pool their datasets, how much credit should one fixed owner receive? The classical answer is the Shapley value, but it averages exponentially many marginal contributions and becomes intractable as the number of owners grows. This paper shows that, once utilities are smooth functionals of empirical distributions represented by RKHS mean embeddings, that combinatorial average collapses: the exact Shapley value of the fixed owner is within O(1/I) of an explicit leading term built from three quantities—the owner’s dataset size, a first-order signal measuring how its distribution differs from the surrounding population in utility-relevant directions, and a harmonic average over coalition sizes. The leading term therefore identifies both the scale of the value ((log I)/I when the signal is nonzero) and a practical reference that large-scale estimators can be compared against. The result turns an opaque average into a transparent population-level quantity that practitioners and theorists can use without enumerating coalitions.

Core claim

Under bounded features, smooth Fréchet-differentiable utilities of RKHS mean embeddings, and i.i.d. surrounding owners, the exact Shapley value ϕ_i^I of a fixed data owner satisfies E|ϕ_i^I − Θ_i^I| = O(1/I), where the leading term is Θ_i^I = (n_i c_i / n̄) (H_{I−1}/I) and c_i = ⟨∇F(μ⋆), μ_i − μ⋆⟩ is the first-order signal of that owner relative to the population embedding μ⋆. Consequently |ϕ_i^I| is of order (log I)/I in probability whenever c_i ≠ 0.

What carries the argument

The leading term Θ_i^I obtained by replacing each coalition’s empirical embedding with the population reference μ⋆ inside a first-order Taylor expansion of the utility, then averaging the resulting per-size contributions with the harmonic weights of the Shapley formula.

Load-bearing premise

The utility of any pooled dataset must be a smooth functional of its average kernel embedding with uniformly bounded gradient and Lipschitz gradient; ordinary machine-learning scores obtained by training a model generally do not satisfy this form.

What would settle it

Construct a sequence of games whose utilities are not smooth functionals of mean embeddings (for example, 0-1 test accuracy of a non-linear classifier trained from scratch) and check whether |ϕ_i^I − Θ_i^I| still decays as O(1/I); a systematic failure of that rate would refute the claim that the leading term asymptotically captures the Shapley value.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Any Shapley estimator whose absolute error is o_P((log I)/I) is automatically consistent in relative error once the first-order signal is nonzero.
  • Permutation Monte Carlo needs a budget m_I ≫ I² / (log I)² and group-testing needs an (ε_I, δ_I) guarantee with ε_I = o((log I)/I) to achieve relative consistency.
  • DU-Shapley and stratified Monte Carlo are leading-order estimators and therefore relatively consistent without extra budget conditions.
  • In large-I regimes the leading term itself becomes a cheap, computable benchmark against which any approximation can be scored when exact Shapley is unavailable.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same first-order signal may serve as a cheap screening statistic for deciding which owners are worth including before any full Shapley computation.
  • If the smoothness assumption can be relaxed to twice-differentiable population risk functionals, the leading-term analysis would cover a much larger class of practical machine-learning utilities.
  • The (log I)/I scale suggests that, for very large coalitions, even exact Shapley values become negligible relative to total utility, which may affect incentive design in data markets.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper studies the asymptotic behavior of the exact finite-game Shapley value of a fixed data owner as the number of surrounding owners grows. Under a population model for surrounding datasets and the assumption that utility is a Fréchet-smooth functional of RKHS mean embeddings, Theorem 3.2 shows that the Shapley value is O(1/I)-close in L1 to an explicit leading term Θ_i^I = (n_i c_i / n̄)(H_{I−1}/I), where c_i is the first-order signal ⟨∇F(μ⋆), μ_i − μ⋆⟩. Corollaries identify the scale log I / I and convert absolute-error bounds into relative consistency for estimators. The analysis is applied to permutation Monte Carlo, group testing, DU-Shapley, and stratified Monte Carlo, and a controlled synthetic experiment uses the leading term as a large-I benchmark.

Significance. If the result holds under the stated assumptions, this is a genuine contribution: it is, to my knowledge, the first asymptotic characterization of the exact finite-game Shapley value in a dataset-valuation setting that keeps one owner non-negligible. The leading term is independently derived (not fitted to Shapley values), the scale log I / I is useful for estimator design, and the absolute-to-relative error principle cleanly organizes existing approximation methods. The appendices supply a complete proof chain (embedding update, first-order expansion, concentration, harmonic averaging). The synthetic benchmark is reproducible and correctly treated as an illustration rather than a substitute for theory. The main limitation—smooth embedding utilities—is already acknowledged by the authors and does not undermine the internal claim.

minor comments (5)
  1. In the abstract and introduction, the phrase “asymptotically captured by a simple leading term” could briefly flag that the O(1/I) L1 bound is the precise statement (Theorem 3.2), so readers do not over-read the claim as almost-sure pathwise convergence.
  2. Section 5: the plug-in estimation of (n̄, μ⋆, c_i) from surrounding data is deferred to future work; a short remark on the order of that additional error (or a pointer that it is left open) would help practitioners who want to use Θ_i^I as a real benchmark.
  3. Notation table and main text: the empty-coalition convention μ(bP_∅)=0 and the bound |Δ_i(∅)|≤Gκ appear in the proof of Theorem 3.2; a one-line reminder in Section 2.4 would make the main-text argument self-contained.
  4. Figure 1 caption: the 1/log I reference curve is a visual guide only; stating that explicitly (as the discussion already does for Monte Carlo) would avoid misreading the faster MC decay as a contradiction.
  5. A few typos: “adataset” in the abstract; “bφ” vs “bϕ” inconsistency in Proposition 4.1; “¯μ” appears once in the proof of Theorem 4.3 where ¯n is intended.

Circularity Check

0 steps flagged

No significant circularity: leading term is derived from Taylor expansion plus population concentration, not fitted to or defined from the Shapley values it approximates.

full rationale

The paper's central claim (Theorem 3.2) is an L1 approximation of the exact finite-game Shapley value ϕ_i^I by an explicit leading term Θ_i^I. That term is obtained by (i) the embedding update identity (Lemma C.1), (ii) a first-order Fréchet expansion of F with controlled remainder (Lemmas C.2–C.3, C.5), (iii) concentration of large-coalition embeddings around μ⋆ (Lemma C.4), and (iv) harmonic averaging of the resulting per-size first-order contributions. None of these steps defines Θ from ϕ or fits parameters to observed Shapley values; the approximation error is proved, not assumed. Estimator consistency (Corollaries 3.4, Prop. 4.1, Thm. 4.3) is then relative distance to this independently derived scale log I/I. Self-citations (DU-Shapley [7], related Tamine et al. works) appear only as objects of analysis or related work, not as load-bearing uniqueness or ansatz imports for the asymptotic theorem. The synthetic benchmark uses known population quantities as an oracle reference, not a fit-then-predict loop. Scope is limited by Assumption 2.2 (smooth embedding utilities), which the authors state as a limitation rather than smuggling into the derivation. Finding: self-contained derivation under stated assumptions; score 0.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 2 invented entities

The central claim rests on three modeling assumptions that turn combinatorial marginal contributions into a first-order expansion around a population embedding. No free parameters are fitted in the theory; experimental constants are only for illustration. The leading term and first-order signal are derived objects, not postulated entities.

axioms (4)
  • domain assumption Bounded feature map: ∥φ(z)∥ ≤ κ < ∞ for all z (Assumption 2.1).
    Needed for uniform control of embedding norms and Taylor remainders; standard for many kernels but restrictive for unbounded feature maps.
  • domain assumption Utility v(D) = F(μ(ˆP_D)) where F is Fréchet differentiable with ∥∇F∥ ≤ G and ∇F M-Lipschitz (Assumption 2.2).
    Load-bearing regularity that converts adding a dataset into a controlled first-order perturbation; real training utilities rarely satisfy it.
  • domain assumption Surrounding players are i.i.d. draws from a common population of datasets with sizes bounded by n_max (Assumption 2.3).
    Defines the growing-player regime and supplies the law-of-large-numbers concentration around μ⋆.
  • standard math Standard Hilbert-space Taylor remainder and concentration inequalities for i.i.d. and without-replacement samples (Lemmas C.2, C.4, C.7).
    Used throughout the error analysis; classical.
invented entities (2)
  • First-order signal c_i = ⟨∇F(μ⋆), μ_i − μ⋆⟩ no independent evidence
    purpose: Scalar that isolates the utility-relevant component of the fixed dataset’s deviation from the population.
    Derived from the gradient of F at the population embedding; not an independent physical or statistical object.
  • Leading term Θ_i^I = (n_i c_i / n̄) (H_{I−1}/I) no independent evidence
    purpose: Explicit asymptotic proxy for the exact Shapley value.
    Obtained by averaging the population-level first-order marginals; defined by the paper’s expansion rather than observed independently.

pith-pipeline@v1.1.0-grok45 · 32810 in / 2990 out tokens · 27056 ms · 2026-07-12T02:55:47.361054+00:00 · methodology

0 comments
read the original abstract

We propose an asymptotic analysis of the Shapley value in a dataset valuation setting in which utilities are modeled as smooth functionals of empirical distributions via reproducing kernel Hilbert space (RKHS) mean embeddings. We prove that, despite its combinatorial definition, the Shapley value of a data source is asymptotically captured by a simple leading term. This term can be interpreted as the first-order contribution of a dataset relative to the surrounding data population. It also identifies the scale of the Shapley value as the number of data sources grows and provides a framework for analyzing existing Shapley value estimators. Moreover, for practitioners working with large numbers of datasets, the leading term becomes a tractable reference against which Shapley value approximations can be benchmarked.

Figures

Figures reproduced from arXiv: 2607.03374 by Benjamin Heymann, Maxime Vono, M\'elissa Tamine, Patrick Loiseau.

Figure 1
Figure 1. Figure 1: Relative error of each estimator averaged over [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

52 extracted references · 10 linked inside Pith

  1. [1]

    A marketplace for data: An algorithmic solution

    Anish Agarwal, Munther Dahleh, and Tuhin Sarkar. A marketplace for data: An algorithmic solution. InProceedings of the 2019 ACM Conference on Economics and Computation, pages 701–726, 2019

    2019

  2. [2]

    Aumann and Lloyd S

    Robert J. Aumann and Lloyd S. Shapley.Values of Non-Atomic Games. Princeton University Press, Princeton, NJ, 1974

    1974

  3. [3]

    Chg shapley: Efficient data valuation and selection towards trustworthy machine learning.arXiv preprint arXiv:2406.11730, 2024

    Huaiguang Cai. Chg shapley: Efficient data valuation and selection towards trustworthy machine learning.arXiv preprint arXiv:2406.11730, 2024

    Pith/arXiv arXiv 2024

  4. [4]

    Polynomial calculation of the shapley value based on sampling

    Javier Castro, Daniel Gómez, and Juan Tejada. Polynomial calculation of the shapley value based on sampling. InComputers & Operations Research, volume 36, pages 1726–1730. Elsevier, 2009

    2009

  5. [5]

    Shapley-guided utility learning for effective graph inference data valuation.arXiv preprint arXiv:2503.18195, 2025

    Hongliang Chi, Qiong Wu, Zhengyi Zhou, and Yao Ma. Shapley-guided utility learning for effective graph inference data valuation.arXiv preprint arXiv:2503.18195, 2025

    Pith/arXiv arXiv 2025

  6. [6]

    Hannah Diehl and Ashia C. Wilson. Semivalue-based data valuation is arbitrary and gameable. arXiv preprint arXiv:2506.12619, 2025

    Pith/arXiv arXiv 2025

  7. [7]

    Du-shapley: A shapley value proxy for efficient dataset valuation.Advances in Neural Information Processing Systems, 37:1973–2000, 2024

    Felipe Garrido-Lucero, Benjamin Heymann, Maxime V ono, Patrick Loiseau, and Vianney Perchet. Du-shapley: A shapley value proxy for efficient dataset valuation.Advances in Neural Information Processing Systems, 37:1973–2000, 2024

    1973

  8. [8]

    Kim, and James Zou

    Amirata Ghorbani, Michael P. Kim, and James Zou. Distributional shapley: A distributional approach to data valuation. InProceedings of the 37th International Conference on Machine Learning (ICML), pages 3424–3435, 2020

    2020

  9. [9]

    Data shapley: Equitable valuation of data for machine learning

    Amirata Ghorbani and James Zou. Data shapley: Equitable valuation of data for machine learning. InInternational conference on machine learning, pages 2242–2251. PMLR, 2019

    2019

  10. [10]

    Datamodels: Predicting predictions from training data.arXiv preprint arXiv:2202.00622, 2022

    Andrew Ilyas, Sung Min Park, Logan Engstrom, Guillaume Leclerc, and Aleksander Madry. Datamodels: Predicting predictions from training data.arXiv preprint arXiv:2202.00622, 2022

    Pith/arXiv arXiv 2022

  11. [11]

    Efficient task-specific data valuation for nearest neighbor algorithms.arXiv preprint arXiv:1908.08619, 2019

    Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nezihe Merve Gurel, Bo Li, Ce Zhang, Costas J Spanos, and Dawn Song. Efficient task-specific data valuation for nearest neighbor algorithms.arXiv preprint arXiv:1908.08619, 2019

    Pith/arXiv arXiv 1908

  12. [12]

    Towards efficient data valuation based on the shapley value

    Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nick Hynes, Nezihe Merve Gürel, Bo Li, Ce Zhang, Dawn Song, and Costas J Spanos. Towards efficient data valuation based on the shapley value. InThe 22nd international conference on artificial intelligence and statistics, pages 1167–1176. PMLR, 2019

    2019

  13. [13]

    Shapley value on uncertain data.arXiv preprint arXiv:2601.14543, 2026

    Zhuofan Jia and Jian Pei. Shapley value on uncertain data.arXiv preprint arXiv:2601.14543, 2026

    arXiv 2026

  14. [14]

    Opendataval: a unified benchmark for data valuation.Advances in Neural Information Processing Systems, 36:28624– 28647, 2023

    Kevin Jiang, Weixin Liang, James Y Zou, and Yongchan Kwon. Opendataval: a unified benchmark for data valuation.Advances in Neural Information Processing Systems, 36:28624– 28647, 2023. 10

    2023

  15. [15]

    Lava: Data valuation without pre-specified learning algorithms

    Hoang Anh Just, Feiyang Kang, Tianhao Wang, Yi Zeng, Myeongseob Ko, Ming Jin, and Ruoxi Jia. Lava: Data valuation without pre-specified learning algorithms. InInternational Conference on Learning Representations, 2023

    2023

  16. [16]

    Understanding black-box predictions via influence functions

    Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. InProceedings of the 34th International Conference on Machine Learning, pages 1885–1894. PMLR, 2017

    2017

  17. [17]

    Efficient computation and analysis of distributional shapley values

    Yongchan Kwon, Manuel A Rivas, and James Zou. Efficient computation and analysis of distributional shapley values. InInternational Conference on Artificial Intelligence and Statistics, pages 793–801. PMLR, 2021

    2021

  18. [18]

    Beta shapley: a unified and noise-reduced data valuation framework for machine learning.arXiv preprint arXiv:2110.14049, 2021

    Yongchan Kwon and James Zou. Beta shapley: a unified and noise-reduced data valuation framework for machine learning.arXiv preprint arXiv:2110.14049, 2021

    Pith/arXiv arXiv 2021

  19. [19]

    Data-oob: Out-of-bag estimate as a simple and efficient data value

    Yongchan Kwon and James Zou. Data-oob: Out-of-bag estimate as a simple and efficient data value. InProceedings of the 40th International Conference on Machine Learning. PMLR, 2023

    2023

  20. [20]

    Measuring the effect of training data on deep learning predictions via randomized experiments

    Jinkun Lin, Anqi Zhang, Mathias Lécuyer, Jinyang Li, Aurojit Panda, and Siddhartha Sen. Measuring the effect of training data on deep learning predictions via randomized experiments. InProceedings of the 39th International Conference on Machine Learning, pages 13468–13504. PMLR, 2022

    2022

  21. [21]

    Gtg-shapley: Efficient and accu- rate participant contribution evaluation in federated learning.ACM Transactions on intelligent Systems and Technology (TIST), 13(4):1–21, 2022

    Zelei Liu, Yuanyuan Chen, Han Yu, Yang Liu, and Lizhen Cui. Gtg-shapley: Efficient and accu- rate participant contribution evaluation in federated learning.ACM Transactions on intelligent Systems and Technology (TIST), 13(4):1–21, 2022

    2022

  22. [22]

    Bounding the es- timation error of sampling-based shapley value approximation.arXiv preprint arXiv:1306.4265, 2013

    Sasan Maleki, Long Tran-Thanh, Greg Hines, Talal Rahwan, and Alex Rogers. Bounding the es- timation error of sampling-based shapley value approximation.arXiv preprint arXiv:1306.4265, 2013

    Pith/arXiv arXiv 2013

  23. [23]

    Sampling permutations for shapley value estimation.Journal of Machine Learning Research, 23(43):1–46, 2022

    Rory Mitchell, Joshua Cooper, Eibe Frank, and Geoffrey Holmes. Sampling permutations for shapley value estimation.Journal of Machine Learning Research, 23(43):1–46, 2022

    2022

  24. [24]

    Singular games have asymptotic values.Mathematics of Operations Research, 6(2):205–212, 1981

    Abraham Neyman. Singular games have asymptotic values.Mathematics of Operations Research, 6(2):205–212, 1981

    1981

  25. [25]

    Weighted majority games have asymptotic value.Mathematics of Operations Research, 13(4):556–580, 1988

    Abraham Neyman. Weighted majority games have asymptotic value.Mathematics of Operations Research, 13(4):556–580, 1988

    1988

  26. [26]

    Deep learning on a data diet: Finding important examples early in training

    Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. Deep learning on a data diet: Finding important examples early in training. InAdvances in Neural Information Processing Systems, volume 34, pages 20596–20607, 2021

    2021

  27. [27]

    Estimating training data influence by tracing gradient descent

    Garima Pruthi, Frederick Liu, Satyen Kale, and Mukund Sundararajan. Estimating training data influence by tracing gradient descent. InAdvances in Neural Information Processing Systems, volume 33, pages 19920–19930, 2020

    2020

  28. [28]

    Probability inequalities for kernel embeddings in sampling without re- placement

    Markus Schneider. Probability inequalities for kernel embeddings in sampling without re- placement. InProceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51, pages 66–74, Cadiz, Spain, 09–11 May 2016

    2016

  29. [29]

    Lloyd S. Shapley. A value for n-person games. In Harold W. Kuhn and Albert W. Tucker, editors,Contributions to the Theory of Games, volume 2, pages 307–317. Princeton University Press, 1953

    1953

  30. [30]

    ingredients

    Rachael Hwee Ling Sim, Xinyi Xu, and Bryan Kian Hsiang Low. Data valuation in machine learning: "ingredients", strategies, and open challenges. In Lud De Raedt, editor,Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, pages 5607–5614. International Joint Conferences on Artificial Intelligence Organization...

    2022

  31. [31]

    Collaborative machine learning with incentive-aware model rewards

    Rachael Hwee Ling Sim, Yehong Zhang, Mun Choon Chan, and Bryan Kian Hsiang Low. Collaborative machine learning with incentive-aware model rewards. InInternational conference on machine learning, pages 8927–8936. PMLR, 2020. 11

    2020

  32. [32]

    Fast-datashapley: Neural modeling for training data valuation

    Haifeng Sun, Yu Xiong, Runze Wu, Xinyu Cai, Changjie Fan, Lan Zhang, and Xiang-Yang Li. Fast-datashapley: Neural modeling for training data valuation. InProceedings of the Nineteenth ACM International Conference on Web Search and Data Mining, pages 607–617, 2026

    2026

  33. [33]

    On the impact of the utility in semivalue-based data valuation

    Mélissa Tamine, Benjamin Heymann, Maxime V ono, and Patrick Loiseau. On the impact of the utility in semivalue-based data valuation. InInternational Conference on Learning Representations, 2026

    2026

  34. [34]

    Data valuation for llm fine- tuning: Efficient shapley value approximation via language model arithmetic.arXiv preprint arXiv:2512.15765, 2025

    Mélissa Tamine, Otmane Sakhi, and Benjamin Heymann. Data valuation for llm fine- tuning: Efficient shapley value approximation via language model arithmetic.arXiv preprint arXiv:2512.15765, 2025

    Pith/arXiv arXiv 2025

  35. [35]

    Incen- tivizing collaboration in machine learning via synthetic data rewards

    Sebastian Shenghong Tay, Xinyi Xu, Chuan Sheng Foo, and Bryan Kian Hsiang Low. Incen- tivizing collaboration in machine learning via synthetic data rewards. InProceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 9448–9456, 2022

    2022

  36. [36]

    Data banzhaf: A robust data valuation framework for machine learning

    Jiachen T Wang and Ruoxi Jia. Data banzhaf: A robust data valuation framework for machine learning. InInternational conference on artificial intelligence and statistics, pages 6388–6421. PMLR, 2023

    2023

  37. [37]

    Efficient data shapley for weighted nearest neighbor algorithms

    Jiachen T Wang, Prateek Mittal, and Ruoxi Jia. Efficient data shapley for weighted nearest neighbor algorithms. InInternational Conference on Artificial Intelligence and Statistics, pages 2557–2565. PMLR, 2024

    2024

  38. [38]

    Data shapley in one training run

    Jiachen T Wang, Prateek Mittal, Dawn Song, and Ruoxi Jia. Data shapley in one training run. arXiv preprint arXiv:2406.11011, 2024

    Pith/arXiv arXiv 2024

  39. [39]

    Uncertainty quantifica- tion of data shapley via statistical inference.arXiv preprint arXiv:2407.19373, 2024

    Mengmeng Wu, Zhihong Liu, Xiang Li, Ruoxi Jia, and Xiangyu Chang. Uncertainty quantifica- tion of data shapley via statistical inference.arXiv preprint arXiv:2407.19373, 2024

    Pith/arXiv arXiv 2024

  40. [40]

    Davinz: Data valuation using deep neural networks at initialization

    Zhaoxuan Wu, Yao Shu, and Bryan Kian Hsiang Low. Davinz: Data valuation using deep neural networks at initialization. InProceedings of the 39th International Conference on Machine Learning, pages 24150–24176. PMLR, 2022

    2022

  41. [41]

    Data shapley as an infinite-order u- statistic: Statistical inference for data valuation.arXiv preprint, 2024

    Zhaoxuan Wu, Yao Shu, and Bryan Kian Hsiang Low. Data shapley as an infinite-order u- statistic: Statistical inference for data valuation.arXiv preprint, 2024. To appear, adjust if published

    2024

  42. [42]

    Validation free and replication robust volume-based data valuation

    Xinyi Xu, Zhaoxuan Wu, Chuan Sheng Foo, and Bryan Kian Hsiang Low. Validation free and replication robust volume-based data valuation. InAdvances in Neural Information Processing Systems, volume 34, pages 10837–10848, 2021

    2021

  43. [43]

    Ravikumar

    Chih-Kuan Yeh, Joon Kim, Ian En-Hsu Yen, and Pradeep K. Ravikumar. Representer point selection for explaining deep neural networks. InAdvances in Neural Information Processing Systems, volume 31, 2018. 12 Outline.The appendices are organized as follows. – Appendix A provides an extended discussion of related work, including Shapley-based data valuation, e...

    2018

  44. [44]

    Null player.If a player has zero marginal contribution to every coalition, i.e., u(S∪ {i}) = u(S)∀S⊆ I \ {i},then its value is zero:ϕ i(u) = 0

  45. [45]

    3.Efficiency.The total value is distributed among all players: P i∈I ϕi(u) =u(I)−u(∅)

    Symmetry.If two players have identical marginal contributions to every coalition, i.e., u(S∪ {i}) =u(S∪ {j})∀S⊆ I \ {i, j}, then they receive the same value: ϕi(u) =ϕ j(u). 3.Efficiency.The total value is distributed among all players: P i∈I ϕi(u) =u(I)−u(∅)

  46. [46]

    Additivity.For any two games u and w on the same player set, ϕi(u+w) =ϕ i(u) + ϕi(w),∀i∈ I. In the game-theoretic formulation of data valuation, each data point is treated as a player in a cooperative game, and the utility of a coalition is typically defined as the performance of a model trained on the corresponding subset. This point-level setting has mo...

  47. [47]

    Decomposing the error.For each coalitionS k, we have: ∆i(Sk) =α Sk ci + ∆i(Sk)−α Sk ci . Taking expectation overS k and averaging overk, we obtain ϕI i −Θ I i = 1 I I−1X k=1 ESk ∆i(Sk)−α Sk ci | {z } =:AI + 1 I I−1X k=1 ESk[αSk]ci −Θ I i ! | {z } =:mI + C0 I , By the triangle inequality, E|ϕI i −Θ I i | ≤E|A I |+E|m I |+ C0 I . We now boundE|A I |andE|m I...

  48. [48]

    The same holds for α2 Sk

    Upper bound onE|A I |We have E|AI |=E " 1 I I−1X k=1 ESk[∆i(Sk)−α Sk ci] # ≤ 1 I I−1X k=1 E ESk |∆i(Sk)−α Sk ci| (by Jensen and triangle inequality) ≤ 1 I I−1X k=1 E (G+ 2M κ)E Sk[αSk |µSk −µ ⋆|] + 2M κ2ESk[α2 Sk] (by Lemma C.5) Now, by the law of total expectation,E[ESk[αSk ∥µSk −µ ⋆∥]] =E[α Sk ∥µSk −µ ⋆∥], where the outer expectation is over the random ...

  49. [49]

    Thus, |mI | ≤ |c i| · 1 I I−1X k=1 E[αSk]− ni ¯n HI−1 I

    Upper bound on E|mI |.Recall that mI = 1 I PI−1 k=1 E[αSk]ci −Θ I i and ΘI i = nici ¯n HI−1 I . Thus, |mI | ≤ |c i| · 1 I I−1X k=1 E[αSk]− ni ¯n HI−1 I . From Assumptions 2.1 and 2.2, we have |ci| ≤ ∥g ⋆∥∥µi −µ ⋆∥ ≤G·2κ . It therefore suffices to bound the term in absolute value. 3.1. Removing the+n i in the denominator.Sinceα Sk =n i/(NSk +n i), define A...

  50. [50]

    This completes the proof

    Conclusion.Combining the bounds forE|A I |,E|m I |, and thek= 0term, we obtain E|ϕI i −Θ I i | ≤ CA +C ′ B +C 0 I = Cϕ I . This completes the proof. 26 D.2 Proof of Corollary 3.3 Corollary D.2(Restate of Corollary 3.3).Under the assumptions of Theorem 3.2, if ci ̸= 0, then |ϕI i |= Θ P logI I . Proof.Let aI := logI I . By the definition of the leading ter...

  51. [51]

    Ifm I ≫ I 2 log2 I , then bϕI i,MC ϕI i −1 P − − →0

  52. [52]

    1 mk,I mk,IX b=1 ∆i(Sk,b)− ni k¯nci # ≤C ∆,strat.(9) 34 Proof.By Jensen’s inequality, E

    If there exist sequences εI =o(logI/I) and δI →0 such that the group-testing budget TI is large enough for the estimator to be an (εI , δI)-approximation of the Shapley vector (ϕI j)I j=1 inℓ 2-norm., then bϕI i,GT ϕI i −1 P − − →0. Proof. We prove that both estimators have absolute erroroP(logI/I) . The relative-error convergence then follows directly fr...