acceptodds
Under review as a conference paper at ICLR 2027

Dithered Gaussian Mechanism for Randomness-Efficient Differential Privacy

Abstract

We present the dithered Gaussian mechanism, an alternative to the discrete Gaussian mechanism for differential privacy that discretizes the private output rather than the noise distribution itself. By interpreting this discretization as post-processing of the Gaussian mechanism, our construction directly inherits the privacy guarantees of the standard Gaussian mechanism while avoiding vulnerabilities caused by finite-precision floating-point outputs. We show that the mechanism is provably randomness-efficient: by sampling the discretized output values directly, the number of high-quality random bits required for privacy can be reduced significantly and made independent of the noise level. This is achieved by separating the randomness into two sources: a high-quality source used for the privacy-critical sampling step, and a high-performance public source, possibly known to the adversary, that supplies the additional randomness needed for randomized discretization. This separation enables the use of cryptographically secure randomness without substantial performance loss. As an application, we study model training with DP-SGD and show that cryptographically secure noise generation with reduced exposure to floating-point vulnerabilities can be achieved with modest practical overhead.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
differential privacy, randomness efficiency, discrete noise, floating-point vulnerability, cryptographically secure noise

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_H4KyOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposed a dithered Gaussian mechanism, which is an alternative to the discrete Gaussian mechanism for differential privacy and is randomness-efficient. Separating the needed randomness enables the use of cryptographically secure randomness without substantial performance loss, and empiricaly validation on DP-SGD has been shown.

Critical strengths

The paper is well structured and nicely written. The presentation is clear and the contribution is clear as well and sufficient. The math looks reasonably correct. The empirical evidence on DP-SGD looks comprehensive.

Critical weaknesses

My major concern is the motivation and contribution, especially on how the authors concince me that they improve the randomness complexity. Please refer to the next section "Questions For Authors".

Questions for authors

I do not use AI-tools to review, so it is likely I miss some of the details and have grammar mistakes since I am not a native speaker. If so, please just indicate what I miss or where I am wrong. Thank you.

Some question that I wish the authors can clarify:

  • The authors say the drop-in replacement for the Gaussian mechanism is "time-efficient", does this just mean "randomness (required to sample Gaussian noise)-efficient", or a consequence of it? I see, e.g., in table 6, there is a modest runtime overhead; I agree the overhead is modest, but why it is called "time-efficient"? Is it because of comparing to other baselines that I miss?
  • The authors said that the number of private random bits can be made independent of the Gaussian noise scale, "without significantly changing the distribution of the perturbation relative to the Gaussian mechanism", so how much does it change the distribution?
  • Is the runtime overhead of about 3% − 7% the only sacrifice by using the authors' method?
  • I am a bit confused that, I agree the authors' method should be randomness-efficient, but why in experiments the authors put a lot of effort in measuing the runtime? Are the directly coorelated?
  • My background in mainly differential privacy in a theory perspective, and I was not very familiar with the "randomness complexity". The authors motivated the study of the "randomness complexity" by saying, e.g., "recent efforts to train language models entirely under differential privacy, such as the VaultGemma 1B model, required quadrillions of Gaussian random draws and petabytes of randomness to obtain a formal privacy guarantee (VaultGemma Team, 2025)", then can the authors method be applied to significantly help on this scenario?
  • Is the runtime overhead due to the dithering or the use of "cryptographically secure randomness" from the Python 'secrets' module? Also, the authors should clarify more on the use of "cryptographically secure randomness" in their method.
3 comments

Thanks for good questions! We comment on each below.

W1 (motivation and contribution). The discrete Gaussian needs about log⁡2(σΔ~/h)+2\log_2(\sigma \tilde\Delta/h) +2 bits per coordinate (equation 4), resulting in 40 bytes in the practical JAX_privacy implementation; the dithered Gaussian needs at most 2.662.66 bits at ξ=σ\xi = \sigma independent of σ\sigma and dd (Lemma 3), allowing us to use only 2 bytes in our PyTorch implementation. The discrepancy in the exact number of random bits is due to computational trade-offs (e.g. sampling a single bit is not cheaper than sampling a single byte of randomness, as calling the random number generator is expensive). We hope that this and our answers to specific questions below address your concern.

