{"id":"c0e8c247-8489-4941-9ab4-e8d3cdb8cd20","arxiv_id":"2608.03737","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"The Dependency Triad summarizes pairwise attribute dependence with three parameters and delivers a constant-time upper-bound estimate of correlation-induced privacy leakage.","lead":"This paper introduces the Dependency Triad, a three-number summary of how two data attributes are related, and uses it to estimate the extra privacy leakage those relations cause under local differential privacy. The goal is to let privacy budget calibration run fast and stay conservative even when the data distribution is not known exactly.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1's beta relies on an unproven LP relaxation; if phi_LP is not an upper bound on the exact phi, or if beta is not monotone in phi, the DT estimator can understate CPL.","rationale":"The reader's weakest_assumption identifies exactly the gap I find most load-bearing: the actual algorithm's beta comes from a relaxed LP whose upper-bound property is asserted but not proven, while the theorem guaranteeing no under-estimation is proven for a different calibration. This is the point at which the paper's central privacy claim -- that the DT reported leakage never understates true CPL -- could fail. I agree with the reader's verdict of CONDITIONAL: the concern is addressable because the LP is very likely a valid upper bound and beta is probably monotone nondecreasing in phi, but until those two links are proven (or empirically falsified with a concrete counterexample), the implementation's guarantee is not established. The paper has genuine independent support: a clear theoretical framework, extensive experiments, and an open-source artifact, all of which count in its favor. The gap is not a demonstrated contradiction and does not warrant rejection; it warrants a conditional acceptance pending a rigorous proof or a targeted numerical verification of the LP relaxation and the phi-to-beta monotonicity.","tokens_in":36357,"tokens_out":29419,"duration_ms":325670,"concrete_test":"For small alphabets (e.g., b=2..5), generate a dense grid of conditional distributions G and G' and uncertainty matrices Delta that keep probabilities in [0,1] and normalize to 1. For each instance: (1) compute phi_exact by enumerating all subsets S and solving the resulting small optimization over G,G', or brute-force gridding; (2) solve the LP in Algorithm 1 to get phi_LP; (3) check phi_LP >= phi_exact; (4) compute beta from (16) and verify it is finite and real; (5) compare the DT estimate from (14) against CPL* from Algorithm 3 for all epsilon in [0,10]. If any instance violates phi_LP >= phi_exact, yields undefined beta, or gives DT < CPL*, then Algorithm 1's privacy guarantee fails. If all instances pass, the missing proof is likely a minor exposition gap rather than a true flaw.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The paper's central privacy claim — that the DT estimator never understates CPL* — rests on Theorem IV.4, which is proven for beta calibrated to the exact CPL* at epsilon0. In the actual deployment path, Algorithm 1 obtains beta from phi computed by the relaxed LP at line 18. The paper asserts, but does not prove, that this LP is an upper bound on the exact MILP phi used in Theorem IV.8 and Definition V.1. Two specific links are missing: (i) a proof that the optimal value of the LP in lines 18-19 is at least the exact max_{S,G,G'} sum_{i in S}(G_i-G'_i) over the uncertainty set; and (ii) a proof that the mapping phi -> beta in (16) is monotone nondecreasing (so using an upper-bound phi cannot decrease the resulting CPL estimate). If either link fails, the delivered (alpha,beta,delta) may produce a CPL estimate below the true privacy loss, violating the paper's 'never understate' guarantee. The concern is not a demonstrated contradiction: the LP likely is an upper bound (setting z_i = max(0,G_i-G'_i) appears to satisfy the constraints), and beta appears monotone in phi, but neither is established. Because the core guarantee is a privacy bound, this missing proof is load-bearing. In addition, the pseudocode has an undefined 0/0 when M_i^+=M_i^-=0, which occurs for zero-probability symbols common in sparse distributions the paper claims to support.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes the Dependency Triad (DT), a three-parameter summary (α, β, δ) of a pairwise conditional distribution, intended to quantify correlation-induced privacy leakage (CPL) under local differential privacy. The authors extend the CPL optimization of [14] to settings with distributional uncertainty, give Algorithm 1 for computing DT (using a relaxed linear program), and give Algorithm 2 for constant-time CPL estimation. The central claims are that CPL-relevant pairwise dependency information can be compressed into three parameters, that the resulting estimator is a conservative upper bound on the exact CPL under distributional uncertainty, and that it scales to high-cardinality and sparse distributions. Experiments on synthetic and five real datasets compare DT with HCC-2/LTM, demonstrate privacy-budget calibration, attribute-inference resistance, and utility gains over random sampling.","tokens_in":36814,"tokens_out":12925,"duration_ms":153115,"significance":"If the theoretical claims are made rigorous, this is a useful contribution: it addresses a real limitation of existing CPL algorithms, which require ground-truth distributions and repeated per-budget computation. The paper ships an artifact link, includes extensive experiments on real datasets, and the idea of an uncertainty-aware, low-dimensional summary of CPL is appealing. However, the central privacy guarantee currently rests on several unproved or under-specified analytic steps, most importantly the relationship between the relaxed LP in Algorithm 1 and the exact calibration theorem. The contribution is therefore promising but conditional.","major_comments":[{"comment":"Theorem IV.4 proves the upper-bound property for a β calibrated using exact CPL* at ε0. In the deployment path, Algorithm 1 obtains β from φ produced by the relaxed LP at line 18 and the formula (16). The paper asserts that this LP is a polynomial-time upper bound to the exact MILP, but no proof is given that (i) the LP optimum is at least max_{S,G,G'} Σ_{i∈S}(G_i−G'_i) over the uncertainty set, and (ii) the map φ ↦ β, and then β ↦ CPL, is monotone nondecreasing. Without (i)–(ii), the delivered (α,β,δ) may understate CPL, violating the core 'never understate' guarantee. This needs an explicit lemma with proof.","section":"§V-B, Algorithm 1 lines 18–22 vs. Theorem IV.4"},{"comment":"The proof sketch asserts that the maximum CPL over all G,G' sharing ratio vector Q equals the maximum over two-point instances supported only on the extreme ratios e^α and e^{-γ}. Appendix C proves the value for a relaxed constraint set (27), but the reduction from the exact ratio-constrained set H to the extreme-ratio set \tilde H is only asserted: intermediate ratios with positive mass cannot simply be set to zero without changing Q, and the argument appears to yield a supremum rather than an attained maximum. Since Theorem IV.4 inherits this result, the equality needs a rigorous proof or a relaxation argument that establishes the upper bound directly.","section":"§IV-B, Theorem IV.1 and Appendix C"},{"comment":"The uncertainty-aware claim relies on Corollary J.1, which states that taking componentwise maxima of two characterizations gives an upper bound, justified by an 'easy' monotonicity of CPL in α, β, and δ. No proof of this monotonicity is provided, and it is not immediate from Corollary IV.7, which only addresses γ. This monotonicity is load-bearing: it justifies using the upper-bound φ from the LP and the entry-wise uncertainty box Δ. A proof for each parameter is needed.","section":"§IV-C, Theorem IV.8 and Appendix J, Corollary J.1"},{"comment":"The LP constraint contains the denominator M_i^+ + M_i^-. When M_i^+ = M_i^- = 0, the constraint is 0 ≤ z_i ≤ 0/0, which is undefined. This occurs when U_i = L'_i and U'_i = L_i, in particular for zero-probability symbols with zero uncertainty—exactly the sparse-distribution regime the paper claims to support. The pseudocode must define a convention (e.g., drop the constraint or set z_i = 0) and state it formally.","section":"§V-B, Algorithm 1 line 18"}],"minor_comments":[{"comment":"The line 'δ←min(1,max(δ, δ))' appears to contain a typo or variable shadowing; the global δ and the loop-local δ are confused. Please rename and clarify.","section":"§V-B, Algorithm 1 line 16"},{"comment":"The caption says 'Figure 3a and Figure 3a'; the second reference should be Figure 3b.","section":"Figure 3 caption"},{"comment":"The toy example states α=1.50, γ=1.38, δ=0 for both scenarios; it would help to state explicitly that α and γ are computed for a fixed ordered pair (x,x') and how the orientation that maximizes leakage is selected.","section":"§IV-B3, toy example"},{"comment":"The 'Near monotone likelihood ratio' row reports mean CPL estimation error 7.9e−4 at ε=0.1 but 2.5e−1 at ε=1 with a large standard deviation; the text should comment on this non-monotonicity in ε, since DT is intended to be tight in high-privacy regimes.","section":"Table IV"},{"comment":"Several theorem references in the text (e.g., 'Theorem IV.8' in the proof of Theorem IV.8, 'Theorem F' in Appendix F) are inconsistent or refer to the appendix by its letter. Please normalize numbering.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The LP-upper-bound issue is likely fixable—setting z_i = max(0, G_i − G'_i) appears to satisfy the constraints, and β appears monotone in φ—but as written the paper's central guarantee is not self-contained. The 0/0 bug in Algorithm 1 is concrete and must be fixed. I would not reject, but the revision must supply the missing proofs rather than only clarifications."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague—\n\nThe thing to know: the Dependency Triad is a genuinely new way to compress pairwise dependency for CPL: three parameters (α, β, δ) plus an uncertainty set, and then constant-time CPL evaluation. That is a useful step beyond ITS, CBP, HCC, and LTM, which need full distributions or heavy precomputation. The experiments on real datasets (SPM, CelebA, Adult, CVD, DSS) show tight NMSE against exact CPL*, and the paper is honest that DT is a conservative surrogate, not a full distribution. Credit where due: the calibration-at-ε0 idea is clever, the sparse-distribution handling via δ is a real attempt, and the authors release code on GitHub. The citation pattern is fine; the main comparisons to [14] and [26] are the right baselines.\n\nBut the reader's main reservation is correct and it is load-bearing. Theorem IV.4 proves the upper bound for a β calibrated against the exact CPL* at ε0. Algorithm 1 computes β from φ returned by a relaxed LP (line 18) and plugs it into (16). The paper never proves that LP value is an upper bound on the exact φ from Definition V.1/Theorem IV.8, and never proves β is monotone in φ. Without those two links, the 'never understates' guarantee of the implemented DT is unproven. The stress-test note's point about 0/0 is also real: when M_i^+ = M_i^- = 0, which happens for zero-probability symbols in exactly the sparse distributions the paper claims to support, the LP constraint is undefined. These are fixable, but for a privacy bound they cannot be left as assertions.\n\nThe circularity burden is also higher than the paper acknowledges. Setting ε0→0 means β is fitted so that the DT estimate equals exact CPL* at that one point. That's not a free prediction at the calibration point. The interesting claim is the upper bound for ε > ε0; the proof sketch in Appendix F is plausible but I did not verify it line by line, and the piecewise segment argument needs a careful check.\n\nBottom line: the central idea is solid and the paper deserves a serious referee. I would send it out, but with a clear request for major revision: prove the LP relaxation guarantees (or use the exact φ), fix the divide-by-zero edge case, and present experiments that separate fitted-at-calibration-point behavior from predictive upper-bound behavior. My own verdict would be conditional, not accept, until the gap is closed. For LDP researchers doing privacy-budget calibration, this is worth reading and testing once the proof gap is fixed.","headline":"The three-parameter compression is a real idea, but the shipped algorithm's core privacy guarantee is unproven because the LP-based beta is never shown to match the theorem's exact-calibration beta.","tokens_in":37192,"tokens_out":3646,"would_cite":false,"duration_ms":41534,"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":"The paper claims that three parameters—α, β, δ—suffice to summarize pairwise dependency information for local differential privacy, producing a constant-time conservative upper bound on correlation-induced leakage.","keywords":["Dependency Triad","local differential privacy","correlation-induced privacy leakage","privacy budget calibration","distributional uncertainty","conservative estimator","multidimensional data","constant-time CPL estimation"],"falsifier":"Take a pair of conditional distributions and an uncertainty matrix Δ, solve the exact maximization of Σ_{i∈S}(G_i−G′_i) over all feasible S,G,G′ by enumeration, and compare it with φ returned by the relaxed LP in Algorithm 1 (line 18). If φ is smaller than the exact maximum, compute DT's CPL estimate for ε>ε0 and compare with CPL* obtained by exhaustive search over S; an estimate below CPL* disproves the upper-bound claim for the algorithm as delivered.","tokens_in":36272,"feed_emoji":"🔒","tokens_out":8348,"duration_ms":91502,"temperature":0.7,"pith_summary":"Local differential privacy promises that a user's released data leaks at most ε, but when attributes are correlated the release of one attribute can leak information about another, and measuring that correlation-induced leakage normally requires the true joint distribution and scales poorly with alphabet size. This paper tries to remove both barriers. It argues that for any pair of attributes, the dependency information relevant to this leakage—including uncertainty about the prior distribution—can be compressed into three scalars, α, β, and δ, which it calls the Dependency Triad. From those scalars a closed-form estimate of worst-case pairwise leakage is evaluated in constant time, and the paper proves it is an upper bound that never understates the risk. The payoff is practical: privacy-budget calibration becomes a one-time parameter computation followed by instant evaluation at any budget, and imperfect prior knowledge can be folded into the parameters through an entry-wise uncertainty matrix.","feed_headline":"Three parameters bound privacy leakage from correlated data","feed_subtitle":"Dependency Triad compresses a joint distribution into α, β, δ and still guarantees the estimate never understates leakage.","key_machinery":"The carrying object is the ratio vector Q=G⊘G′, the element-wise division of the two conditional distributions. The proof first relaxes all feasible likelihood ratios to the extreme interval [e^{-γ}, e^α] and solves the resulting linear-fractional problem, obtaining a closed-form bound (Theorem IV.1) that depends only on the extremes; a sparsity correction δ is then introduced (Theorem IV.3). The calibrated lower endpoint e^{-β} replaces e^{-γ} by matching the estimate to the exact CPL* at a chosen budget ε0, and Theorem IV.4 shows the resulting estimate is an upper bound for all larger budgets. Uncertainty in the known distribution enters as an entry-wise matrix Δ that widens α, β, δ to the","core_discovery":"Given two correlated attributes X_k and X̂ with conditional probability vectors G and G′, the exact correlation-induced privacy leakage CPL* is the optimum of a ratio of linear forms over all subsets of X̂'s alphabet. The paper's central discovery is that the part of that distribution needed to upper-bound CPL* survives in just three scalars: α, the log of the largest (uncertainty-corrected) likelihood ratio; δ, the mass sitting on entries whose conditional denominator can be zero; and β, a calibrated lower ratio level obtained by matching the closed-form estimate to the exact CPL* at one chosen privacy budget ε0. With (α,β,δ) in hand, CPL is given by a piecewise closed-form expression, and","pith_inferences":["If the compression is as general as claimed, the same ratio-extremes-plus-calibration scheme should extend to approximate (ε,δ)-LDP mechanisms by adding a second slack term for the δ-privacy parameter; the paper lists this as future work, and the existing proof structure suggests the natural form.","Because β is calibrated at one anchor budget ε0, tightness is guaranteed to degrade as ε moves far above ε0; a testable extension is a piecewise triad with multiple anchor budgets, which would tighten the bound in low-privacy regimes without breaking the upper-bound property.","The two-sided sparsity slacks (δ̃, δ̂) derived in the proof are collapsed into a single δ for simplicity; on sparse or asymmetric distributions, keeping them separate would likely tighten the estimate while preserving the bound.","The empirical role split—β dominates leakage in the strong-privacy regime and α in the weak-privacy regime—suggests the triad could serve as an interpretable pairwise feature for selecting which attribute pairs to collect jointly or which are most exposed to attribute inference."],"forward_implications":["A one-time offline computation of (α,β,δ) costs O(a²b^3.5) and occupies O(1) space; after that, CPL at any privacy budget is a constant-time lookup, making iterative privacy-budget search practical for high-cardinality attributes.","Pairwise DT estimates compose through the sequential-composition bound into a total-leakage estimate for multidimensional records, so the triad serves as the building block, not the endpoint.","When several prior distributions are available, using the range or standard deviation as Δ yields uncertainty-aware per-attribute budgets that deliberately sit below the nominal optimum, hedging against demographic shifts.","Across five real datasets, DT's normalized error against exact CPL* stays below 0.025 for ε∈[0.01,10] and below 0.003 for ε≤1, so the conservative guarantee is tight where LDP is typically deployed.","In attribute-inference attack experiments at matched utility, DT achieves attack resistance comparable to simple budget splitting while consuming a smaller total privacy budget."],"supporting_citations":[{"why":"Supplies the ε-LDP definition adopted throughout; every privacy-leakage argument is built on this definition.","marker":"[8]"},{"why":"Formulates pairwise CPL as the subset-ratio optimization in (6) and provides the exact CPL* baseline that DT is designed to upper-bound.","marker":"[14]"},{"why":"Provides the piecewise-function CPL solution and the ratio-sorting view of the optimization that motivates compressing the ratio vector.","marker":"[26]"},{"why":"Yields the sequential-composition upper bound used to assemble pairwise CPL estimates into a total leakage bound.","marker":"[30]"},{"why":"Supplies the real-world SPM dataset used in the privacy-budget calibration and demographic-shift experiments.","marker":"[28]"}],"fun_headline_variants":["Three scalars, one tight bound on privacy leak","Dependency Triad: quantify correlated-data leakage fast","Correlated attributes? Leakage bound in just α, β, δ","Constant-time CPL estimate from three dependency numbers"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The upper-bound guarantee is proven for a β calibrated against the exact CPL* at ε0, but Algorithm 1 actually derives β from a relaxed linear program whose solution φ is asserted, not proven, to be an upper bound on the calibration statistic; if φ falls below the true maximum, the delivered estimate could understate the true leakage.","fun_headline_variants_meta":{"raw":{"variants":["Three scalars, one tight bound on privacy leak","Dependency Triad: quantify correlated-data leakage fast","Correlated attributes? Leakage bound in just α, β, δ","Constant-time CPL estimate from three dependency numbers"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000151,"raw_usage":{"total_tokens":1051,"prompt_tokens":774,"completion_tokens":277,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":518,"completion_tokens_details":{"reasoning_tokens":210}},"tokens_in":518,"tokens_out":277,"duration_ms":4140,"temperature":1.0,"reasoning_tokens":210,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T13:46:09.134465+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a pair of conditional distributions and an uncertainty matrix Δ, solve the exact maximization of Σ_{i∈S}(G_i−G′_i) over all feasible S,G,G′ by enumeration, and compare it with φ returned by the relaxed LP in Algorithm 1 (line 18). If φ is smaller than the exact maximum, compute DT's CPL estimate for ε>ε0 and compare with CPL* obtained by exhaustive search over S; an estimate below CPL* disproves the upper-bound claim for the algorithm as delivered.","supporting_citations":[{"cited_title":"Local privacy and statistical minimax rates,","cited_arxiv_id":null,"evidence_quote":"Supplies the ε-LDP definition adopted throughout; every privacy-leakage argument is built on this definition."},{"cited_title":"The Hidden Cost of Correlation: Rethinking Privacy Leakage in Local Differential Privacy","cited_arxiv_id":"2508.12539","evidence_quote":"Formulates pairwise CPL as the subset-ratio optimization in (6) and provides the exact CPL* baseline that DT is designed to upper-bound."},{"cited_title":"Quantifying differential privacy under temporal correlations,","cited_arxiv_id":null,"evidence_quote":"Provides the piecewise-function CPL solution and the ratio-sorting view of the optimization that motivates compressing the ratio vector."},{"cited_title":"A comprehensive survey on local differential privacy toward data statistics and analysis,","cited_arxiv_id":null,"evidence_quote":"Yields the sequential-composition upper bound used to assemble pairwise CPL estimates into a total leakage bound."},{"cited_title":"ACS Supplemental Poverty Measure (SPM) Research Files: 2009–2019, 2021–2023,","cited_arxiv_id":null,"evidence_quote":"Supplies the real-world SPM dataset used in the privacy-budget calibration and demographic-shift experiments."}],"review_version":1}