- Rating
- 3
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper propose a quantization scheme that has LDP guarantee and good MSE performance.
Critical strengths
The paper is well organized and the presentation is good. I can clearly understand what is the main algorithm and what problem the authors try to address. The contribution is sufficient and the technical contents look correct.
Critical weaknesses
My major concern is the notation and technical contents are heavy, and it is not easy to follow and verify important things. For example, at the very high level, intuitively, why the authors' approach improves, for example, SQKR? Does the author provide rigorous guarantee on the compression performance? I would suggest the authors to improve the organization and presentation in the final version.
There are some other questions, 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.
Things that i'd suggested to be clarified:
- Is this truncated-Laplace entirely new, or it has appeared at somewhere else?
- I'm a bit confused, what does the authors mean by "metric-aware"? Are the baseline methods mentioned not "metric-aware"?
- Why need to define \zeta^2 inside Theorem 5.2? If you only use it in Section 6 and Theorem 6.1, it can be defined there.
- Why choose in experiments? What happends if is very large or very small?
- I see Theorem 3.1 for privacy guarantee and Theorem 3.2 for MSE, how about compression performance?
- How about the time complexity of the proposed scheme?
- I suggest increase the legends' font size of figure 1.
- For privacy+compression, one method that improves the Coordinate Subsampled Gaussian Mechanism (CSGM) (Chen et al., 2023) is "Universal exact compression of differentially private mechanisms." (NeurIPS 24) by Liu et al. It also provides local DP guarantee and gives clear near-optimal compression performance. Since the authors mentioned CSGM, it would be reasonable to compare to this scheme as well, perhaps from a high-level scheme comparison.
5 comments
Clarifications on Truncated Laplace, "Metric-Aware", , -Regimes, Runtime, Legends & PPR (Bullets 1,2,3,4,6,7)
2. Clarifications on Truncated Laplace, "Metric-Aware", , -Regimes, Runtime, Legends & PPR
- Is truncated-Laplace new? (Bullet 1): 1D discrete and bounded/truncated Laplace mechanisms on bounded scalar intervals are classical in differential privacy (e.g., Ghosh et al., 2012; Geng & Viswanath, 2016; Holohan et al., 2020—now cited in Section 5). What is new in SSTQ is integrating 1D truncated-Laplace perturbation (tightened to exact -LDP scale in Appendix E.1) + nearest-codeword rounding over arbitrary non-uniform codebooks inside a subsampled Kashin vector quantizer with identity decoding, proving that: (i) omitting debiasing removes the variance blow-up while inducing a vector bias that is strictly independent of both ambient dimension and bit-width (Theorem 5.2), and (ii) optimizing its exact loss recovers the classical Panter–Dite law as (Section 5.1).
- Meaning of "metric-aware" vs. baselines (Bullet 2): Clarified at the start of Section 5: here "metric-aware" refers specifically to how the LDP step perturbs the discrete codebook labels. Flat-RR (used in SSTQ-Flat, vqSGD's cross-polytope RR, and SQKR's -RR) is metric-oblivious (categorical) on : conditional on flipping , every label receives equal probability regardless of scalar distance (flipping is as likely as flipping to an adjacent bin). Our Section 5 mechanism assigns transition probabilities decaying exponentially with , keeping perturbations within for any . (PrivUnit is geometry-aware on , which is why its MSE is , but emits continuous -bit vectors; SSTQ brings metric-awareness to discrete -bit scalar codebooks.)
- Defining in Section 6 rather than Theorem 5.2 (Bullet 3): Fixed! Theorem 5.2 now states directly without introducing , which is defined only in Section 6 / Theorem 6.1.
- Why , and behavior at very small or very large (Bullet 4): is a standard moderate-privacy benchmark in prior LDP gradient compression work (Chen et al., 2020; Gandikota et al., 2021). We added an explicit -sweep across (Figure 5a and fixed-budget Table 3):
- Very small (): Privacy noise dominates spatial distortion; matching (Section 5), -bit quantization ( SSTQ / SQKR) already saturates the minimax rate among unbiased schemes, while Metric-Aware SSTQ achieves the lowest single-message MSE ( vs. at ) via variance reduction at the cost of a larger bias floor.
- Large (): Privacy noise and Metric-Aware bias () rapidly vanish; -bit schemes stall at an irreducible quantization floor ( at ), whereas multi-bit SSTQ () drops MSE by () at fixed bits (whereas SQKR's private-coin cost grows linearly with ).
- Time complexity (Bullet 6): Summarized in Table 1, Proposition 3.3(2) (proved in Appendix C.3), and Table 2: client encoding takes time via FWHT (/client at , independent of ; offline codebook solve takes once). By linearity of , the server sums 1-sparse client updates in additions followed by one inverse FWHT of cost —an amortized time per client.
- Figure 1 legend font size (Bullet 7): Enlarged across all panels of Figure 1 (and Figures 3–6).
Comparison with Liu et al. (NeurIPS 2024) (Bullet 8)
- Comparison with Liu et al. (NeurIPS 2024), "Universal exact compression of differentially private mechanisms" (Bullet 8): Thank you for this pointer! We added Poisson Private Representation (PPR) (Liu et al., 2024) to Table 1 and Appendix A.2. PPR uses the Poisson functional representation over shared randomness to exactly simulate local randomizers within a logarithmic gap of bits, strictly improving upon CSGM (Chen et al., 2023). SSTQ complements PPR along three practical axes: (1) Private-coin pure -LDP vs. Shared Randomness: PPR relies on shared Poisson randomness between client and server (or -bit PRG seeds under computational DP), whereas SSTQ is strictly private-coin under information-theoretic pure -LDP at total bits; (2) Fixed vs. Variable Length: SSTQ emits fixed -bit packets rather than variable-length codes; and (3) -Independent Runtime: Exact Poisson/rejection channel simulation incurs expected runtime scaling as as grows, whereas SSTQ runs in time uniformly for all .
High-Level Intuition vs. SQKR & Rigorous Compression Guarantee (Critical Weakness & Bullet 5)
We sincerely thank you for the positive assessment and clear suggestions to improve intuition, terminology, notation, and related-work comparisons. Every suggestion has been incorporated in blue in the revised manuscript.
1. High-Level Intuition vs. SQKR & Rigorous Compression Guarantee (Critical Weakness & Bullet 5)