{"id":"1cb8ab4e-88ad-4ca3-aef5-fff6c685b67b","arxiv_id":"2504.16668","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":1,"one_line_summary":"The authors introduce IPSS, a stratified-sampling algorithm that approximates Shapley-based data value in federated learning by focusing on small, high-impact coalitions of clients.","lead":"This paper proposes a faster way to estimate how much each participant's data contributes in federated learning, using a sampling trick that focuses on the most informative combinations of data owners. If it works, it could make fair payments and incentive schemes practical in cross-silo federated learning, where the exact calculation is exponentially expensive.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The key-combinations premise is not established for general FL utilities: a plausible linear utility (one disjoint class per client) puts 80% of Shapley mass in large coalitions, so IPSS's pruning and its error guarantee fail.","rationale":"The central claim is that Shapley-based FL data valuation can be approximated with a small budget because only small coalitions ('key combinations') matter. The load-bearing condition is that FL utilities saturate, so marginal contributions of large coalitions are negligible. The weakest evidence is Sec. IV-A: one dataset (FEMNIST) with 10 clients, plus a linear-regression MSE model in Sec. IV-C. I considered the algorithm-level inconsistencies the reader lists (Theorem 1's random denominator, Theorem 2's variance model, Algorithm 3's normalization and Example 3's impossible equal-frequency constraint) and agree they are real; but those are fixable presentation or specification defects. The deeper, harder to fix issue is the saturation assumption, because a linear or threshold-like FL utility is realistic and makes the pruning step discard most of the Shapley sum. I checked the arithmetic with U(S)=|S|/10: for n=10 each player's SV is 0.1, each of the 10 strata contributes 0.01, so keeping only strata 0 and 1 gives 0.02, a relative error of 0.8. This is not an exotic pathological game; it is exactly what happens when clients contribute disjoint label classes and the test set spans all classes. Therefore the paper's headline conclusion is not robust to a natural class of FL utility functions, and the reported error bounds do not cover the algorithm's actual claim. The reader's weakest_assumption identifies the same spot, so I mark agreement as 'agree'. The verdict is unchanged: as written, the central claim is not supported.","tokens_in":20617,"tokens_out":15051,"duration_ms":142289,"concrete_test":"Run the exact ground-truth comparison of Sec. IV-A on a non-saturating FL utility: split MNIST into 10 clients, each holding all training samples of exactly one digit, define U(S) as the trained model's test accuracy on the full 10-digit test set, compute exact MC-SV by evaluating all 2^10 client subsets, and compute K-Greedy K=2 relative error with the same l2 metric. If the relative error is far above 1% (theory predicts 80% for U(S)=|S|/10), the key-combinations premise fails in a realistic FL setting, and IPSS's pruning and Theorem 3's error bound do not transfer.","verdict_should_be":"UNCHANGED","load_bearing_attack":"IPSS's claim of minor approximation error rests on the key-combinations phenomenon (Sec. IV-A): with n=10 on FEMNIST, K-Greedy with K≤2 has relative error <1%, so combinations larger than pairs can be pruned. This is a property of the utility function, not of Shapley value or FL per se. The paper supports it only by Fig. 4 (one benchmark, 10 clients) and by Lemma 1/Theorem 3, which assume a linear-regression MSE utility whose expected value depends only on total sample size and decays as O(1/(t|S|)). Nothing in the analysis rules out FL utilities with substantial mass in large coalitions. A concrete counterexample is a 10-client FL task in which each client holds a disjoint digit class and U(S) is test accuracy on all 10 classes; then U(S)=|S|/10. For this valid, non-pathological utility, every marginal contribution is exactly 1/10, so each stratum k=0,...,9 contributes 1/10 of the total Shapley value. Truncating at |S|≤1 (the K=2 regime of Fig. 4) discards 8 of 10 strata and incurs 80% relative error, not <1%. Thus the pruning step is not guaranteed to work for FL utilities with complementary or near-linear contributions. Theorem 3 does not repair this: it bounds the truncation error only under the specialized MSE model and, as written, does not analyze the sampled P in Algorithm 3. The central claim that SV in FL can be approximated accurately with a small budget therefore depends on an unproven saturation assumption.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes IPSS, a sampling-based approximation algorithm for Shapley-value data valuation in cross-silo federated learning. It first introduces a unified stratified-sampling framework that can instantiate both the marginal-contribution (MC-SV) and complementary-contribution (CC-SV) schemes, claims an unbiasedness result and a variance comparison favoring MC-SV, then identifies an empirically observed 'key combinations' phenomenon: on FEMNIST with ten clients, using only coalitions of size at most two gives relative error below 1%. Building on this, IPSS prunes all coalitions above a threshold k* and samples only a small number of size-(k*+1) coalitions. The paper provides a theoretical error bound under a linear-regression MSE utility model and reports extensive experiments on synthetic partitions of MNIST and on FEMNIST and Adult, showing that IPSS achieves low relative error and competitive runtime compared with several baselines.","tokens_in":20845,"tokens_out":6789,"duration_ms":62302,"significance":"If the central claims were established, the paper would address an important practical problem: approximate Shapley-value data valuation in FL with only a small number of FL model trainings. The proposed framework, the systematic comparison of MC-SV and CC-SV under stratified sampling, and the extensive benchmark evaluation are useful contributions. The paper also provides a public code repository. However, the theoretical results that support the main claims have serious gaps, and the key-combinations phenomenon is shown only on one configuration and under a specialized utility model; a simple complementary utility counterexample defeats the claimed small-error guarantee. The empirical results are suggestive but do not compensate for the load-bearing theoretical defects.","major_comments":[{"comment":"The unbiasedness proof is not valid as written. In Algorithm 1, m_{i,k} is a random variable counting how many sampled coalitions containing i have a sampled paired coalition, and the estimator in line 17 divides φ̂_{i,k} by m_{i,k}. The proof in Eq. (6) treats m_{i,k} as a fixed denominator, writing E[φ̂_{i,k}/m_{i,k}] = E[φ̂_{i,k}]/m_{i,k}, which is not justified for a ratio estimator. Moreover, m_{i,k}=0 occurs with positive probability, in which case the estimator is undefined. Thus Theorem 1 does not establish that Algorithm 1 gives an unbiased estimate of the Shapley value.","section":"Sec. III-A, Theorem 1 (Alg. 1, Eqs. (6)-(7))"},{"comment":"The variance comparison rests on an unjustified and very strong assumption. Eq. (8) states Var[Σ_{j=1}^t e_j] = t^2 σ^2, which treats the per-sample prediction errors as perfectly correlated across all t training samples. This is not derived from a standard linear-regression noise model and is implausible as a general assumption. In addition, the proof compares MC-SV and CC-SV only when both use the exact same m_{i,k} values, whereas the theorem statement claims a comparison 'for any sampling strategy' of CC-SV. Therefore the conclusion that MC-SV always has lower variance in the stratified framework is not established.","section":"Sec. III-B, Theorem 2 (Eqs. (8)-(11))"},{"comment":"Theorem 3's proof bounds a deterministic truncation error, not the stochastic estimator produced by Algorithm 3. The quantity E[φ̂_i^{k*}] in Eq. (16) is the expected value obtained when all coalitions of size at most k* are fully evaluated, i.e., when strata above k* are simply discarded. However, Algorithm 3 lines 8-14 do not discard stratum k*; they randomly sample a set P of size-(k*+1) coalitions, and line 16 uses only the sampled P in the second sum. The variance and sampling error introduced by P are never analyzed. Hence the claimed error bound O((n-k*)/(k* n t)) does not apply to the random output of Algorithm 3.","section":"Sec. IV-C, Theorem 3 (Alg. 3, Eqs. (16)-(19))"},{"comment":"The key-combinations premise is not established for general FL utility functions. The empirical evidence is limited to one benchmark (FEMNIST) with ten clients, and the theoretical support in Lemma 1 and Theorem 3 assumes a linear-regression MSE utility whose expected value depends only on the total sample size and decays as O(1/(t|S|)). No argument rules out FL tasks with complementary or near-additive utilities. For example, consider n=10 clients where each holds one disjoint digit class and U(S) is the test accuracy on all ten classes, so U(S)=|S|/10. Then every marginal contribution is exactly 1/10, each stratum contributes 1/10 of the total Shapley value, and truncating at |S|≤1 (the K=2 regime of Fig. 4) discards 80% of the Shapley mass, not <1%. The pruning step in IPSS therefore relies on an unproven saturation assumption, and the paper's central claim of 'minor approximation error' for arbitrary FL settings is not supported.","section":"Sec. IV-A (Fig. 4, 'Key Combinations Phenomenon')"},{"comment":"Even within the linear-regression MSE model, the analysis only covers a very narrow class of utilities: the expected MSE in Eq. (12) is taken from Donahue and Kleinberg [24] and depends only on the total number of training samples, not on which clients or classes are included. The paper does not state this restriction clearly in the main text or in the abstract, and the algorithm is advocated for general FL utility functions such as model accuracy on real benchmarks. The theoretical analysis should be explicitly framed as a case study, and the general claim that IPSS provably achieves small error should be withdrawn or substantially qualified.","section":"Sec. IV-C, Lemma 1 and Theorem 3 (utility model)"}],"minor_comments":[{"comment":"In K-Greedy, the denominator is written as n·Δ{n \\choose |S|}, but the MC-SV formula in Definition 3 requires n·Δ{n-1 \\choose |S|}; this appears to be a typo and should be corrected.","section":"Sec. V-A, Algorithm 2 line 7"},{"comment":"The name 'Exteneded-TMC' is misspelled; it should be 'Extended-TMC'.","section":"Sec. V-A, 'Compared Algorithms'"},{"comment":"The text says 'validate our approximation algorithm on two real dataset' (and earlier mentions Sent-140), but only FEMNIST and Adult are reported. Please clarify whether Sent-140 results are omitted or whether the sentence is inaccurate.","section":"Sec. V-C, datasets"},{"comment":"Figure 4 reports the key empirical phenomenon supporting the main pruning idea, but the figure caption and text do not report error bars, number of runs, or the variance across runs. Adding this information would help assess the robustness of the '<1%' claim.","section":"Fig. 4 and Fig. 10"},{"comment":"The example does not explain how the sampled set P is chosen to satisfy the equal-frequency constraint (line 11) when n=4 and |P|=5; a brief explanation or a different illustrative choice would improve clarity.","section":"Sec. IV-B, Example 3"}],"recommendation":"reject","confidential_remarks":"The theoretical gaps are too central for a minor revision: Theorem 1 is an invalid unbiasedness proof, Theorem 2 relies on an ad hoc perfect-correlation variance model, Theorem 3 does not analyze Algorithm 3's actual stochastic estimator, and the key-combinations phenomenon is contradicted by a simple additive utility example. A resubmission would need a substantially rewritten theoretical analysis and a much broader empirical validation of the pruning assumption, possibly with explicit conditions under which IPSS is guaranteed to work."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Wanted to give you a quick read on arXiv:2504.16668. The paper proposes IPSS, a stratified-sampling plus pruning algorithm for Shapley-based data valuation in federated learning. The good news: it is a genuine attempt to unify the MC-SV and CC-SV computation schemes under one sampling framework, it gives a variance argument for preferring MC-SV, and the empirical work is extensive — multiple datasets, MLP/CNN/XGB, comparison against eight baselines, and they ship code. The reported speedups are large, e.g., IPSS roughly 170x faster than exact MC-Shapley on the 10-client MLP case with very low relative error. If the key-combinations phenomenon (only small coalitions matter) holds, this is a practical engineering contribution.\n\nBut the paper has load-bearing theoretical gaps. Theorem 1 claims unbiasedness while dividing by a random count m_{i,k}; that's a ratio estimator and generally biased. Theorem 2's variance comparison relies on Var[sum e_j] = t^2 sigma^2, which assumes perfect correlation among errors; that's not stated and seems unrealistic. Theorem 3 bounds the deterministic truncation (summing strata up to k*) rather than the actual stochastic estimator in Algorithm 3; the sampled P of size k*+1 is not analyzed. Algorithm 3's line 16 estimator is not correctly normalized for the sampled part, and Example 3 violates the algorithm's own equal-frequency constraint (the claimed P gives client counts [3,2,2,3], not equal). These are not cosmetic; they undermine the central claim that IPSS approximates the Shapley value accurately with a small budget.\n\nThe key-combinations premise itself is the biggest risk. It is supported empirically by one benchmark (FEMNIST, 10 clients) and theoretically only under a linear-regression MSE utility where marginal contributions decay with coalition size. Nothing rules out FL utilities with significant mass in large coalitions. A simple disjoint-class accuracy utility U(S)=|S|/10 gives every stratum the same Shapley mass; truncating at pairs throws away 80% of the value. That is not exotic in FL.\n\nSo: the paper is worth a serious referee, but the current version needs major work. The empirical recipe may be useful to practitioners, and the unified sampling framework is a nice contribution, but the theory has to be redone and the key-combinations claim needs support beyond one benchmark. I'd send it to review, but with a strong expectation of heavy revision.","headline":"A practically useful algorithm and extensive experiments, but the theory has load-bearing holes and the key-combinations premise is not established beyond one benchmark.","tokens_in":21490,"tokens_out":6628,"would_cite":true,"duration_ms":60916,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that Shapley-value data valuation in federated learning can be approximated with under 1% relative error by evaluating only combinations of at most two clients, and proposes an algorithm, IPSS, that achieves this by…","keywords":["Shapley value","data valuation","federated learning","stratified sampling","approximation algorithm","key combinations","model utility"],"falsifier":"Take a federated task where accuracy keeps climbing as clients are added (for example, a small-data, high-feature-dimension regression or a task where each client contributes unique hard examples), compute the exact Shapley values by training on all subsets, run IPSS with the same sampling budget, and check whether the relative error stays under the paper's bound; if it exceeds the bound, the key-combinations premise fails.","tokens_in":20295,"feed_emoji":"📊","tokens_out":4654,"duration_ms":43929,"temperature":0.7,"pith_summary":"The paper is trying to make Shapley-value-based data valuation practical in cross-silo federated learning, where the exact value requires training and evaluating models on an exponential number of client subsets. It argues that most of those combinations do not matter: because model utility saturates as more clients join, only combinations with a few clients carry significant weight. On that premise it builds IPSS, a sampling algorithm that evaluates all combinations up to a small size and samples a balanced set of the next size, and it reports relative errors under 1% with large speedups over exact computation and over existing approximation baselines. If the premise holds broadly, fair monetary or credit allocation among data providers becomes computationally feasible.","feed_headline":"Few client subsets estimate Shapley data value under 1% error","feed_subtitle":"New IPSS algorithm prunes most dataset combinations, cutting federated-learning data valuation cost dramatically.","key_machinery":"The central machinery is a stratified-sampling estimator built on the marginal-contribution form of the Shapley value. Dataset combinations are grouped into strata by the number of clients they contain, and the algorithm computes average marginal contributions within each stratum, pruning all strata above a cutoff $k^*$ because those combinations are conjectured to have negligible impact. The load-bearing mechanism is the key-combinations phenomenon: marginal utilities shrink as a coalition grows, so large coalitions contribute little to the final value. The variance comparison between MC-SV and CC-SV, and the closed-form MSE analysis for linear regression, are what justify the chosen scheme and the error bound.","core_discovery":"The paper's central claim is that data valuation by Shapley value in federated learning can be approximated accurately using only a small group of dataset combinations, a phenomenon it calls key combinations. Concretely, on FEMNIST with ten clients, combinations involving no more than two clients yield a relative error below 1% compared with the exact marginal-contribution Shapley value. The proposed algorithm, IPSS, prunes all combinations above a cutoff size $k^*$, evaluates the remaining combinations exactly, and samples a balanced set of combinations of size $k^*+1$, then estimates each client's value by averaging marginal contributions across strata. Under a linear-regression model with negative mean squared error as utility, the paper derives a relative error bound of $O((n-k^*)/(k^* n t))$, and it argues that the marginal-contribution scheme (MC-SV) has lower estimation variance than the complementary-contribution scheme (CC-SV) when both are used inside the same stratified-sampling framework.","pith_inferences":["Editorial inference: if the key-combinations phenomenon holds beyond the linear-regression and saturated-accuracy settings tested here, the same pruning idea could apply to other cooperative-game approximation problems where utility saturates, such as model markets or data cooperatives.","Editorial inference: the saturation premise suggests a practical diagnostic: a server could measure how quickly marginal contributions decay from a few pilot evaluations and then decide adaptively how many strata to prune, rather than assuming a fixed cutoff.","Editorial inference: for tasks where utility does not saturate within the relevant number of clients, such as small-data regimes or tasks where each additional client contributes unique hard examples, IPSS would need to include larger strata; the paper's error analysis has not been shown for those cases.","Editorial inference: because the pruning is justified empirically on one benchmark and theoretically only under linear regression, the strongest near-term test is to reproduce the key-combinations curve on other FL benchmarks and model families before relying on IPSS for financial settlement among providers."],"forward_implications":["Data valuation cost drops from $O(2^n)$ model trainings to $O(\\gamma)$ for a user-chosen sampling budget $\\gamma$.","On FEMNIST with ten clients, combinations of size at most two give relative error under 1%, so a small budget of model trainings can produce near-exact Shapley values.","Within the proposed stratified-sampling framework, the marginal-contribution scheme has lower variance than the complementary-contribution scheme, so MC-SV should be preferred for FL data valuation.","IPSS remains efficient and accurate with up to 100 clients, and it better satisfies the no-free-rider and symmetric-fairness properties than the comparison baselines.","Under the linear-regression utility model, the relative error of IPSS is bounded by $O((n-k^*)/(k^* n t))$, which is small when each client holds many samples relative to the feature dimension."],"supporting_citations":[{"why":"Supplies the truncated Monte Carlo sampling baseline and the standard sampling-based Shapley approximation formulation that this work extends.","marker":"[17]"},{"why":"Supplies the closed-form expected MSE for linear regression used in Lemma 1 and in the key-combinations error bound.","marker":"[24]"},{"why":"Supplies the linear-regression error variance formula used to compare MC-SV and CC-SV in Theorem 2.","marker":"[22]"},{"why":"Supplies the FEMNIST/LEAF benchmark used to demonstrate the key-combinations phenomenon empirically.","marker":"[23]"},{"why":"Supplies FedAvg, the federated learning algorithm used in all experimental evaluations.","marker":"[5]"},{"why":"Supplies the complementary-contribution CC-SV scheme and the CC-Shapley sampling baseline that IPSS is compared against.","marker":"[19]"},{"why":"Supplies the DIG-FL baseline and the participant-contribution evaluation method that IPSS is compared with.","marker":"[7]"},{"why":"Supplies the GTG-Shapley gradient-based baseline used in the experimental comparisons.","marker":"[12]"}],"fun_headline_variants":["Few subsets give near-exact Shapley for federated data","IPSS: Fast, accurate data valuation for federated learning","Shapley value in FL: only key client subsets needed","Data valuation for FL made practical by sampling insight","Under 1% error: Shapley data value from few subsets"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument assumes that the value of adding one more client's data becomes negligible once enough clients are already in the coalition, so the algorithm can safely ignore all large coalitions; if that saturation fails, the pruning step discards a large share of the Shapley sum and the reported error bounds no longer apply.","fun_headline_variants_meta":{"raw":{"variants":["Few subsets give near-exact Shapley for federated data","IPSS: Fast, accurate data valuation for federated learning","Shapley value in FL: only key client subsets needed","Data valuation for FL made practical by sampling insight","Under 1% error: Shapley data value from few subsets"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001006,"raw_usage":{"total_tokens":4271,"prompt_tokens":981,"completion_tokens":3290,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":597,"completion_tokens_details":{"reasoning_tokens":3204}},"tokens_in":597,"tokens_out":3290,"duration_ms":22255,"temperature":1.0,"reasoning_tokens":3204,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T10:59:40.199839+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a federated task where accuracy keeps climbing as clients are added (for example, a small-data, high-feature-dimension regression or a task where each client contributes unique hard examples), compute the exact Shapley values by training on all subsets, run IPSS with the same sampling budget, and check whether the relative error stays under the paper's bound; if it exceeds the bound, the key-combinations premise fails.","supporting_citations":[{"cited_title":"Data shapley: Equitable valuation of data for machine learning,","cited_arxiv_id":null,"evidence_quote":"Supplies the truncated Monte Carlo sampling baseline and the standard sampling-based Shapley approximation formulation that this work extends."},{"cited_title":"Model-sharing games: Analyzing federated learning under voluntary participation,","cited_arxiv_id":null,"evidence_quote":"Supplies the closed-form expected MSE for linear regression used in Lemma 1 and in the key-combinations error bound."},{"cited_title":"The truth about linear regression,","cited_arxiv_id":null,"evidence_quote":"Supplies the linear-regression error variance formula used to compare MC-SV and CC-SV in Theorem 2."},{"cited_title":"Communication-efficient learning of deep networks from decentralized data,","cited_arxiv_id":null,"evidence_quote":"Supplies FedAvg, the federated learning algorithm used in all experimental evaluations."},{"cited_title":"Efficient sampling approaches to shapley value approximation,","cited_arxiv_id":null,"evidence_quote":"Supplies the complementary-contribution CC-SV scheme and the CC-Shapley sampling baseline that IPSS is compared against."},{"cited_title":"Efficient participant contribu- tion evaluation for horizontal and vertical federated learning,","cited_arxiv_id":null,"evidence_quote":"Supplies the DIG-FL baseline and the participant-contribution evaluation method that IPSS is compared with."},{"cited_title":"Gtg-shapley: Efficient and accurate participant contribution evaluation in federated learning,","cited_arxiv_id":null,"evidence_quote":"Supplies the GTG-Shapley gradient-based baseline used in the experimental comparisons."}],"review_version":1}