Q1 (meaning of “time-efficient”). This is in relation to other methods that avoid floating point vulnerabilities and use cryptographically secure randomness generators. Tables 1-4 show speedups of 2x to 500x. In the context of DP-SGD, this reduces the overhead relative to implementing the Gaussian mechanism with non-secure randomness to 4-7%, while using the discrete Gaussian incurs overheads of 45-220%. We will rephrase to make this more clear.

Q2 (change of distribution). Lemma 1 gives the exact noise distribution for every input. Proposition 2 bounds the total variation distance from Gaussian noise, e.g. 0.02 for ξ=σ\xi=\sigma, see Figure 2 for the dependency on ξ/σ\xi/\sigma.

Q3 (what is sacrificed). There are three main sacrifices, all relatively minor: 1) The runtime overhead you note, 2) A slight increase in noise at the same privacy level, e.g. 4% standard deviation for ξ=σ\xi = \sigma, resulting in a slight degradation in accuracy (Tables 8 and 9), and 3) Noise is not additive across parties, so it cannot directly be combined with secure aggregation in federated settings.

Q4 (runtime). They are related but not the same. Randomness complexity matters because cryptographically secure random bits are relatively expensive to generate. Tables 1-4 show the cost of applying cryptographically secure random bits compared to using cheaper pseudorandomness, showing that noise generation is a bottleneck in the former.

Q5 (help in practical scenarios). In principle, yes. Our method replaces the noise addition step in DP-SGD and uses the same privacy accountant so the efficiency results apply at any scale, making use of cryptographically secure generators (and hence computational DP) feasible. However, we have not run at VaultGemma d≈109d \approx 10^9 scale, our largest experiment is on BERT-Base with d≈108d \approx 10^8.

Q6 (source of overhead). On GPU the sampling arithmetic is cheap, and in large dimension most time usage is for generating secure bytes on the CPU and transferring to the GPU (3.1 ms with non-secure vs 74 ms with secure randomness at d=107d = 10^7, see Tables 2 and 4). At d=105d = 10^5 the two parts are comparable (1.4 vs 2.3 ms). Both could be reduced with improved hardware support for secure random generation on the GPU. We use the secrets module only for sampling the ZiZ_i, the dither comes from cheap, public randomness.

Thank you for your detailed responses. I appreciate the authors' efforts, and several of my original concerns have been addressed.

I have carefully considered based on the authors' responses and discussions with other reviewers. I still have reservations regarding the overall contribution and practical significance of the proposed method. One thing I concern is the TV guarantee is only for the marginal distribution rather than the joint, and it could be unclear to what extent the proposed method can significantly benefit large-scale models, which was an important motivation.

I also share Reviewer 5fpw's remaining concerns regarding the numerical accuracy assumptions and the lack of fully certified guarantees for the practical implementation.

Considering these remaining concerns, I would prefer to maintain my original score and let AC decide. Thank you.

Thanks for the follow-up. We would like to comment on two aspects.

1. Total variation distance guarantee We would like to emphasize that if the shifts are chosen uniformly at random rather than using pairwise independence, we do get a bound on total variation distance for the whole output vector. Since the shifts can be chosen using cheap, public randomness this is arguably not even at a significant cost in practice, even though the total randomness complexity will increase.

2. Numerical accuracy assumptions Though reducing reliance on guarantees of underlying libraries will be a meaningful improvement of our work, we feel that the discussion so far has overlooked an aspect of the bigger picture:

Existing practical DP-SGD implementations rely on a questionable assumption, namely A0: A standard, fast pseudorandom generator is sufficient to defend against attacks on privacy.

Our work shows that this assumption can be replaced, at low cost, with a much more believable and tested assumption namely A0*: A cryptographically secure pseudorandom generator is sufficient to defend against attacks on privacy. Even under additional assumptions A1-A3 we argue that the guarantees provided are significantly stronger than for past implementations.

Reviewer_5fpwOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes the Dithered Gaussian Mechanism, a randomness-efficient alternative to the discrete Gaussian mechanism for differential privacy. The key idea is to discretize the output of the Gaussian mechanism using a randomly shifted grid, allowing the resulting mechanism to inherit the privacy guarantees of the standard Gaussian mechanism through post-processing. The authors establish bounds on private randomness complexity and characterize the utility loss introduced by dithering. Experiments demonstrate substantial reductions in randomness consumption and competitive performance in DP-SGD.

