{"id":"5191a13b-28ea-40ed-935a-19829a6f3387","arxiv_id":"2412.10357","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A correlated-noise mechanism releases differentially private sparse histograms with roughly half the threshold and noise of the standard Gaussian Sparse Histogram Mechanism.","lead":"This paper shows a private counting method that adds one shared random number to all counts, then smaller individual noise, so it can safely discard more low counts. The result is a sparse histogram with roughly half the error at the same privacy level, which could make private search logs and usage statistics noticeably more accurate.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.5's tighter privacy bound rests on an acknowledged sketch whose key conditional-probability inequality is unproved; the factor-of-two threshold reduction is therefore not yet established.","rationale":"The reader's verdict is CONDITIONAL and correctly flags the acknowledged sketch in Theorem 3.5. My stress-test agrees with that verdict but identifies a different weakest point than the reader's stated weakest_assumption. The reader emphasized the requirement of an a priori sparsity bound k; that is a genuine limitation, and the paper's own Section 8 acknowledges it, but it is a modeling assumption rather than a correctness gap. The more load-bearing issue for the central factor-of-two claim is the unproved conditional-probability inequality inside the proof of Theorem 3.5. That inequality is the only thing connecting the correlated Gaussian mechanism bound with the threshold/private-loss event in the technically difficult U⊂U′ case. The paper explicitly writes 'We sketch the argument below', so the incompleteness is acknowledged, not hidden. I do not claim the theorem is false: Theorem 3.3 (add-the-deltas) has a complete proof and already gives a provable improvement in many settings, and the discrete-Gaussian section provides an independent zCDP argument. But the headline informal theorem and the best experimental numbers depend on Theorem 3.5. A conditional verdict is therefore exactly right: accept only after the sketch is replaced by a rigorous proof, or the informal theorem is softened to what follows from Theorem 3.3. My recommendation is UNCHANGED because the reader's CONDITIONAL verdict already captures this requirement; I would only sharpen the condition by naming the specific unproved inequality that must be supplied.","tokens_in":22690,"tokens_out":9094,"duration_ms":83071,"concrete_test":"Take a concrete instance, e.g., k=2, j=1, σ=1, τ=2, ε=0.35. Compute the bad-output set Y_ε for mechanism F and numerically evaluate whether Pr[G(g′)∈Y_ε] ≤ Pr[F(g′)∈Y_ε] / ψ(k−j), using Monte Carlo or exact numerical integration over the Gaussian densities. If the inequality fails for any parameter choice, Theorem 3.5's U⊂U′ case is false. If it holds for a range of parameters, the authors still must supply a complete proof of the conditional-probability chain replacing the sentence 'We sketch the argument below'.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central utility claim (noise and threshold reduced by about a factor of two) is justified mainly by Theorem 3.5, the 'tighter analysis'. Its proof in Appendix B, case U⊂U′, contains the step: 'We sketch the argument below' followed by an assertion that Pr[F(g′)∈Y_ε] / ψ(k−j) ≥ Pr[G(g′)∈Y_ε]. This inequality is the bridge that converts the Gaussian-mechanism bound with privacy parameter ε̂(j)=ε+ln ψ(k−j) into the final (ε,δ) bound for the correlated mechanism. The provided justification relies on several unproved conditional-probability orderings: Pr[G(g′)∈Y_ε | N_{k+1}≤β] ≥ Pr[G(g′)∈Y_ε], Pr[⊤ | F(g′)≤β] ≥ Pr[⊤], and an equality equating F-conditioned probabilities to G-conditioned probabilities. These are nontrivial because F outputs additional coordinates and a ⊥ symbol, and conditioning on ⊤ correlates the noise on the extra entries with the shared k+1-th noise. The proof also does not define precisely how Y_ε, a set over F's output space, is evaluated under G's distribution. Without this inequality, the fourth term of the max in Theorem 3.5 is unsupported. Since the experiments and the informal factor-of-two statement rely on this theorem, the central claim is not yet rigorously verified. This is a gap in the argument, not an external disagreement: the proof itself labels the step a sketch.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the release of k-sparse histograms under (ε,δ)-differential privacy. It proposes the Correlated Stability Histogram (CSH, Algorithm 2), which adds a shared correlated Gaussian sample Zcorr to all non-zero counts before thresholding, adapting the correlated Gaussian mechanism of Lebeda [2024]. The authors give two privacy analyses: an add-the-deltas bound (Theorem 3.3) and a tighter case-by-case bound (Theorem 3.5), claiming that the CSH achieves the same privacy with roughly half the noise magnitude and half the threshold of the Gaussian Sparse Histogram Mechanism (GSHM). They extend the mechanism to the top-k setting without a known sparsity bound (Section 4), to aggregator functions (Section 6), and to discrete Gaussian noise (Section 7), and they report experiments (Section 5) showing threshold reductions of about 43% for large k.","tokens_in":22984,"tokens_out":23718,"duration_ms":168617,"significance":"The mechanism is a natural application of correlated noise to sparse histograms, and the discrete Gaussian variant is practically motivated. The add-the-deltas analysis (Theorem 3.3) is complete and already yields an asymptotic factor-of-two improvement in noise magnitude for large k, which is a genuine contribution. However, the tighter analysis (Theorem 3.5), which drives the best experimental numbers, is not rigorously proven; the proof in Appendix B contains a sketched inequality and internal inconsistencies. Thus, while the central idea appears sound, the strongest quantitative claims currently rest on an unverified theorem.","major_comments":[{"comment":"The key inequality Pr[G(g′)∈Y_ε] ≤ Pr[F(g′)∈Y_ε]/ψ(k−j) is only sketched (\"We sketch the argument below\") and is load-bearing for the fourth term of the max in Theorem 3.5. The conditional-probability steps are asserted without proof, and there are internal inconsistencies: G adds noise to coordinate k+1 for both g and g′, while F adds noise only to non-zero entries; since g_{k+1}=0, G(g) and F(g) do not have the same distribution as the proof claims. The set Y_ε is defined via F's densities but is then used for G without a precise embedding. A complete proof of the inequality, with a clear definition of Y_ε over the common output space, is required before Theorem 3.5 can be accepted.","section":"Appendix B, proof of Theorem 3.5 (case U⊂U′)"},{"comment":"Because the fourth max term uses εhat(j)=ε+ln ψ(k−j) and this depends entirely on the unproved inequality from Appendix B, the theorem is currently unsupported. The paper's abstract and Section 1.1 present the factor-of-two improvement as the main result, and Figure 3 attributes the best threshold reduction to \"tighter analysis (this work)\"; therefore this gap affects the paper's central quantitative claims. The authors should either provide a rigorous proof or explicitly state Theorem 3.5 as a conjecture and base the headline claims on Theorem 3.3 with the appropriate asymptotic caveat.","section":"Section 3.2, Theorem 3.5"},{"comment":"The informal statement that CSH achieves parameters σ/2+o(1) and τ/2+o(1) is not formally derived from either Theorem 3.3 or Theorem 3.5. The paper should state and prove a formal asymptotic version of this claim (e.g., from Theorem 3.3), or clearly delimit which quantitative improvement follows from each theorem. Without this, the connection between the headline claim and the formal results is not explicit.","section":"Section 1.1, Theorem 1.1"}],"minor_comments":[{"comment":"Several typos obscure the proof: \"ĝ_i = ĝ_i\" should presumably be \"ĝ_i = g′_i\"; \"H̃_i = g̃_i + g̃_i/k^{1/4}\" should presumably be \"H̃_i = g̃_i + g̃_{k+1}/k^{1/4}\"; \"repeatable sample\" should be \"repeatedly sample\"; and the condition \"until H̃_i≠i\" is unclear, likely \"H̃_i≠0\".","section":"Appendix B"},{"comment":"The line \"Ĥ(X′)_i = 2·Ĥ(X′)_i−1\" is self-referential and should read \"2·H(X′)_i−1\".","section":"Lemma 7.5"},{"comment":"The claimed modification of δgauss to √(k+5√k) when releasing an estimate of H(X)_{(k+1)} is stated without proof or citation; it needs a derivation or a reference.","section":"Section 4, last paragraph"},{"comment":"The sentence \"τ′ = 1 + H(X)_{(k+1)}\" appears inconsistent with Algorithm 3, which subtracts H(X)_{(k+1)} (without the +1) from all counters.","section":"Section 6, Additional sparsity threshold"},{"comment":"Step (1) is described as a union bound, but it is actually a deterministic implication (if the sum exceeds τ, then at least one of the two thresholds is exceeded); rephrasing would improve accuracy.","section":"Lemma 3.2 proof"},{"comment":"In Algorithm 4, the noise samples are Z_i∼N_Z(0,4σ^2) and Z_corr∼N_Z(0,4σ^2/√k), while the output divides by 2; the text should clarify that the \"scale\" parameter of the discrete Gaussian is not the standard deviation, to avoid confusion with the continuous case.","section":"Section 7, Algorithm 4"}],"recommendation":"major_revision","confidential_remarks":"The manuscript's main gap is in the proof of Theorem 3.5, which is a significant but local issue. The add-the-deltas analysis is complete and gives a credible factor-of-two asymptotic improvement, so the paper is salvageable with a major revision. I would suggest the editor require the authors to either prove the sketched inequality rigorously or restructure the claims around Theorem 3.3. The paper cites the first author's prior work heavily, but this is a legitimate use of prior results rather than circularity. The experimental section should be updated to avoid overclaiming based on the unproven tighter analysis."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Hi [Name],\n\nThe short version: this paper introduces the Correlated Stability Histogram (CSH), which adds one correlated Gaussian sample to all counters of a sparse histogram before thresholding, and proves privacy bounds. The add-the-deltas analysis (Theorem 3.3) is complete, clearly written, and already gives a real improvement over the standard GSHM in the k-sparse setting. The tighter analysis (Theorem 3.5) is not complete; the key inequality in Appendix B is explicitly sketched, and the sketch rests on conditional-probability orderings that are nontrivial and may or may not hold. The factor-of-two claim in Theorem 1.1 is backed mainly by that theorem, so it is not yet established.\n\nWhat is new: adapting Lebeda's correlated Gaussian trick to the thresholded stability histogram is not routine, because the threshold creates the infinite-privacy-loss event and the correlated noise couples the counters. The paper handles that coupling honestly and provides the top-k extension and a discrete Gaussian variant, both useful. I believe the mechanism itself is sound and the add-the-deltas bound is a legitimate contribution.\n\nWhere it is soft: first, Theorem 3.5. The proof labels one step a sketch, and the inequality Pr[G(g')∈Y_ε] ≤ Pr[F(g')∈Y_ε]/ψ(k-j) is the bridge that converts the Gaussian bound into the final fourth term. Without a full argument, the best numerical results are unsupported. This is fixable but it is a real gap. Second, the informal Theorem 1.1 states noise σ/2 + o(1) and threshold τ/2 + o(1) without a formal asymptotic statement; the o(1) is not defined relative to what. Third, the mechanism requires an a priori bound on the ℓ0 norm of the histogram, and the top-k extension subtracts the (k+1)-th largest count, which adds bias; the paper acknowledges this in Section 8. That is a limitation, not a flaw.\n\nMy recommendation: deserve a serious referee. Not a desk reject. The sound part is worth publishing; the tight-analysis gap should be resolved before acceptance. I would tell the authors to either complete the proof of Theorem 3.5 or soften the claims and clearly mark which numerical results depend on the sketch.\n\nOverall: worth reading if you work on private histograms or sparse queries. The paper is honest about its own gaps, which makes me trust it more.\n\nBest.","headline":"Novel and useful extension of correlated Gaussian noise to thresholded sparse histograms, with a fully proved add-the-deltas bound and an acknowledged gap in the tighter analysis that should be fixed before the factor-of-two claim is accepted.","tokens_in":23558,"tokens_out":2136,"would_cite":true,"duration_ms":19607,"reading_group":"yes","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 adding one sample of correlated Gaussian noise, shared across all non-zero counters of a sparse histogram, lets the Gaussian Sparse Histogram Mechanism deliver the same differential privacy guarantee with roughly…","keywords":["differential privacy","Gaussian sparse histogram mechanism","correlated noise","stability histogram","sparsity","top-k counting queries","discrete Gaussian mechanism"],"falsifier":"Take the mechanism configured with $k=1$ and run it on a two-entry histogram whose support can grow by two between neighbors. The asserted $\\delta_{\\mathrm{inf}}$ uses the exponent $k+1=2$ in Lemma 3.2, but the actual event of either of two newly appearing counters crossing the threshold has probability $1-\\Phi(\\tau/(\\sigma(1+1^{-1/4})))^{3}$, which exceeds the claimed bound; a numerical check of these probabilities for realistic $\\tau,\\sigma$ settles whether the sparsity assumption can be relaxed.","tokens_in":22453,"feed_emoji":"📊","tokens_out":9453,"duration_ms":77338,"temperature":0.7,"pith_summary":"The paper claims that the standard Gaussian Sparse Histogram Mechanism (GSHM) can be improved by adding a single shared sample of correlated Gaussian noise to every non-zero counter, producing the Correlated Stability Histogram (CSH). The authors prove that if the histogram is known to be $k$-sparse and monotonic, CSH achieves the same $(\\varepsilon,\\delta)$-differential privacy as GSHM with noise magnitude $\\sigma/2+o(1)$ and threshold $\\tau/2+o(1)$, effectively halving the dominant source of error at no privacy cost. The key step is a tail bound (Lemma 3.2) controlling the probability that any of the correlated noisy terms crosses the threshold, which replaces the corresponding independent-noise bound in the GSHM analysis. The paper also extends the mechanism to top-$k$ counting without a known sparsity bound, and to discrete Gaussian noise; both extensions inherit the factor-two improvement in settings where the added bias is acceptable.","feed_headline":"Correlated noise halves the cost of private sparse histograms","feed_subtitle":"One shared Gaussian sample cuts both noise and threshold by up to half at the same privacy budget.","key_machinery":"The load-bearing object is the shared correlated noise sample $Z_{\\mathrm{corr}}\\sim N(0,\\sigma^2/\\sqrt{k})$, added to every non-zero counter along with an independent $N(0,\\sigma^2)$ sample. Because all counters share $Z_{\\mathrm{corr}}$, the combined noise is no longer independent across entries, and the paper's Lemma 3.2 supplies the replacement tool: the probability that any of $j+1$ correlated noisy terms exceeds $\\tau$ is at most $1-\\Phi(\\tau/(\\sigma(1+k^{-1/4})))^{j+1}$. This bound, joined with the intermediate-histogram construction (a synthetic histogram with the same support as one neighbor but the values of the other) and with Lemma 2.8 from the correlated Gaussian mechanism, lets the proofs separate the Gaussian-privacy loss $\\delta_{\\mathrm{gauss}}$ from the infinite-privacy-loss event $\\delta_{\\mathrm{inf}}$ and show that both scale as if the effective sensitivity were about half of the uncorrelated mechanism's $\\sqrt{k}$.","core_discovery":"On the paper's own terms, the central discovery is that monotonicity and a known sparsity bound $k$ make it possible to use the correlated Gaussian mechanism in the sparse regime. Algorithm 2 samples one correlated noise $Z_{\\mathrm{corr}}\\sim N(0,\\sigma^2/\\sqrt{k})$ and adds it, together with independent $N(0,\\sigma^2)$ samples, to each non-zero counter; the correlated term carries a $1/\\sqrt{k}$-scaled version of the signal that would otherwise have to be paid for independently on all $k$ counters. Theorem 3.3 (add-the-deltas) and Theorem 3.5 (tighter case analysis) give explicit upper bounds on $\\delta$ for this mechanism, and Theorem 1.1 states the consequence: if GSHM releases a $k$-sparse monotonic histogram under $(\\varepsilon,\\delta)$-DP with noise $\\sigma$ and threshold $\\tau$, then CSH does so with noise $\\sigma/2+o(1)$ and threshold $\\tau/2+o(1)$.","pith_inferences":["Beyond the paper, the authors state that Theorem 3.5 is not tight; an exact analysis along the lines of the uncorrelated GSHM analysis would pin down whether the factor-two is inherent or partly an artifact of the proof technique, and could further lower the threshold.","Beyond the paper, the top-$k$ reduction's bias suggests a trade-off the paper only sketches: spending part of the privacy budget on a private estimate of $H(X)_{(k+1)}$ and adding it back as post-processing would let a user trade noise against bias deliberately.","Beyond the paper, the correlated-noise trick is not tied to Gaussians in principle; the discrete Gaussian construction's reliance on half-integer steps indicates that any noise distribution closed under affine post-processing could host the same mechanism, a testable hypothesis for other discrete families.","Beyond the paper, because the improvement factor grows with $k$, the practical win is concentrated where $k$ is large relative to per-user sparsity $m$; the paper notes that for $m\\le k/4$ the uncorrelated GSHM remains preferable, leaving open whether the alternative correlated-noise construction could cover that regime."],"forward_implications":["If Theorem 1.1 is correct, any deployment of GSHM on $k$-sparse monotonic histograms can halve its noise magnitude and threshold while keeping the same $(\\varepsilon,\\delta)$, shrinking worst-case error by roughly a factor of two.","In the Misra-Gries sketch setting, where $k$-sparsity holds by construction, the same privacy budget buys a materially more accurate sketch-derived histogram without changing the sketch size.","The paper's experiments show the looser add-the-deltas analysis of CSH already beats the exact uncorrelated analysis: at $k=51914$ with $(\\varepsilon,\\delta)=(0.35,10^{-5})$ the required threshold drops from about $13950$ to about $7860$, a reduction of about 43 percent.","The discrete Gaussian variant (Algorithm 4) gives the same improvement on finite computers, using half-integer scaling so the correlated-noise trick survives discretization; its privacy proof runs through $\\rho$-zCDP rather than a direct $(\\varepsilon,\\delta)$ analysis.","For histograms with no known sparsity bound, Algorithm 3 first subtracts the $(k+1)$-th largest count, producing a $k$-sparse monotonic histogram; privacy is preserved, but the pre-processing adds bias that grows when the data is far from $k$-sparse."],"supporting_citations":[{"why":"Gives the exact privacy analysis of the uncorrelated GSHM, which serves as the baseline and as the case-distinction template the tighter analysis extends.","marker":"[Wilkins et al. 2024]"},{"why":"Introduces the add-the-deltas technique and the GSHM with Gaussian noise, the main comparison point for the CSH's looser analysis.","marker":"[Google Anonymization Team 2020]"},{"why":"Supplies the correlated Gaussian mechanism and the monotonicity technique that the CSH adapts to the sparse setting.","marker":"[Lebeda 2024]"},{"why":"Analyzes correlated Gaussian noise for sparse user contributions; the paper cites it as the alternative that yields no practical improvement for $k\\ll d$ in this setting.","marker":"[Joseph and Yu 2024]"},{"why":"Provides the analytic Gaussian mechanism calibration (Lemma 2.5) used in every $\\delta$ bound in the paper.","marker":"[Balle and Wang 2018]"},{"why":"Provides the discrete Gaussian distribution and the multivariate discrete Gaussian zCDP guarantee used in Section 7.","marker":"[Canonne et al. 2022]"},{"why":"Establishes that Misra-Gries sketches of size $k$ produce $k$-sparse monotonic histograms, motivating the sparsity assumption.","marker":"[Lebeda and Tetek 2023]"}],"fun_headline_variants":["Correlated noise halves private sparse histogram error","Sparse histograms get half the noise with correlated Gaussian","CSH: correlated noise halves threshold for private histograms","Private histogram threshold halved by correlated noise","Halving noise and threshold in private sparse histograms"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that every dataset has at most $k$ non-zero histogram entries, and that neighboring histograms are monotone (all counts move in the same direction); if the true sparsity ever exceeds $k$, the probability bound on revealing a previously-zero counter is no longer valid and the claimed $\\delta$ is not guaranteed.","fun_headline_variants_meta":{"raw":{"variants":["Correlated noise halves private sparse histogram error","Sparse histograms get half the noise with correlated Gaussian","CSH: correlated noise halves threshold for private histograms","Private histogram threshold halved by correlated noise","Halving noise and threshold in private sparse histograms"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000276,"raw_usage":{"total_tokens":1668,"prompt_tokens":987,"completion_tokens":681,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":603,"completion_tokens_details":{"reasoning_tokens":607}},"tokens_in":603,"tokens_out":681,"duration_ms":7023,"temperature":1.0,"reasoning_tokens":607,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T15:56:30.261737+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the mechanism configured with $k=1$ and run it on a two-entry histogram whose support can grow by two between neighbors. The asserted $\\delta_{\\mathrm{inf}}$ uses the exponent $k+1=2$ in Lemma 3.2, but the actual event of either of two newly appearing counters crossing the threshold has probability $1-\\Phi(\\tau/(\\sigma(1+1^{-1/4})))^{3}$, which exceeds the claimed bound; a numerical check of these probabilities for realistic $\\tau,\\sigma$ settles whether the sparsity assumption can be relaxed.","supporting_citations":[],"review_version":1}