{"id":"cb557c9e-87e5-4a3f-b7ec-724f3676adb9","arxiv_id":"2509.02856","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"AHDP, an add-remove heterogeneous differential privacy framework, protects both user data and the user's privacy demand, and correlation-agnostic mechanisms exist for mean, frequency, and linear regression estimation.","lead":"Standard heterogeneous differential privacy falls short when a user's data and their requested privacy level are correlated, and the paper introduces a new definition, add-remove heterogeneous differential privacy (AHDP), that protects the (data, privacy demand) pair as a unit. The work is relevant because personalized privacy is used in data markets, and ignoring this correlation can publicly single out the users who ask for the most privacy.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; central claim survives, with minor non-central flaws (Example 1, Proposition 10 proof, count follow-up).","rationale":"The paper's central claim is that standard HDP is inadequate under data-privacy correlations and that AHDP restores meaningful guarantees with universal mechanisms. This claim is supported by the deterministic privacy-demand-output counterexample, which is well-defined and independent of the flawed Example 1, and by the distributional AHDP guarantee, which does not depend on an adversary knowing W. The reader's weakest assumption about adversary knowledge of W is a real boundary on the operational power bounds, but it is explicitly stated and does not affect the core definitional guarantee. The minor defects—Example 1's infinite Laplace scale, the omitted proof of Proposition 10, and the degenerate count case in Proposition 9—are localized and fixable. They do not threaten the existence of universal AHDP mechanisms, because the Sampling Mechanism and the count estimator inside Proposition 10 already provide valid constructions. Therefore the reader's conditional verdict remains appropriate, and no further verdict change is needed.","tokens_in":31170,"tokens_out":18610,"duration_ms":229434,"concrete_test":"Verify Proposition 10 by deriving the ratio mechanism from composition and post-processing (Propositions 1 and 2) with the numerator alpha1-AHDP and the denominator alpha2-AHDP; if the ratio fails to satisfy (alpha1+alpha2)-AHDP, the mean/frequency mechanisms would need revision. Also instantiate Proposition 9 with f≡1 to confirm the h-l=0 degeneracy; if count estimation does not follow, the paper should cite Proposition 10's denominator instead.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No load-bearing objection to the central claim. The HDP failure is established by the deterministic mechanism that outputs the privacy-demand vector (Section 2.4), which satisfies Definition 2 and leaks data whenever the correlation support W maps eps to x; this does not depend on the ill-defined Laplace mechanism in Example 1, where eps=0 makes 1/||eps||_1 infinite. AHDP's distributional guarantee is correlation-agnostic by construction, and Propositions 1-3 and 6-7 support the operational claims. The main residual issues are non-central: Proposition 10 is stated without proof; Proposition 9 as written cannot yield count estimation because for f≡1 one has h-l=0, giving a degenerate Laplace scale; and the threat-model bounds assume an adversary who knows W, which is an explicit modeling assumption rather than an internal inconsistency. None of these undermines the existence of universal AHDP mechanisms, since the Sampling Mechanism (Appendix F) is proved and the count estimator used inside Proposition 10 and frequency estimation is valid.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies heterogeneous differential privacy (HDP) when a user's data and privacy demand may be correlated. It argues that the conventional HDP definition (Definition 2), which treats datasets as neighboring if a single user's data changes while their privacy level is fixed, fails to provide meaningful protection under such correlations (Section 2.4). The paper introduces Add-remove Heterogeneous Differential Privacy (AHDP, Definition 3), in which neighboring datasets differ by adding or removing a (data, privacy-demand) tuple, and the privacy loss is governed by a function alpha on the support W of such tuples. It proves composition and post-processing (Propositions 1--2), gives a hypothesis-testing characterization (Proposition 3), derives adversarial power bounds for AHDP and homogeneous DP (Propositions 4--7), and constructs universal AHDP mechanisms that do not require knowledge of W: the Sampling Mechanism (Section 5.1), linear-query mechanisms (Proposition 9), a mean-estimation mechanism (Proposition 10), and a linear-regression mechanism (Mechanism 1). Experiments on LLM-generated synthetic data compare these mechanisms for mean estimation, frequency estimation, and regression.","tokens_in":31310,"tokens_out":7287,"duration_ms":77258,"significance":"If correct, AHDP is a useful contribution: it moves the neighboring-dataset relation to the joint data--privacy tuple, preventing the privacy demand itself from acting as a covert data channel. The hypothesis-testing interpretation (Section 4) is a clean unifying tool, and the power bounds give concrete statements about adversarial inference. The existence of universal AHDP mechanisms is the strongest part of the paper; in particular, the Sampling Mechanism is proved in Appendix F and is correlation-agnostic in a practical sense. The paper also releases its synthetic datasets. The main technical gaps (the ill-defined Example 1, the unproved Proposition 10, and the degenerate count case in Proposition 9) are localized and fixable; they do not appear to invalidate the AHDP definition itself.","major_comments":[{"comment":"The mechanism in Example 1 is not well-defined for the very dataset used to make the point. When all users have eps_i=0, we have ||eps||_1=0, so the term <eps,x>/||eps||_1 and the Laplace scale 1/||eps||_1 involve division by zero. The coupling also contains the tuple (0,∞), which requires arithmetic with infinity (e.g., ∞·0) that is not defined in the notation of Section 2.1. The subsequent deterministic example (outputting the privacy-demand vector) is a valid illustration of the failure, but Example 1 should be repaired or replaced, since it is presented as the primary demonstration of the central negative result.","section":"Section 2.4, Example 1"},{"comment":"The mean-estimation mechanism is asserted to be (α1+α2)-AHDP, but no proof is given. Appendix H proves the frequency-estimation mechanism, not Proposition 10, and the text does not reduce the claim to Proposition 9 or to composition. Since mean estimation is a headline application in the abstract and contributions, a proof (or a precise derivation) must be supplied.","section":"Section 5.2, Proposition 10"},{"comment":"The statement that count estimation 'immediately follows' by taking f(x)=1 is incorrect. For f≡1, l=h=1, so the Laplace scale h-l is zero and the proof divides by h-l; the proposed mechanism degenerates to the constant 1 and does not estimate the count. This should be corrected explicitly, for instance by excluding the degenerate f≡1 case or by using the Sampling Mechanism for count estimation.","section":"Section 5.2, Proposition 9"}],"minor_comments":[{"comment":"The experimental comparisons report only means or medians over trials. With 5000 trials in the first two experiments and 200 in the regression experiment, standard errors or confidence intervals should be reported; without them, claims such as 'SM, t=0.5 outperforms other methods' are not statistically substantiated.","section":"Section 6, Figures 6, 8, 9"},{"comment":"In the statement of Proposition 6, part (B2) says 'P(M,H1)' but the converse construction is for a mechanism M''; the notation should be consistent (P(M'',H1)).","section":"Section 4.2, Proposition 6(B2)"},{"comment":"Typo in the proposition statement: 'is satisfies' should be 'satisfies'.","section":"Section 5.2, Proposition 9"},{"comment":"There is a stray period in 'For example. In Acquisti and Grossklags [5]'.","section":"Section 1"},{"comment":"The abstract says the synthetic datasets are released for future research, but no repository or URL is provided. Please include a data availability statement.","section":"Abstract / Data availability"}],"recommendation":"major_revision","confidential_remarks":"The paper fits the journal's scope and the AHDP definition is a genuine contribution. The requested changes—repairing Example 1, proving Proposition 10, and correcting the count claim in Proposition 9—are local and feasible. If these are addressed, the paper could be acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Jim—\n\nWorth a look if you care about personalized DP. The central claim is right: standard HDP (swap-neighbor, fixed privacy demand) gives no meaningful protection when a user's privacy level is correlated with their data, because the mechanism that outputs the privacy vector alone satisfies HDP and leaks data. The fix is AHDP, which treats the (data, privacy) tuple as the protected unit and uses add-remove neighbors weighted by a domain W. That is essentially the add-remove HDP of Jorgensen et al., and the paper says so; the new part is formulating correlations as the support W, proving that W-agnostic ('universal') mechanisms exist, and quantifying adversarial power via hypothesis testing.\n\nThe main theorems hold up: composition, post-processing, the power bounds, and the linear-query mechanism are all derived cleanly. Proposition 8's impossibility of unbiased universal estimation is a nice, simple negative result. The hypothesis-testing framework in Section 4 is a useful lens even outside this paper.\n\nSoft spots are real but not fatal. Example 1 divides by ||epsilon||_1 with epsilon = 0, so the stated Laplace mechanism is undefined; the point is already made by the deterministic privacy-vector mechanism, so Example 1 should be repaired rather than deleted. Proposition 10 is stated without proof, and the text's claim that count estimation follows from Proposition 9 with f=1 is wrong—with l = h = 1 the mechanism outputs a constant, useless for counting. The count estimators used in the mean and frequency mechanisms are fine; the error is in that sentence. Experiments have no error bars and no artifact link, which matters since the datasets are LLM-generated and the prompt is the only spec. Those are all fixable in revision.\n\nOne modeling assumption to keep in view: the guarantees assume an adversary who knows W. That is explicit in Section 2.4, so it is not a hidden flaw, but it means the framework's threat model is support-aware. Fine for a first step.\n\nWho is this for? Anyone working on heterogeneous or personalized privacy, or on data markets. It is a solid extension, not a revolution, and the authors are honest about the prior work. I'd send it to review; the referees will have a clear, bounded list of corrections. Bring it to the reading group if you want a concrete example of why neighbor definitions matter.\n\nBest,\n\n[You]","headline":"A sound extension of heterogeneous DP that fixes a real gap—correlated data and privacy demand—but carries some rough edges in examples and reproducibility.","tokens_in":31845,"tokens_out":2361,"would_cite":true,"duration_ms":27349,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P27"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper argues that the usual heterogeneous differential privacy framework can silently leak data whenever users' privacy choices are correlated with their data, and that the fix is to redefine neighboring datasets as add/remove operation","keywords":["differential privacy","heterogeneous differential privacy","personalized privacy","data-privacy correlation","add-remove neighbors","hypothesis testing","mean estimation","linear regression"],"falsifier":"Run a membership-inference test on a correlated dataset with $W$ known to the adversary: for example, $W = \\{(1,0),(0,\\infty)\\}$ with all users at $(1,0)$, and a standard HDP mechanism that outputs the privacy-demand vector. The paper predicts the adversary can recover the dataset (power near 1) under standard HDP, while a $W$-AHDP mechanism on the same output must make the two hypotheses $\\{D_0\\}$ and $\\{D_0 + (1,0)\\}$ statistically indistinguishable with power at most $1/(1+e^0)=1/2$; the same experiment with $W$ hidden should show the leak disappears.","tokens_in":31005,"feed_emoji":"🔒","tokens_out":7361,"duration_ms":81953,"temperature":0.7,"texified_at":"2026-08-05T20:23:20.352375+00:00","pith_summary":"The paper argues that heterogeneous differential privacy (HDP), as usually defined, gives no real privacy when the data a user shares is correlated with the privacy level that user demands. The reason is that HDP treats two datasets as neighbors only when one user's data changes while that user's privacy level stays fixed; under correlation, such neighbor pairs can be absent, so a dataset can be uniquely identifiable. The paper's fix, add-remove heterogeneous differential privacy (AHDP), makes neighboring datasets differ by adding or removing one (data, privacy demand) tuple, and certifies the mechanism only if the per-tuple privacy budget stays below the user's demanded $\\epsilon$. This restores worst-case meaning: an adversary who knows the possible correlations still cannot distinguish the dataset from one that adds or removes a tuple, and the guarantee is expressed cleanly through hypothesis-testing bounds on adversarial power. A sympathetic reader would care because HDP is the framework used in personalized-privacy and data-auction work, where the independence assumption has been a convenience rather than a deliberate design.","texify_model":"deepseek-v4-flash","texify_usage":{"total_tokens":8058,"prompt_tokens":858,"completion_tokens":7200,"prompt_tokens_details":{"cached_tokens":0},"prompt_cache_hit_tokens":0,"prompt_cache_miss_tokens":858,"completion_tokens_details":{"reasoning_tokens":6394}},"feed_headline":"Correlated data and privacy choices break standard heterogeneous DP","feed_subtitle":"A new neighbor definition makes privacy promises hold even when sensitive data shapes users' privacy choices.","key_machinery":"The load-bearing object is the (data, privacy demand) tuple and the correlation-support set $W \\subseteq X \\times \\mathbb{R}_{\\ge 0}$. AHDP defines privacy through the add-remove distance $d_\\alpha(D,D') = \\sum_{(x,\\epsilon) \\in W} \\alpha(x,\\epsilon) |h_D(x,\\epsilon) - h_{D'}(x,\\epsilon)|$; a mechanism is $W$-AHDP when $\\alpha(x,\\epsilon) \\leq \\epsilon$, meaning the effective privacy guarantee for a tuple never exceeds what the user demanded. This distance turns the set of possible tuples into a graph and makes adding or removing any tuple the primitive privacy event, so a high-privacy tuple ($\\epsilon$ near 0) cannot silently be distinguished from an absent one. The universal mechanisms additionally use a bounded weighting functio","core_discovery":"On the paper's own terms, the central claim is that standard heterogeneous DP, defined with swap neighbors over data while holding each user's privacy level fixed, fails under data-privacy correlations, and that the right replacement is AHDP. In AHDP, datapoints are tuples $(x, \\epsilon)$, the domain $W$ of possible tuples is the model of correlation, and the privacy guarantee is that for every pair of datasets, the log-ratio of output probabilities is bounded by a weighted add-remove distance. The framework then yields concrete guarantees: for any $W$-AHDP mechanism and an adversary who knows $W$ and observes part of the dataset, the maximum probability of recovering the hidden data is bounded by ex","pith_inferences":["The paper's threat model assumes an adversary knows W, the support of possible (data, privacy-demand) pairs. If that knowledge is absent, publishing epsilon values is not automatically a data leak; the practical takeaway is that the public design of privacy menus must itself be treated as part of the privacy budget.","The same add-remove tuple perspective could be tested in a local-DP variant where users never reveal epsilon to the server, but the paper notes this makes it hard for the server to judge data quality; one could experiment with public sampling probabilities as a compromise.","The asymptotic bias formula suggests a concrete tuning rule: choose alpha(x,epsilon) to satisfy privacy while minimizing Cov(X, alpha(X,epsilon)) / E[alpha(X,epsilon)]; on a given dataset one can estimate this ratio and select among alpha functions by a bias-variance trade-off, which the experiments only begin to map.","A natural extension the authors leave implicit is to (epsilon,delta)-relaxations of AHDP and to use the hypothesis-testing power bounds as a membership-inference benchmark against real-world datasets, which they list as future work."],"forward_implications":["If AHDP is adopted, personalized-privacy mechanisms no longer need to assume data and privacy demand are independent; the same mechanism can be certified against any finite correlation support W.","Privacy demand itself must be treated as sensitive: mechanisms that merely publish epsilon values satisfy the old HDP definition but can be rejected by AHDP, since epsilon values correlate with data.","For any W-AHDP mechanism, an adversary with full knowledge of W, the mechanism, and part of the dataset has bounded identification power; for a single missing tuple the bound is 1/(1 + e^{-epsilon}) in the two-hypothesis model and 1/(1 + sum_{(x,epsilon) in W_o} e^{-epsilon}) in the one-tuple-hiding model.","Correlation-agnostic (universal) AHDP mechanisms exist: weighted linear queries with Laplace noise and the sampling mechanism, with simple implementations for sum, mean, frequency, and linear regression; no unbiased universal AHDP estimator exists for general linear statistics, but bias can be controlled, for example the asymptotic bias has a covariance term Cov(X, alpha(X,epsilon)) / E[alpha(X,ep","Basic sequential composition and post-processing hold for AHDP, so mechanisms can be built modularly and certified at the end."],"supporting_citations":[{"why":"Supplies the standard HDP definition and the linear weighted-sum mechanisms used in Example 1 to show that a dataset can be uniquely identified under correlations.","marker":"[36]"},{"why":"Provides the add-remove personalized DP definition and the Sampling Mechanism that the paper reuses as a universal AHDP mechanism.","marker":"[40]"},{"why":"Foundational definition of differential privacy and noise calibration that AHDP generalizes and composes.","marker":"[29,30]"},{"why":"Supplies the hypothesis-testing characterization of DP that Proposition 3 adapts to AHDP.","marker":"[42]"},{"why":"Statistical framework for DP treating privacy as a hypothesis-testing problem, which the adversarial-power analysis generalizes.","marker":"[56]"},{"why":"Exponential mechanism used in the paper's converse constructions of worst-case-optimal AHDP mechanisms.","marker":"[49]"},{"why":"Functional mechanism for private linear regression; Mechanism 1 is an AHDP-weighted variant of it.","marker":"[58]"}],"fun_headline_variants":["HDP falls when privacy demands are data-driven","New framework AHDP handles correlated data and privacy","Standard DP can't handle privacy choices as data — AHDP can","Correlated privacy choices? AHDP provides the fix","AHDP: robust privacy when data shapes your privacy level"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The negative result against the old HDP definition and the advertised guarantees of AHDP assume an adversary who knows the set of possible (data, privacy-demand) pairs; if the adversary does not know that set, publishing privacy demands does not obviously leak data, and the paper's threat-model bounds do not apply.","fun_headline_variants_meta":{"raw":{"variants":["HDP falls when privacy demands are data-driven","New framework AHDP handles correlated data and privacy","Standard DP can't handle privacy choices as data — AHDP can","Correlated privacy choices? AHDP provides the fix","AHDP: robust privacy when data shapes your privacy level"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00027,"raw_usage":{"total_tokens":1463,"prompt_tokens":743,"completion_tokens":720,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":487,"completion_tokens_details":{"reasoning_tokens":642}},"tokens_in":487,"tokens_out":720,"duration_ms":8640,"temperature":1.0,"reasoning_tokens":642,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T11:21:52.791474+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a membership-inference test on a correlated dataset with $W$ known to the adversary: for example, $W = \\{(1,0),(0,\\infty)\\}$ with all users at $(1,0)$, and a standard HDP mechanism that outputs the privacy-demand vector. The paper predicts the adversary can recover the dataset (power near 1) under standard HDP, while a $W$-AHDP mechanism on the same output must make the two hypotheses $\\{D_0\\}$ and $\\{D_0 + (1,0)\\}$ statistically indistinguishable with power at most $1/(1+e^0)=1/2$; the same experiment with $W$ hidden should show the leak disappears.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the standard HDP definition and the linear weighted-sum mechanisms used in Example 1 to show that a dataset can be uniquely identified under correlations."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the add-remove personalized DP definition and the Sampling Mechanism that the paper reuses as a universal AHDP mechanism."},{"cited_title":"Privacy-Aware Data Acquisition under Data Similarity in Regression Markets","cited_arxiv_id":"2312.02611","evidence_quote":"Statistical framework for DP treating privacy as a hypothesis-testing problem, which the adversarial-power analysis generalizes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Exponential mechanism used in the paper's converse constructions of worst-case-optimal AHDP mechanisms."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Functional mechanism for private linear regression; Mechanism 1 is an AHDP-weighted variant of it."}],"review_version":1}