acceptodds
Under review as a conference paper at ICLR 2027

SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant

Abstract

Achieving local differential privacy (LDP) in distributed optimization at low communication cost remains challenging: existing vector quantization methods such as vqSGD rely on high-dimensional geometric constructions and incur unfavorable dimension-dependent variance. We propose Subsampled Stochastic TurboQuant (SSTQ), combining a bounded Kashin representation, data-independent coordinate subsampling, and privacy-aware one-dimensional quantization. SSTQ has two variants: (1) a Flat Randomized Response variant that is unbiased and, for fixed codebook bit-width , frame redundancy, and dimension-independent Kashin level, achieves reconstruction MSE linear in the ambient dimension using only bits per message, where is the Kashin frame size; and (2) a metric-aware truncated-Laplace variant that removes the exponential bit-width dependence at the cost of a non-vanishing bias. We also derive a convex uniform-surrogate codebook objective whose worst-case codebook-dependent bound improves from to . Experiments on synthetic regression, Fashion-MNIST, and CIFAR-10 compare the per-message privacy–utility and uplink-communication trade-offs of SSTQ against established baselines, demonstrating favorable utility and communication efficiency.

Primary area:
learning theory
Keywords:
Local Differential Privacy, Communication-Efficient Learning, Vector Quantization, Kashin Representations, Federated Learning, Privacy-Aware Codebook Optimization, Randomized Response

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_8BLfOpenReview ↗
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 ϵ=3\epsilon=3 in experiments? What happends if ϵ\epsilon 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
AuthorsOpenReview ↗

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)

  • Intuitive improvement over SQKR (Section 3, "High-Level Intuition"): Both SQKR and SSTQ spread a dd-dimensional vector across N=Θ(d)N = \Theta(d) Kashin coordinates bounded in [−B,B][-B,B] (B=O(1/d)B = \mathcal{O}(1/\sqrt{d})), avoiding vqSGD's Θ(d3)\Theta(d^3) cross-polytope bottleneck. However, SQKR binarizes every coordinate to ±B\\{\pm B\\} (11 bit) and samples kk coordinates: (i) in the private-coin model (no shared randomness), sending kk coordinates forces the client to pay the ⌈log⁡2N⌉\lceil\log_2 N\rceil-bit index address kk separate times (k(⌈log⁡2N⌉+1)k(\lceil\log_2 N\rceil+1) bits, e.g., 68–7668\text{–}76 bits at k=4k=4), while 2k2^k-RR still incurs O(4k)\mathcal{O}(4^k) variance capping k≤⌈ϵlog⁡2e⌉k \le \lceil\epsilon\log_2 e\rceil; and (ii) at k=1k=1, forcing small or near-zero coordinates onto ±B\pm B locks variance at its boundary ceiling B2B^2. SSTQ instead amortizes a single coordinate index (⌈log⁡2N⌉\lceil\log_2 N\rceil bits) with a bb-bit privacy-aware scalar codebook (⌈log⁡2N⌉+b=18–22\lceil\log_2 N\rceil + b = 18\text{–}22 bits): interior codewords ∣ci∣<B\lvert c_i \rvert < B shrink quantization and privatization energy whenever ∣yJ∣<B\lvert y_J \rvert < B (reducing MSE by 3.5×–19×3.5\times\text{–}19\times on interior vectors; Figure 5a), while Metric-Aware SSTQ eliminates exponential 2b2^b variance growth altogether.
  • Rigorous compression guarantee (Proposition 3.3(1)): Unlike variable-length entropy/channel-simulation schemes whose rate holds only in expectation, every SSTQ message (J,Z)∈[N]×[2b](J, Z) \in [N]\times[2^b] has deterministic worst-case length ⌈log⁡2N⌉+b=⌈log⁡2(ρd)⌉+b\lceil\log_2 N\rceil + b = \lceil\log_2(\rho d)\rceil + b bits in the private-coin model (40,720×40{,}720\times compression vs. float32 on Fashion-MNIST at b=4b=4; 143,514×143{,}514\times on CIFAR-10) while satisfying the rigorous MSE bounds of Theorems 3.2, 4.3, and 5.2.
AuthorsOpenReview ↗

Clarifications on Truncated Laplace, "Metric-Aware", , -Regimes, Runtime, Legends & PPR (Bullets 1,2,3,4,6,7)