Critical strengths

The paper addresses an important practical problem at the intersection of differential privacy, numerical security, and computational efficiency. The proposed mechanism is conceptually elegant, particularly in its use of post-processing to preserve existing Gaussian privacy accounting.

The theoretical analysis of randomness complexity is valuable, and the experimental evaluation extends beyond synthetic benchmarks to practical DP-SGD workloads. The authors also make a meaningful effort to address numerical implementation issues through adaptive-precision sampling.

Critical weaknesses
  • W1: Insufficient Guarantees for Finite-Precision Implementations: A central motivation of the paper is to address vulnerabilities in finite-precision Gaussian sampling. However, the formal privacy guarantee applies to an idealized mechanism, while the implementation relies on numerical Gaussian CDF evaluations, floating-point acceptance criteria, and an arbitrary-precision fallback. Although Appendix B describes reasonable precautions, it does not establish rigorous bounds on numerical errors or their impact on privacy guarantees. In particular, a fixed numerical margin alone does not constitute a certified error bound. This gap between theory and implementation weakens the paper's central security claim.

  • W2: Limited Characterization of High-Dimensional Utility: Lemma 1 and Proposition 2 characterize the marginal noise distribution and its proximity to a Gaussian, but do not establish similar guarantees for the joint distribution. The proposed affine dither construction ensures pairwise independence while introducing higher-order dependencies among coordinates. Although these dependencies do not invalidate the privacy argument, their effects on optimization and learning dynamics remain unclear. A direct comparison with independent dithering would help determine whether reducing public randomness introduces practical utility trade-offs.

Questions for authors
  • Q1: Can the authors provide a rigorous numerical-error bound for the practical sampling implementation, and characterize how this error affects the resulting differential privacy guarantee?

  • Q2: How do the higher-order dependencies introduced by affine dithering affect high-dimensional noise properties and the convergence behavior of DP-SGD? Could the authors compare affine dithering against fully independent dithering?

  • Q3: Can the authors disentangle the effects of privacy accounting, input discretization, and implementation differences in their comparison with discrete Gaussian mechanisms?

6 comments

Thanks for your constructive feedback and questions! We comment on each point below.

W1/Q1 (Insufficient Guarantees for Finite-Precision Implementations). We agree that a fixed margin is not a certified bound, so we have now analyzed the error. Floating point computations are used only to certify samples: a candidate kk is accepted only if the random interval [L,R)[L, R), which is represented exactly, lies inside the cell [F(k−1),F(k))[F(k−1), F(k)) by more than a margin. If the margin is larger than the error of the two computed CDF values, the accepted kk is the ideal inverse-transform sample for every continuation of the random bits. The output then has exactly the distribution in eq. (6), and the privacy guarantee is unchanged, with no additional ε\varepsilon or δ\delta. A rounding analysis bounds this error by 2−52ξ(∣k∣+2)/σ2^{-52}\xi (|k|+2)/\sigma plus the error of the float64 CDF routine. This is far below our margin of 10−1210^{-12} in our experiments, but it can exceed it when σ\sigma is small relative to ∣f(X)i∣|f(X)_i|, so the concern is justified. We will replace the fixed margin by this per-coordinate bound and will state the result as a proposition in Appendix B. The remaining coordinates are resolved in arbitrary precision with exact rational inputs and 64 guard bits. We evaluated torch.special.ndtr in float64 on a uniform grid of 10610^6 points in [−10,10][-10,10], comparing against a 100-digit mpmath reference. This range covers the expected CDF arguments in our sampling algorithm. The maximum observed absolute error was 1.19×10−161.19\times10^{-16}.

W2/Q2 (Limited Characterization of High-Dimensional Utility). The use of pairwise independence for the shifts is used only to get O(log⁡d)O(\log d) public bits in Lemma 10. This already suffices to get the same covariance structure as with fully random shifts, and the uniform parts account only for a fraction 1/13 of the variance for ξ=σ\xi=\sigma. In practice, there are many cheap alternatives that avoid higher-order dependencies. We repeated the CIFAR-10 experiments using dithers generated by a pseudorandom generator for each coordinate independently, which we refer to as “Fully independent”, and compared them with the proposed pairwise independent sampling. We report the new results in the table below. The differences are within the reported error bars for most settings, with no systematic advantage for either approach.

