{"id":"174ad1b3-4a77-4e93-939d-c2cd0ceb5db4","arxiv_id":"2411.16478","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"PRIEST-KLD is a family of differentially private, communication-efficient estimators of KL divergence for federated data, with three trust models; however, the unbiasedness and privacy proofs have load-bearing gaps.","lead":"This paper presents three algorithms for privately estimating KL divergence between a known reference distribution and a private federated dataset. The work targets federated drift detection, but key proofs ignore client-sampling bias and the noise calibration does not cover the released estimator.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.3's unbiasedness proof conflates the random SecAgg frequency from sampled clients with the true global distribution P; since E log(P_C/Π) ≠ log(P/Π), the headline unbiased-estimation claim is not established.","rationale":"The paper's central contribution is the claim that PRIEST-KLD gives an unbiased, differentially private estimator of DKL(Π∥P) in a federated setting. For that to hold, every step of the proof must be valid when the randomness of client selection is included. The proof of Theorem 4.3 uses the identities E_{X∼Π}[P(X)/Π(X)]=1 and E[λ(r−1)−log r]=DKL(Π∥P); these identities hold for the fixed global distribution P. In Algorithm 1, however, r is formed from P_C, the SecAgg over a sampled subset C_t. The expectation over the client sample cannot be moved inside the log: E_C[log(P_C/Π)] ≠ log(E_C[P_C]/Π), so the unbiasedness step is invalid. The concrete two-client example makes the failure quantitative: each sampled client yields DKL ≈ 0.511 against a true divergence of 0. This is an internal inconsistency, not a disagreement with the field's consensus. The reader's weakest_assumption identifies the same client-sampling issue, and I agree; I would therefore leave the reader's REJECT verdict unchanged. The DP sensitivity objection in the reader's verdict is a separate, additional problem that strengthens the rejection but is not needed for this conclusion.","tokens_in":19995,"tokens_out":11682,"duration_ms":112445,"concrete_test":"Run Algorithm 1 with a two-symbol domain: Π=(1/2,1/2); client A's local distribution is (0.9,0.1), client B's is (0.1,0.9), giving pooled global P=(0.5,0.5) and DKL(Π∥P)=0. For T=1000 rounds, sample one client uniformly at random, draw x_t∼Π, and compute the λ=0 estimator −log r, r=P_C(x_t)/Π(x_t). Report the empirical mean. If client subsampling is ignored, the expectation is DKL(Π∥P_C)≈0.511; a correct unbiased estimator should concentrate near 0. Repeating with |C_t|=2 (both clients) should recover 0, isolating the client-sampling randomness as the source of the bias.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 4.3 proves unbiasedness by applying Facts 4.1 and 4.2 to r(x_t)=P(x_t)/Π(x_t), where P(x_t) is the value computed in Algorithm 1 (line 7). That value is not the global distribution P: it is the SecAgg of frequencies reported by a randomly sampled subset C_t⊂C, so it is a random quantity P_C(x_t) whose law depends on C_t. For each realized P_C, Fact 4.2 only gives E_{X∼Π}[λ(r−1)−log r] = DKL(Π∥P_C), not DKL(Π∥P). After averaging over the client sample, the estimator's expectation is E_C[DKL(Π∥P_C)], and Jensen's inequality gives E_C[DKL(Π∥P_C)] ≥ DKL(Π∥E_C[P_C]); equality requires P_C=P almost surely. The failure is specifically the log term: E_C log(P_C(X)/Π(X)) ≠ log(E_C[P_C(X)]/Π(X)). A minimal example with X={0,1}, Π=(1/2,1/2), two clients with local distributions (0.9,0.1) and (0.1,0.9), and |C_t|=1 gives estimator expectation DKL(Π∥P_A)=DKL(Π∥P_B)≈0.511 for every sampled client, while the true DKL(Π∥P)=0. Thus Theorems 4.3 and 4.7 do not establish unbiasedness; the abstract's claim that the private estimators are accurate relative to a non-private baseline is not supported by an unbiasedness argument.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper introduces PRIEST-KLD, a family of algorithms for estimating the KL divergence DKL(Π∥P) between a public reference distribution Π and a private federated distribution P under three trust models: Trusted, TAgg, and Dist. The server samples T points from Π; in each round a randomly sampled subset of clients reports the frequency of the sampled symbol, a secure aggregation yields P(xt), and the estimator averages λ(P(xt)/Π(xt)−1)−log(P(xt)/Π(xt)) over the T rounds. The paper claims unbiasedness under the Trusted and TAgg models, bounded variance, and (ε,δ)-DP via Gaussian noise calibrated to the sensitivity of the true KL divergence, and it presents FEMNIST experiments concluding that the private estimators achieve accuracy comparable to a non-private baseline.","tokens_in":20361,"tokens_out":6659,"duration_ms":64883,"significance":"If the theorems were correct, PRIEST-KLD would be a useful primitive for federated analytics: communication cost bounded by T queries, a natural Monte Carlo/Bregman estimator, and formal DP guarantees under several trust assumptions. The problem is well motivated, and the paper is transparent about the Dist model lacking unbiasedness. However, the central formal claims are not established: the unbiasedness proof conflates the randomly sampled aggregate with the global distribution, and the DP proof calibrates noise to the sensitivity of the true KL query rather than to the sensitivity of the released estimator. The experimental section also selects λ in-sample on the same data used to report accuracy. These issues are load-bearing, so the significance of the paper as it stands is limited.","major_comments":[{"comment":"The proof applies Fact 4.2 to r(xt)=P(xt)/Π(xt), treating P(xt) from Algorithm 1 line 7 as the fixed global distribution P. In fact P(xt) is the SecAgg average over the randomly sampled client subset Ct, so r is random even conditional on xt. Unbiasedness would require E_{X∼Π,Ct}[λ(P_C(X)/Π(X)−1)−log(P_C(X)/Π(X))] = DKL(Π∥P), but Jensen's inequality gives E_C[−log(P_C/Π)] ≥ −log(E_C[P_C]/Π), with equality only if P_C is constant. A minimal example with X={0,1}, Π=(1/2,1/2), two clients with local distributions (0.9,0.1) and (0.1,0.9), and |Ct|=1 yields an estimator expectation of about 0.511 while DKL(Π∥P)=0. Thus Theorems 4.3 and 4.7 do not establish unbiasedness, and Theorem 4.4's variance bound inherits the same incorrect premise.","section":"Section 4.2.1, Theorem 4.3 (and Theorem 4.7)"},{"comment":"The DP proof sets f(P)=DKL(Π∥P) and adds Gaussian noise with variance proportional to Δ(f), the sensitivity of the exact KL query. But the released object is D̂, the noisy average of λ(r−1)−log r over T sampled symbols and sampled clients; D̂ is not f(P), and its sensitivity is not bounded by Δ(f). Theorem 4.10 bounds a per-sample expression by (α̂+1)|λ1−λ2| + λ2/(N m) + log 2, which is not a sensitivity bound for the final averaged estimator and still depends on λ0,P. Moreover, Theorem 4.9's bound Δ(η|P>1)<0.7 is restricted to histograms in which every symbol occurs at least twice (P>1), a condition not enforced by Algorithms 1–3 and unrealistic for the 65,536-symbol FEMNIST domain. Therefore the (ε,δ)-DP guarantee in Theorem 4.6 is not established.","section":"Section 4.2.2, Theorem 4.6 and Section 4.2.3, Theorem 4.9"},{"comment":"The DP proof for the Dist model asserts that one change to the input changes P(xt) by at most 1/N, but this is not justified under client-level adjacency: changing one client's data changes its local frequency by 1/|D_c|, so the aggregated average can change by 1/(|Ct||D_c|), which is not necessarily bounded by 1/N. The proof also does not account for the T queries or the effect of the max{·,τ} truncation on sensitivity. Consequently the Dist model's (ε,δ)-DP claim is not established.","section":"Section 4.3, Theorem 4.11"},{"comment":"The empirical claim that the private estimators achieve accuracy comparable to a non-private baseline is weakened by in-sample selection: in Section 5.1, λ is chosen by minimizing MSE on the same FEMNIST distribution pairs, and the MSE values reported in Section 5.2 are computed on those same pairs. There is no held-out split, cross-validation, or error bars, and the baseline estimator is not fully specified. The experimental conclusion is therefore descriptive of the fitted setting rather than a predictive comparison.","section":"Section 5.1 and Section 5.2"}],"minor_comments":[{"comment":"The notation for the noise η′ is confusing: line 10 and line 11 both add η′, and the proof later refers to 2η′/T, so the reader cannot tell whether the noise is added once or twice and what its variance is.","section":"Section 4.2.2, Algorithm 2"},{"comment":"The proof says 'By similar arguments to the proof of Theorem 4.6,' but Theorem 4.6 is the DP claim; the unbiasedness argument should refer to Theorem 4.3 or to Facts 4.1 and 4.2.","section":"Section 4.2.2, Theorem 4.7 proof"},{"comment":"Corollary 4.5 minimizes the upper bound from Theorem 4.4, not the actual variance; the text should say 'the variance upper bound is minimized at' rather than describing the result as the optimal λ0.","section":"Section 4.2.1, Corollary 4.5"},{"comment":"The narrative about choosing λ is inconsistent: Section 5.1.1 recommends λ=0.1, Section 5.1.2 later selects λ=0.05 for all models, and the relationship between these recommendations is not reconciled.","section":"Section 5.1"},{"comment":"The reference distribution Π for the FEMNIST experiments is not fully specified: it is unclear whether Π is the empirical distribution of a fixed writer/digit store or some other distribution, and how the 65,536-dimensional probabilities are formed from the reported 1,400-image samples.","section":"Section 5, experimental setup"}],"recommendation":"reject","confidential_remarks":"The paper addresses a timely and important problem, but the central formal claims are not correct as written. The unbiasedness and DP proofs contain load-bearing errors that are not localized presentation issues, and the experiments are partly in-sample. I would not consider this paper publishable in its current form; a substantially revised version that corrects the unbiasedness analysis under client subsampling and properly calibrates DP noise to the sensitivity of the actual released estimator could be reconsidered."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's what you should know. This paper has the right instinct—use a public reference distribution, sample from it, ask clients for local frequencies, and plug into the control-variate estimator λ(r−1)−log r—and it wraps that in three trust models. The sensitivity analysis of KL divergence under a replacement adjacency for histograms where every symbol appears at least twice (Theorem 4.9) is a real, new-looking result, and the paper is upfront that its Dist variant is biased.\n\nThe problem is that the headline theoretical claims do not survive contact with the actual algorithm. Theorem 4.3 and 4.7 claim unbiased estimation, but Algorithm 1 and 2 compute P(xt) by secure aggregation over a randomly sampled subset C_t of clients. That P_C is a random variable, not the global P. Fact 4.2 only says E_{X~Π}[λ(r−1)−log r] = DKL(Π||P) for a fixed P. After averaging over the client sample you get E_C[DKL(Π||P_C)], which Jensen only lower-bounds by DKL(Π||E_C[P_C]). A two-client, one-client-sampled example where the clients have swapped distributions gives estimator expectation about 0.51 while the true KL is 0. So the unbiasedness claims are not established. If every client participated every round, the proof would work; that is not the algorithm.\n\nThe DP proof has a parallel gap. Theorem 4.6 calibrates Gaussian noise to the sensitivity of the true KL query f(P)=DKL(Π||P), but the released quantity is the Monte Carlo estimate plus noise. What needs a sensitivity bound is the released estimator as a function of the dataset. Theorem 4.10 attempts that, but the bound contains |λ0,P1 − λ0,P2| and λ0,P2, so it is not a data-independent sensitivity, and the theorem is never used. The Dist proof (Theorem 4.11) is a handwave about histogram sensitivity that does not account for the SecAgg and clipping steps. There is also a practical support problem: when no sampled client has x_t, P(xt)=0 and log r(xt) is undefined; the full-support assumption on P is not ensured by the experiments. The empirical section selects λ by minimizing MSE on the same FEMNIST data used to report accuracy, so the 'comparable to baseline' result is partly in-sample.\n\nWhat is genuinely good: the decomposition into trust models, the control-variate estimator, and the restricted-domain sensitivity bound. The flaws are repairable—define the estimator over all clients or prove unbiasedness over the sampling, and do the DP proof for the actual estimator—but as submitted the central claims do not hold.\n\nI would send this to peer review rather than desk-reject, because the problem is real and a careful referee could guide a solid revision. I would not cite it in its current form.","headline":"A sensible architecture for private federated KL divergence, but the unbiasedness and DP proofs have a load-bearing gap: client subsampling makes the estimator biased and the sensitivity of the released estimator is never established.","tokens_in":20861,"tokens_out":4395,"would_cite":false,"duration_ms":43742,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P27","62B10","94A17"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that KL divergence from a public reference to private federated data can be estimated privately and with bounded communication through Monte Carlo probes, with unbiasedness in two trust models.","keywords":["KL divergence","federated learning","differential privacy","secure aggregation","Monte Carlo subsampling","distribution drift","trusted aggregator model","communication efficiency"],"falsifier":"Run Algorithm 1 on a fixed finite domain with $n$ clients, each holding one item, sampling $|C_t|1}})<0.7$; an information-theoretic inequality bounds the variance-optimal $\\lambda_0$, and Theorem 4.4 bounds the final variance.","core_discovery":"On the paper's own terms, the discovery is that KL divergence is estimable in the federated setting by drawing $T$ symbols from the public distribution $\\Pi$ and averaging the Bregman tangent expression $\\lambda(r-1)-\\log r$ with $r(x)=P(x)/\\Pi(x)$. Facts 4.1 and 4.2 show the expectation of this expression is $D_{\\mathrm{KL}}(\\Pi\\parallel P)$, giving unbiased estimates in the Trusted and TAgg models; adding Gaussian noise calibrated to the sensitivity of the KL query (bounded by $0.7$ on distributions whose symbols each occur at least twice, Theorem 4.9) yields $(\\varepsilon,\\delta)$-DP. The fully distributed variant adds client-side noise and a clipping floor $\\tau$, preserving DP but explicitly giving up unbiasedness.","pith_inferences":["The same Bregman-tangent estimator could be adapted to other divergences expressible as expectations under the reference distribution, so the algorithmic template may transfer beyond KL divergence.","A natural next step would be to derive privacy-amplification bounds from the random client subsampling itself; if such bounds hold, the required added noise could shrink as the sampling rate decreases.","The sensitivity analysis suggests the privacy guarantee is independent of domain size when all symbols appear frequently; testing on sparse high-dimensional domains would reveal how the $\\tau$ clipping in the Dist model interacts with that bound."],"forward_implications":["A server can detect distribution drift against a public reference without collecting raw client data, since the communication cost is $T$ probes and per-probe secure-aggregated counts.","Under the Trusted and TAgg models, the estimator is unbiased with variance bounded by Theorem 4.4, so accuracy improves by increasing $T$ or choosing $\\lambda$ near the recommended range.","The TAgg and Dist versions provide formal $(\\varepsilon,\\delta)$-DP guarantees, with Dist preferred empirically when privacy is strict and TAgg preferred as $\\varepsilon$ grows.","Because the sensitivity bound for the KL query is a constant below $0.7$, the Gaussian noise added for privacy does not scale with the size of the domain.","Experiments on the handwritten-digit benchmark indicate that sampling roughly 10% of clients per round and setting $\\lambda\\approx 0.1$ gives a good privacy-accuracy trade-off."],"supporting_citations":[{"why":"Defines the KL divergence that the estimator targets.","marker":"[7]"},{"why":"Supplies the $(\\varepsilon,\\delta)$-DP definition and the Gaussian noise mechanism used to privatize all three algorithm variants.","marker":"[8]"},{"why":"Provides the secure aggregation protocol used to compute $P(x_t)$ without revealing per-client inputs.","marker":"[6]"},{"why":"Establishes the shift-invariance obstruction that motivates comparing a private distribution with a public reference $\\Pi$ instead of two private distributions.","marker":"[10]"},{"why":"Supplies the Monte Carlo subsampling rationale for averaging per-sample estimates.","marker":"[24]"},{"why":"Identifies KL divergence as a Bregman divergence, giving the tangent expression $\\lambda(r-1)-\\log r$ used as the per-sample estimator.","marker":"[25]"},{"why":"Provides the information-theoretic inequality used to bound the optimal variance parameter $\\lambda_0$.","marker":"[26]"},{"why":"Supplies the handwritten-digit benchmark data used in the experimental comparison against the non-private baseline.","marker":"[27]"}],"fun_headline_variants":["Federated private KL divergence, efficient and accurate","Private KL divergence over federated networks","Distributed private KL divergence estimation","KL divergence with privacy in federated settings","Private and communication-efficient KL divergence"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The unbiasedness proofs assume that the aggregated frequency $P(x_t)$ equals the exact global probability $P(x_t)$ when the expectation identity is applied; if only a random subset of clients participates, the expected log ratio is not the log of the global ratio, so the promised zero bias can fail.","fun_headline_variants_meta":{"raw":{"variants":["Federated private KL divergence, efficient and accurate","Private KL divergence over federated networks","Distributed private KL divergence estimation","KL divergence with privacy in federated settings","Private and communication-efficient KL divergence"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000469,"raw_usage":{"total_tokens":2288,"prompt_tokens":849,"completion_tokens":1439,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":465,"completion_tokens_details":{"reasoning_tokens":1376}},"tokens_in":465,"tokens_out":1439,"duration_ms":13863,"temperature":1.0,"reasoning_tokens":1376,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T13:04:55.824139+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 on a fixed finite domain with $n$ clients, each holding one item, sampling $|C_t|