2. Clarifications on Truncated Laplace, "Metric-Aware", ζ2\zeta^2, ϵ\epsilon-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 ϵ\epsilon-LDP scale DB/ϵ=2B/ϵD_B/\epsilon = 2B/\epsilon 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 O(2b)\mathcal{O}(2^b) variance blow-up while inducing a vector bias ∣E[x^]−x∣22≤16K2R2ρϵ2\\|\mathbb{E}[\hat{x}]-x\\|_2^2 \le \frac{16K^2R^2}{\rho\epsilon^2} that is strictly independent of both ambient dimension dd and bit-width bb (Theorem 5.2), and (ii) optimizing its exact loss L∗_MA-SSTQ\mathcal{L}^*\_{\mathrm{MA\text{-}SSTQ}} recovers the classical Panter–Dite fY1/3f_Y^{1/3} law as ϵ→∞\epsilon \to \infty (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 M=2bM = 2^b discrete codebook labels. Flat-RR (used in SSTQ-Flat, vqSGD's cross-polytope RR, and SQKR's 2k2^k-RR) is metric-oblivious (categorical) on [M][M]: conditional on flipping V=kV=k, every label i≠ki \ne k receives equal probability q=(eϵ+M−1)−1q = (e^\epsilon+M-1)^{-1} regardless of scalar distance ∣ci−ck∣\lvert c_i - c_k \rvert (flipping −B→+B-B \to +B is as likely as flipping to an adjacent bin). Our Section 5 mechanism assigns transition probabilities decaying exponentially with ∣t−ck∣\lvert t - c_k \rvert, keeping perturbations within O(B/ϵ)\mathcal{O}(B/\epsilon) for any M=2bM=2^b. (PrivUnit is geometry-aware on Sd−1\mathbb{S}^{d-1}, which is why its MSE is O(d/ϵ2)\mathcal{O}(d/\epsilon^2), but emits continuous 32d32d-bit vectors; SSTQ brings metric-awareness to discrete ⌈log⁡2N⌉+b\lceil\log_2 N\rceil+b-bit scalar codebooks.)
  • Defining ζ2\zeta^2 in Section 6 rather than Theorem 5.2 (Bullet 3): Fixed! Theorem 5.2 now states ∣E[x^]−x∣22≤16K2R2ρϵ2\\|\mathbb{E}[\hat{x}]-x\\|_2^2 \le \frac{16K^2R^2}{\rho\epsilon^2} directly without introducing ζ2\zeta^2, which is defined only in Section 6 / Theorem 6.1.
  • Why ϵ=3\epsilon = 3, and behavior at very small or very large ϵ\epsilon (Bullet 4): ϵ=3\epsilon = 3 is a standard moderate-privacy benchmark in prior LDP gradient compression work (Chen et al., 2020; Gandikota et al., 2021). We added an explicit ϵ\epsilon-sweep across ϵ∈0.5,1,2,3,5,8\epsilon \in \\{0.5, 1, 2, 3, 5, 8\\} (Figure 5a and fixed-budget Table 3):
    • Very small ϵ\epsilon (ϵ≤1\epsilon \le 1): Privacy noise Θ(d/ϵ2)\Theta(d/\epsilon^2) dominates spatial distortion; matching bsat=1b_{\mathrm{sat}} = 1 (Section 5), 11-bit quantization (b=1b=1 SSTQ / k=1k=1 SQKR) already saturates the minimax rate among unbiased schemes, while Metric-Aware SSTQ achieves the lowest single-message MSE (11.711.7 vs. 182.9182.9 at ϵ=1,d=1,000\epsilon=1, d=1{,}000) via variance reduction at the cost of a larger O(1/ϵ2)\mathcal{O}(1/\epsilon^2) bias floor.
    • Large ϵ\epsilon (ϵ≥5\epsilon \ge 5): Privacy noise and Metric-Aware bias (∝1/ϵ2\propto 1/\epsilon^2) rapidly vanish; 11-bit schemes stall at an irreducible quantization floor (39.139.1 at ϵ=8\epsilon=8), whereas multi-bit SSTQ (b=4b=4) drops MSE by 19×19\times (2.042.04) at fixed ⌈log⁡2N⌉+4\lceil\log_2 N\rceil+4 bits (whereas SQKR's private-coin cost k(⌈log⁡2N⌉+1)k(\lceil\log_2 N\rceil+1) grows linearly with ϵ\epsilon).
  • Time complexity (Bullet 6): Summarized in Table 1, Proposition 3.3(2) (proved in Appendix C.3), and Table 2: client encoding takes O(rNlog⁡N+b)=O(dlog⁡d)\mathcal{O}(r N \log N + b) = \mathcal{O}(d\log d) time via FWHT (≈0.8–1.5 ms\approx 0.8\text{–}1.5\,\mathrm{ms}/client at d=25,450d=25{,}450, independent of ϵ\epsilon; offline codebook solve takes 14 ms14\,\mathrm{ms} once). By linearity of dNU⊤\frac{d}{N}U^\top, the server sums WW 1-sparse client updates in O(W)\mathcal{O}(W) additions followed by one inverse FWHT of cost O(Nlog⁡N)\mathcal{O}(N\log N)—an amortized O(1+dlog⁡dW)\mathcal{O}(1 + \frac{d\log d}{W}) time per client.
  • Figure 1 legend font size (Bullet 7): Enlarged across all panels of Figure 1 (and Figures 3–6).
AuthorsOpenReview ↗

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 I(X;Z)I(X;Z) bits, strictly improving upon CSGM (Chen et al., 2023). SSTQ complements PPR along three practical axes: (1) Private-coin pure ϵ\epsilon-LDP vs. Shared Randomness: PPR relies on shared Poisson randomness between client and server (or ≥128\ge 128-bit PRG seeds under computational DP), whereas SSTQ is strictly private-coin under information-theoretic pure ϵ\epsilon-LDP at 18–2218\text{–}22 total bits; (2) Fixed vs. Variable Length: SSTQ emits fixed ⌈log⁡2N⌉+b\lceil\log_2 N\rceil+b-bit packets rather than variable-length codes; and (3) ϵ\epsilon-Independent Runtime: Exact Poisson/rejection channel simulation incurs expected runtime scaling as Ω(eϵ)\Omega(e^\epsilon) as ϵ\epsilon grows, whereas SSTQ runs in O(dlog⁡d)\mathcal{O}(d\log d) time uniformly for all ϵ>0\epsilon > 0.
Reviewer_PB1XOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes SSTQ, a differentially private vector quantization method that avoids the d^3 dependence of the variance in prior work such as vqSGD. SSTQ has two variants: (1) Flat Randomized Response, which is unbiased but whose variance depends exponentially on the bit-width; and (2) a metric-aware truncated-Laplace variant, which trades some bias for slower variance growth. The authors also propose a method for optimizing the codebook, and evaluate the utility and communication efficiency of the algorithms on real datasets.

Critical strengths
  • The trade-off among utility, privacy, and communication efficiency is an important problem.
  • The paper provides algorithms for different bit-width regimes, supported by a detailed theoretical analysis.
Critical weaknesses
  • The experiments are limited and insufficient to demonstrate the advantages of the proposed method.
  • The effect of the codebook optimization is unclear. The experimental results do not show a consistent improvement.
Questions for authors
  • The advantage of SSTQ over methods such as PrivUnit seems to lie mainly in communication efficiency. However, methods that can compress the number of bits for mechanisms like PrivUnit, e.g., [1], are not compared. Could the authors include such baselines?
  • Even Clean SGD reaches only about 65% test accuracy on Fashion-MNIST and 29% on CIFAR-10. Does this indicate underfitting, and could it affect the conclusions? In addition, the variance across runs is not reported.
  • Does the optimized codebook place many codewords near 0? If so, this would undermine the benefit of using multiple bits.
  • What are the execution times of SSTQ and the baselines?

[1] Feldman, Vitaly, and Kunal Talwar. "Lossless compression of efficient private local randomizers." International Conference on Machine Learning. PMLR, 2021.

3 comments
AuthorsOpenReview ↗

Question 1, Weakness 1 & Question 2

We thank you for praising the clarity of presentation and theoretical depth, and for raising four practical questions that substantially strengthened our experimental evaluation. Using the 10-page rebuttal page limit, we have substantially strengthened both the theoretical exposition and empirical evaluation (all changes are highlighted in blue in the revised manuscript).

1. Comparison with Lossless Compression of PrivUnit — Feldman & Talwar (ICML 2021) (Question 1)

We implemented exact rejection-sampled PRG compression of PrivUnit (FT-PrivUnit, Feldman & Talwar, 2021) and added it to Table 1, Section 7 (Figure 1), Appendix A.2, and Tables 2–3:

  1. Privacy & Bandwidth (128 bits vs. 18–22 bits in private-coin): Without shared public randomness, FT-PrivUnit rejection-samples over cryptographic PRG seeds and transmits the accepted seed s∈0,1λsecs \in \\{0,1\\}^{\lambda_{\mathrm{sec}}}. First, replacing true randomness with a PRG relaxes information-theoretic pure ϵ\epsilon-LDP to computational DP. Second, cryptographic security requires seed length λsec≥128\lambda_{\mathrm{sec}} \ge 128 bits per message—still 5.8×–7.1×5.8\times\text{–}7.1\times more bits than SSTQ (18–2218\text{–}22 bits)! Reaching O(ϵ)\mathcal{O}(\epsilon) bits requires shared public randomness (public-coin), just like public-coin SQKR.
  2. Exponential Θ(deϵ)\Theta(d e^\epsilon) Client Runtime (Figure 5b, Table 2): Empirically at d=25,450d = 25{,}450, FT-PrivUnit's average rejection trials per client grow from 1.121.12 (ϵ=0.5\epsilon=0.5) and 6.06.0 (ϵ=3\epsilon=3, 3.54 ms3.54\,\mathrm{ms}) to 28.428.4 (ϵ=5\epsilon=5, 17.3 ms17.3\,\mathrm{ms}) and 259.0259.0 (ϵ=8\epsilon=8, 134.3 ms134.3\,\mathrm{ms}—170×170\times slower than SSTQ's 0.79 ms0.79\,\mathrm{ms}), whereas SSTQ's encoding time stays flat at ≈0.8–1.5 ms\approx 0.8\text{–}1.5\,\mathrm{ms} across all ϵ>0\epsilon > 0.
  3. Accuracy–Communication Trade-off: FT-PrivUnit matches PrivUnit's accuracy (64.80 ± 0.57% on Fashion-MNIST; 23.86 ± 1.11% on CIFAR-10; 70.22 ± 0.77% converged Fashion-MNIST) at 128128 bits (computational DP), whereas SSTQ achieves within 2–3.52\text{–}3.5\\% at 18–2218\text{–}22 bits under information-theoretic pure ϵ\epsilon-LDP with ϵ\epsilon-independent runtime.

2. Higher-Accuracy (Non-Underfitting) Regime & Multi-Seed Variance (Weakness 1 & Question 2)

  • Multi-seed variance: All experiments now report mean ±\pm std across independent seeds (55 seeds on Fashion-MNIST and synthetic regression; 33 seeds on CIFAR-10 and converged benchmarks; Figures 1, 3, 4, 6; Tables 2–3), showing tight standard deviations (~0.3%–1.5%) and consistent rankings.
  • Why Clean SGD was 65.3% / 29.4% & new converged benchmarks (Table 3, Figure 6): In the original stress test, all methods used aggressive client clipping C=0.1C = 0.1 for T=100T=100 single-batch steps on raw [0,1][0,1] pixels, bounding total parameter travel. Re-evaluating the exact same architectures with data-oblivious [−1,1][-1,1] pixel centering and C=1.0C = 1.0 raises Clean SGD to 78.90 ± 0.59% on Fashion-MNIST (and 84.1% at T=150T=150) and 38.83 ± 0.12% on CIFAR-10 (approaching the capacity of a 32-unit MLP on raw CIFAR-10 pixels). In this converged regime, SSTQ (Flat-Opt, b=2) leads all quantized pure-LDP methods on both datasets: 67.63 ± 0.45% (1818 bits) on Fashion-MNIST—beating k=4k=4 SQKR (66.56 ± 0.43%, 6868 bits) and 11-bit SSTQ / SQKR (64.37 ± 0.67%)—and 24.23 ± 0.66% (2020 bits) on CIFAR-10—beating k=4k=4 SQKR (23.86 ± 0.97%, 7676 bits) and 11-bit SSTQ / SQKR (22.88 ± 0.90%), while SSTQ (Flat-Opt, b=4) beats Flat-Uni on both (65.30 ± 1.51% vs. 63.16 ± 1.39% and 23.59 ± 0.36% vs. 22.90 ± 0.27%) and Metric-Aware b=4 reaches 65.36 ± 0.55% on Fashion-MNIST.
AuthorsOpenReview ↗

Weakness 2 & Question 3, Question 4

3. Codewords Near 00 in the Optimized Codebook (Weakness 2 & Question 3)

Your intuition is spot-on and reflects two distinct regimes in LSSTQ\mathcal{L}_{\mathrm{SSTQ}} (Remark 4.4 & Figure 5c):

  • Well-separated regime when bb is matched to ϵ\epsilon (M≤2m∗+1M \le 2m^*+1): Balancing cubic quantization distortion against the ℓ2\ell_2 privacy penalty supports 2m∗≍2(eϵ−12)1/32m^* \asymp 2\bigl(\frac{e^\epsilon-1}{2}\bigr)^{1/3} effective nonzero levels. At b=4b=4 (M=16M=16) for ϵ=5\epsilon = 5 and ϵ=8\epsilon = 8, all 1616 codewords are well-separated across [−B,B][-B,B] (±0.007, ±0.031, ±0.079, ..., ±1.0B at ϵ=5\epsilon=5), providing denser spacing near 00 than a uniform grid where Kashin coordinates concentrate.
  • Privacy-saturated regime when M=2bM = 2^b exceeds Flat-RR's capacity (M>2m∗+1M > 2m^*+1): Under Flat-RR, uniform noise flips onto every label with probability q=(eϵ+M−1)−1q = (e^\epsilon+M-1)^{-1}, contributing variance ∝∑i=1Mci2\propto \sum_{i=1}^M c_i^2. Spreading excess labels uniformly inflates MSE as Θ(4b)\Theta(4^b), whereas Γ∗\Gamma^* keeps ≈2m∗\approx 2m^* outer levels at Ω(B/m∗)\Omega(B/m^*) and concentrates the excess inner levels tightly around 00 (6/16 within 10−4B10^{-4}B of 00 at ϵ=3\epsilon=3; 10/16 at ϵ=1\epsilon=1). Because ∣ci∣≈0\lvert c_i \rvert \approx 0 adds negligible energy (ci2≈0c_i^2 \approx 0), these near-zero levels act as variance-suppressing "abstention" symbols, shrinking ∑(ci/B)2\sum (c_i/B)^2 from 6.046.04 (uniform) to 2.502.50 (ϵ=3\epsilon=3) and 2.052.05 (ϵ=1\epsilon=1) and yielding the O(4b)→O(2b)\mathcal{O}(4^b) \to \mathcal{O}(2^b) improvement of Theorem 4.3 (11.9×11.9\times lower regression error at b=8,ϵ=3b=8, \epsilon=3: 206.5 vs. 2449.9!).
  • Practical rule: Heavy accumulation at 00 signals that Flat-RR has reached its privacy-limited resolution ceiling—so one can either save bits by setting b≈⌈log⁡2(1+2m∗)⌉b \approx \lceil\log_2(1+2m^*)\rceil (explaining why b=2b=2 Flat-Opt is so strong at ϵ=3\epsilon=3!) or switch to Metric-Aware SSTQ (Section 5), which has no ∑ci2\sum c_i^2 penalty. (We also fixed a script bug in b=4b=4 synthetic regression where Flat-Uni had scaled its grid by private ∣g∣2\\|g\\|_2 instead of public Bmax⁡B_{\max}; once fixed, Flat-Opt beats Flat-Uni across every setting.)

4. Execution Times of SSTQ and Baselines (Question 4)

We report vectorized OpenMP wall-clock runtimes at d=25,450d = 25{,}450 in Table 2 and Figure 5b:

  • Offline codebook optimization (SSTQ Flat-Opt): Solved once per (d,b,ϵ)(d,b,\epsilon) in 14 ms14\,\mathrm{ms} via SLSQP.
  • Client encoding: vqSGD takes 0.37 ms0.37\,\mathrm{ms} (O(d)\mathcal{O}(d)), PrivUnit takes 0.95 ms0.95\,\mathrm{ms} (O(d)\mathcal{O}(d)), SQKR takes 1.04 ms1.04\,\mathrm{ms} (O(dlog⁡d)\mathcal{O}(d\log d)), and SSTQ takes 1.08 ms1.08\,\mathrm{ms} at ϵ=3\epsilon=3 (0.79 ms0.79\,\mathrm{ms} at ϵ=8\epsilon=8) (O(dlog⁡d)\mathcal{O}(d\log d), invariant across ϵ\epsilon), whereas FT-PrivUnit grows from 3.54 ms3.54\,\mathrm{ms} (ϵ=3\epsilon=3) to 134.3 ms134.3\,\mathrm{ms} (ϵ=8\epsilon=8, 259259 draws) due to Θ(deϵ)\Theta(d e^\epsilon) rejection sampling.
  • Server decoding across WW clients: By linearity of dNU⊤\frac{d}{N}U^\top, the server accumulates WW 1-sparse client updates in O(W)\mathcal{O}(W) additions and executes one single FWHT of cost O(Nlog⁡N)\mathcal{O}(N\log N) per round—an amortized O(1+dlog⁡dW)\mathcal{O}(1 + \frac{d\log d}{W}) per client (Proposition 3.3(2)).
AuthorsOpenReview ↗

A gentle reminder as the deadline is approaching

Thank you again for your constructive feedback, which has meaningfully strengthened our work.

As the discussion phase closes soon, we wanted to let you know that we have addressed all the points raised in your review with new experiments and analyses. If any of your concerns remain, please let us know so we can discuss them further.

If our response has resolved your questions, we would be grateful if you would consider updating your score to reflect these improvements. Thank you for your time and guidance!

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

The paper studies communication-efficient vector release under local differential privacy. SSTQ combines Kashin representations, coordinate subsampling, and scalar quantization. It develops an unbiased Flat-RR variant with a convex codebook objective, and a biased truncated-Laplace variant whose privacy-noise bound avoids exponential dependence on the codebook bit-width. The analysis is supported by synthetic regression and small neural-network experiments.

Critical strengths
  1. The privacy-aware codebook objective is simple and strongly convex. The improved bit-width dependence is a useful result for multi-bit flat RR quantization, although it offers no advantage over the single-bit mechanism.
  2. This paper explicitly considers the communication cost of the sampled coordinate indices. It also distinguishes between unbiased and biased variants and incorporates the bias of the latter into the convergence analysis.
Critical weaknesses
  1. The advantage over SQKR is not isolated. Table 2 compares four-coordinate SQKR and one-coordinate SSTQ. According to the paper’s cost formula, SQKR with k=1 requires only 17/19 bits, which is lower than SSTQ’s 20/22 bits. Without this comparison or a b=1 SSTQ baseline, the benefits of the multi-bit design remain unclear.
  2. The theory needs a clearer connection to the implementation. Equation (44) appears to discard the frame row weights in Equation (43), which requires a proof for unequal row norms. Appendix G also assumes K=2 and residual contraction η≈0.4 for a Hadamard construction without a certificate. These gaps make the applicability of the stated utility guarantees uncertain.
Questions for authors
  1. Across several training seeds, how do k=1 SQKR and b=1 SSTQ compare with the proposed variants under matched privacy and communication budgets?

  2. What coordinate distribution is used in Equation (44), and how are the row-norm weights handled? After residual correction, can it be proven that the implemented Kashin coefficient remains within a common interval?

  3. Does the conclusion hold under a fixed total privacy budget? Appendix G.3 implies that for the reported 100-round runs, ε_total=300; the current experiments only establish per-message trade-offs.

  4. Why does the optimized codebook perform worse than the uniform grid in the CIFAR-10 and b=4 regression experiments? Does this persist across seeds, indicating a mismatch between the alternative coefficient distribution and the actual coefficient distribution?

  5. What is the server-side clipping activation frequency for each method, and how would the results change without it? Appendix G describes the resulting bias as negligible but does not quantify it.

4 comments
AuthorsOpenReview ↗

Isolating Multi-Bit SSTQ vs. SQKR and SSTQ (Weakness 1 & Question 1)

We thank you for an exceptionally careful reading of both our proofs and experimental details. Every mathematical and empirical question you raised directly improved the paper; we address each point below. Using the 10-page rebuttal page limit, we have substantially strengthened both the theoretical exposition and empirical evaluation (all changes are highlighted in blue in the revised manuscript).

1. Isolating Multi-Bit SSTQ vs. k=1k=1 SQKR and b=1b=1 SSTQ (Weakness 1 & Question 1)

  • Exact distributional equivalence at 1 bit: Under public Kashin bound Bmax⁡=KC/NB_{\max} = KC/\sqrt{N}, b=1b=1 SSTQ (Flat-RR) (Γ=(−Bmax⁡,+Bmax⁡)\Gamma = (-B_{\max}, +B_{\max})) and k=1k=1 private-coin SQKR induce the exact same joint distribution on [N]×{±1}[N] \times \{\pm 1\} at ⌈log⁡2N⌉+1\lceil\log_2 N\rceil + 1 bits (1717 bits on Fashion-MNIST; 1919 bits on CIFAR-10), while SSTQ avoids quantizing the N−1N-1 unsampled coordinates (O(1)\mathcal{O}(1) vs. O(N)\mathcal{O}(N) post-Kashin operations). We formalize and prove this in Proposition 3.3(1) & Appendix C.3.
  • Why and when multi-bit SSTQ (b≥2b \ge 2) outperforms b=1b=1 SSTQ ≡k=1\equiv k=1 SQKR: For b=1b=1, every codeword satisfies cZ2≡Bmax⁡2c_Z^2 \equiv B_{\max}^2, locking MSE at the boundary ceiling dK2C2ρ(eϵ+1eϵ−1)2−∥x∥22\frac{dK^2C^2}{\rho}\bigl(\frac{e^\epsilon+1}{e^\epsilon-1}\bigr)^2 - \|x\|_2^2 even when yJ≈0y_J \approx 0 or ∥x∥2<C\|x\|_2 < C. Multi-bit SSTQ introduces interior levels ∣ci∣<Bmax⁡|c_i| < B_{\max}:
    1. Exact MSE (d=1,000,ϵ=3d=1{,}000, \epsilon=3, Figure 5a): At saturation (∥x∥2=C\|x\|_2 = C), b=1b=1 SSTQ / k=1k=1 SQKR has MSE=47.64\mathrm{MSE} = 47.64, whereas b=2b=2 SSTQ (Flat-Opt) reduces MSE by 31%31\% (32.9132.91, +1+1 bit) and b=4b=4 Metric-Aware reduces MSE by 3.6×3.6\times (13.2513.25, +3+3 bits). When gradients lie inside the clipping ball (∥x∥2=0.3C\|x\|_2 = 0.3C, typical once optimization progresses), b=1b=1 SSTQ / k=1k=1 SQKR stays stuck at 47.6747.67, whereas b=4b=4 Metric-Aware drops to 9.259.25 (5.2×5.2\times lower), b=2b=2 Flat-Opt drops to 9.689.68 (4.9×4.9\times lower), and b=4b=4 Flat-Opt drops to 13.6813.68 (3.5×3.5\times lower; 19×19\times lower at ϵ=8\epsilon=8: 2.042.04 vs. 39.1139.11). Meanwhile, reducing SQKR's variance via k>1k>1 multiplies the entire ⌈log⁡2N⌉\lceil\log_2 N\rceil-bit address kk times (68/7668/76 bits at k=4k=4).
    2. Multi-seed federated comparisons across regimes:
      • Saturated C=0.1C=0.1 stress test (ϵ=3\epsilon=3, Figure 1): Because C=0.1C=0.1 clips 100%100\% of client gradients to ∥g∥2=C\|g\|_2 = C, on Fashion-MNIST (55 seeds) k=1k=1 SQKR / b=1b=1 SSTQ (62.87 ± 0.99%, 1717 bits), b=2b=2 SSTQ (62.69 ± 0.68%, 1818 bits), and b=4b=4 SSTQ (62.63 ± 0.91%, 2020 bits) all perform comparably while matching k=4k=4 SQKR (62.16 ± 0.27%, 6868 bits); on CIFAR-10 (33 seeds), b=2b=2 SSTQ (20.30 ± 1.78%, 2020 bits) edges both k=1k=1 SQKR / b=1b=1 SSTQ (19.36 ± 1.75%, 1919 bits) and k=4k=4 SQKR (20.08 ± 1.78%, 7676 bits).
      • Non-saturated / converged regimes (C=1.0C=1.0, Table 3 & Figure 3): Once gradients are not perpetually pinned to ∥g∥2=C\|g\|_2=C, multi-bit SSTQ cleanly separates from 11-bit quantization across seeds: on converged Fashion-MNIST, b=2 Flat-Opt reaches 67.63 ± 0.45% (1818 bits) vs. 64.37 ± 0.67% for k=1k=1 SQKR / b=1b=1 SSTQ (+3.26%+3.26\%, >4.5σ>4.5\sigma) and 66.56 ± 0.43% for k=4k=4 SQKR (6868 bits), while on converged CIFAR-10, b=2 Flat-Opt reaches 24.23 ± 0.66% (2020 bits), beating both k=4k=4 SQKR (23.86 ± 0.97%, 7676 bits) and k=1k=1 SQKR / b=1b=1 SSTQ (22.88 ± 0.90%, 1919 bits); on least-squares regression (55 seeds), b=4 Flat-Opt beats k=1k=1 SQKR / b=1b=1 SSTQ across every dimension (48.8 ± 1.8 vs. 63.0 ± 3.9 at d=100d=100; 144.2 ± 5.2 vs. 169.8 ± 10.8 at d=200d=200; 433.7 ± 8.5 vs. 497.6 ± 10.3 at d=500d=500).
AuthorsOpenReview ↗

Row-Norm Weights in Eq. (43)(44) & Hadamard Kashin Envelope (Weakness 2 & Question 2)

2. Row-Norm Weights in Eq. (43)→\to(44) & Hadamard Kashin Envelope (Weakness 2 & Question 2)

  • Exact proof of Eq. (43)→\to(44) for arbitrary unequal row norms and discrete coordinates: Thank you for spotting the unjustified unweighted density fY(y) dyf_Y(y)\,dy in Eq. (44). For any deterministic x∈B2d(R)x \in B_2^d(R) and any scaled Parseval frame UU with (possibly unequal) squared row norms wj=∣uj∣22w_j = \\|u_j\\|_2^2, define the row-norm-weighted empirical measure on [−B,B][-B,B]:

    μx,U:=1N∑j=1N∣uj∣22 δyj.\mu_{x,U} := \frac{1}{N}\sum_{j=1}^N \\|u_j\\|_2^2\,\delta_{y_j}.

    By Lemma C.1 (∑j=1N∣uj∣22=Tr(U⊤U)=N\sum_{j=1}^N \\|u_j\\|_2^2 = \mathrm{Tr}(U^\top U) = N), μx,U\mu_{x,U} is an exact probability distribution (μx,U([−B,B])=1\mu_{x,U}([-B,B]) = 1). Substituting the conditional second-moment identity E[y~j2∣J=j]=1p−q[rΓ(yj)+yj2+1eϵ−1∑i=1Mci2]\mathbb{E}[\tilde{y}_j^2 \mid J=j] = \frac{1}{p-q}\bigl[r_\Gamma(y_j) + y_j^2 + \frac{1}{e^\epsilon-1}\sum_{i=1}^M c_i^2\bigr] into Eq. (43) gives the exact identity:

    d2N∑j=1N∣uj∣22 E[y~j2∣J=j]=d2p−q[∫[−B,B](rΓ(y)+y2) dμx,U(y)+1eϵ−1∑i=1Mci2].\frac{d^2}{N}\sum_{j=1}^N \\|u_j\\|_2^2\,\mathbb{E}[\tilde{y}_j^2 \mid J=j] = \frac{d^2}{p-q}\left[\int_{[-B,B]}\bigl(r_\Gamma(y)+y^2\bigr)\,d\mu_{x,U}(y) + \frac{1}{e^\epsilon-1}\sum_{i=1}^M c_i^2\right].

    Crucially: (i) the regularization term 1eϵ−1∑i=1Mci2\frac{1}{e^\epsilon-1}\sum_{i=1}^M c_i^2 has no jj-dependence, so its row weights sum to 1N∑j=1N∣uj∣22=1\frac{1}{N}\sum_{j=1}^N \\|u_j\\|_2^2 = 1 with no μU\mu_U inflation; and (ii) for every y∈[−B,B]y \in [-B,B] (including repeated codewords where rΓ(y)=0r_\Gamma(y)=0), rΓ(y)+y2≤max⁡(ck2,ck+12)≤B2r_\Gamma(y)+y^2 \le \max(c_k^2, c_{k+1}^2) \le B^2 pointwise, so ∫[−B,B](rΓ(y)+y2) dμx,U(y)≤B2 μx,U([−B,B])=B2\int_{[-B,B]}(r_\Gamma(y)+y^2)\,d\mu_{x,U}(y) \le B^2\,\mu_{x,U}([-B,B]) = B^2. Thus Theorem 4.3 holds verbatim for arbitrary unequal row norms and atomic coordinates (revised Appendix D.3; note also that for our randomized partial Hadamard frame, ∣uj∣22=1\\|u_j\\|_2^2 = 1 identically).

  • Kashin residual correction and common interval [−Bmax⁡,Bmax⁡][-B_{\max}, B_{\max}]:

    • Direct answer to your theoretical question: If unclipped residual correction ycorr=yc(r)+Uery_{\mathrm{corr}} = y_c^{(r)} + U e_r is applied without an (η,δ)(\eta,\delta)-uncertainty certificate, POCS firm non-expansiveness only guarantees ∣er∣2≤∣x∣2≤C\\|e_r\\|_2 \le \\|x\\|_2 \le C, yielding a worst-case bound ∣ycorr∣∞≤KCN+μUC=O(1)\\|y_{\mathrm{corr}}\\|_\infty \le \frac{KC}{\sqrt{N}} + \sqrt{\mu_U}C = \mathcal{O}(1)—so one cannot certify an O(C/N)\mathcal{O}(C/\sqrt{N}) interval without either invoking high-probability randomized Hadamard RIP/UP bounds (K=O(log⁡d)K = \mathcal{O}(\log d), Lyubarskii & Vershynin 2010) or enforcing a local check ∣er∣2≤τtolC/N\\|e_r\\|_2 \le \tau_{\mathrm{tol}}C/\sqrt{N}. Indeed, you were right to question K=2,η≈0.4K=2, \eta \approx 0.4: measuring ∣e30∥2/∣x∣2\\|e_{30}\\\|_2/\\|x\\|_2 directly at d=25,450,N=65,536d=25{,}450, N=65{,}536 shows a nonzero POCS residual of ≈0.25\approx 0.25 under prefix zero-padding (0.120.12 under random-column SRHT at K=2K=2, dropping to 5×10−65\times 10^{-6} at K=3K=3).
    • Why pure ϵ\epsilon-LDP and a common interval hold unconditionally in our implementation: Auditing our code (kashin()) showed that Appendix G's prose misdescribed termination: our implementation runs r=30r=30 POCS steps and returns the hard-clipped vector yc(r)=clip(y(r),−B,B)y_c^{(r)} = \mathrm{clip}(y^{(r)}, -B, B) (B≤KC/N=:Bmax⁡B \le KC/\sqrt{N} =: B_{\max}), never adding an unclipped residual. Thus every coordinate deterministically lies in the common public interval [−Bmax⁡,Bmax⁡][-B_{\max}, B_{\max}] for every x∈B2d(C)x \in B_2^d(C) and any matrix UU, certifying pure ϵ\epsilon-LDP unconditionally, while any nonzero er(x)=x−dNU⊤yc(r)e_r(x) = x - \frac{d}{N}U^\top y_c^{(r)} enters Theorem 6.1 directly via the bounded-bias parameter ζrep=sup⁡∣x∣2≤C∣er(x)∣2\zeta_{\mathrm{rep}} = \sup_{\\|x\\|_2\le C}\\|e_r(x)\\|_2 (shared equally by SQKR and SSTQ). We corrected Appendix G accordingly.
AuthorsOpenReview ↗

Questions 3, 4, 5

3. Fixed Total Privacy Budget ϵtotal\epsilon_{\mathrm{total}} (Question 3)

We added strict pure-LDP fixed-ϵtotal\epsilon_{\mathrm{total}} experiments in Section 7 & Appendix G (Table 3): partitioning Fashion-MNIST across Nusers=2,000N_{\mathrm{users}} = 2{,}000 disjoint clients sampled in round-robin cohorts of W=100W=100 over T=40T=40 rounds (22 participations per user), exact pure-LDP parallel + sequential composition guarantees user-level ϵtotal=2ϵround∈3,6,10\epsilon_{\mathrm{total}} = 2\epsilon_{\mathrm{round}} \in \\{3, 6, 10\\} with zero (ϵ,δ)(\epsilon,\delta) relaxation:

  • ϵtotal=3\epsilon_{\mathrm{total}} = 3 (ϵround=1.5\epsilon_{\mathrm{round}} = 1.5): Matching our saturation formula bsat=1b_{\mathrm{sat}}=1, k=1k=1 SQKR / b=1b=1 SSTQ leads quantized methods (45.59 ± 3.50%, 1717 bits vs. 38.20 ± 1.81% for SQKR with k=min⁡⌈1.5log⁡2e⌉,4=3k=\min\\{\lceil 1.5\log_2 e\rceil,4\\}=3 at 5151 bits, or 27.89 ± 2.64% if forced to k=4k=4 at 6868 bits; 26.80 ± 6.32% for Flat-Opt b=4 vs. 23.02 ± 1.99% for Flat-Uni b=4; 10.34% for vqSGD).
  • ϵtotal=6\epsilon_{\mathrm{total}} = 6 (ϵround=3.0\epsilon_{\mathrm{round}} = 3.0): SSTQ (Flat-Opt, b=2) (55.73 ± 1.05%, 1818 bits) beats both k=1k=1 SQKR / b=1b=1 SSTQ (49.60 ± 1.80%, +6.13+6.13\\%) and k=4k=4 SQKR (54.17 ± 1.30%, 6868 bits), while Metric-Aware b=4 reaches 51.31 ± 1.26% and Flat-Opt b=4 (48.97 ± 2.20%) beats Flat-Uni b=4 (46.82 ± 2.63%).
  • ϵtotal=10\epsilon_{\mathrm{total}} = 10 (ϵround=5.0\epsilon_{\mathrm{round}} = 5.0): SSTQ (Flat-Opt, b=4) (58.31 ± 0.40%, 2020 bits) and b=2 (58.19 ± 1.59%, 1818 bits) outperform both Flat-Uni b=4 (56.78 ± 2.33%) and k=1k=1 SQKR / b=1b=1 SSTQ (54.30 ± 1.11%, +4.01+4.01\\%).

4. Optimized vs. Uniform Codebook in b=4b=4 Regression & CIFAR-10 (Question 4)

Your question uncovered an envelope bug in our original synthetic regression script (ldp_comparison.py):

  • In b=4b=4 regression: SSTQ (Flat-Opt) precomputed its codebook on the public clipping envelope Bmax⁡=KC/NB_{\max} = KC/\sqrt{N}, whereas SSTQ (Flat-Uni) had inadvertently built its grid on [−B,B][-B,B] using the unprivatized per-client gradient norm B=K∥g∥2/NB = K\|g\|_2/\sqrt{N} (which shrinks far below C=1C=1 as realizable least-squares converges, leaking ∥g∥2\|g\|_2). Once all methods use the valid public bound Bmax⁡B_{\max} (Figure 3, Figure 4), SSTQ (Flat-Opt) outperforms SSTQ (Flat-Uni) across every dimension and bit-width (55 seeds: 48.8 ± 1.8 vs. 55.4 ± 3.3 at d=100d=100; 144.2 ± 5.2 vs. 155.1 ± 4.8 at d=200d=200; 433.7 ± 8.5 vs. 440.9 ± 3.8 at d=500d=500; and at b=8,d=200b=8, d=200: 206.5 ± 6.7 vs. 2449.9 ± 263.0, an 11.9×11.9\times reduction!).
  • In CIFAR-10 (b=4,ϵ=3b=4, \epsilon=3): Both already used Bmax⁡B_{\max}, and the single-seed inversion does not persist across seeds: over 33 seeds, SSTQ (Flat-Opt, b=4) achieves 19.19 ± 0.97% vs. 18.62 ± 1.29% for SSTQ (Flat-Uni, b=4) (and 62.63 ± 0.91% vs. 62.11 ± 0.65% across 55 seeds on Fashion-MNIST; 65.30 ± 1.51% vs. 63.16 ± 1.39% on converged Fashion-MNIST; and 23.59 ± 0.36% vs. 22.90 ± 0.27% on converged CIFAR-10).

5. Server-Side Clipping Activation Frequency & Ablation Without It (Question 5)

We logged exact round-by-round aggregate norms ∥gˉ∥2\|\bar{g}\|_2 across all seeds (Table 2, Appendix G):

  • Clean, PrivUnit, FT-PrivUnit, SQKR, and all SSTQ variants: Server-cap (10.0) activation frequency is 0.0%0.0\% (0/1000/100 rounds across every seed) on both Fashion-MNIST (max ∥gˉ∥2≤2.79\|\bar{g}\|_2 \le 2.79) and CIFAR-10 (max ∥gˉ∥2≤5.33\|\bar{g}\|_2 \le 5.33). Re-running SSTQ (Flat-Opt, b=4) with server clipping completely disabled produces bit-for-bit identical accuracies (63.06 ± 0.95% across seeds 00–22 in both cases) and identically zero clipping bias.
  • vqSGD: Activates the 10.0 cap in 100.0%100.0\% of rounds (mean ∥gˉ∥2=4,256\|\bar{g}\|_2 = 4{,}256 on Fashion-MNIST and 32,47832{,}478 on CIFAR-10); disabling it degrades vqSGD further (8.99 ± 2.48% vs. 9.90 ± 2.84%) and causes logit overflow. Thus the server cap served solely to keep vqSGD numerically plottable.
AuthorsOpenReview ↗

A gentle reminder as the deadline is approaching

Thank you again for your constructive feedback, which has meaningfully strengthened our work.

As the discussion phase closes soon, we wanted to let you know that we have addressed all the points raised in your review with new experiments and analyses. If any of your concerns remain, please let us know so we can discuss them further.

If our response has resolved your questions, we would be grateful if you would consider updating your score to reflect these improvements. Thank you for your time and guidance!

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Comment to Area Chair and All Reviewers

We sincerely thank the Area Chair and Reviewers nG6R, PB1X, and 8BLf for their constructive, insightful reviews. Using the 10-page rebuttal page limit, we have substantially strengthened both the theoretical exposition and empirical evaluation (all changes are highlighted in blue in the revised manuscript):

  1. Isolated 1-Bit vs. Multi-Bit & Modern Compression Baselines (nG6R, PB1X, 8BLf):

    • We prove (Proposition 3.3) that under public Kashin bound Bmax⁡B_{\max}, b=1b=1 SSTQ (Flat-RR) and k=1k=1 private-coin SQKR induce the exact same message distribution at ⌈log⁡2N⌉+1\lceil\log_2 N\rceil+1 bits (1717/1919 bits), and evaluate k=1k=1 SQKR / b=1b=1 SSTQ, b=2,4b=2,4 SSTQ, and PRG-Compressed PrivUnit (FT-PrivUnit) (Feldman & Talwar, ICML 2021) across multiple random seeds (reporting mean ±\pm std and wall-clock runtimes; Figure 1, Table 2, Table 3).
    • We also add a protocol and complexity comparison with Poisson Private Representation (PPR) (Liu et al., NeurIPS 2024) in Table 1 and Appendix A.2.
  2. Higher-Accuracy Converged Regime, ϵ\epsilon-Sweep & Strict User-Level ϵtotal\epsilon_{\mathrm{total}} (nG6R, PB1X, 8BLf):

    • We evaluate a higher-accuracy converged regime without C=0.1C=0.1 saturation (78.90 ± 0.59% Clean on Fashion-MNIST; 38.83 ± 0.12% Clean on CIFAR-10; Table 3, Figure 6), where multi-bit SSTQ (Flat-Opt, b=2) leads all quantized pure-LDP methods on both datasets: 67.63 ± 0.45% (1818 bits) on Fashion-MNIST—beating k=1k=1 SQKR / b=1b=1 SSTQ (64.37 ± 0.67%, 1717 bits, +3.26%+3.26\%) and k=4k=4 SQKR (66.56 ± 0.43%, 6868 bits, 3.8×3.8\times fewer bits)—and 24.23 ± 0.66% (2020 bits) on CIFAR-10 vs. 23.86 ± 0.97% (k=4k=4 SQKR, 7676 bits) and 22.88 ± 0.90% (b=1b=1).
    • We evaluate strict pure-LDP user-level total budgets ϵtotal∈{3,6,10}\epsilon_{\mathrm{total}} \in \{3, 6, 10\} across 2,0002{,}000 disjoint users (Table 3) as well as an exact single-message ϵ\epsilon-sweep across ϵ∈[0.5,8]\epsilon \in [0.5, 8] (Figure 5).
  3. Exact Theory–Implementation Alignment (nG6R):

    • Eq. (43)→\to(44) for unequal row norms: Repaired in Appendix D.3 with zero loss via the exact row-norm-weighted discrete probability measure μx,U≔1N∑j=1N∥uj∥22δyj\mu_{x,U} \coloneqq \frac{1}{N}\sum_{j=1}^N \|u_j\|_2^2 \delta_{y_j} (valid by Lemma C.1), requiring neither equal row norms nor a continuous density.
    • Kashin envelope & common interval: Aligned Appendix G with our exact clipped-POCS implementation (yc(r)∈[−Bmax⁡,Bmax⁡]Ny_c^{(r)} \in [-B_{\max}, B_{\max}]^N; Brègman, 1967; Caldas et al., 2018), which unconditionally certifies pure ϵ\epsilon-LDP on a common public interval without frame certificates, and quantified finite-iteration projection residuals.
    • Server-side clipping & b=4b=4 regression: Measured exact server-cap (10.0) activation rates (Table 2): 0.0%0.0\% of rounds across all seeds for Clean, PrivUnit, FT-PrivUnit, SQKR, and all SSTQ variants (zero clipping bias; unclipped runs are bit-for-bit identical) vs. 100.0%100.0\% for vqSGD. We also fixed an envelope discrepancy in the synthetic b=4b=4 regression script where uniform-grid baselines had inadvertently used the private norm ∥g∥2\|g\|_2 instead of public Bmax⁡B_{\max}; under public Bmax⁡B_{\max}, SSTQ (Flat-Opt) beats Flat-Uni, k=1k=1 SQKR, and k=4k=4 SQKR across all dimensions (Figure 3, Figure 4).
  4. Clarity, Attribution, Codebook Structure & Figure Readability (8BLf, PB1X):

    • Added high-level intuition vs. SQKR (Section 3), formal 11-bit equivalence and O(1+dlog⁡dW)\mathcal{O}(1 + \frac{d\log d}{W}) amortized server decoding with full proof (Proposition 3.3, Appendix C.3), attribution and tightened DB=2BD_B=2B analysis of 1D truncated Laplace (Section 5, Appendix E), structure of Γ∗\Gamma^* in well-separated vs. privacy-saturated regimes (Remark 4.4, Figure 5c), deferred ζ2\zeta^2 to Section 6, and enlarged all figure legends.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.