MechanismDither γi\gamma_iε=0.5\varepsilon = 0.5ε=1\varepsilon = 1ε=2\varepsilon = 2ε=4\varepsilon = 4ε=8\varepsilon = 8
Dithered (ξ=0.5σ\xi = 0.5\sigma)Pairwise independent42.3 ±\pm 0.447.2 ±\pm 0.551.5 ±\pm 1.453.9 ±\pm 0.556.2 ±\pm 1.1
Fully independent43.3 ±\pm 0.447.3 ±\pm 0.951.2 ±\pm 1.254.2 ±\pm 0.656.2 ±\pm 0.7
Dithered (ξ=σ\xi = \sigma)Pairwise independent42.6 ±\pm 0.346.4 ±\pm 0.750.5 ±\pm 0.554.2 ±\pm 0.356.7 ±\pm 1.2
Fully independent42.2 ±\pm 0.546.9 ±\pm 0.451.1 ±\pm 0.853.0 ±\pm 1.056.4 ±\pm 0.9
Dithered (ξ=2σ\xi = 2\sigma)Pairwise independent42.5 ±\pm 0.445.5 ±\pm 0.849.4 ±\pm 0.752.9 ±\pm 1.055.3 ±\pm 1.0
Fully independent41.2 ±\pm 1.046.0 ±\pm 1.249.4 ±\pm 1.152.9 ±\pm 0.654.7 ±\pm 0.9

Q3 (disentangling effects of privacy accounting, input discretization, and implementation differences):

Input discretization. This accounts for most of the accuracy gap: According to (1), deterministic rounding with h=c/dh=c/\sqrt{d} increases sensitivity, and hence noise, by a factor of 1+c/21+c/2. This is 1.25, 1.5 and 2 for our three choices of hh. A smaller hh closes this gap, and in the jax_privacy implementation it does not change the running time or the number of random bytes (Tables 1-4). We therefore do not claim an accuracy advantage over discrete Gaussian.

Privacy accounting. The discrete Gaussian is analyzed using zCDP with an RDP accountant, whereas our mechanism inherits the PRV accountant of the Gaussian mechanism. Though the PRV accountant is slightly more accurate, in our settings the gap is small.

Implementation. The running time differences come from noise generation. Tables 1-4 isolate this step: the discrete Gaussian sampler uses 40 random bytes/coord against 2 for ours, and more than half of its time is spent generating secure random bytes.

Summary: The accuracy differences in Figure 4 are mainly due to discretization and only to a small extent due to accounting. The advantages that hold for any hh are 20 times fewer random bytes, faster sampling, and no separate privacy analysis.

Thank you for the detailed response and additional experiments. I appreciate the authors' efforts, particularly the comparison between pairwise and independent dithering, which substantially addresses my concern about high-dimensional utility (W2).

However, my main concern regarding finite-precision privacy guarantees (W1) remains unresolved. While the proposed adaptive margin is a promising improvement, the empirical comparison of torch.special.ndtr against high-precision references does not establish a rigorous worst-case error bound.

I would appreciate clarification on two points:

  1. Certified numerical accuracy: Can the authors establish a rigorous error bound for the CDF evaluation and demonstrate that the adaptive margin always exceeds the numerical error, including in the fallback procedure?
  2. End-to-end privacy guarantee: Can the authors formally establish that the implemented sampler preserves the ideal output distribution, or otherwise quantify the resulting privacy degradation?

Overall, I find the proposed mechanism interesting and the additional results encouraging. However, given that finite-precision security is a central motivation of the paper, I consider W1 important to resolve.

I will maintain my current rating (Weak Reject) for now, but would be open to reconsidering it if this concern is adequately addressed.

Thank you for your quick reply!

We agree that we can be more rigorous about the guarantees that our sampling provides. Below, we formulate an exact guarantee under explicit assumptions on the accuracy of the numerical routines, with large safety margins, and explain how these assumptions can be removed using certified arithmetic.

