{"id":"f0941a62-8f16-4420-8b91-8e808ab0e149","arxiv_id":"2607.06320","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":4,"one_line_summary":"The dithered Gaussian mechanism discretizes the output of the Gaussian mechanism via a randomly shifted grid, inheriting Gaussian privacy guarantees while reducing private randomness to a constant per coordinate.","lead":"The paper introduces a way to add privacy-protecting noise to data that uses fewer high-quality random bits and avoids floating-point security vulnerabilities. A smart generalist might read it because it could make large-scale privacy-preserving machine learning (like DP-SGD) cheaper and more secure to deploy.","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"Algorithm 2's truncation range depends on f(X), so the approximate sampler is not a clean post-processing of the Gaussian mechanism; the paper does not formally bridge this gap.","rationale":"The reader correctly identified the most load-bearing concern: the gap between the idealized exact-sampling mechanism (for which the post-processing argument is clean and correct) and the approximate Algorithm 2 (which is used in all experiments but lacks a formal privacy guarantee). The core theoretical contributions — the post-processing argument for exact sampling, the entropy bound (Lemma 3), the TV distance bound (Proposition 2), and the lower bound (Theorem 4) — are all correct and well-proved. The concern is specifically about the practical implementation: Algorithm 2's truncation range depends on f(X), so its output is not a deterministic post-processing of the Gaussian mechanism, and the paper does not formally bridge this gap. This is addressable: a TV-distance argument would likely show that the privacy degrades by at most O(δ'), but the paper needs to state and prove this. The verdict remains CONDITIONAL because the core theory is sound and the gap is bridgeable, but until it is bridged, the practical privacy guarantee for the implemented algorithm is unverified. No code is provided, which further limits reproducibility of the experimental claims. I agree with the reader's assessment.","tokens_in":23852,"tokens_out":4025,"duration_ms":268726,"concrete_test":"Formally derive the privacy guarantee of Algorithm 2 as follows: For a 1-dimensional instance, let P_X be the ideal distribution (Eq. 6) and Q_X be the truncated-and-renormalized distribution from Algorithm 2. Compute dTV(P_X, Q_X) as a function of f(X)_i, σ, ξ, and δ'. If this TV distance is uniformly bounded by δ' (or c·δ' for small constant c) over all f(X)_i, then by the standard post-processing + TV argument, Algorithm 2 satisfies (ε, δ + 2δ')-DP. If the TV distance is not uniformly bounded — e.g., if it grows with |f(X)_i|/σ — then the truncation introduces a data-dependent privacy leak and the concern lands hard. This check can be done analytically or numerically for a grid of parameter values.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claim — that the dithered Gaussian mechanism 'directly inherits the privacy guarantees of the standard Gaussian mechanism' via post-processing — is correct for the idealized Algorithm 1 with exact sampling: Z_i is a deterministic function of f(X)_i + y_i, so M(f(X)) is post-processing of the Gaussian mechanism (Lemma 5). However, the practical Algorithm 2 used in all experiments does not sample from the exact distribution in Eq. (6). It truncates the sampling range to [k_min_i, k_max_i] where k_min_i = floor(c_i - σz_δ'/ξ), k_max_i = ceil(c_i + σz_δ'/ξ), and c_i = f(X)_i/ξ - γ_i + 1/2. Since c_i depends on f(X)_i, the truncation range is data-dependent. The algorithm then renormalizes probabilities within this range (line 16: P_i,· ← P_i,· / Σ P_i,j). The renormalization factor 1/(1 - p_tail) depends on f(X)_i because the tail mass p_tail outside the range depends on where the range is centered relative to the distribution. This means the output of Algorithm 2 is NOT a deterministic function of f(X) + y; it is a different distribution whose relationship to the Gaussian mechanism is not established. The paper does not prove that Algorithm 2 satisfies (ε, δ + δ')-DP or any variant. The tail probability is bounded by δ' uniformly over f(X) (by construction of z_δ'), so a standard TV-distance argument would likely yield (ε, δ + 2δ')-DP, but this is not stated or proved. Since all experimental results (Figure 5) use Algorithm 2, the practical privacy guarantee for the demonstrated DP-SGD training is formally unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"glm-5.2","summary":"The paper introduces the 'dithered Gaussian mechanism,' a method for differential privacy that discretizes the output of the Gaussian mechanism rather than the noise distribution. The key idea is that rounding a Gaussian-perturbed value to a randomly shifted grid constitutes post-processing of the standard Gaussian mechanism, thereby directly inheriting its $(ε,δ)$-DP guarantee. The authors show that this approach requires only $O(d)$ private random bits with per-coordinate entropy independent of the noise scale $σ$ (Lemma 3), by separating randomness into a public dither and a private sampling step. A lower bound on private entropy for any DP mechanism is established (Theorem 4). Experiments on CIFAR-10 demonstrate that the mechanism can be used in DP-SGD with cryptographically secure noise generation at modest overhead (~30%) compared to standard implementations.","tokens_in":24106,"tokens_out":1516,"duration_ms":281841,"significance":"The paper addresses a genuine practical gap: the mismatch between idealized continuous Gaussian noise and finite-precision implementations, and the high cost of cryptographically secure randomness at scale. The post-processing argument for privacy is clean and correct for the idealized mechanism (Algorithm 1): since $Z_i$ is a deterministic function of $f(X)_i + y_i$, the output is a post-processing of the Gaussian mechanism (Lemma 5). The entropy bound (Lemma 3) is derived from first principles using a standard discrete entropy inequality (Lemma 7) and a Cauchy-Schwarz variance bound, and is parameter-free in the sense that it depends only on the ratio $σ/ξ$. The lower bound (Theorem 4) provides a matching scale for private entropy. The DP-SGD experiments provide a falsifiable practical benchmark. These are substantive contributions to the theory and practice of differential privacy.","major_comments":[{"comment":"§3, Algorithm 2 and Appendix B: The central claim that the mechanism 'directly inherits the privacy guarantees of the standard Gaussian mechanism' via post-processing (Lemma 5) is correct for the idealized Algorithm 1 with exact sampling. However, the practical Algorithm 2 used in all experiments (Figure 5) does not sample from the exact distribution in Eq. (6). Algorithm 2 truncates the sampling range to $[k^{min}_i, k^{max}_i]$ where $k^{min}_i = ⌊c_i - σz_{δ'}/ξ⌋$, $k^{max}_i = ⌈c_i + σz_{δ'}/ξ⌉$, and $c_i = f(X)_i/ξ - γ_i + 1/2$. Since $c_i$ depends on $f(X)_i$, the truncation range is data-dependent. The algorithm then renormalizes probabilities within this range (line 16: $P_{i,·} ← P_{i,·} / Σ P_{i,j}$). The renormalization factor $1/(1 - p_{tail})$ depends on $f(X)_i$ because the tail mass $p_{tail}$ outside the range depends on where the range is centered relative to the discret","section":null},{"comment":"distribution. This means the output of Algorithm 2 is NOT a deterministic function of $f(X) + y$; it is a different distribution whose relationship to the Gaussian mechanism is not formally established. The paper does not prove that Algorithm 2 satisfies $(ε, δ + δ')$-DP or any variant. The tail probability is bounded by $δ'$ uniformly over $f(X)$ (by construction of $z_{δ'}$), so a standard TV-distance argument would likely yield $(ε, δ + 2δ')$-DP, but this is not stated or proved. Since all experimental results (Figure 5) use Algorithm 2, the practical privacy guarantee for the implemented mechanism is not formally established. This is a load-bearing gap: the paper's motivation emphasizes avoiding floating-point vulnerabilities and inheriting Gaussian privacy, but the actually implemented mechanism lacks a formal privacy proof. The fix is likely straightforward (a TV-distance argument或","section":null},{"comment":"a coupling argument showing the approximate sampler is within $δ'$ of the exact sampler), but it must be stated explicitly.","section":null}],"minor_comments":[{"comment":"Abstract: 'thedithered' — missing space. Also appears in §1 ('thedithered Gaussian mechanism').","section":null},{"comment":"§3, Eq. (6): The notation $Pr[Z_i = k]$ uses $f(X)_i$ but the conditioning on $γ_i$ is implicit. Making the conditioning explicit (e.g., $Pr[Z_i = k | γ_i]$) would improve clarity.","section":null},{"comment":"§3, Figure 2: The caption references $N(0, 2)$ but the figure labels show $σ=1, 2, 4$. It would help to clarify the relationship between the figure parameters and the caption.","section":null},{"comment":"§4, Figure 4: The discrete Gaussian comparison uses discretization levels $h ∈ {0.5/√d, 1/√d, 2/√d}$, but the text in §2 discusses sensitivity increases from discretization. It would be helpful to note whether the RMSE comparison accounts for the sensitivity increase of the discrete Gaussian.","section":null},{"comment":"Appendix B, Algorithm 2, line 16: The normalization step uses $P_{i,·}$ notation that is not defined elsewhere. Clarifying that this refers to the vector $(P_{i,0}, ..., P_{i,m-1})$ would help.","section":null},{"comment":"§3.1: The comparison to Ghentiyala [26] is useful but the claim that Ghentiyala's variance in random bits is 'much higher' could benefit from quantitative support.","section":null},{"comment":"Appendix C, proof of Theorem 4: The constant $a$ is introduced as 'a sufficiently small absolute constant' but its relationship to $c_0$ is not fully specified. A brief remark on the required relative sizes would help reproducibility.","section":null},{"comment":"§4: The experiments use batch size 512, which is noted as affecting the overhead. It would strengthen the paper to include at least one data point with a smaller batch size to show how overhead scales, given that the paper cites Egan [20] on overheads at batch size 32.","section":null}],"recommendation":"major_revision","confidential_remarks":"The core theoretical contribution (post-processing argument + entropy bound) is sound and novel. The gap between the idealized and approximate sampler is the main issue, but it appears fixable with a standard TV-distance argument. I would recommend the authors add a formal theorem (likely in Appendix B) proving that Algorithm 2 satisfies $(ε, δ + O(δ'))$-DP, and update the main text to clarify that the implemented mechanism has this slightly relaxed guarantee. If this is addressed, the paper should be suitable for publication."},"author_rebuttal":{"model":"glm-5.2","summary":"The referee correctly identifies that Algorithm 2 (the practical implementation) lacks a formal privacy proof, because the data-dependent truncation and renormalization break the direct post-processing argument that applies to the idealized Algorithm 1. We agree this is a load-bearing gap and will add a formal proof. The fix is indeed a TV-distance argument: per coordinate, the truncated-and-renormalized distribution is within δ' in TV distance of the exact distribution (since the tail mass is at most δ' by construction), giving an overall (ε, δ + d·δ')-DP guarantee for Algorithm 2. We will state and prove this explicitly in the revision.","responses":[{"response":"The referee is correct on all counts. Algorithm 2's truncation range depends on c_i = f(X)_i/ξ - γ_i + 1/2, which depends on the data, and the renormalization on line 16 changes the distribution so that the output is no longer a deterministic post-processing of f(X) + y. The post-processing argument (Lemma 5) applies only to the idealized Algorithm 1. We will add a formal privacy proof for Algorithm 2 in the revision.","revision_made":"yes","referee_comment":"Algorithm 2 truncates the sampling range data-dependently and renormalizes, so its output is NOT a deterministic function of f(X)+y. The relationship to the Gaussian mechanism is not formally established. The paper does not prove Algorithm 2 satisfies (ε, δ+δ')-DP or any variant. Since all experiments use Algorithm 2, the practical privacy guarantee is not formally established."},{"response":"We agree and will include the following argument explicitly in the revision. For each coordinate i, let P denote the exact distribution of Z_i (from Algorithm 1 / Eq. 6) and let Q denote the truncated-and-renormalized distribution (from Algorithm 2). By construction, the truncation range [k_i^min, k_i^max] is centered at c_i and has half-width σ·z_{δ'}/ξ, so the tail mass p_tail = Pr_{P}[Z_i ∉ [k_i^min, k_i^max]] ≤ δ' uniformly over all f(X)_i (by the choice of z_{δ'}). A direct calculation shows that dTV(P, Q) = p_tail ≤ δ' per coordinate: for k in the range, |P(k) - Q(k)| = P(k)·p_tail/(1-p_tail), and for k outside the range, |P(k) - Q(k)| = P(k), so dTV(P,Q) = (1/2)[(1-p_tail)·p_tail/(1-p_tail) + p_tail] = p_tail. Since the d coordinates are independent, the TV distance between the joint distributions is at most d·δ' (by a standard coupling/union bound). By the standard result that if P satisfies (ε,δ)-DP and dTV(P,Q) ≤ η then Q satisfies (ε, δ+η)-DP, Algorithm 2 satisfies (ε, δ + d·δ')-DP. In the experiments, δ' can be set to δ/(2d) (or smaller) so that the additional privacy loss d·δ' is at most δ/2, which is negligible relative to the target δ. We will state this bound as a theorem, verify that the experimental parameters satisfy it, and clarify in the experimental section that the reported privacy budgets account for this additional term. We thank the referee for identifying this gap.","revision_made":"yes","referee_comment":"The fix is likely straightforward (a TV-distance argument or coupling argument showing the approximate sampler is within δ' of the exact sampler), but it must be stated explicitly."}],"tokens_in":23600,"tokens_out":2102,"duration_ms":111518,"standing_objections":[]},"desk_editor":{"model":"glm-5.2","letter":"The main thing to know: this paper proposes a discretized Gaussian mechanism that inherits (ε,δ)-DP via post-processing, with constant per-coordinate private entropy independent of noise scale. The core construction is new and the theory for the idealized version is correct. The one real gap is that the practical implementation (Algorithm 2) is not formally bridged to the privacy theorem, though the gap is closeable with a standard argument.","headline":"Core idea is genuinely new and the theory for the idealized mechanism is sound; the gap between the idealized sampler and the practical Algorithm 2 is real but addressable.","tokens_in":24646,"tokens_out":1378,"would_cite":true,"duration_ms":147232,"reading_group":"no","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"glm-5.2","headline":"Rounding Gaussian Noise to a Grid Cuts Private Randomness to a Constant","keywords":[],"falsifier":"If the approximate sampling procedure (Algorithm 2) introduces distributional errors that depend on f(X) in a way that cannot be bounded by the truncation parameter delta', the privacy guarantee could be compromised. A concrete test would be to construct neighboring datasets X and X' where the truncation boundaries fall differently relative to f(X) and f(X'), and verify whether the output distributions satisfy the (epsilon, delta)-differential privacy inequality.","tokens_in":23871,"feed_emoji":"🎲","tokens_out":1078,"duration_ms":210305,"temperature":0.7,"pith_summary":"The dithered Gaussian mechanism is a method for releasing differentially private statistics that produces discrete outputs while inheriting the privacy guarantees of the continuous Gaussian mechanism. The core idea is to take the output of the standard Gaussian mechanism—adding Gaussian noise to a sensitive value—and round it to a randomly shifted grid. Because this rounding is a post-processing step applied after the noise has already been added, the privacy guarantee carries over automatically, with no need for a separate privacy analysis. The random grid shift (the dither) is generated from public randomness and can be revealed to an adversary without compromising privacy. The key insight is that, conditioned on the public dither, the discrete output can be sampled directly from an explicit distribution over grid points, rather than first sampling a continuous Gaussian value and then rounding it. This direct sampling requires only a constant number of private random bits per coordinate, independent of the noise scale sigma, because the grid spacing can be chosen comparable to the noise scale without significantly distorting the output distribution. The paper proves an upper bound on the private entropy per coordinate and a matching lower bound showing that the ratio of the privacy noise scale to the accuracy scale governs the minimum private randomness required. Applied to differentially private stochastic gradient descent, the mechanism provides cryptographically secure noise generation with roughly 20-30% runtime overhead compared to standard implementations, while eliminating floating-point vulnerabilities that arise when continuous noise is naively discretized by a computer's floating-point representation.","feed_headline":"Rounded Gaussian Noise Cuts Private Random Bits to a Constant","feed_subtitle":"A grid-based post-processing of the Gaussian mechanism inherits privacy for free while needing only O(d) cryptographic random bits, with 20-","key_machinery":"The mechanism works by observing that the event of rounding the Gaussian-perturbed value to a particular grid point k is equivalent to the Gaussian noise falling in a specific interval, whose probability is a difference of Gaussian CDF values. This gives an explicit discrete distribution that can be sampled directly. The public dither gamma_i = (a*i + b) mod 1, generated from just two uniform random numbers a and b, provides pairwise-independent per-coordinate grid shifts. The entropy bound uses the fact that the discrete output Z_i can be viewed as a rounded version of a Gaussian random variable, and applies a discrete maximum entropy bound (Lemma 7) combined with a variance bound obtained","core_discovery":"The central object is the dithered Gaussian mechanism, defined by adding Gaussian noise to a sensitive value, adding a public random offset, rounding to a grid, and then subtracting the offset. The mechanism's discrete output distribution, conditioned on the public dither, can be written in closed form as a difference of Gaussian cumulative distribution function values, enabling direct sampling from the discrete distribution without generating intermediate continuous Gaussian noise. This yields a private entropy bound of (d/2) log_2(2*pi*e*((sigma/xi + 1/2)^2 + 1/12)) bits, which is constant per coordinate when the grid spacing xi is chosen comparable to the noise scale sigma. The privacyguа","pith_inferences":[],"forward_implications":["The dithered approach can serve as a drop-in replacement for the Gaussian mechanism in any system that already uses Gaussian-based privacy accounting, including composition theorems and subsampling amplification, without requiring re-derivation of privacy bounds.","The separation of public and private randomness suggests a practical architecture where fast public pseudorandom generators supply the dither while slower cryptographic generators handle only the low-entropy private sampling step, reducing the cost of cryptographically secure noise in large-scale private machine learning.","The same dithering construction extends to the Laplace mechanism, where the paper shows improved randomness complexity bounds over prior work, suggesting the technique is broadly applicable to additive-noise privacy mechanisms beyond the Gaussian case.","The lower bound (Theorem 4) establishes that the ratio of noise scale to accuracy scale fundamentally governs private randomness requirements, providing a benchmark against which any future randomness-efficient private mechanism can be measured."],"fun_headline_variants":["Dithered Gaussian Mechanism Makes Private Random Bits Independent of Noise Scale","Discretizing Gaussian Outputs Cuts Cryptographic Random Bits to Constant per Coordinate","Public Dither Offset Lets Gaussian Privacy Survive Grid Rounding","Grid-Rounded Gaussian Noise Needs Only O(d) High-Quality Random Bits","Two-Source Randomness Separation Reduces Private Entropy in Gaussian Mechanism"],"cache_read_input_tokens":0,"weakest_assumption_plain":"The privacy guarantee rests on the claim that the discrete output can be sampled exactly from the distribution defined by differences of Gaussian CDF values. In practice, the paper uses an approximate sampler that truncates the sampling range with small probability delta', and if the truncation or precision of this approximate sampler introduces errors that depend on the sensitive input, the clean post-processing argument that inherits Gaussian privacy may not fully apply to,","fun_headline_variants_meta":{"raw":{"variants":["Dithered Gaussian Mechanism Makes Private Random Bits Independent of Noise Scale","Discretizing Gaussian Outputs Cuts Cryptographic Random Bits to Constant per Coordinate","Public Dither Offset Lets Gaussian Privacy Survive Grid Rounding","Grid-Rounded Gaussian Noise Needs Only O(d) High-Quality Random Bits","Two-Source Randomness Separation Reduces Private Entropy in Gaussian Mechanism"]},"model":"glm-5.2","effort":"high","cost_usd":0.0,"raw_usage":{"total_tokens":634,"prompt_tokens":553,"completion_tokens":81,"prompt_tokens_details":null},"tokens_in":553,"tokens_out":81,"duration_ms":35862,"temperature":1.0,"reasoning_tokens":null,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-08T09:50:06.627046+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"If the approximate sampling procedure (Algorithm 2) introduces distributional errors that depend on f(X) in a way that cannot be bounded by the truncation parameter delta', the privacy guarantee could be compromised. A concrete test would be to construct neighboring datasets X and X' where the truncation boundaries fall differently relative to f(X) and f(X'), and verify whether the output distributions satisfy the (epsilon, delta)-differential privacy inequality.","supporting_citations":[],"review_version":1}