Assumptions.

  • (A1) Float64 ++,−-, ×\times, ÷\div are correctly rounded (IEEE 754).
  • (A2) For every float64 input, the library's error function erf is within τ=10−12\tau = 10^{-12} of the true value.
  • (A3) In the fallback, mpmath at working precision pp evaluates the cell boundaries with absolute error below 2−(p−64)2^{-(p - 64)}; that is, it may lose up to 64 bits.

Q1. Certified numerical accuracy.

A candidate kik_i is accepted only if the random interval lies inside the computed cell boundaries with a margin of at least εi=10−12+2−50ξ(∣ki∣+2)/σ\varepsilon_i = 10^{-12} + 2^{-50}\xi (|k_i| + 2)/\sigma. Two sources of error must be accounted for:

Argument. Under A1, rounding in the argument of Φ\Phi changes the CDF value by at most 2−52ξ(∣ki∣+2)/σ+2−532^{-52}\xi (|k_i| + 2)/\sigma + 2^{-53}.

CDF routine. In PyTorch 2.10, torch.special.ndtr computes Φ(x)=(1+erf(x/2))/2\Phi(x) = (1 + \text{erf}(x / \sqrt{2}))/2; see [1]. Under A1 and A2 the result is within τ/2+2−52\tau / 2 + 2^{-52} of Φ(x)\Phi(x) for every float64 xx. The sum is below εi\varepsilon_i.

We will update the anonymous repository to this form of the margin.

Fallback. Coordinates not resolved in float64 are handled in arbitrary precision on the exact rational values of the inputs, with 64 guard bits beyond the resolution of the random interval; this is A3. One could replace mpmath by ball arithmetic (Arb), which returns rigorous enclosures and makes A3 unnecessary.

Q2. End-to-end guarantee.

Proposition. Under A1–A3, for all finite float64 inputs and every sequence of random bits, every accepted kik_i satisfies [Li,Ri)⊆[Fi(ki−1),Fi(ki)][L_i, R_i) \subseteq [F_i(k_i - 1), F_i(k_i)], so it equals the ideal inverse transform sample. The sampler terminates with probability 1. Hence the output has exactly the distribution in eq. (6), and the privacy guarantee is that of the Gaussian mechanism, with no additional ε\varepsilon or δ\delta. The guarantee holds for each individual sample, so numerical errors do not accumulate with the dimension or the number of iterations.

How weak is A2? Depending on the code path, build and hardware, erf is provided by Intel Vector Mathematics (VM) library in high accuracy mode, SLEEF, the C library, or CUDA. Intel states a design requirement of less than 1 ULP (Unit in the last place) [2,3]. NVIDIA reports a maximum observed error of 2 ULP, but notes that this comes from numerical testing and is not formally guaranteed [4]. Both are consistent with our empirical comparison. A2 leaves more than three orders of magnitude beyond these figures. The tolerance τ\tau is a free parameter: a larger τ\tau weakens the assumption further, at the cost of sending a fraction of coordinates proportional to τ\tau to the fallback.

Removing A2. The dependence on math libraries can be avoided altogether. Φ\Phi can be evaluated by a degree-4 Taylor expansion around tabulated nodes tj=j⋅2−8t_j = j \cdot 2^{-8}, using only float64 additions and multiplications. Its error is at most 2−492^{-49} for every input, and this follows from A1 alone: the Taylor remainder is below 2.9×10−162.9 \times 10^{-16}, the table rounding below 2.3×10−162.3 \times 10^{-16}, and the rounding in Horner's rule below 9×10−169 \times 10^{-16}. We have a reference implementation of this variant and will include it in the released code.

[1] https://github.com/pytorch/pytorch/blob/v2.10.0/aten/src/ATen/native/UnaryOps.cpp#L715C1-L719C1

[2] https://www.intel.com/content/www/us/en/docs/onemkl/developer-reference-vector-math-performance-accuracy-data/2021-1/overview.html

[3] https://www.intel.com/content/www/us/en/docs/onemkl/developer-reference-vector-math-performance-accuracy-data/2021-1/erf.html

[4] https://docs.nvidia.com/cuda/cuda-programming-guide/05-appendices/mathematical-functions.html

Reviewer_vimrOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes a dithered Gaussian mechanism for differential privacy. The goal is 1. to reduce the amount of private randomness required for noise generation, 2. while addressing privacy leakage arising from heuristic floating-point approximations of Gaussian noise. The main idea is to discretize the output of the Gaussian mechanism, rather than discretizing the input before adding discrete Gaussian noise. Specifically, the mechanism can be viewed as first adding Gaussian noise to the sensitive vector, and then rounding the result to a uniformly spaced grid with a random shift (dithering). Instead of explicitly generating the Gaussian noise, the authors directly sample the discretized output using probabilities expressed in terms of the Gaussian CDF. Since this discretization is a post-processing of the Gaussian mechanism for every fixed shift, the resulting mechanism directly inherits its differential privacy guarantees.

Empirically, the paper compares the proposed mechanism with existing discrete Gaussian implementations in terms of randomness consumption, sampling time, and reconstruction error. The proposed method uses substantially fewer random bits and achieves faster sampling while maintaining error close to the standard Gaussian mechanism. The authors further evaluate the mechanism in DP-SGD, showing that it achieves accuracy close to the Gaussian baseline with small runtime overhead.

Critical strengths
  • The problem studied is natural and meaningful, both theoretically and practically towards the use of differential privacy in large-scale machine learning.

  • The proposed solution achieves promising theoretical and empirical results, with formal privacy and randomness complexity guarantees, substantial improvements in randomness consumption and runtime over the evaluated baselines, and comparable accuracy on the considered tasks.

Critical weaknesses
  • I think the paper could better clarify its technical novelty relative to previous work. In particular, while the authors cite Ghentiyala (2026) and mention that their randomness complexity analysis "extends similar observations", they do not explicitly discuss that Ghentiyala also uses randomly shifted quantization grids to reduce private randomness.

    More broadly, the paper could benefit from a section discussing the substantial existing literature on dithered discretization / quantization. The use of uniformly shifted quantization grids to obtain unbiased errors independent of the quantized values is a classical technique (e.g., Schuchman (1964); Zamir and Feder (1992) ). Lemma 1 appears to be an application of this principle. I would encourage the authors to acknowledge this connection. Recent work on dithered quantization, including Feng et al. (2026) and Lin et al. (2026), also seems relevant, e.g. the latter employs exactly the same pairwise-independent shifts γi=(ai+b)mod  1\gamma_i=(ai+b) \mod 1 as Algorithm 1 of this paper.

  • The paper does not provide an experimental comparison with the natural ablation of using deterministic rounding without dithering. As mentioned in the paper, deterministic rounding also preserves the DP guarantees of the Gaussian mechanism through post-processing. Moreover, the O(d)O(d) private randomness complexity bound for ξ=Θ(σ)\xi=\Theta(\sigma) still holds without random shifts. Therefor the main potential disadvantages of deterministic rounding seem to be its bias and utility, both of which could be evaluated experimentally. I think such a comparison would be valuable for understanding the practical benefits of dithering, especially since it is a central component of the proposed mechanism.

Schuchman (1964). Dither Signals and Their Effect on Quantization Noise. IEEE Transactions on Communications.

Zamir and Feder (1992). On Universal Quantization by Randomized Uniform/Lattice Quantizers. IEEE Transactions on Information Theory.

Ghentiyala (2026). Efficient Derandomization of Differentially Private Counting Queries. SIAM Symposium on Simplicity in Algorithms.

Feng et al. (2026). Provable Quantization with Randomized Hadamard Transform. arXiv:2605.13810

Lin et al. (2026). Pairwise-Independent Dithering for Single-Stage Hadamard Quantization. arXiv:2608.02564

Questions for authors

I don't have any specific questions beyond the points raised in the Weaknesses section.

2 comments

Thanks for your constructive feedback and questions! We comment on each point below.

W1 (technical novelty). Our key mathematical observation is that the entropy of the Gaussian mechanism, rounded to a grid of granularity comparable to the noise magnitude, is O(1)O(1) bits per coordinate. This implies that it is possible to sample such values with expected O(1)O(1) bits of randomness. Past work did not make use of this, losing logarithmic factors in the randomness/noise trade-off. (To be fair, past work focused on more theoretical settings with significantly larger error, where o(1)o(1) bits of randomness per coordinate is possible.) Our key technical contribution is that sampling with such low randomness complexity is possible not only in principle, but can be implemented to be efficient and competitive with alternative sampling methods. This paves the way for using cryptographically secure pseudorandom noise generators, addressing a key weakness of existing techniques that rely on weak pseudorandomness.

W1 (comparison with Ghentiyala). The construction of Ghentiyala can be thought of as a crude generation of the output distribution: An output coordinate is either equal to its most likely output value (under the noise distribution), or it is not. For a sufficiently crude discretization, most coordinates will assume their most likely values. One can first sample the set of coordinates that assume their most likely values, after which we only need to sample the undetermined coordinates, which is done in the naïve way using a logarithmic number of random bits. In contrast, we sample according to conditional entropy which is O(1)O(1). We will add a discussion of this to the next revision of the paper.

W1 (dithering). Ghentiyala already used dithered quantization in his construction. However, we would like to make clear that the choice of dithered quantization is not critical to our privacy bound, nor to the entropy bound (11): Since the discretization grid can be public, rounding to any fixed grid would still be private and have similar error magnitude and randomness complexity. One could use standard randomized rounding (non-subtractive dither) with any fixed grid to ensure unbiased rounding error. What dithered quantization gives us is an unbiased estimator whose error distribution and randomness complexity is identical for all coordinates. Also, as shown by Ghentiyala, it allows us to get o(1)o(1) randomness complexity in the high-error regime. The affine shifts in Algorithm 1 coincide with those used in Lin et al. (arXiv, August 2026), which is concurrent, independent work on quantization for a different problem (no privacy). The construction is itself a continuous analogue of Carter and Wegman’s pairwise-independent hash functions from the 1970s (Appendix G). We will cite both Lin et al. and Feng et al. in the revision.

W2 (deterministic rounding). We agree it is of some interest to compare to deterministic rounding. Figure 5(a) in Appendix E already compares the randomness complexity for the two methods, showing an advantage of dithering only when ξ/σ\xi/\sigma is large. We repeated the CIFAR-10 experiments using deterministic rounding instead of dithering and report the results in the table below. The accuracies are similar across the different settings, with differences within the reported error bars in most cases and no systematic advantage for either approach.

MechanismDither γi\gamma_iε=0.5\varepsilon = 0.5ε=1\varepsilon = 1ε=2\varepsilon = 2ε=4\varepsilon = 4ε=8\varepsilon = 8
Dithered (ξ=0.5σ\xi = 0.5\sigma)Pairwise independent42.3 ±\pm 0.447.2 ±\pm 0.551.5 ±\pm 1.453.9 ±\pm 0.556.2 ±\pm 1.1
Deterministic rounding43.3 ±\pm 0.747.3 ±\pm 0.751.1 ±\pm 0.554.4 ±\pm 0.856.3 ±\pm 0.1
Dithered (ξ=σ\xi = \sigma)Pairwise independent42.6 ±\pm 0.346.4 ±\pm 0.750.5 ±\pm 0.554.2 ±\pm 0.356.7 ±\pm 1.2
Deterministic rounding42.2 ±\pm 0.446.8 ±\pm 0.550.5 ±\pm 0.652.8 ±\pm 0.656.4 ±\pm 0.4
Dithered (ξ=2σ\xi = 2\sigma)Pairwise independent42.5 ±\pm 0.445.5 ±\pm 0.849.4 ±\pm 0.752.9 ±\pm 1.055.3 ±\pm 1.0
Deterministic rounding42.3 ±\pm 0.845.8 ±\pm 0.649.7 ±\pm 0.752.9 ±\pm 1.054.8 ±\pm 0.6

In short, we believe that in practical settings, where the input is already somewhat random, as in the case of gradients during training, the difference between deterministic and dithered rounding will be negligible. We also compared the RMSE of the two mechanisms with random inputs and observed virtually identical values. The main advantages of dithering are therefore its guarantees for worst-case inputs, particularly improved randomness complexity.

Thank you for your responses! I think including the more detailed discussions of related works and the deterministic rounding experiment result would benefit the paper. I therefore retain my positive score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.