Paper deep dive
SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant
Adel Javanmard, David P. Woodruff, Vahab Mirrokni
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Achieving local differential privacy in distributed optimization while maintaining low communication cost remains challenging. Existing vector quantization methods, such as vqSGD, use high-dimensional geometric constructions but incur unfavorable dimension-dependent variance. In this work, we propose Subsampled Stochastic TurboQuant (SSTQ), a framework that combines overcomplete equal-norm tight frames, coordinate subsampling, and privacy-aware one-dimensional quantization. SSTQ includes two variants: a Flat Randomized Response version and a Metric-Aware Laplace version, the latter being better suited to higher codebook bit-width regimes. We show that SSTQ achieves optimal mean squared error scaling while using only $\lceil \log_2 N \rceil + b$ bits per client, where $N = \Theta(d)$ is the frame size. We also derive a surrogate privacy-aware codebook objective that reduces the codebook-dependent MSE scaling from $O(4^b)$ to $O(2^b)$. Finally, we empirically evaluate SSTQ against established baselines on federated learning tasks using CIFAR-10 and Fashion-MNIST, demonstrating favorable utility and communication efficiency.
Tags
Links
- Source: https://arxiv.org/abs/2608.05127v1
- Canonical: https://arxiv.org/abs/2608.05127v1
PDF not stored locally. Use the link above to view on the source site.
Full Text
156,418 characters extracted from source content.
Expand or collapse full text
SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant Adel Javanmard University of Southern California, ajavanma@usc.edu Google Research, mirrokni@google.com David P. Woodruff Carnegie Mellon University, dwoodruf@andrew.cmu.edu Google Research, mirrokni@google.com Vahab Mirrokni Google Research, mirrokni@google.com Abstract Achieving local differential privacy in distributed optimization while maintaining low communication cost remains challenging. Existing vector quantization methods, such as vqSGD, use high-dimensional geometric constructions but incur unfavorable dimension-dependent variance. In this work, we propose Subsampled Stochastic TurboQuant (SSTQ), a framework that combines overcomplete equal-norm tight frames, coordinate subsampling, and privacy-aware one-dimensional quantization. SSTQ includes two variants: a Flat Randomized Response version and a Metric-Aware Laplace version, the latter being better suited to higher codebook bit-width regimes. We show that SSTQ achieves optimal mean squared error scaling while using only ⌈log2N⌉+b _2N +b bits per client, where N=Θ(d)N= (d) is the frame size. We also derive a surrogate privacy-aware codebook objective that reduces the codebook-dependent MSE scaling from (4b)O(4^b) to (2b)O(2^b). Finally, we empirically evaluate SSTQ against established baselines on federated learning tasks using CIFAR-10 and Fashion-MNIST, demonstrating favorable utility and communication efficiency. 1 Introduction and Motivation The communication bottleneck in federated learning (FL) and large-scale distributed optimization has led to significant interest in gradient compression techniques [15, 12]. At the same time, protecting sensitive client data against adversarial or untrusted aggregators necessitates the use of Local Differential Privacy (LDP) [10, 14, 18]. These two objectives—communication efficiency and strong privacy guarantees—are inherently at odds. Compression reduces high-dimensional continuous signals to compact discrete representations, while LDP requires adding noise and maintaining sufficient support over the same space to ensure plausible deniability. Existing approaches to private vector release can be broadly understood through three underlying paradigms, each with distinct limitations. Geometric quantization methods, such as vqSGD [11], encode vectors using structured high-dimensional polytopes and apply randomized response over the resulting discrete set. While communication-efficient, their reliance on high-dimensional geometry leads to unfavorable variance scaling, which can grow cubically with the dimension. A second class of methods achieves optimal variance scaling under LDP. Mechanisms such as SQKR [6] and PrivUnit [4] attain the information-theoretic limit of O(d/ϵ2)O(d/ε^2) by operating over bounded representations, including Kashin frames or continuous distributions. However, these approaches either impose restrictive communication constraints—such as 1-bit quantization and shared randomness in SQKR—or require transmitting dense, uncompressed vectors, as in PrivUnit, limiting their practicality in bandwidth-constrained settings. Finally, recent advances in data-oblivious quantization, such as TurboQuant [19], demonstrate that near-optimal distortion can be achieved across a wide range of codebook bit-widths and dimensions by combining orthogonal transformations with scalar codebooks. While these methods are highly effective for compression, they do not provide privacy guarantees and can suffer from directional bias when combined with naive privatization schemes. In addition, the TurboQuant pipeline first applies a random rotation to the input vectors and then exploits the near-independence of coordinates in high-dimensional spaces to apply optimal scalar quantization to each coordinate. Consequently, the number of output bits scales on the order of the input dimension, corresponding to a constant bit-width per coordinate. In contrast, the present focus is on transmitting a compressed representation using a number of bits that grows logarithmically with the dimension. In this work, we build on these insights and develop a data-oblivious, differentially private quantization framework based on one-dimensional Kashin representations. We derive the corresponding mean squared error and design codebooks that are optimized for the privatized setting, enabling efficient communication while preserving strong privacy guarantees. To emphasize this connection, we incorporate “TurboQuant” directly into the name of our procedure. Table 1: Comparison of Vector LDP Mechanisms with our proposed SSTQ pipeline (x∈d−1x ^d-1) Mechanism Topological / DP Geometry Number of Bits per Client Pure LDP MSE vqSGD Rigid Cross-Polytope ⌈log2d⌉+1 _2d +1 bits (d3ϵ2)O ( d^3ε^2 ) SQKR (Dense) Binary Kashin Frame (d)O(d) bits (dϵ2)O ( dε^2 ) SQKR (Subsampled) Binary Kashin Frame k(log2d+1)k( _2d+1) bits* (dmin(ϵ2,ϵ,b0))O ( d (ε^2,ε,b_0) ) PrivUnit Continuous Sphere d−1S^d-1 Θ(d) (d) bits (dϵ2)O ( dε^2 ) SSTQ (Flat randomization) 1D Kashin ⌈log2N⌉+b _2N +b bits (d(1+4bϵ∧ϵ2))O (d (1+ 4^bε ε^2 ) ) SSTQ (Flat randomization) 1D Kashin-Optimized Codebook ⌈log2N⌉+b _2N +b bits (d(1+2bϵ∧ϵ2))O (d (1+ 2^bε ε^2 ) ) SSTQ (Metric-Aware) 1D Kashin ⌈log2N⌉+b _2N +b bits (d(1+1(2b−1)2∧ϵ∧ϵ2))O (d (1+ 1(2^b-1)^2 ε ε^2 ) ) *This characterization holds in the private-coin setting with k=min(⌈log2e⌉ϵ,b0)k= ( _2e ε,b_0). If shared randomness is available (the public-coin setting), it reduces to k bits per client. 1.1 Our Contributions We present a unified framework connecting information-theoretic quantization with local differential privacy. Our main contributions are as follows: • SSTQ architecture: We introduce Subsampled Stochastic TurboQuant (SSTQ), which combines overcomplete equal-norm tight frames with data-oblivious coordinate subsampling. We show that this structure achieves the (d/(1∧ϵ∧ϵ2))O(d/(1 ε ε^2)) variance scaling, which is the optimal rate for the ϵ=O(1)ε=O(1) regime [9], while requiring only ⌈log2N⌉+b _2N +b bits per client in a private-coin setting. Here, N=Θ(d)N= (d) is the number of coefficients in the Kashin representation, chosen slightly larger than the original dimension d to guarantee that no single coordinate carries too much signal. • Privacy-aware codebook optimization: We derive a surrogate privacy-aware stochastic quantization loss ℒSSTQL_SSTQ, yielding a convex formulation for codebook design. This reduces the codebook-dependent MSE scaling from (4b)O(4^b) (worst-case, Theorem 3.2) to (2b)O(2^b) (Theorem 4.3), an exponential improvement in the base that grows with the codebook bit-width b. • Metric-aware mechanism for dense regimes: We propose a metric-aware Laplace mechanism that avoids the exponential variance growth of standard randomized response at higher codebook bit-widths, while preserving pure ϵε-LDP and enabling efficient multi-bit quantization. • Empirical evaluation: We evaluate SSTQ (Flat-R and Metric-Aware) against established baselines, including PrivUnit, vqSGD, and SQKR, in federated learning tasks on CIFAR-10 and Fashion-MNIST. Experiments are conducted across varying dimensions and codebook sizes to assess utility, variance behavior, and communication efficiency. 1.2 Distinctions from Prior Kashin-Based LDP Mechanisms Overcomplete tight frames (Kashin representations) have been used in prior work, notably SQKR [6], to control sensitivity under joint privacy and communication constraints. While SQKR achieves the optimal (d/(ϵ∧ϵ2))O(d/(ε ε^2)) mean squared error scaling, its design imposes several structural limitations. SSTQ differs in three key aspects: First, SSTQ removes the effective bandwidth restriction present in SQKR. In SQKR, dense encoding requires transmitting one bit per Kashin coefficient, leading to Θ(d) (d) bits. In the subsampled setting, grouping k coordinates with Flat Randomized Response incurs an exponential variance penalty (4k)O(4^k) (see Claim C.1 in [6]), which forces k to be capped by min(⌈log2e⌉ϵ,b0) ( _2e ε,b_0). In contrast, SSTQ allocates the full b-bit budget to a single coordinate. In its metric-aware variant, it operates over a one-dimensional codebook, thereby fully utilizing the available bandwidth without incurring exponential penalties. Second, SSTQ replaces 1-bit quantization with a continuous surrogate optimization. SQKR maps Kashin coefficients to their extreme values prior to privatization, which fixes the baseline variance at a high level. SSTQ instead performs stochastic quantization over a multi-bit codebook optimized for the privatized setting, effectively reducing quantization error while accommodating LDP noise. Third, SSTQ operates as a private-coin protocol with explicit communication cost. SQKR relies on shared randomness to coordinate subsampling; without it, transmitting indices increases the communication cost to (klogd)O(k d) to send the indices of the k sampled coordinates. SSTQ directly transmits the sampled index along with the quantized value, resulting in a fixed cost of ⌈log2N⌉+b _2N +b bits, independent of shared randomness assumptions. 2 Related Work and Mathematical Preliminaries 2.1 Related Work The fundamental tension between Local Differential Privacy (LDP) and extreme communication bandwidth in distributed mean estimation has motivated a rich recent literature. Our Subsampled Stochastic TurboQuant (SSTQ) framework differs from prior approaches along three axes: privacy threat model, quantization efficiency, and geometric optimization. Geometric Quantization and Dimensional Curses. Foundational mechanisms such as PrivUnit and PrivUnitG [4, 2] achieve the information-theoretic optimal LDP variance of (d/ϵ2)O(d/ε^2) but require transmitting uncompressed dense continuous vectors. By contrast, geometric quantizers such as vqSGD [11] reduce bandwidth logarithmically by mapping vectors to high-dimensional cross-polytopes. However, this rigid geometry shrinks the LDP probability gap and triggers the Θ(d3/ϵ2) (d^3/ε^2) variance curse proven in Appendix A. While recent work has broken dimension dependence for sparse discrete distribution estimation under communication constraints [7], SSTQ achieves a similar breakthrough for dense, high-dimensional continuous gradient quantization. Random Projections and Subspace LDP. To reduce the (d)O(d) communication bottleneck of optimal LDP mechanisms, methods such as ProjUnit [1] project gradients into a lower k-dimensional subspace before applying continuous LDP. Although ProjUnit achieves order-optimal expected MSE, it still outputs continuous vectors that require further quantization and relies on dense matrix-vector multiplications during decoding. SSTQ instead natively unifies LDP with discrete quantization: by coupling an Equal-Norm Tight Frame with 1-sparse oblivious subsampling, it reduces the problem to exact 1D scalar quantization, with payload ⌈log2N⌉+b _2N +b bits. Central/Shuffle DP and Coordinate Subsampling. Coordinate subsampling has also been used to amplify privacy under relaxed trust models. The Coordinate Subsampled Gaussian Mechanism (CSGM) [8] combines Kashin’s representation with random subsampling to achieve optimal (d/n2ϵ2)O(d/n^2ε^2) error for the estimation of the aggregated mean across n clients under Central/Shuffle DP, but it depends on a trusted central server or a secure shuffler. SSTQ instead operates in the strictly stronger pure ϵε-Local DP setting, providing message-level plausible deniability without trusted aggregation. Geometric Constants and Continuous Optimization. The streaming variant L2L_2-CSGM [5] shows that pushing L2L_2 geometries through L∞L_∞ Kashin bounds with rigid 1-bit quantization, as in SQKR [6], leads to suboptimal MSE constants. SSTQ demonstrates that this limitation stems from the rigid binarization, not from the overcomplete frame itself: by replacing 1-bit quantization with a multi-bit continuous surrogate geometry optimized via ℒSSTQL_SSTQ, it factors out these spatial penalties and reduces the codebook-dependent MSE scaling from (4b)O(4^b) to (2b)O(2^b) (Theorem 4.3), all within pure LDP. 2.2 Mathematical Preliminaries Before presenting the algorithmic developments, we briefly review the basic notions of local differential privacy and overcomplete frame theory. Local Differential Privacy (LDP). LDP requires each client to perturb its data before transmission, ensuring that the released message remains private even against an untrusted aggregator. In particular, the server cannot reliably infer the original client data, regardless of any auxiliary information or post-processing. The formal definition is as follows. Definition 2.1 (ϵε-Local Differential Privacy). A randomized mechanism ℳ:→M:X satisfies pure ϵε-Local Differential Privacy (ϵε-LDP) if for all pairs of possible inputs x,x′∈x,x and for all measurable subsets of outputs S⊆S : Pr[ℳ(x)∈S]≤eϵPr[ℳ(x′)∈S] [M(x)∈ S]≤ e^ε [M(x )∈ S] (1) where ϵ>0ε>0 is the strict privacy budget. Equal-Norm Tight Frames and Kashin Representations. Standard orthogonal bases (i.e., standard d×d× d rotation matrices) cannot guarantee (1/d)O(1/ d) coordinate bounds for all worst-case inputs. To systematically suppress the maximum coordinate magnitude and enforce dense, uniformly bounded coordinates, we must utilize redundant, overcomplete frames. Definition 2.2 (Equal-Norm Tight Frame (ENTF)). A set of vectors u1,…,uN\u_1,…,u_N\ in ℝdR^d (where N≥dN≥ d) forms a tight frame with frame bound A if for all x∈ℝdx ^d, ∑j=1N⟨x,uj⟩2=A‖x‖22 _j=1^N x,u_j ^2=A x _2^2. Let U∈ℝN×dU ^N× d be the matrix whose rows are ujTu_j^T. The tight frame condition is mathematically equivalent to UTU=AIdU^TU=AI_d. An Equal-Norm Tight Frame further enforces that all row vectors have identical Euclidean length: ‖uj‖2=c u_j _2=c for all j. Lemma 2.3 (ENTF Trace Property). For a normalized ENTF U∈ℝN×dU ^N× d constructed such that UTU=NdIdU^TU= NdI_d, it necessarily follows that the L2L_2 norm of every row is strictly 11, i.e., ‖uj‖22=1 u_j _2^2=1 for all j∈1,…,Nj∈\1,…,N\. Theorem 2.4 (Kashin’s Representation Theorem). Let U∈ℝN×dU ^N× d be an ENTF with N>dN>d that satisfies the Lyubarskii–Vershynin uncertainty principle [16]. Then for any x∈ℝdx ^d, there exists a coefficient vector y∈ℝNy ^N such that: (i) dNUTy=x dNU^Ty=x; (i) ‖y‖∞≤KN‖x‖2 y _∞≤ K N x _2, where K>1K>1 is a constant dependent only on the redundancy ratio N/dN/d. This theorem ensures that any d-dimensional vector can be represented in a higher-dimensional space N where every single coordinate is uniformly bounded. We refer to [16] (Theorem 3.5) for a proof. Note that not every ENTF admits a Kashin representation and the uncertainty principle plays a key role. By [16] (Theorem 4.1), a Haar-random orthogonal frame U∈ℝN×dU ^N× d satisfies the uncertainty principle with high probability whenever N≥C0dN≥ C_0d for a universal constant C0C_0, and hence can be used for Kashin’s representation. In practice, generating and storing a dense random orthogonal matrix is expensive. In [16] (Theorem 4.3 and Remark 1), it is shown that random partial Fourier matrices also give a polylogarithmic Kashin level (as opposed to constant level). In our theoretical results we work with constant K, but in our experiments, for a faster implementation we use a randomized partial Hadamard transform for the Kashin representation. 3 Subsampled Stochastic TurboQuant (SSTQ) As discussed in Appendix A, prior work on geometric vector quantization, most notably vqSGD [11], suffers from a Θ(d3/ϵ2) (d^3/ε^2) variance growth rate, which severely limits its effectiveness for high-dimensional gradient embeddings. To address this limitation, we propose Subsampled Stochastic TurboQuant (SSTQ), a framework that decouples the codebook size M from the ambient dimension d by combining overcomplete tight frames, data-oblivious coordinate subsampling, and one-dimensional stochastic quantization. The SSTQ Algorithmic Pipeline. We define the ambient dimension d, the overcomplete frame size N>dN>d (e.g., N=⌈1.2d⌉N= 1.2d ), and the privacy budget ϵε. We construct a continuous 1D scalar codebook Γ=c1,…,cM =\c_1,…,c_M\ bounded in [−B,B][-B,B], where M=2bM=2^b is the number of quantization centroids and B=KNB= K N is the strict maximum spatial envelope established by the Kashin Representation (Theorem 2.4). We refer to b=log2(M)b= _2(M) as the “codebook bit-width”. Throughout, we assume the codebook is ordered (c1≤c2≤⋯≤cMc_1≤ c_2≤·s≤ c_M), boundary-anchored (c1=−Bc_1=-B, cM=Bc_M=B), and zero-mean (∑i=1Mci=0 _i=1^Mc_i=0). Algorithm 1 currently takes a codebook Γ as input; the design of this codebook is discussed later in Section 4, where we derive a surrogate privacy-aware stochastic quantization loss to guide codebook optimization. The algorithm currently uses Flat Randomized Response. In Section 5, we introduce an alternative variant based on a Metric-Aware Laplace mechanism, which replaces the flat randomized response with continuous truncated Laplace noise injection followed by nearest-codeword quantization, and is better suited to higher codebook bit-width regimes. Note that because the protocol employs a 1-sparse projection over an N-dimensional Kashin frame, compressing the full d-dimensional target vector requires transmitting exactly two discrete components: the coordinate support index (requiring ⌈log2N⌉ _2N bits) and the quantized scalar coefficient (requiring b bits). Consequently, the communication payload per client evaluates to ⌈log2N⌉+b _2N +b bits. Notably, this scheme does not rely on shared randomness (i.e., public-coin assumptions), in contrast to SQKR [6]. Theoretical Guarantees. We now state the theoretical guarantees on the utility and privacy of the SSTQ pipeline. The proofs of these properties are deferred to Appendix B. Theorem 3.1 (Strict ϵε-LDP and Unbiasedness). The SSTQ with flat randomized response, as presented in Algorithm 1, satisfies pure ϵε-Local Differential Privacy. Furthermore, the decoding algorithm given by Algorithm 2 returns an unbiased estimator, [x^]=xE[ x]=x. Our next theorem bounds the mean-squared-error (MSE) of the SSTQ (with Flat-R) algorithm. Theorem 3.2 (MSE of SSTQ (Flat-R)). For any input vector x∈d−1x ^d-1 processed via the SSTQ pipeline (with any ordered, boundary-anchored, zero-mean codebook Γ supported in [−B,B][-B,B]) the Mean Squared Error (variance) of the reconstructed vector x x is bounded by MSESSTQ:=[‖x^−x‖22]<d2K2N(p−q)2=(d(1+4bϵ∧ϵ2)).MSE_SSTQ:=E[ x-x _2^2]< d^2K^2N(p-q)^2=O (d (1+ 4^bε ε^2 ) ). (2) Note that for constant codebook bit-width b and ϵ=O(1)ε=O(1), the SSTQ achieves the optimal minimax rate of O(d/min(ϵ,ϵ2))O(d/ (ε,ε^2)) for the private mean estimation (no-quantization), established by [9], with the normalization x∈Sd−1x∈ S^d-1. Remark 3.3. In non-private quantization, increasing the codebook bit-width b reduces quantization error by refining the discrete grid of M=2bM=2^b states. Under local differential privacy, however, the mean squared error is affected both by quantization error and by the variance introduced through privatization. With Flat Randomized Response, a client’s true bin is replaced uniformly by one of the other M−1M-1 without using the geometry of the codebook. As M grows, this uniform randomization increasingly dilutes the signal and leads to larger reconstruction error. In particular, unbiased decoding under uniform Randomized Response requires a correction factor that scales with M=2bM=2^b, which motivates the metric-aware randomization mechanism introduced in Section 5. Algorithm 1 SSTQ Client Encoding Algorithm 0: Target vector x∈d−1x ^d-1, ENTF U∈ℝN×dU ^N× d, Codebook Γ 1: Redundant Kashin Bounding: Execute Lyubarskii’s algorithm to find the coefficient vector y∈ℝNy ^N such that dNUTy=x dNU^Ty=x and ‖y‖∞≤B=KN y _∞≤ B= K N. 2: Oblivious Subsampling: Uniformly sample an index j∼Unif(1,N)j (1,N) independent of the data. Extract the scalar coordinate yjy_j. 3: Strict Stochastic Interpolation: Identify adjacent codebook bounds such that yj∈[ck,ck+1]y_j∈[c_k,c_k+1] in Γ . Stochastically round yjy_j to a discrete token v∈ck,ck+1v∈\c_k,c_k+1\ via exact linear interpolation: Pr(v=ck+1)=yj−ckck+1−ck,Pr(v=ck)=ck+1−yjck+1−ck (v=c_k+1)= y_j-c_kc_k+1-c_k, (v=c_k)= c_k+1-y_jc_k+1-c_k 4: Flat Randomized Response: Apply pure ϵε-LDP over the M elements of Γ . Output noisy token z∈Γz∈ such that: Pr(z=ci∣v)=p=eϵeϵ+M−1if ci=vq=1eϵ+M−1if ci≠v (z=c_i v)= casesp= e^εe^ε+M-1&if c_i=v\\ q= 1e^ε+M-1&if c_i≠ v cases 5: return Transmit the private tuple (j,index of z)(j,index of z). Cost: ⌈log2N⌉+b _2N +b bits. Algorithm 2 SSTQ Server Decoding Algorithm 0: Client message tuple (j,z)(j,z), Codebook Γ , ENTF U∈ℝN×dU ^N× d. 1: 1D Unbiasing: Compute the debiased coordinate scalar y~j=zp−q y_j= zp-q. 2: Sparse Reconstruction: Build the 1-sparse upscaled vector y~=N⋅y~j⋅ej∈ℝN y=N· y_j· e_j ^N, where eje_j is the j-th standard basis vector. 3: Frame Projection: Reconstruct the unbiased target vector via exact ENTF projection: x^=dNUTy~∈ℝd x= dNU^T y ^d 4: return Unbiased estimator x x. 4 Surrogate Privacy-Aware Codebook Optimization (ℒSSTQL_SSTQ) A salient feature of SSTQ is its use of Equal-Norm Tight Frames (ENTFs) and Kashin representations, which spread the signal across all coordinates. Building on this property, we derive a privacy-aware codebook optimization that is data-oblivious and well suited to online applications. Consider SSTQ (Flat-R) in Algorithm 1. Assume a continuous coordinate y∈[ck,ck+1]y∈[c_k,c_k+1]. The stochastic interpolation variance satisfies Var(v∣y)=[v2∣y]−y2Var(v y)=E[v^2 y]-y^2, and the linear interpolation probabilities in Algorithm 1 yield the inverted parabola Var(v∣y)=(y−ck)(ck+1−y)Var(v y)=(y-c_k)(c_k+1-y). As shown in Appendix C.1 by applying the law of total variance to the randomized response output y~j y_j and the discrete probability relations of Flat R, we can compute the conditional variance of the estimator given the true coordinate y: Var(y~j∣y)=1p−qVar(v∣y)+(1p−q−1)y2+q(p−q)2∑i=1Mci2.Var( y_j y)= 1p-qVar(v y)+ ( 1p-q-1 )y^2+ q(p-q)^2 _i=1^Mc_i^2. (3) Because the estimator is locally unbiased, the uncentered second moment is given by [y~j2∣y]=Var(y~j∣y)+y2E[ y_j^2 y]=Var( y_j y)+y^2. Adding y2y^2 to the equation cancels out the −y2-y^2 term: [y~j2∣y]=1p−qVar(v∣y)+1p−qy2+q(p−q)2∑i=1Mci2.E[ y_j^2 y]= 1p-qVar(v y)+ 1p-qy^2+ q(p-q)^2 _i=1^Mc_i^2. (4) Taking the unconditional expectation over an arbitrary continuous data distribution Y∼fY(y)Y f_Y(y), factoring out 1p−q 1p-q, and applying the identity qp−q=1eϵ−1 qp-q= 1e^ε-1, we obtain: [y~j2]=1p−q[Y[Var(v∣y)]+1eϵ−1∑i=1Mci2]⏟:=ℒSSTQ∗(Γ)+1p−qY[y2].E[ y_j^2]= 1p-q [E_Y[Var(v y)]+ 1e^ε-1 _i=1^Mc_i^2 ]_:=L^*_SSTQ( )+ 1p-qE_Y[y^2]. (5) It is straightforward to see that MSESSTQ<d2[y~j2]MSE_SSTQ<d^2E[ y_j^2] (see Equation (51)). Also in (5) because Y[y2]E_Y[y^2] is constant for a given dataset, we can drop it when we optimize the empirical expected variance over codebook Γ . The Surrogate Objective and Strict Convexity. By expanding ℒSSTQ∗L^*_SSTQ from (5) in terms of fY(y)f_Y(y) we have ℒSSTQ∗(Γ)=∑k=1M−1∫ckck+1(y−ck)(ck+1−y)fY(y)y+1eϵ−1∑i=1Mci2.L^*_SSTQ( )= _k=1^M-1 _c_k^c_k+1(y-c_k)(c_k+1-y)f_Y(y)\,dy\;\;+\;\; 1e^ε-1 _i=1^Mc_i^2\,. (6) While the Kashin representation explicitly bounds coordinates within [−B,B][-B,B] (where B=K/NB=K/ N), their true empirical density fY(y)f_Y(y) is data-dependent and unknown prior to execution. We use the continuous uniform distribution fY(y)=12Bf_Y(y)= 12B as a surrogate to optimize the codebook. Note that the resulting codebook will not be a uniform grid, even when the uniform distribution is used for fY(y)f_Y(y). Definition 4.1 (Surrogate Privacy-Aware Codebook Objective). By using the uniform distribution fy(y)=12Bf_y(y)= 12B in the definition of ℒSSTQ∗L^*_SSTQ, we define the following: ℒSSTQ(Γ)=∑k=1M−1(ck+1−ck)312B+1eϵ−1∑i=1Mci2,L_SSTQ( )= _k=1^M-1 (c_k+1-c_k)^312B\;\;+\;\; 1e^ε-1 _i=1^Mc_i^2\,, (7) subject to the anchored Kashin boundaries c1=−Bc_1=-B and cM=Bc_M=B, the ordering constraint c1≤c2≤⋯≤cMc_1≤ c_2≤·s≤ c_M, and the zero-sum condition ∑i=1Mci=0 _i=1^Mc_i=0. Note that the LDP term acts as an explicit ℓ2 _2 regularization penalty on the codeword positions. Since the boundary codewords c1=−Bc_1=-B and cM=Bc_M=B are fixed by the anchored constraints, this penalty acts exclusively on the M−2M-2 interior codewords, pulling them toward the origin to offset the variance inflation from Flat Randomized Response. Theorem 4.2 (Global Convexity of ℒSSTQL_SSTQ). The objective function ℒSSTQ(Γ)L_SSTQ( ) is strictly globally convex and has a unique global minimizer Γ∗ ^*. The proof is deferred to Appendix C. Tightening Expected MSE via Optimal Codebook Selection. While Theorem 3.2 establishes a worst-case MSE bound scaling quadratic in the codebook size (M=2bM=2^b), for any continuous codebook with range [−B,B][-B,B], we next show that the optimized codebook Γ∗ ^* can improve this bound to scale linearly in the codebook size. Theorem 4.3. Let Γ∗ ^* be the global minimizer of the surrogate loss ℒSSTQ(Γ)L_SSTQ( ). Assuming that M=2b≥(4(eϵ−1))1/3+1M=2^b≥(4(e^ε-1))^1/3+1, for SSTQ (Flat-R) with codebook Γ∗ ^*, we have MSESSTQ=(d(1+2bϵ∧ϵ2)).MSE_SSTQ=O (d (1+ 2^bε ε^2 ) ). (8) The proof proceeds by constructing a family of candidate codebooks. For an integer parameter 1≤m≤⌊(M−1)/2⌋1≤ m≤ (M-1)/2 , we define Γ~m∈ _m to span exactly m contiguous gap intervals of size B/mB/m, mapping the corresponding values from −B-B to B, while collapsing the remaining M−2m−1M-2m-1 indices symmetrically to 0. We then compare the surrogate loss evaluated at the optimized codebook with the minimum loss over this family, which yields a tighter dependence on M. 5 Codebook Bit-Width Scalability: The Metric-Aware Laplace Mechanism As discussed in Remark 3.3, standard Flat Randomized Response incurs a variance penalty that grows rapidly with b, since the probability gap p−qp-q shrinks on the order of 2−b2^-b. This makes the optimal spatial variance guarantee less effective in high-precision, multi-bit settings. To overcome this limitation and support arbitrarily dense codebooks, we introduce a Metric-Aware Laplace Mechanism. Given the true secret token v=ckv=c_k, instead of Flat Randomized Response (line 4 in Algorithm 1), the mechanism operates in two steps: 1. Continuous Laplace sampling. Draw a continuous sample T from a truncated Laplace distribution on [−B,B][-B,B] centered at ckc_k: fT|v=ck(t)=1Zkexp(−ϵ|t−ck|2Δ),t∈[−B,B],f_T|v=c_k(t)= 1Z_k \! (- ε|t-c_k|2 ), t∈[-B,B], (9) where Δ=2B=2KN =2B= 2K N is the domain width and Zk=∫−BBexp(−ϵ|t−ck|2Δ)tZ_k= _-B^B \! (- ε|t-c_k|2 )dt is the normalizing constant. 2. Nearest-codeword quantization. Set z=argminci∈Γ|T−ci|z= _c_i∈ |T-c_i|. The effective probability of outputting z=ciz=c_i given v=ckv=c_k is therefore Pi|k=Pr[z=ci∣v=ck]=1Zk∫celliexp(−ϵ|t−ck|2Δ)t,P_i|k= [z=c_i v=c_k]= 1Z_k _cell_i \! (- ε|t-c_k|2 )dt, (10) where cellicell_i is the Voronoi cell of codeword cic_i, and the codebook has size M=2bM=2^b. Privacy follows directly from the post-processing theorem of differential privacy. The continuous Laplace sampling step (Step 1) satisfies pure ϵε-LDP: for any two tokens ck,cm∈Γc_k,c_m∈ and any measurable set S⊆[−B,B]S [-B,B], the density ratio is bounded by eϵe^ε (see Appendix D). The nearest-codeword quantization step (Step 2) is a deterministic post-processing of the noisy sample T and therefore cannot degrade the privacy guarantee. Theorem 5.1 (Pure ϵε-LDP of Metric-Aware Laplace). For any codebook bounded in [−B,B][-B,B], the Metric-Aware Laplace Mechanism defined above satisfies pure ϵε-LDP. The metric-aware variant relaxes the requirement of coordinate-level unbiasedness during server-side decoding. Upon receiving the ϵε-LDP randomized codeword z=ciz=c_i, the central aggregator applies identity decoding, directly setting wi=ciw_i=c_i and projecting it into a 1-sparse vector y~=Nwiej=Nciej y=Nw_ie_j=Nc_ie_j, where we recall j as the (uniformly) sampled index by the encoder. This design explicitly trades a localized bias for reduced variance, enabling seamless integration with arbitrarily optimized, non-uniform continuous codebooks. Because the transition probabilities (10) are Voronoi-cell integrals of the continuous Laplace density, the mechanism moments are controlled by the continuous distribution regardless of the codebook geometry. Theorem 5.2 (MSE and Bias of metric-aware SSTQ). We assume a codebook of size M=2bM=2^b with its maximum codebook gap satisfying Δmax=maxk(ck+1−ck)≤C2B2b−1 _ = _k(c_k+1-c_k)≤ C 2B2^b-1 for a structural constant C≥1C≥ 1. Then, the Mean Squared Error (MSE) and the expected bias of SSTQ (with metric-aware mechanism) are bounded by: MSEMA _MA :=[‖x^−x‖22]≤dK2ρ(1+2C2(2b−1)2+16ϵ+256ϵ2)−1 :=E[\| x-x\|_2^2]≤ dK^2ρ (1+ 2C^2(2^b-1)^2+ 16ε+ 256ε^2 )-1 ζ2 ζ^2 :=‖[x^]−x‖22≤64K2ρϵ2, :=\|E[ x]-x\|_2^2≤ 64K^2ρε^2, where ρ=N/d>1ρ=N/d>1 is the frame redundancy ratio, and K=(1)K=O(1) is the Kashin representation constant establishing the continuous domain bound B=KNB= K N. We refer to Appendix D.2 for the proof of Theorem 5.2. Structural Implications. As shown by this theorem, the bias of the estimator is bounded independently of the ambient dimension d. In addition, this bound is independent of the discretization bit-width b. Therefore, the benefit of metric-aware mechanism is that by trading a dimension-free and bit-width free bias we obtain a smaller variance, addressing the O(2b)O(2^b) dependence in the Flat-R variant. Note that the term (4−b)O(4^-b) in the MSE bound captures the deterministic spatial quantization error. It decays exponentially as the codebook bit-width b increases. The terms (ϵ−1)O(ε^-1) and (ϵ−2)O(ε^-2) capture the stochastic noise injected to satisfy Local Differential Privacy: the (ϵ−2)O(ε^-2) term arises from the Laplace mechanism variance, while the (ϵ−1)O(ε^-1) term arises from the cross-correlation between the signal and the boundary bias of the truncated Laplace distribution. Together, they define a strict algebraic floor that cannot be mitigated by increasing the grid density M. Optimal Codebook Bit-Width Allocation. The additive structure of the bound proves that allocating bits as b→∞b→∞ provides diminishing returns. The asymptotic improvement of the MSE strictly saturates once the spatial discretization error is subsumed by the privacy variance floor. By equating these two dominant scales we get the optimal required codebook dimension: 1(2b−1)2≍1ϵ∧ϵ2⟹b=(⌈log2(ϵ)⌉) 1(2^b-1)^2 1ε ε^2 b=O\! ( _2(ε) ) The codebook bit-width b scales logarithmically, confirming that relatively compressed codebooks are mathematically sufficient to achieve the fundamental operational bounds of the metric-aware mechanism. 5.1 Codebook Optimization For a vector x, recall the Kashin coefficient vector y defined through the relation dNUTy=x dNU^Ty=x. This vector depends on the private input x; consequently, the marginal density fYf_Y of the Kashin coordinates (induced by randomness of the frame U) depends on private data and is not known to the mechanism designer a priori. In practice, SSTQ sidesteps this dependence entirely: the surrogate codebook objective ℒSSTQL_SSTQ (Definition 4.1) replaces fYf_Y with the uniform density fY(y)=1/(2B)f_Y(y)=1/(2B), which depends only on the Kashin bound B=K/NB=K/ N and is independent of any client’s private data. In this section, we consider codebook optimization under the true density fYf_Y; this should be understood as an oracle or public-distribution result. Realizing it in practice would require either genuinely public auxiliary data that characterizes fYf_Y, or a separately private codebook-learning procedure with explicit privacy accounting. Similar to the flat randomization mechanism, we can write a data-dependent objective loss that captures the codebook-dependent part of MSE bound. For the metric-aware mechanism, the loss is derived in Appendix D.2.1 and is given by ℒMA-SSTQ∗(Γ)=∑k=1M−1∫ckck+1Wk(y−ck)(ck+1−y)fY(y)y+∑i=1MπiVi,L^*_MA-SSTQ( )= _k=1^M-1 _c_k^c_k+1W_k(y-c_k)(c_k+1-y)f_Y(y)\,dy\;\;+\;\; _i=1^M _iV_i\,, where πi=∫−BBPr[v=ci∣y]fY(y)y _i= _-B^B [v=c_i y]f_Y(y)\,dy defines the precise unconditional assignment probability of the intermediate token v=civ=c_i. In addition, μi=[z∣v=ci] _i=E[z v=c_i] (the expected output codeword) and Vi=[(z−ci)2∣v=ci]V_i=E[(z-c_i)^2 v=c_i] (the metric-aware variance), both computed under the effective transition probabilities (10), and Wk=2(μk+1−μk)ck+1−ck−1W_k= 2( _k+1- _k)c_k+1-c_k-1. In the flat randomization mechanism, the objective function includes a rigid regularization penalty derived from the variance of uniform point selection: G(Γ)∝∑i=1Mci2G( ) _i=1^Mc_i^2. For a uniform grid over [−B,B][-B,B], this sum diverges as (M)O(M). Consequently, the uniform grid yields a theoretically vacuous MSE bound as M grows. By optimizing the codebook against a uniform surrogate distribution fY(y)=12Bf_Y(y)= 12B, the optimizer is forced to cluster points near the origin, suppressing the (M)O(M) penalty to an (1)O(1) bound. This structural adaptation provides a strict theoretical improvement over the uniform grid, independent of the actual target distribution. In contrast, the metric-aware mechanism utilizes identity decoding, which localizes the mechanism variance. The variance penalty evaluates as an expectation over the assignment probabilities: ∑i=1MπiVi _i=1^M _iV_i. As shown by (60), the local mechanism variance under the continuous Laplace is unconditionally bounded by Vi≤Vmax≈(ϵ−2)V_i≤ V_ (ε^-2), independently of the codebook geometry and size. Also the assignment probabilities sum to exactly 11, and so the global variance penalty is strictly (1)O(1) with respect to M. The uniform grid does not diverge. Therefore, optimizing a uniform surrogate loss cannot yield an asymptotic scaling improvement over the uniform grid; it merely shifts bounded variance against spatial resolution, which strictly weakens the worst-case bound. However, if the true data distribution fY(y)f_Y(y) is fixed and known, optimizing the true loss allows the codebook to systematically exploit the geometric concentration of the data. By leveraging high-resolution quantization theory, the optimizer allocates denser coordinates to high-probability regions, strictly reducing the spatial quantization error below the geometric limits of the uniform grid. We formalize this in the next theorem. Tight Bounds under the True Distribution. We formalize this improvement by introducing the Panter-Dite functional, which quantifies the compressibility of a continuous density. Let the distribution shape factor be defined as: Cf=14B2(∫−BBfY(y)1/3y)3C_f= 14B^2 ( _-B^Bf_Y(y)^1/3\,dy )^3 By Hölder’s inequality, Cf≤1C_f≤ 1 for all valid densities supported on [−B,B][-B,B], with equality holding if and only if fY(y)f_Y(y) is the uniform distribution. Theorem 5.3. Let x∈ℝdx ^d with ‖x‖2=1\|x\|_2=1. Let ρ=N/d>1ρ=N/d>1 be the frame redundancy ratio, and K=(1)K=O(1) be the Kashin representation constant establishing the continuous domain bound B=KNB= K N. Assume the true Kashin coordinates follow a known, strictly positive and continuous probability density fY(y)f_Y(y) supported on [−B,B][-B,B]. For any finite codebook size M=2b≥2M=2^b≥ 2, let Γ∗ ^* be the optimal codebook that minimizes the loss ℒMA-SSTQ∗(Γ)L^*_MA-SSTQ( ). The expected bias and Mean Squared Error of the metric-aware SSTQ estimator are bounded by: ζ2 ζ^2 :=‖[x^]−x‖22≤64K2ρϵ2 :=\|E[ x]-x\|_2^2≤ 64K^2ρε^2 MSEMA _MA :=[‖x^−x‖22]≤dK2ρ(1+2C02(2b−1)2+16ϵ+256ϵ2)−1 :=E[\| x-x\|_2^2]≤ dK^2ρ (1+ 2C_0^2(2^b-1)^2+ 16ε+ 256ε^2 )-1 where the spatial constant C02C_0^2 satisfies C02≤min(1,23CfRM)C_0^2≤ (1,\; 23C_fR_M ). Here, RM=1M−1∑k=1M−1supy∈[ck,ck+1]fY(y)infy∈[ck,ck+1]fY(y)≥1R_M= 1M-1 _k=1^M-1 _y∈[c_k,c_k+1]f_Y(y) _y∈[c_k,c_k+1]f_Y(y)≥ 1 is the average local oscillation ratio of the density across the intervals of the proxy codebook. Since Cf<1C_f<1 for any strictly non-uniform density, and RM→1R_M→ 1, as b→∞b→∞, hence for sufficiently high resolutions, C02<1C_0^2<1, guaranteeing strict improvement in the MSE bound compared to the bound derived in Theorem 5.2 (Recall that there C≥1C≥ 1). The Asymptotic Limit (ϵ→∞ε→∞) and the Panter-Dite Framework. The benefits of codebook optimization formulation become most apparent when considering the limit as privacy constraints relax (ϵ→∞ε→∞). In this regime, the continuous Laplace density fT|v(t)∝exp(−ϵ|t−v|4B)f_T|v(t) (- ε|t-v|4B) concentrates at a Dirac delta centered at v. Consequently, T→vT→ v almost surely, the quantization step maps T to its nearest codeword deterministically. The localized variance vanishes (Vk→0V_k→ 0), the structural drift collapses (βk→0 _k→ 0), and the spatial scale modifier Wk→1W_k→ 1. Note that the initial stochastic interpolation step remains active even in this limit; for a non-codeword input yjy_j, the mechanism reduces to stochastic endpoint rounding followed by deterministic identity output, which is the classical dithered quantizer. Substituting these limits, the loss simplifies to the classical spatial quantization distortion: limϵ→∞ℒMA-SSTQ(Γ)=∑k=1M−1∫ckck+1(y−ck)(ck+1−y)fY(y)y _ε→∞L_MA-SSTQ( )= _k=1^M-1 _c_k^c_k+1(y-c_k)(c_k+1-y)f_Y(y)\,dy In the high-resolution limit (M→∞M→∞) of classical quantization theory, the discrete codebook intervals can be approximated by a continuous point density function λ(y)λ(y). The spatial sum converges to the continuous integral 16(M−1)2∫−BBfY(y)λ(y)2y 16(M-1)^2 _-B^B f_Y(y)λ(y)^2\,dy. The Panter-Dite framework (1951) [17] establishes that minimizing this spatial integral via Hölder’s inequality strictly requires the continuous point density to satisfy: λ∗(y)=fY(y)1/3∫−BBfY(z)1/3zλ^*(y)= f_Y(y)^1/3 _-B^Bf_Y(z)^1/3\,dz Therefore, as local differential privacy constraints vanish, the optimal metric-aware codebook abandons variance regularization and allocates discrete coordinates exactly proportional to fY(y)1/3f_Y(y)^1/3. This formally bridges optimal differentially private randomization with the classical foundations of scalar source coding. 6 Federated Learning Convergence Analysis We next consider the application of our proposed SSTQ algorithm to private federated learning. We adopt a standard federated learning setup and operate under common assumptions of non-convex optimization and bounded statistical variance, stated below. Consider n clients, with fi(w)f_i(w) the local loss objective for client i, and F(w)=1n∑i=1nfi(w)F(w)= 1n _i=1^nf_i(w) the global objective. Assumption 6.1 (Optimization Conditions). Let ℱt=σ(w0,g^i,s:i∈[n],s<t)F_t=σ\! (w_0,\; g_i,s:i∈[n],\,s<t ) denote the σ-algebra generated by the initial point and all transmitted gradients prior to step t. Since wtw_t is a deterministic function of (w0,g^i,0,…,g^i,t−1)i=1n(w_0, g_i,0,…, g_i,t-1)_i=1^n, the iterate wtw_t is ℱtF_t-measurable. Write t[⋅]=[⋅∣ℱt]E_t[·]=E[· _t]. We assume: (i) Smoothness. The global objective F(w)=1n∑i=1nfi(w)F(w)= 1n _i=1^nf_i(w) is L-smooth, i.e. ‖∇F(x)−∇F(y)‖2≤L‖x−y‖2 ∇ F(x)-∇ F(y) _2≤ L x-y _2 for all x,yx,y. (i) Stochastic gradient bounds. Let gi,t=∇fi(wt,ξi,t)g_i,t=∇ f_i(w_t, _i,t) be the stochastic minibatch gradient sampled by client i at step t. We assume bounded conditional variance and a bounded conditional second moment: t[‖gi,t−∇fi(wt)‖22]≤σ2,t[‖gi,t‖22]≤G2,∀i,t.E_t\! [ g_i,t-∇ f_i(w_t) _2^2 ]≤σ^2, _t\! [ g_i,t _2^2 ]≤ G^2, ∀\,i,\,t. (i) Compression noise. Let g^i,t g_i,t be the (private quantized) gradient transmitted by client i. We assume a bounded conditional compression error: t[‖g^i,t−gi,t‖22]≤ωG2,∀i,t.E_t\! [ g_i,t-g_i,t _2^2 ]≤ω\,G^2, ∀\,i,\,t. (iv) Bounded bias (a.s.). Define the global server estimator g^t=1n∑i=1ng^i,t g_t= 1n _i=1^n g_i,t and the conditional bias bt:=t[g^t]−∇F(wt)b_t:=E_t[ g_t]-∇ F(w_t). We assume there exists ζ≥0ζ≥ 0 such that ‖bt‖22≤ζ2almost surely, for all t. b_t _2^2≤ζ^2 surely, for all t. (v) Conditional independence. Conditioned on ℱtF_t, the client estimator errors g^i,t−∇fi(wt)i=1n\ g_i,t-∇ f_i(w_t)\_i=1^n are mutually independent. (vi) Bounded below. F∗:=infwF(w)>−∞F^*:= _wF(w)>-∞. Denote Δ0:=F(w0)−F∗ _0:=F(w_0)-F^*. Our next theorem is a general convergence result for distributed SGD under Assumption 6.1. Theorem 6.2 (Non-Convex DSGD Convergence Rate). Under Assumption 6.1, consider the iterates wt+1=wt−ηg^tw_t+1=w_t-η\, g_t run for T steps across n clients. Define V:=2(ωG2+σ2)n+ζ2V:= 2(ω G^2+σ^2)n+ζ^2. (Non-asymptotic bound.) Setting η=min14L,Δ0LVTη= \! \ 14L,\; _0LVT \ guarantees: min0≤t≤T−1[‖∇F(wt)‖22]≤16LΔ0T+8Δ0LVT+2ζ2. _0≤ t≤ T-1E\! [ ∇ F(w_t) _2^2 ]\;≤\; 16L _0T+ 8 _0LV T+2ζ^2. (11) (Asymptotic rate.) For T≥16LΔ0/VT≥ 16L _0/V, the above simplifies to: min0≤t≤T−1[‖∇F(wt)‖22]≤(ωG2+σ2nT+ζ2), _0≤ t≤ T-1E\! [ ∇ F(w_t) _2^2 ]\;≤\;O\! ( ω G^2+σ^2 nT+ζ^2 ), (12) where (⋅)O(·) hides dependence on the problem constants Δ0 _0 and L. The formal proof, which utilizes the L-smooth descent lemma and controls the bias term via Young’s inequality, is deferred to Appendix E. We next specialize this general convergence theorem to the two variants of our SSTQ framework. Corollary 6.3 (Convergence under Flat Randomized Response). Using SSTQ with Flat R, the estimator is strictly unbiased (ζ=0ζ=0) per Theorem 3.1 and by Theorem 4.3 (assuming M≥(4(eϵ−1))1/3+1M≥(4(e^ε-1))^1/3+1), the variance multiplier is bounded by ω=(d⋅2b/(ϵ∧ϵ2))ω=O(d· 2^b/(ε ε^2)). Hence, the convergence rate of distributed SGD simplifies to: min0≤t≤T−1[‖∇F(wt)‖22]≤(1T+d⋅2b⋅(ϵ∧ϵ2)−1G2+σ2nT). _0≤ t≤ T-1E[ ∇ F(w_t) _2^2] ( 1T+ d· 2^b·(ε ε^2)^-1G^2+σ^2 nT ). (13) For higher codebook bit-widths where the (2b)O(2^b) penalty becomes a computational bottleneck, we switch the framework to the Metric-Aware Laplace mechanism with identity decoding. This trades absolute unbiasedness for smaller variance bound. Corollary 6.4 (Convergence under Metric-Aware Mechanism). Using SSTQ with the Metric-Aware Laplace mechanism, by Theorem 5.2 the variance multiplier and the bias are bounded by ω=(d(1+ϵ−1+ϵ−2))ω=O(d(1+ε^-1+ε^-2)) and ζ2=(G2ϵ−2)ζ^2=O (G^2ε^-2 ). Hence, the convergence rate of distributed SGD simplifies to: min0≤t≤T−1[‖∇F(wt)‖22]≤(1T+G2d(1+ϵ−1+ϵ−2)+σ2nT+G2ϵ−2). _0≤ t≤ T-1E[ ∇ F(w_t) _2^2] ( 1T+ G^2d(1+ε^-1+ε^-2)+σ^2 nT+G^2ε^-2 ). (14) 7 Neural Network Experiments We evaluate the practical performance of the LDP mechanisms in a federated learning setting with neural network models on two standard image classification benchmarks: Fashion-MNIST and CIFAR-10. Experimental Setup. We train a fully connected neural network with a single hidden layer of 32 units and ReLU activations. For Fashion-MNIST (10 classes, 784784-dimensional inputs), the model has d=25,450d=25,450 parameters; for CIFAR-10 (10 classes, 3,0723,072-dimensional inputs), the model has d=98,666d=98,666 parameters. For all Kashin-based methods (SQKR, SSTQ), we construct the frame using a randomized partial Hadamard transform. We simulate a federated setting with W=100W=100 workers, each holding a disjoint partition of the training data. At each of the T=100T=100 communication rounds, every worker computes a stochastic gradient on a mini-batch of size 6464, clips it to ‖g‖2≤C=0.1\|g\|_2≤ C=0.1, applies the LDP mechanism, and transmits the privatized message to the server. The server aggregates the received messages, applies a gradient norm cap of 10.010.0 for stability, and updates the global model with a constant learning rate (η=0.2η=0.2 for Fashion-MNIST, η=0.5η=0.5 for CIFAR-10). All methods operate under pure ε -LDP with per-round ε=3 =3 and bit budget b=4b=4. Remark 7.1 (Effect of server-side clipping). Server-side gradient clipping at threshold R is a nonlinear operation: [CR(g^)]≠CR([g^])E[C_R( g)]≠ C_R(E[ g]) in general, so clipping introduces a small bias even when the underlying estimator is unbiased. In the convergence framework of Theorem 6.2, this clipping-induced bias is absorbed into the ζ2ζ^2 term. In our experiments, the client-side clipping at C=0.1C=0.1 combined with the frame scaling B=K/NB=K/ N ensures that the reconstructed one-coordinate estimator has bounded norm, and the server-side cap of 10.010.0 activates infrequently. The theoretical convergence rates in Corollaries 6.3 and 6.4 hold exactly for the unclipped algorithm; the clipped variant converges to a neighborhood that includes the additional clipping bias. Remark 7.2 (Per-round vs. cumulative privacy budget). All reported privacy parameters are per-round guarantees: each client’s message in each round satisfies ε -LDP independently. Under basic composition with T rounds of full participation, the cumulative budget is εtotal=Tε _total=T . We report per-round ε (i.e., message-level privacy) because it isolates the mechanism’s intrinsic privacy–utility trade-off and is the standard metric across all baselines compared (vqSGD, SQKR, PrivUnit). In practice, client subsampling (where each client participates in only a fraction of rounds) provides privacy amplification by subsampling [3], and advanced composition [13] yields εtotal=(εTlog(1/δ)) _total=O( T (1/δ)) under (ε,δ)( ,δ)-DP. These orthogonal techniques apply equally to all mechanisms and are independent of the quantization scheme. To ensure a fair comparison, we use a common random seed for mini-batch selection across all methods, so that each method trains on exactly the same sequence of data batches. The only source of randomness that differs across methods is the LDP noise. Test accuracy is evaluated on the full held-out test set (10,00010,000 images) at each round. Results. Figure 1 presents the training loss, test accuracy, and accuracy-vs-communication-cost tradeoff for both datasets. The communication cost per client per round is summarized in Table 2. Figure 1: Neural network experiments under ε -LDP (ε=3 =3, b=4b=4, W=100W=100 workers). Top row: Fashion-MNIST (d=25,450d=25,450). Bottom row: CIFAR-10 (d=98,666d=98,666). Left: Training cross-entropy loss vs. SGD steps. Center: Test accuracy vs. SGD steps. Right: Final test accuracy vs. bits transmitted per client (log scale). Table 2: Communication cost per client per round (b=4b=4, ε=3 =3). Method Formula Fashion-MNIST CIFAR-10 Clean / PrivUnit 32d32d 814,400814,400 3,157,3123,157,312 vqSGD ⌈log2d⌉+1 _2d +1 1616 1818 SQKR k(⌈log2d⌉+1)k( _2d +1) 6464 7272 SSTQ (all variants) ⌈log2N⌉+b _2N +b 2020 2222 Fashion-MNIST. On the training loss (Figure 1, top-left), Clean SGD and PrivUnit decrease steadily, reaching final losses of approximately 1.21.2 and 1.251.25, respectively. SQKR and SSTQ (Flat-R) converge at a slightly slower rate, settling around 1.31.3, which reflects the additional variance from quantization and privacy noise. SSTQ (Metric-Aware) converges more slowly (final loss ≈1.7≈ 1.7), consistent with the small bias ζ2ζ^2 from the identity decoder (Corollary 6.4). vqSGD exhibits divergent training loss, increasing from 2.52.5 to ≈4.0≈ 4.0, confirming that its O(d3/ε2)O(d^3/ ^2) variance scaling drastically degrades its performance at d=25,450d=25,450. On test accuracy (Figure 1, top-center), Clean SGD reaches 65.4%65.4\% and PrivUnit closely tracks at 63.3%63.3\%. Among quantized methods, SQKR achieves 63.2%63.2\% using 6464 bits per client, while SSTQ (Flat-R, optimized codebook) achieves 63.3%63.3\% and SSTQ (Flat-R, uniform codebook) reaches 62.4%62.4\%—both using only 2020 bits per client, a 3.2×3.2× reduction compared to SQKR. Notably, the SSTQ Flat variants and SQKR now achieve nearly the same accuracy as PrivUnit, with the gap between all three quantized methods within 1%1\%. vqSGD fails to learn (7.2%7.2\%, near random chance). We note that SSTQ (Metric-Aware) underperforms SSTQ (Flat-R) due to its bias. However, its advantage becomes apparent at larger bit widths (b)(b), as discussed in Appendix G and demonstrated in Figure 4 therein. CIFAR-10. The higher dimensionality (d=98,666d=98,666) amplifies the variance effects. On training loss (Figure 1, bottom-left), Clean SGD and PrivUnit steadily decrease, while SQKR and SSTQ variants remain relatively flat around 2.22.2. vqSGD again diverges dramatically, with training loss rising to ≈5.7≈ 5.7. On test accuracy (Figure 1, bottom-center), Clean SGD reaches 29.1%29.1\% and PrivUnit 21.3%21.3\%. Among quantized methods, SQKR achieves 21.0%21.0\% (72 bits), followed by SSTQ (Flat-R, uniform codebook) at 19.7%19.7\%, SSTQ (Flat-R, optimized codebook) at 19.1%19.1\% (both using 22 bits), and SSTQ (Metric-Aware) at 17.7%17.7\%. vqSGD reaches 10.3%10.3\% (18 bits). Accuracy vs. Communication Cost. The rightmost panels of Figure 1 present the accuracy-vs-bits tradeoff (see also Table 2). SSTQ achieves accuracy comparable to SQKR while requiring substantially fewer bits per client. On Fashion-MNIST, SSTQ (Flat-R, optimized codebook) achieves 63.3%63.3\%—essentially matching SQKR’s 63.2%63.2\%—while using 3.2×3.2× fewer bits (2020 vs. 6464 bits). On CIFAR-10, the gap is similarly small: SSTQ (Flat-R, optimized codebook) reaches 19.1%19.1\% compared to SQKR’s 21.0%21.0\%, a difference of only 2%2\%, while using 3.3×3.3× fewer bits (2222 vs. 7272 bits). This communication advantage arises because SQKR transmits k=min(⌈2ε⌉,b0)k= ( 2 ,b_0) coordinates, each requiring ⌈log2d⌉+1 _2d +1 bits to encode, whereas SSTQ transmits a single coordinate index plus a b-bit quantization level, yielding a total of ⌈log2N⌉+b _2N +b bits. vqSGD uses the fewest bits (1616–1818) but fails to converge, confirming that its cubic variance scaling renders it impractical in high dimensions. PrivUnit achieves the best accuracy among private methods but requires full-precision transmission (>>800K bits), making it impractical for communication-constrained settings. It is worth noting that the 32d32d cost reported in Table 2 reflects float32 encoding. Using lower precision (e.g., 16d16d or 8d8d) reduces the constant but does not change the Θ(d) (d) scaling, which is inherent to any mechanism that outputs a d-dimensional vector. Computational Cost. All Kashin-based methods (SQKR, SSTQ) share the same computational bottleneck: the iterative Kashin representation, which involves repeated applications of the randomized partial Hadamard transform on a vector of dimension N=2⌈log2(2.5d)⌉N=2 _2(2.5\,d) , costing O(NlogN)O(N N) per client per round. In our experiments, each SGD step takes approximately 1818 s on Fashion-MNIST and 6565 s on CIFAR-10 (single CPU), with the Kashin transform accounting for over 99%99\% of the per-worker computation. The remaining operations (quantization, R or Laplace sampling) are O(M)O(M) for SSTQ and O(N)O(N) for SQKR. The server-side reconstruction requires applying a single column of the frame transform, costing O(d)O(d) per client, which is negligible compared to the Kashin encoding. In contrast, vqSGD avoids the Kashin representation entirely: it operates directly on the gradient vector using simplex sampling, costing only O(d)O(d) per client. This makes vqSGD significantly faster per step (approximately 55–10×10× compared to Kashin-based methods), but as demonstrated above, this computational advantage is negated by its prohibitive variance scaling in high dimensions. PrivUnit also avoids Kashin representations (O(d)O(d) per client) but requires transmitting full-dimensional vectors, making it communication-efficient only in a per-dimension sense. Conclusion and Limitations. Our proposed SSTQ framework provides a principled, communication-efficient framework for high-dimensional mean estimation that maintains pure LDP guarantees while reclaiming optimal geometric scaling. By unifying discrete quantization with adaptive, privacy-aware codebook optimization, it bypasses the variance penalties in quantization with fixed geometrical structures. However, our approach assumes a predetermined communication budget and a known data range; future work should address practical extensions to highly non-stationary data streams and the design of robust, range-agnostic adaptive mechanisms to further improve real-world deployment flexibility. Acknowledgment. Some of the results in this paper were obtained with significant interaction with a larger version of Google’s Deep Think Gemini-based model. The authors verified the entire paper and take full responsibility for all results. References [1] H. Asi, V. Feldman, J. Nelson, H. Nguyen, and K. Talwar (2023) Fast optimal locally private mean estimation via random projections. Advances in Neural Information Processing Systems 36, p. 16271–16282. Cited by: §2.1. [2] H. Asi, V. Feldman, and K. Talwar (2022) Optimal algorithms for mean estimation under local differential privacy. In International Conference on Machine Learning, p. 1046–1056. Cited by: §2.1. [3] B. Balle, G. Barthe, and M. Gaboardi (2018) Privacy amplification by subsampling: tight analyses via couplings and divergences. Advances in neural information processing systems 31. Cited by: Remark 7.2. [4] A. Bhowmick, J. Duchi, J. Freudiger, G. Kapoor, and R. Rogers (2018) Protection against reconstruction and its applications in private federated learning. arXiv preprint arXiv:1812.00984. Cited by: §1, §2.1. [5] W. Chen, B. Isik, P. Kairouz, A. No, S. Oh, and Z. Xu (2024) Improved communication-privacy trade-offs in ℓ2 _2 mean estimation under streaming differential privacy. arXiv preprint arXiv:2405.02341. Cited by: §2.1. [6] W. Chen, P. Kairouz, and A. Ozgur (2020) Breaking the communication-privacy-accuracy trilemma. Advances in Neural Information Processing Systems 33, p. 3312–3324. Cited by: §1.2, §1.2, §1, §2.1, §3. [7] W. Chen, P. Kairouz, and A. Ozgur (2021) Breaking the dimension dependence in sparse distribution estimation under communication constraints. In Conference on Learning Theory, p. 1028–1059. Cited by: §2.1. [8] W. Chen, D. Song, A. Ozgur, and P. Kairouz (2023) Privacy amplification via compression: achieving the optimal privacy-accuracy-communication trade-off in distributed mean estimation. Advances in Neural Information Processing Systems 36, p. 69202–69227. Cited by: §2.1. [9] J. Duchi and R. Rogers (2019) Lower bounds for locally private estimation via communication complexity. In Conference on Learning Theory, p. 1161–1191. Cited by: 1st item, §3. [10] C. Dwork, F. McSherry, K. Nissim, and A. Smith (2006) Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, p. 265–284. Cited by: §1. [11] V. Gandikota, D. Kane, R. K. Maity, and A. Mazumdar (2021) vqSGD: vector quantized stochastic gradient descent. In International Conference on Artificial Intelligence and Statistics, p. 2195–2205. Cited by: Appendix A, §1, §2.1, §3. [12] P. Kairouz and H. B. McMahan (2021) Advances and open problems in federated learning. Foundations and trends in machine learning 14 (1-2), p. 1–210. Cited by: §1. [13] P. Kairouz, S. Oh, and P. Viswanath (2015) The composition theorem for differential privacy. In International Conference on Machine Learning, p. 1376–1385. Cited by: Remark 7.2. [14] S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith (2011) What can we learn privately?. SIAM Journal on Computing 40 (3), p. 793–826. Cited by: §1. [15] T. Li, A. K. Sahu, A. Talwalkar, and V. Smith (2020) Federated learning: challenges, methods, and future directions. IEEE signal processing magazine 37 (3), p. 50–60. Cited by: §1. [16] Y. Lyubarskii and R. Vershynin (2010) Uncertainty principles and vector quantization. IEEE Transactions on Information Theory 56 (7), p. 3491–3501. Cited by: §2.2, Theorem 2.4. [17] P. Panter and W. Dite (1951) Quantization distortion in pulse-count modulation with nonuniform spacing of levels. Proceedings of the IRE 39 (1), p. 44–48. Cited by: §5.1. [18] S. L. Warner (1965) Randomized response: a survey technique for eliminating evasive answer bias. Journal of the American statistical association 60 (309), p. 63–69. Cited by: §1. [19] A. Zandieh, M. Daliri, M. Hadian, and V. Mirrokni (2026) Turboquant: online vector quantization with near-optimal distortion rate. In International Conference on Learning Representations, Vol. 2026, p. 56418–56439. Cited by: §1. Appendix A Curse of Dimensionality in Fixed-Geometry LDP Previous studies in geometric vector quantization, most notably vqSGD [11], have claimed that quantizing vectors to a cross-polytope and applying Randomized Response yields a variance of (d2/ϵ2)O(d^2/ε^2) for the proposed unbiased estimator. We challenge this assertion and demonstrate that this formulation actually incurs a variance of Θ(d3/ϵ2) (d^3/ε^2). This fundamental scaling issue critically impairs the performance of high-dimensional gradient embeddings in privacy-constrained settings. Formalization of vqSGD and Cross-Polytope LDP. Geometric vector quantization methods, such as vqSGD, typically map continuous vectors x∈d−1x ^d-1 to the vertices of a discrete geometric object. A canonical choice is the cross-polytope codebook, defined as: cp=±deii=1d,C_cp=\± de_i\_i=1^d, (15) where eie_i is the i-th standard basis vector in ℝdR^d. Note that the total size of this discrete domain is exactly M=2dM=2d vertices. To achieve pure ϵε-Local Differential Privacy, vqSGD applies a Flat Randomized Response (R) to a selected vertex v∈cpv _cp. The mechanism outputs a noisy vertex z∈cpz _cp such that the transition probabilities are: p p =Pr(z=v∣v)=eϵeϵ+2d−1, = (z=v v)= e^εe^ε+2d-1, (16) q q =Pr(z=c≠v∣v)=1eϵ+2d−1. = (z=c≠ v v)= 1e^ε+2d-1. (17) Using the fact that the sum of vertices is zero, the server debiases the output z using a simple scaling factor of 1p−q 1p-q and outputs the estimator x^=zp−q x= zp-q. The High-Dimensional Variance Growth. Many analyses conceptually treat the unbiasing scalar 1(p−q)2 1(p-q)^2 as an (1/ϵ2)O(1/ε^2) constant when evaluating the expected Mean Squared Error (MSE). We explicitly show that because the codebook size M=2dM=2d is intertwined with the ambient dimension, the probability gap p−qp-q shrinks as (1/d)O(1/d). Theorem A.1 (Strict Lower Bound of the Dimensionality Curse). For any input vector x∈d−1x ^d-1 quantized via the Cross-Polytope cpC_cp and perturbed via Flat Randomized Response for pure ϵε-LDP, the exact Mean Squared Error (variance) of the unbiased estimator scales asymptotically as: MSEvqSGD=Θ(d3ϵ2).MSE_vqSGD= ( d^3ε^2 ). (18) Before proceeding to the proof, we provide a remark on alternative polytopes, noting that they are subject to analogous limitations. Remark A.2 (Generalization to Alternative Polytopes). While vqSGD and related geometric approaches occasionally employ alternative discrete hulls—such as orthoplexes or random spherical simplices (where M=d+1M=d+1)—these isomorphic geometries fundamentally share an (d)O(d) vertex count. Consequently, their flat Randomized Response probability gaps inherently shrink as (1/d)O(1/d), unavoidably triggering the same Θ(d3/ϵ2) (d^3/ε^2) variance curse. Conversely, mapping to dense uniform hypercubes bypasses this geometric penalty but necessitates transmitting (d)O(d) bits per client, which fails to satisfy the fundamental requirements of federated communication compression. Proof of Theorem A.1. Let x∈d−1x ^d-1 be an input unit vector. Assume the client stochastically quantizes x to a true vertex v in the cross-polytope codebook cp=±deii=1dC_cp=\± de_i\_i=1^d such that [v∣x]=xE[v x]=x. The pure ϵε-LDP Flat Randomized Response mechanism then outputs a noisy token z∈cpz _cp given v. The server constructs the unbiased estimator x^=zp−q x= zp-q. To compute the Mean Square Error (MSE), we use the unbiasedness property of the estimator to write [x^]=v[z∣v[zp−q∣v]∣x]=[v]=xE[ x]=E_v[E_z v[ zp-q v] x]=E[v]=x, and therefore: MSEvqSGD _vqSGD =[‖x^−x‖22] =E[ x-x _2^2] =[‖x^‖22]−2[⟨x^,x⟩]+‖x‖22 =E[ x _2^2]-2E[ x,x ]+ x _2^2 =[‖x^‖22]−2⟨x,x⟩+‖x‖22 =E[ x _2^2]-2 x,x + x _2^2 =[‖x^‖22]−‖x‖22 =E[ x _2^2]- x _2^2 =[‖zp−q‖22]−1 =E [ zp-q _2^2 ]-1 =1(p−q)2[‖z‖22]−1. = 1(p-q)^2E[ z _2^2]-1. (19) By definition of the cross-polytope codebook cpC_cp, every vertex z∈cpz _cp takes the form ±dei± de_i, and so ‖z‖22=d z _2^2=d. Next, we evaluate the unbiasing scalar. The cross-polytope cpC_cp consists of exactly M=2dM=2d discrete vertices. Under Flat Randomized Response for pure ϵε-LDP over M elements, the transition probabilities are defined as: p=eϵeϵ+2d−1,andq=1eϵ+2d−1.p= e^εe^ε+2d-1, q= 1e^ε+2d-1. (20) The probability gap evaluates to: p−q=eϵ−1eϵ+2d−1.p-q= e^ε-1e^ε+2d-1. (21) Substituting this multiplier and [‖z‖22]=dE[ z _2^2]=d directly back into Equation (19): MSEvqSGD=d(p−q)2−1=d(eϵ+2d−1eϵ−1)2−1.MSE_vqSGD= d(p-q)^2-1=d ( e^ε+2d-1e^ε-1 )^2-1. (22) We expand the numerator by writing (eϵ+2d−1)2(e^ε+2d-1)^2 as ((eϵ−1)+2d)2((e^ε-1)+2d)^2: MSEvqSGD _vqSGD =d(eϵ−1)2((eϵ−1)2+4d(eϵ−1)+4d2)−1 = d(e^ε-1)^2 ((e^ε-1)^2+4d(e^ε-1)+4d^2 )-1 =d(1+4deϵ−1+4d2(eϵ−1)2)−1 =d (1+ 4de^ε-1+ 4d^2(e^ε-1)^2 )-1 =d−1+4d2eϵ−1+4d3(eϵ−1)2. =d-1+ 4d^2e^ε-1+ 4d^3(e^ε-1)^2. As d→∞d→∞, the cubic term 4d3(eϵ−1)2 4d^3(e^ε-1)^2 dominates the error expression. For any fixed privacy budget ϵ>0ε>0, the denominator (eϵ−1)2(e^ε-1)^2 is a strictly positive constant. Utilizing the Taylor series expansion for ϵ≤1ε≤ 1, we observe that eϵ−1≈ϵe^ε-1≈ε, so (eϵ−1)2=Θ(ϵ2)(e^ε-1)^2= (ε^2). Therefore, the variance scales as: MSEvqSGD=Θ(d3ϵ2).MSE_vqSGD= ( d^3ε^2 ). (23) This completes the proof. ∎ Appendix B Proofs for the SSTQ Mechanism This appendix provides the formal mathematical proofs for the theoretical guarantees of the Subsampled Stochastic TurboQuant (SSTQ) architecture with Flat randomization response introduced in Section 3. We first prove that SSTQ satisfies pure ϵε-Local Differential Privacy and guarantees an unbiased gradient estimator. We then establish a bound on the conditional variance of the 1D randomized response mechanism, by which we prove that SSTQ achieves the information-theoretic optimal (d/ϵ2)O(d/ε^2) Mean Squared Error. B.1 Proof of Strict ϵε-LDP and Unbiasedness Proof of Theorem 3.1. We establish the privacy and utility guarantees in two distinct parts. Part 1: Strict pure ϵε-LDP. The SSTQ client encoding algorithm transmits a tuple (j,z)(j,z), where j is the subsampled coordinate index and z∈Γz∈ is the noisy stochastically quantized token. First, the subsampling index j∼Unif(1,N)j (1,N) is generated uniformly at random, totally independent of the client’s private data x. Because the distribution of j does not depend on x, its transmission consumes exactly ϵ=0ε=0 privacy budget. Second, the stochastic quantization step maps the continuous Kashin coordinate yjy_j into a finite, discrete codebook Γ=c1,…,cM =\c_1,…,c_M\ bounded in [−B,B][-B,B], yielding a true token v∈Γv∈ . This step is a local data-independent mapping applied to the already bounded coordinate. Third, the algorithm applies Flat Randomized Response over the constant domain M=2bM=2^b to produce the noisy token z. By the definition of the mechanism, the transition probabilities are p=eϵeϵ+M−1p= e^εe^ε+M-1 if z=vz=v, and q=1eϵ+M−1q= 1e^ε+M-1 if z≠vz≠ v. For any two possible true tokens v,v′∈Γv,v ∈ and any output z∈Γz∈ , the maximum probability ratio is strictly bounded by: Pr(z∣v)Pr(z∣v′)≤pq=eϵeϵ+M−11eϵ+M−1=eϵ. (z v) (z v )≤ pq= e^εe^ε+M-1 1e^ε+M-1=e^ε. (24) Because the maximum probability ratio between any two inputs is exactly eϵe^ε, the mechanism satisfies pure ϵε-LDP on the client device, without requiring a trusted shuffler or shared public coin. Part 2: Unbiasedness. We trace the expectations backwards from the server’s estimator x x to the true vector x. First, the server receives z and constructs the 1D debiased scalar y~j=zp−q y_j= zp-q. Given the zero-mean codebook constraint (∑i=1Mci=0 _i=1^Mc_i=0), the expected value of z given the true token v is: [z∣v]=pv+q∑ci≠vci=pv+q(∑i=1Mci−v)=pv+q(0−v)=(p−q)v.E[z v]=pv+q _c_i≠ vc_i=pv+q ( _i=1^Mc_i-v )=pv+q(0-v)=(p-q)v. (25) Thus, the debiased scalar yields [y~j∣v]=[zp−q|v]=vE[ y_j v]=E [ zp-q\; |\;v ]=v. Second, the true token v is generated via exact linear stochastic interpolation of the continuous coordinate yj∈[ck,ck+1]y_j∈[c_k,c_k+1]. The expected value is: [v∣yj]=ck+1Pr(v=ck+1)+ckPr(v=ck)=ck+1(yj−ckck+1−ck)+ck(ck+1−yjck+1−ck)=yj.E[v y_j]=c_k+1 (v=c_k+1)+c_k (v=c_k)=c_k+1 ( y_j-c_kc_k+1-c_k )+c_k ( c_k+1-y_jc_k+1-c_k )=y_j. (26) Third, taking the expectation over the uniform oblivious subsampling index j∼Unif(1,N)j (1,N), the server’s reconstructed 1-sparse vector y~=N⋅y~j⋅ej y=N· y_j· e_j yields: j[y~]=∑j=1NPr(j)(N⋅yj⋅ej)=∑j=1N1N(N⋅yj⋅ej)=∑j=1Nyjej=y.E_j[ y]= _j=1^N (j)(N· y_j· e_j)= _j=1^N 1N(N· y_j· e_j)= _j=1^Ny_je_j=y. (27) Finally, the server projects y~ y back into the ambient space via the Equal-Norm Tight Frame U. Because the Kashin representation guarantees exact reconstruction dNUTy=x dNU^Ty=x (Theorem 2.4), applying linearity of expectation yields: [x^]=[dNUTy~]=dNUT[y~]=dNUTy=x.E[ x]=E [ dNU^T y ]= dNU^TE[ y]= dNU^Ty=x. (28) The global estimator is therefore strictly unbiased. ∎ B.2 MSE bound for SSTQ (Flat-R) We begin by proving Lemma 2.3 on ENTF trace property. Proof of Lemma 2.3. Consider the trace of the matrix UUT∈ℝN×NUU^T ^N× N. By the cyclic permutation property of the trace operator: Tr(UUT)=Tr(UTU).Tr(U^T)=Tr(U^TU). (29) We are given UTU=NdIdU^TU= NdI_d. Therefore: Tr(UTU)=Tr(NdId)=Nd×d=N.Tr(U^TU)=Tr ( NdI_d )= Nd× d=N. (30) The diagonal elements of the outer product UUTUU^T are explicitly the squared Euclidean norms of the rows of U. Thus, Tr(UUT)=∑j=1N‖uj‖22Tr(U^T)= _j=1^N u_j _2^2. Since the frame is strictly Equal-Norm, all ‖uj‖22 u_j _2^2 are identical. Therefore, N⋅‖uj‖22=N· u_j _2^2=N, which strictly implies ‖uj‖2=1 u_j _2=1. ∎ To formalize how SSTQ addresses the curse of dimensionality, we first bound the conditional variance of the 1D randomized response mechanism operating over the bounded Kashin coefficients. Lemma B.1. For any stochastically quantized client token v∈Γv∈ rigorously bounded by |v|≤KN |v |≤ K N, the variance of the server’s debiased estimator satisfies: [y~j2∣v]≤K2/N(p−q)2.E[ y_j^2 v]≤ K^2/N(p-q)^2. (31) Because the discrete domain size M over which the randomized response mechanism operates is now defined by the constant payload bit-width (M=2bM=2^b), the unbiasing probability gap (p−q)(p-q) is structurally decoupled from the high-dimensional geometry. This decoupling enables to bypass the curse of dimensionality. Proof of Lemma B.1. We compute the conditional variance (or uncentered second moment, given the zero mean) of the debiased estimator y~j=zp−q y_j= zp-q given the true quantized token v∈Γv∈ . Since [y~j∣v]=vE[ y_j v]=v, the variance is Var(y~j∣v)=[y~j2∣v]−v2Var( y_j v)=E[ y_j^2 v]-v^2. However, we are primarily interested in bounding the uncentered second moment [y~j2∣v]E[ y_j^2 v]. The second moment of the Flat Randomized Response output z is: [z2∣v]=pv2+q∑ci≠vci2=(p−q)v2+q∑i=1Mci2.E[z^2 v]=pv^2+q _c_i≠ vc_i^2=(p-q)v^2+q _i=1^Mc_i^2. (32) Dividing by the unbiasing scalar squared (p−q)2(p-q)^2 gives: [y~j2∣v]=[(zp−q)2|v]=1p−qv2+q(p−q)2∑i=1Mci2.E[ y_j^2 v]=E [ ( zp-q )^2\; |\;v ]= 1p-qv^2+ q(p-q)^2 _i=1^Mc_i^2. (33) By the Kashin bounding property, every centroid in the codebook ci∈Γc_i∈ and the true token v are bounded in the range [−B,B][-B,B], where B=KNB= K N. Therefore, ci2≤K2Nc_i^2≤ K^2N and v2≤K2Nv^2≤ K^2N. Substituting these limits, we arrive at: [y~j2∣v] [ y_j^2 v] ≤K2/Np−q+q∑i=1M(K2/N)(p−q)2 ≤ K^2/Np-q+ q _i=1^M(K^2/N)(p-q)^2 =K2/Np−q+qM(K2/N)(p−q)2 = K^2/Np-q+ qM(K^2/N)(p-q)^2 =K2/N(p−q)2[(p−q)+qM]. = K^2/N(p-q)^2 [(p-q)+qM ]. (34) In addition, the randomization probabilities sum to one: p+(M−1)q=1p+(M-1)q=1, which along with the previous equation yields the claim. ∎ We next proceed to bound the MSE achieved by SSTQ (Flat-R variant). Proof of Theorem 3.2. We evaluate the expected Mean Squared Error (total variance) of the full d-dimensional reconstructed gradient x x. Let U∈ℝN×dU ^N× d be the Equal-Norm Tight Frame where UTU=NdIdU^TU= NdI_d. The server reconstructs the target gradient via the projection x^=dNUTy~ x= dNU^T y. The 1-sparse vector is y~=Ny~jej y=N y_je_j. Thus, the projection evaluates to: x^=dNUT(Ny~jej)=dy~jUTej=dy~juj, x= dNU^T(N y_je_j)=d y_jU^Te_j=d y_ju_j, (35) where ujTu_j^T is the j-th row of the frame matrix U. We calculate the expected squared ℓ2 _2 norm of the estimator x x: [‖x^‖22]=[‖dy~juj‖22]=d2[y~j2‖uj‖22].E[ x _2^2]=E [ d y_ju_j _2^2 ]=d^2E[ y_j^2 u_j _2^2]. (36) By Lemma 2.3, an ENTF properly normalized such that UTU=NdIdU^TU= NdI_d forces the Euclidean norm of every single row to be exactly unity: ‖uj‖22=1 u_j _2^2=1 for all j∈1,…,Nj∈\1,…,N\. Therefore: [‖x^‖22]=d2[y~j2].E[ x _2^2]=d^2E[ y_j^2]. (37) By the law of total expectation over the uniform subsampling index j and the true token v: [y~j2]=1N∑j=1Nv[[y~j2∣v]|j].E[ y_j^2]= 1N _j=1^NE_v [E[ y_j^2 v]\; |\;j ]. (38) Applying the upper bound from Lemma B.1), we get: [y~j2]≤1N∑j=1N(K2/N(p−q)2)=K2/N(p−q)2.E[ y_j^2]≤ 1N _j=1^N ( K^2/N(p-q)^2 )= K^2/N(p-q)^2. (39) Because the estimator is unbiased ([x^]=xE[ x]=x) and x∈d−1x ^d-1, the MSE simplifies as: MSESSTQ _SSTQ =[‖x^−x‖22] =E[ x-x _2^2] =[‖x^‖22]−2[⟨x^,x⟩]+[‖x‖22] =E[ x _2^2]-2E[ x,x ]+E[ x _2^2] =[‖x^‖22]−2‖x‖22+‖x‖22 =E[ x _2^2]-2 x _2^2+ x _2^2 =[‖x^‖22]−1. =E[ x _2^2]-1. (40) Substituting the bound from Equation (37): MSESSTQ≤d2(K2/N(p−q)2)−1<d2K2N(p−q)2.MSE_SSTQ≤ d^2 ( K^2/N(p-q)^2 )-1< d^2K^2N(p-q)^2. (41) Because the Kashin representation fundamentally requires an overcomplete frame, the redundancy ratio is an absolute constant strictly greater than 1 (e.g., N=⌈1.2d⌉N= 1.2d ). Thus, N=Θ(d)N= (d), and we can rewrite the bound as: MSESSTQ<d2K2d(N/d)(p−q)2=(dK2(p−q)2).MSE_SSTQ< d^2K^2d(N/d)(p-q)^2=O ( dK^2(p-q)^2 ). (42) Finally, we evaluate the unbiasing scalar. Because the algorithm operates over a 1D scalar codebook, the codebook size M=2bM=2^b is an (1)O(1) constant completely independent of d. The probability gap (p−q)(p-q) for Flat Randomized Response is: p−q=eϵ−1eϵ+2b−1.p-q= e^ε-1e^ε+2^b-1. (43) Therefore, 1(p−q)2=(1+2beϵ−1)2<1+2b+1ϵ+4bϵ2≤1+4b(1ϵ+1ϵ2)≤1+2⋅4bϵ∧ϵ2. 1(p-q)^2= (1+ 2^be^ε-1 )^2<1+ 2^b+1ε+ 4^bε^2≤ 1+4^b ( 1ε+ 1ε^2 )≤ 1+ 2· 4^bε ε^2. Using this bound into (42), we get MSESSTQ=(d(1+4bϵ∧ϵ2)),MSE_SSTQ=O (d (1+ 4^bε ε^2 ) )\,, which completes the proof. ∎ Appendix C Proofs for Surrogate Codebook Optimization This appendix provides the analytical derivations and formal proofs for the surrogate continuous codebook optimization framework (ℒSSTQL_SSTQ) introduced in Section 4. C.1 Derivation of the Surrogate Minimax Objective We start by deriving the exact closed-form relation between the expected Mean Squared Error of the Local Differential Privacy mechanism and the continuous codebook geometry. Derivation of Equation (5) and Definition 4.1. Let y∈[−B,B]y∈[-B,B] be a bounded Kashin coordinate, and assume it lies in the interval [ck,ck+1][c_k,c_k+1] between two adjacent centroids in the codebook Γ . As defined in Algorithm 1, y is stochastically quantized to a true token v∈ck,ck+1v∈\c_k,c_k+1\ via exact linear interpolation. The conditional variance of this stochastic interpolation step is: Var(v∣y) (v y) =[v2∣y]−y2 =E[v^2 y]-y^2 =ck+12(y−ckck+1−ck)+ck2(ck+1−yck+1−ck)−y2 =c_k+1^2 ( y-c_kc_k+1-c_k )+c_k^2 ( c_k+1-yc_k+1-c_k )-y^2 =(y−ck)(ck+1−y). =(y-c_k)(c_k+1-y). (44) Next, the Flat Randomized Response mechanism maps the true token v to a noisy token z∈Γz∈ . The server computes the debiased estimator y~j=zp−q y_j= zp-q. Because Flat R operates over the M centroids in Γ , its second moment evaluates to [z2∣v]=(p−q)v2+q∑i=1Mci2E[z^2 v]=(p-q)v^2+q _i=1^Mc_i^2. Dividing by (p−q)2(p-q)^2, we obtain: [y~j2∣v]=1p−qv2+q(p−q)2∑i=1Mci2.E[ y_j^2 v]= 1p-qv^2+ q(p-q)^2 _i=1^Mc_i^2. (45) Since [y~j∣v]=vE[ y_j v]=v, the conditional variance is: Var(y~j∣v)=[y~j2∣v]−v2=(1p−q−1)v2+q(p−q)2∑i=1Mci2.Var( y_j v)=E[ y_j^2 v]-v^2= ( 1p-q-1 )v^2+ q(p-q)^2 _i=1^Mc_i^2. (46) By invoking the Law of Total Variance over the two cascaded stochastic mechanisms (quantization followed by LDP), the variance of the estimator given the continuous coordinate y is: Var(y~j∣y) ( y_j y) =v[Var(y~j∣v)∣y]+Varv([y~j∣v]∣y) =E_v[Var( y_j v) y]+Var_v(E[ y_j v] y) =v[(1p−q−1)v2+q(p−q)2∑i=1Mci2|y]+Var(v∣y). =E_v [ ( 1p-q-1 )v^2+ q(p-q)^2 _i=1^Mc_i^2\ |\ y ]+Var(v y). (47) Substituting v[v2∣y]=Var(v∣y)+y2E_v[v^2 y]=Var(v y)+y^2, we get: Var(y~j∣y) ( y_j y) =(1p−q−1)(Var(v∣y)+y2)+q(p−q)2∑i=1Mci2+Var(v∣y) = ( 1p-q-1 ) (Var(v y)+y^2 )+ q(p-q)^2 _i=1^Mc_i^2+Var(v y) =1p−qVar(v∣y)+(1p−q−1)y2+q(p−q)2∑i=1Mci2. = 1p-qVar(v y)+ ( 1p-q-1 )y^2+ q(p-q)^2 _i=1^Mc_i^2. (48) Because the estimator is locally unbiased ([y~j∣y]=yE[ y_j y]=y), we have: [y~j2∣y]=Var(y~j∣y)+y2=1p−qVar(v∣y)+1p−qy2+q(p−q)2∑i=1Mci2.E[ y_j^2 y]=Var( y_j y)+y^2= 1p-qVar(v y)+ 1p-qy^2+ q(p-q)^2 _i=1^Mc_i^2. (49) Taking the unconditional expectation over an arbitrary continuous data density Y∼fY(y)Y f_Y(y), factoring out 1p−q 1p-q, and applying the Flat R probability identity qp−q=1eϵ−1 qp-q= 1e^ε-1, we derive the surrogate loss formulation ℒSSTQL_SSTQ: Y[y~j2] _Y[ y_j^2] =1p−q[Y[Var(v∣y)]+qp−q∑i=1Mci2]+1p−qY[y2] = 1p-q [E_Y[Var(v y)]+ qp-q _i=1^Mc_i^2 ]+ 1p-qE_Y[y^2] =1p−q[Y[Var(v∣y)]+1eϵ−1∑i=1Mci2]⏟=ℒSSTQ(Γ)+1p−qY[y2]. = 1p-q [E_Y[Var(v y)]+ 1e^ε-1 _i=1^Mc_i^2 ]_=L_SSTQ( )+ 1p-qE_Y[y^2]. (50) Integrating Y[Var(v∣y)]E_Y[Var(v y)] over the density fY(y)f_Y(y) results in the loss given by Definition 4.1. ∎ C.2 Proof of Global Convexity Proof of Theorem 4.2. We decompose the objective function into the spatial quantization penalty F(Γ)F( ) and the variance regularization penalty G(Γ)G( ): ℒSSTQ(Γ)=F(Γ)+G(Γ)L_SSTQ( )=F( )+G( ) where F(Γ)=∑k=1M−1(ck+1−ck)312B,andG(Γ)=λ∑i=1Mci2F( )= _k=1^M-1 (c_k+1-c_k)^312B, G( )=λ _i=1^Mc_i^2 with the privacy-dependent scalar λ=1eϵ−1λ= 1e^ε-1. For any valid privacy budget ϵ>0ε>0, the parameter λ is strictly positive. We show that F is convex and G is strictly convex and hence the loss is a strictly convex function of Γ . Let D∈ℝ(M−1)×MD ^(M-1)× M be the finite difference matrix defined such that the k-th element of the matrix-vector product is (DΓ)k=ck+1−ck(D )_k=c_k+1-c_k. The feasible set D corresponds to the region where DΓ≥0D ≥ 0 element-wise. We define the scalar function ϕ(x)=x312Bφ(x)= x^312B. For x≥0x≥ 0, its second derivative is ϕ′(x)=x2B≥0φ (x)= x2B≥ 0. The term F(Γ)F( ) can be written as F(Γ)=∑k=1M−1ϕ((DΓ)k)F( )= _k=1^M-1φ((D )_k). By the chain rule for vectors, the Hessian matrix of F(Γ)F( ) is given by: ∇2F(Γ)=D⊤diag(ϕ′((DΓ)1),…,ϕ′((DΓ)M−1))D∇^2F( )=D diag (φ ((D )_1),…,φ ((D )_M-1) )D Because (DΓ)k≥0(D )_k≥ 0 for all Γ∈ , the diagonal matrix contains solely non-negative entries. Consequently, for any vector v∈ℝMv ^M, the quadratic form v⊤∇2F(Γ)v≥0v ∇^2F( )v≥ 0. This establishes that the Hessian ∇2F(Γ)∇^2F( ) is positive semi-definite (∇2F(Γ)⪰0∇^2F( ) 0), and thus F(Γ)F( ) is convex on D. The regularization term evaluates to a scaled squared Euclidean norm, G(Γ)=λ‖Γ‖22G( )=λ\| \|_2^2. The Hessian matrix of this canonical quadratic form is: ∇2G(Γ)=2λIM∇^2G( )=2λ I_M where IMI_M is the M×M× M identity matrix. Because λ>0λ>0, the matrix 2λIM2λ I_M is strictly positive definite (∇2G(Γ)≻0∇^2G( ) 0). This establishes that G(Γ)G( ) is strongly convex on ℝMR^M. The Hessian of the total objective function is the sum of the constituent Hessians: ∇2ℒSSTQ(Γ)=∇2F(Γ)+∇2G(Γ)∇^2L_SSTQ( )=∇^2F( )+∇^2G( ) The sum of a positive semi-definite matrix and a strictly positive definite matrix is strictly positive definite. Thus, ∇2ℒSSTQ(Γ)⪰2λIM≻0∇^2L_SSTQ( ) 2λ I_M 0 for all Γ∈ . This rigorously guarantees that ℒSSTQ(Γ)L_SSTQ( ) is strictly globally convex (and formally, strongly convex) over the feasible domain. We next prove the existence of the global minimizer via coercivity. A continuous function defined on a closed set is guaranteed to attain a global minimum if it is coercive, meaning the function value diverges to infinity as the norm of the input diverges (lim‖Γ‖2→∞ℒSSTQ(Γ)=∞ _\| \|_2→∞L_SSTQ( )=∞). For any Γ∈ , the condition ck+1−ck≥0c_k+1-c_k≥ 0 guarantees that F(Γ)≥0F( )≥ 0. Consequently, the total loss function is strictly bounded from below by its quadratic regularization term: ℒSSTQ(Γ)≥G(Γ)=λ‖Γ‖22L_SSTQ( )≥ G( )=λ\| \|_2^2 Taking the limit as the norm of the codebook grows yields: lim‖Γ‖2→∞ℒSSTQ(Γ)≥lim‖Γ‖2→∞λ‖Γ‖22=∞ _\| \|_2→∞L_SSTQ( )≥ _\| \|_2→∞λ\| \|_2^2=∞ The strong coercivity of the objective function on the closed convex set D ensures that the infimum is finite and attained. Thus, there exists at least one global minimizer Γ∗∈ ^* . Note that if explicit boundary constraints such as c1=−Bc_1=-B and cM=Bc_M=B are enforced, the monotonic ordering requirement confines all coordinates strictly to the interval [−B,B][-B,B]. The feasible set D then becomes a compact subset of ℝMR^M, and existence is directly guaranteed by the Weierstrass extreme value theorem without requiring the coercivity argument. The uniqueness of global minimizer follows from the strict convexity (if there are two distinct global minimizers, their average will attain a smaller function value which is a contradiction.) ∎ C.3 Improved MSE Bound Using Optimized Codebook Proof of Theorem 4.3. By recalling Equations (40) and (37), we have MSESSTQ=[‖x^‖22−1]<[‖x^‖22]=d2[y~j2]. _SSTQ=E[ x _2^2-1]<E[ x _2^2]=d^2E[ y_j^2]\,. (51) Next by combining (6) and (5) we get MSESSTQ≤d2p−q[∑k=1M−1∫ckck+1(y−ck)(ck+1−y)fY(y)y+1eϵ−1∑i=1Mci2+∫−BBy2fY(y)y] _SSTQ≤ d^2p-q [ _k=1^M-1 _c_k^c_k+1(y-c_k)(c_k+1-y)f_Y(y)\,dy\;\;+\;\; 1e^ε-1 _i=1^Mc_i^2+ _-B^By^2f_Y(y)\,dy ] (52) We denote the right-hand side (without the scaling factor d2p−q d^2p-q) by U(Γ)U( ) as a function of the codebook Γ , and decompose it as the data-dependent part I(Γ)I( ) and the regularization part G(Γ)G( ) given by I(Γ) I( ) :=∑k=1M−1∫ckck+1[(y−ck)(ck+1−y)+y2]fY(y)y := _k=1^M-1 _c_k^c_k+1[(y-c_k)(c_k+1-y)+y^2]f_Y(y)\,dy (53) G(Γ) G( ) :=λ∑i=1Mci2, :=λ _i=1^Mc_i^2\,, (54) with λ=(eϵ−1)−1λ=(e^ε-1)^-1, and so U(Γ)=I(Γ)+G(Γ)U( )=I( )+G( ). We next upper bound I(Γ)I( ). Define the polynomial within the brackets as hk(y)h_k(y) for y∈[ck,ck+1]y∈[c_k,c_k+1]: hk(y)=(y−ck)(ck+1−y)+y2h_k(y)=(y-c_k)(c_k+1-y)+y^2 Expanding hk(y)h_k(y) yields: hk(y)=yck+1−y2−ckck+1+cky+y2=(ck+ck+1)y−ckck+1h_k(y)=yc_k+1-y^2-c_kc_k+1+c_ky+y^2=(c_k+c_k+1)y-c_kc_k+1 The function hk(y)h_k(y) is an affine function with respect to y. By the properties of affine functions on closed intervals, hk(y)h_k(y) attains its maximum at one of the boundaries of the interval [ck,ck+1][c_k,c_k+1]. Evaluating hk(y)h_k(y) at the endpoints gives: hk(ck)=(ck+ck+1)ck−ckck+1=ck2h_k(c_k)=(c_k+c_k+1)c_k-c_kc_k+1=c_k^2 hk(ck+1)=(ck+ck+1)ck+1−ckck+1=ck+12h_k(c_k+1)=(c_k+c_k+1)c_k+1-c_kc_k+1=c_k+1^2 Thus, for all y∈[ck,ck+1]y∈[c_k,c_k+1], the function is bounded by: hk(y)≤max(ck2,ck+12)h_k(y)≤ (c_k^2,c_k+1^2) Because the codebook elements are constrained to the interval [−B,B][-B,B], it follows that ci2≤B2c_i^2≤ B^2 for all i∈1,…,Mi∈\1,…,M\. Therefore, hk(y)≤B2h_k(y)≤ B^2 uniformly for all k∈1,…,M−1k∈\1,…,M-1\ and y∈[ck,ck+1]y∈[c_k,c_k+1]. Applying this pointwise upper bound to the integrals results in: I(Γ)≤∑k=1M−1∫ckck+1B2fY(y)y=B2∫−BBfY(y)yI( )≤ _k=1^M-1 _c_k^c_k+1B^2f_Y(y)\,dy=B^2 _-B^Bf_Y(y)\,dy Because fY(y)f_Y(y) is a valid probability density function supported on [−B,B][-B,B], its integral over this domain evaluates to 11. Hence, I(Γ)≤B2I( )≤ B^2. This bound is independent of the distribution fY(y)f_Y(y) and holds for any feasible codebook, including Γ∗ ^*. We next upper bound the regularization term G(Γ∗)G( ^*). To constrain G(Γ∗)G( ^*), we evaluate J(Γ)=F(Γ)+G(Γ)J( )=F( )+G( ) where F(Γ)=∑k=1M−1Δk312BF( )= _k=1^M-1 _k^312B. By the continuous global optimality of Γ∗ ^*, J(Γ∗)≤J(Γ~)J( ^*)≤ J( ) for any valid proxy codebook sequence. For an integer parameter 1≤m≤⌊M−12⌋1≤ m≤ M-12 , define Γ~m∈ _m to span exactly m contiguous gap intervals of size B/mB/m mapping respectively from −B-B and B, collapsing the remaining M−2m−1M-2m-1 indices symmetrically to 0. This sequence computes strictly to F(Γ~m)=2m(B/m)312B=B26m2F( _m)=2m (B/m)^312B= B^26m^2 and G(Γ~m)=2λ∑j=1m(jBm)2=λB2(m+1)(2m+1)3mG( _m)=2λ _j=1^m ( jBm )^2=λ B^2 (m+1)(2m+1)3m. Applying Jensen’s inequality to the objective yields a strict minimal floor F(Γ∗)≥2B23(M−1)2F( ^*)≥ 2B^23(M-1)^2. Subtracting this extracts the uniform limit: G(Γ∗)≤F(Γ~m)+G(Γ~m)−F(Γ∗)≤B26m2+B2(m+1)(2m+1)3m(eϵ−1)−2B23(M−1)2G( ^*)≤ F( _m)+G( _m)-F( ^*)≤ B^26m^2+ B^2(m+1)(2m+1)3m(e^ε-1)- 2B^23(M-1)^2 Combining the bounds on I(Γ∗)I( ^*) and G(Γ∗)G( ^*) we obtain U(Γ∗)≤B2+min1≤m≤⌊M−12⌋B2(16m2+(m+1)(2m+1)3m(eϵ−1))−2B23(M−1)2U( ^*)≤ B^2+ _1≤ m≤ M-12 B^2 ( 16m^2+ (m+1)(2m+1)3m(e^ε-1) )- 2B^23(M-1)^2 To quantify the term with minimum over m on the right-hand side, consider the continuous relaxation of the objective function, defined approximately as g(m)≈B2(16m2+2λm3)g(m)≈ B^2 ( 16m^2+ 2λ m3 ). Setting the first derivative to zero provides the unconstrained optimum m∗≈(2λ)−1/3m^*≈(2λ)^-1/3. We proceed by setting m=(2λ)−1/3∨1m=(2λ)^-1/3 1, since we should have m≥1m≥ 1. In addition, by our assumption, M>(4(eϵ−1))1/3+1M>(4(e^ε-1))^1/3+1, which implies that M−12≥m M-12≥ m, and so this is a valid choice. Substituting m back into the objective yields the asymptotic behavior: 16m2+(m+1)(2m+1)3m(eϵ−1)=(λ2/3∨λ)=(ϵ−1∨ϵ−2/3), 16m^2+ (m+1)(2m+1)3m(e^ε-1)=O(λ^2/3 λ)=O(ε^-1 ε^-2/3)\,, using the fact that λ<1/ϵλ<1/ε. This also implies that 2B23(M−1)2=(λ2/3B2)=(B2ϵ−2/3) 2B^23(M-1)^2=O(λ^2/3B^2)=O(B^2ε^-2/3). Hence, U(Γ∗)=(B2(1+ϵ−1+ϵ−2/3))=(B2(1+ϵ−1)).U( ^*)=O(B^2(1+ε^-1+ε^-2/3))=O(B^2(1+ε^-1)). Consequently, MSESSTQ=(d2p−qB2(1+ϵ−1)))=(d(1+Mϵ−1+Mϵ−2)),MSE_SSTQ=O ( d^2p-qB^2(1+ε^-1)) )=O (d(1+Mε^-1+Mε^-2) )\,, since B=O(d−1/2)B=O(d^-1/2) and p−q=1/(1+Mλ)p-q=1/(1+Mλ), and so 1/(p−q)<1+Mϵ−11/(p-q)<1+Mε^-1. This completes the proof. ∎ Appendix D Proofs for the Metric-Aware Laplace Mechanism This appendix provides the formal mathematical proofs for the Metric-Aware Laplace mechanism introduced in Section 5. The mechanism operates in two stages: (1) continuous Laplace sampling, and (2) nearest-codeword quantization. We first prove that the mechanism satisfies pure ϵε-LDP via the post-processing theorem. We then formulate the surrogate objective ℒSSTQMAL_SSTQ^MA and establish upper bounds on the variance and the bias of the estimator under identity decoding. The global bias is entirely independent of the ambient dimension. D.1 Proof of ϵε-LDP Proof of Theorem 5.1. The proof follows from the post-processing theorem of differential privacy. The mechanism consists of two stages: Stage 1 (Continuous Laplace Sampling). Given the true token v=ckv=c_k, the mechanism draws T from a truncated Laplace distribution on [−B,B][-B,B] with density fT|v=ck(t)=1Zkexp(−ϵ|t−ck|2Δ)f_T|v=c_k(t)= 1Z_k (- ε|t-c_k|2 ) for t∈[−B,B]t∈[-B,B], where Δ=2B =2B. This continuous mechanism satisfies ϵε-LDP: for any two tokens ck,cm∈Γc_k,c_m∈ and any measurable set S⊆[−B,B]S [-B,B], Pr(T∈S∣v=ck)Pr(T∈S∣v=cm)=∫S1Zke−ϵ|t−ck|2Δt∫S1Zme−ϵ|t−cm|2Δt. (T∈ S v=c_k) (T∈ S v=c_m)= _S 1Z_ke^- ε|t-c_k|2 \,dt _S 1Z_me^- ε|t-c_m|2 \,dt. (55) For the numerator, using the triangle inequality |t−ck|≥|t−cm|−|cm−ck||t-c_k|≥|t-c_m|-|c_m-c_k|: e−ϵ|t−ck|2Δ≤eϵ|cm−ck|2Δ⋅e−ϵ|t−cm|2Δ. e^- ε|t-c_k|2 ≤ e ε|c_m-c_k|2 · e^- ε|t-c_m|2 . (56) Integrating over S yields ∫S1Zke−ϵ|t−ck|2Δt≤ZmZkeϵ|cm−ck|2Δ∫S1Zme−ϵ|t−cm|2Δt _S 1Z_ke^- ε|t-c_k|2 dt≤ Z_mZ_ke ε|c_m-c_k|2 _S 1Z_me^- ε|t-c_m|2 dt. An analogous bound shows ZmZk≤eϵ|cm−ck|2Δ Z_mZ_k≤ e ε|c_m-c_k|2 . Multiplying yields: Pr(T∈S∣v=ck)Pr(T∈S∣v=cm)≤exp(ϵ|ck−cm|Δ)≤eϵ, (T∈ S v=c_k) (T∈ S v=c_m)≤ ( ε|c_k-c_m| )≤ e^ε, (57) where the final step uses |ck−cm|≤2B=Δ|c_k-c_m|≤ 2B= . Stage 2 (Nearest-Codeword Quantization). The output z=argminci∈Γ|T−ci|z= _c_i∈ |T-c_i| is a deterministic function of T. By the post-processing theorem of differential privacy, applying a deterministic function to the output of an ϵε-LDP mechanism preserves ϵε-LDP. Therefore, the composed mechanism satisfies pure ϵε-LDP for any codebook geometry. ∎ D.2 MSE and Bias Bounds under Identity Decoding D.2.1 Derivation of Surrogate Loss Objective for the Metric-Aware Mechanism To optimize the codebook Γ=c1,…,cM =\c_1,…,c_M\ under the Metric-Aware Laplace mechanism, the loss objective must evaluate the expected mean squared error. We define ℒMA-SSTQ∗(Γ):=[(y−z)2], ^*_MA-SSTQ( ):=E[(y-z)^2], (58) utilizing identity decoding. We first recall the pipeline. Let y denote the continuous coordinate drawn from the density fY(y)f_Y(y). The mechanism pipeline operates as follows: 1. Stochastic Quantization: The continuous coordinate y∈[ck,ck+1]y∈[c_k,c_k+1] is stochastically assigned to a token v∈ck,ck+1v∈\c_k,c_k+1\ to enforce the unbiasedness property [v|y]=yE[v|y]=y. The transition probabilities are pk(y)=ck+1−yck+1−ckp_k(y)= c_k+1-yc_k+1-c_k and pk+1(y)=y−ckck+1−ckp_k+1(y)= y-c_kc_k+1-c_k. 2. Metric-Aware Privatization: Given the token v=cjv=c_j, the mechanism draws a continuous sample T from the truncated Laplace distribution fT|v=cj(t)=1Zjexp(−ϵ|t−cj|4B)f_T|v=c_j(t)= 1Z_j (- ε|t-c_j|4B ) for t∈[−B,B]t∈[-B,B], and outputs the nearest codeword z=argminci∈Γ|T−ci|z= _c_i∈ |T-c_i|. The effective transition probability Pi|j=Pr[z=ci∣v=cj]P_i|j= [z=c_i v=c_j] is given by Eq. 10. 3. Identity Decoding: The decoder assigns the reconstructed coordinate directly as y^=z y=z. By the Law of Total Expectation, the conditional error decomposes as: [(y−z)2∣y]=v|y[z|v[(y−z)2]]E[(y-z)^2 y]=E_v|y [E_z|v[(y-z)^2] ] For a fixed intermediate token v=cjv=c_j, we define two geometric statistics representing the mechanism’s behavior: • Expected Structural Bias: μj=[z∣v=cj] _j=E[z v=c_j], the expected output codeword under the effective transition probabilities (10). • Localized Mechanism Variance: Vj=[(z−cj)2∣v=cj]V_j=E[(z-c_j)^2 v=c_j]. Expanding the inner expectation explicitly around cjc_j gives: z|v[(y−cj+cj−z)2]=(y−cj)2+2(y−cj)(cj−μj)+VjE_z|v[(y-c_j+c_j-z)^2]=(y-c_j)^2+2(y-c_j)(c_j- _j)+V_j Evaluating the outer expectation over the token support v∈ck,ck+1v∈\c_k,c_k+1\ strictly partitions the polynomial into three distinct components: 1. Base Quantization Error: Applying the probabilities yields the standard error polynomial: pk(y)(y−ck)2+pk+1(y)(y−ck+1)2=ck+1−yck+1−ck(y−ck)2+y−ckck+1−ck(y−ck+1)2p_k(y)(y-c_k)^2+p_k+1(y)(y-c_k+1)^2= c_k+1-yc_k+1-c_k(y-c_k)^2+ y-c_kc_k+1-c_k(y-c_k+1)^2 Factoring out the term (y−ck)(ck+1−y)(y-c_k)(c_k+1-y) leaves: (y−ck)(ck+1−y)ck+1−ck[(y−ck)+(ck+1−y)]=(y−ck)(ck+1−y) (y-c_k)(c_k+1-y)c_k+1-c_k [(y-c_k)+(c_k+1-y) ]=(y-c_k)(c_k+1-y) 2. Cross-Correlation Bias Term: The expected cross-term captures the interaction between the quantization interval bounds and the mechanism’s structural bias: 2pk(y)(y−ck)(ck−μk)+2pk+1(y)(y−ck+1)(ck+1−μk+1)2p_k(y)(y-c_k)(c_k- _k)+2p_k+1(y)(y-c_k+1)(c_k+1- _k+1) Applying the sign substitution y−ck+1=−(ck+1−y)y-c_k+1=-(c_k+1-y) and replacing pk(y),pk+1(y)p_k(y),p_k+1(y) transforms this to: 2ck+1−yck+1−ck(y−ck)(ck−μk)−2y−ckck+1−ck(ck+1−y)(ck+1−μk+1)2 c_k+1-yc_k+1-c_k(y-c_k)(c_k- _k)-2 y-c_kc_k+1-c_k(c_k+1-y)(c_k+1- _k+1) Factoring out the data-dependent polynomial provides the algebraic simplification: 2(y−ck)(ck+1−y)ck+1−ck[ck−μk−(ck+1−μk+1)]=2(y−ck)(ck+1−y)(μk+1−μkck+1−ck−1)2 (y-c_k)(c_k+1-y)c_k+1-c_k [c_k- _k-(c_k+1- _k+1) ]=2(y-c_k)(c_k+1-y) ( _k+1- _kc_k+1-c_k-1 ) 3. Expected Privacy Variance: The expected structural variance interpolates linearly between the two valid token states: v|y[Vv]=pk(y)Vk+pk+1(y)Vk+1E_v|y[V_v]=p_k(y)V_k+p_k+1(y)V_k+1 Summing the base quantization error and the cross-correlation bias exactly consolidates the y-dependent portion of the loss. We define the scale modifier WkW_k: Wk=1+2(μk+1−μkck+1−ck−1)=2(μk+1−μk)ck+1−ck−1W_k=1+2 ( _k+1- _kc_k+1-c_k-1 )= 2( _k+1- _k)c_k+1-c_k-1 Integrating the components over the density fY(y)f_Y(y) establishes the intermediate objective: ℒMA-SSTQ∗(Γ)=∑k=1M−1∫ckck+1[Wk(y−ck)(ck+1−y)+pk(y)Vk+pk+1(y)Vk+1]fY(y)yL^*_MA-SSTQ( )= _k=1^M-1 _c_k^c_k+1 [W_k(y-c_k)(c_k+1-y)+p_k(y)V_k+p_k+1(y)V_k+1 ]f_Y(y)\,dy By regrouping the local variance assignments globally across the entire support domain [−B,B][-B,B], the continuous expected mean squared error minimizes to its definitive analytical form: ℒMA-SSTQ∗(Γ)=∑k=1M−1∫ckck+1Wk(y−ck)(ck+1−y)fY(y)y+∑i=1MπiVi,L^*_MA-SSTQ( )= _k=1^M-1 _c_k^c_k+1W_k(y-c_k)(c_k+1-y)f_Y(y)\,dy\;\;+\;\; _i=1^M _iV_i\,, where πi=∫−BBPr[v=ci∣y]fY(y)y _i= _-B^B [v=c_i y]f_Y(y)\,dy defines the precise unconditional assignment probability of the intermediate token v=civ=c_i. D.2.2 Proof of Theorem 5.2 Let x∈ℝdx ^d be the target vector, and assume ‖x‖2=1\|x\|_2=1. By Kashin’s representation theorem, there exists a vector y∈ℝNy ^N such that x=dNUTyx= dNU^Ty, where U∈ℝN×dU ^N× d is an Equal-Norm Tight Frame (ENTF) satisfying the tight frame condition UTU=NdIdU^TU= NdI_d and ‖uj‖2=1\|u_j\|_2=1 for all j∈1,…,Nj∈\1,…,N\. The coordinates of the Kashin representation y are uniformly bounded such that ‖y‖∞≤B\|y\|_∞≤ B, where B=KN‖x‖2=KNB= K N\|x\|_2= K N. Let ρ=Nd>1ρ= Nd>1 denote the frame redundancy ratio. Consequently, the uniform coordinate variance bound satisfies B2=K2ρdB^2= K^2ρ d. Furthermore, the squared Euclidean norm of the coefficient vector satisfies ‖y‖22≤N‖y‖∞2≤NB2=K2\|y\|_2^2≤ N\|y\|_∞^2≤ NB^2=K^2. The identity decoding protocol uniformly selects an index j∈1,…,Nj∈\1,…,N\ at random and returns the estimator x^=dNUT(Nzjej)=dzjuj x= dNU^T(Nz_je_j)=dz_ju_j, where zj∈Γ∗z_j∈ ^* is the privatized token. We assume the codebook size is M=2bM=2^b and adheres to a non-degenerate spatial resolution, such that the maximum codebook gap satisfies Δmax=maxk(ck+1−ck)≤C2B2b−1 _ = _k(c_k+1-c_k)≤ C 2B2^b-1 for a structural constant C≥1C≥ 1. Step 1: Pointwise Statistics of the Metric-Aware Mechanism. Note that, once the input x and the frame U are fixed, the Kashin coefficient vector y is deterministic. All expectations in this proof are therefore taken over the stochastic quantization and the privacy mechanism only; yjy_j is a fixed scalar throughout. For any continuous coordinate yj∈[ck,ck+1]y_j∈[c_k,c_k+1], the initial stochastic quantization step assigns an intermediate token vj∈ck,ck+1v_j∈\c_k,c_k+1\ with local assignment probabilities pk(yj)=ck+1−yjΔkp_k(y_j)= c_k+1-y_j _k and pk+1(yj)=yj−ckΔkp_k+1(y_j)= y_j-c_k _k, where Δk=ck+1−ck _k=c_k+1-c_k. This interpolation enforces local unbiasedness: [vj]=pk(yj)ck+pk+1(yj)ck+1=yjE[v_j]=p_k(y_j)c_k+p_k+1(y_j)c_k+1=y_j. Given vj=ckv_j=c_k, the mechanism draws a continuous sample T∼TruncLaplace(ck,4Bϵ,[−B,B])T (c_k, 4Bε,[-B,B]) and outputs zj=argminci∈Γ|T−ci|z_j= _c_i∈ |T-c_i|. Define the expected structural drift of the mechanism evaluated at a centroid ckc_k as βk=[zj∣vj=ck]−ck, _k=E[z_j v_j=c_k]-c_k, and the localized mechanism variance as Vk=[(zj−ck)2∣vj=ck].V_k=E[(z_j-c_k)^2 v_j=c_k]. Since zj=argminci|T−ci|z_j= _c_i|T-c_i| is the nearest codeword to T, and ckc_k is itself a codeword, the triangle inequality gives |zj−ck|≤|zj−T|+|T−ck|≤2|T−ck||z_j-c_k|≤|z_j-T|+|T-c_k|≤ 2|T-c_k| (because |zj−T|≤|ck−T||z_j-T|≤|c_k-T| by definition of nearest codeword). Bias bound. Applying the triangle inequality for conditional expectations: |βk|=|[zj−ck∣vj=ck]|≤[|zj−ck|∣vj=ck]≤2[|T−ck|∣vj=ck]≤2λ=8Bϵ,| _k|=|E[z_j-c_k v_j=c_k]| [|z_j-c_k| v_j=c_k]≤ 2\,E[|T-c_k| v_j=c_k]≤ 2λ= 8Bε, (59) where λ=4Bϵλ= 4Bε is the Laplace scale and [|T−ck|∣vj=ck]≤λE[|T-c_k| v_j=c_k]≤λ since truncation only reduces the mean absolute deviation. Variance bound. Squaring the pointwise inequality |zj−ck|≤2|T−ck||z_j-c_k|≤ 2|T-c_k| and taking expectations: Vk=[(zj−ck)2∣vj=ck]≤4[(T−ck)2∣vj=ck]≤4⋅2λ2=128B2ϵ2, V_k=E[(z_j-c_k)^2 v_j=c_k]≤ 4\,E[(T-c_k)^2 v_j=c_k]≤ 4· 2λ^2= 128B^2ε^2, (60) where [(T−ck)2∣vj=ck]≤2λ2=32B2ϵ2E[(T-c_k)^2 v_j=c_k]≤ 2λ^2= 32B^2ε^2 is the second moment of the untruncated Laplace (truncation can only reduce this). We write βmax=maxk|βk|≤8Bϵ _ = _k| _k|≤ 8Bε and Vmax=maxkVk≤128B2ϵ2V_ = _kV_k≤ 128B^2ε^2. For a fixed coordinate value yjy_j, define the function r(yj)=[zj]−yjr(y_j)=E[z_j]-y_j, where the expectation is over the stochastic quantization and the privacy mechanism. By the Law of Total Expectation over vjv_j, this expands as: r(yj) r(y_j) =pk(yj)[zj∣vj=ck]+pk+1(yj)[zj∣vj=ck+1]−yj =p_k(y_j)E[z_j v_j=c_k]+p_k+1(y_j)E[z_j v_j=c_k+1]-y_j =pk(yj)(ck+βk)+pk+1(yj)(ck+1+βk+1)−(pk(yj)ck+pk+1(yj)ck+1) =p_k(y_j)(c_k+ _k)+p_k+1(y_j)(c_k+1+ _k+1)- (p_k(y_j)c_k+p_k+1(y_j)c_k+1 ) =pk(yj)βk+pk+1(yj)βk+1. =p_k(y_j) _k+p_k+1(y_j) _k+1. Because pk(yj)p_k(y_j) and pk+1(yj)p_k+1(y_j) form a valid probability mass function, r(yj)r(y_j) is a convex combination of the local drifts βk _k and βk+1 _k+1. It follows that |r(yj)|≤βmax|r(y_j)|≤ _ for all yj∈[−B,B]y_j∈[-B,B]. Defining the global bias vector =[r(y1),…,r(yN)]T∈ℝNr=[r(y_1),…,r(y_N)]^T ^N (which is deterministic), we obtain the norm inequality ‖22≤Nβmax2\|r\|_2^2≤ N _ ^2. Step 2: Upper Bound on the Expected Bias (ζ2ζ^2). Taking the expectation of the estimator over the mechanism stochasticity and the uniform index (j) selection yields: [x^]=1N∑j=1Nd[zj∣j]uj=dNUT[z]=dNUT(y+)=x+dNUT.E[ x]= 1N _j=1^NdE[z_j j]u_j= dNU^TE[z]= dNU^T(y+r)=x+ dNU^Tr. The squared Euclidean vector bias is ζ2=‖dNUT‖22=d2N2TUUTζ^2= \| dNU^Tr \|_2^2= d^2N^2r^TU^Tr. Since UTU=NdIdU^TU= NdI_d, the non-zero eigenvalues of the symmetric matrix UUTUU^T are exactly Nd Nd. Applying this operator norm constraint bounds the quadratic form: ζ2≤d2N2(Nd)‖22=dN‖22≤dN(Nβmax2)=dβmax2.ζ^2≤ d^2N^2 ( Nd )\|r\|_2^2= dN\|r\|_2^2≤ dN (N _ ^2 )=d _ ^2. Substituting βmax≤8Bϵ _ ≤ 8Bε and B2=K2ρdB^2= K^2ρ d produces the final bound on the bias: ζ2≤d(64B2ϵ2)=64dK2ρdϵ2=64K2ρϵ2.ζ^2≤ d ( 64B^2ε^2 )= 64dK^2ρ dε^2= 64K^2ρε^2. Step 3: Upper Bound on the Loss. For yj∈[ck,ck+1]y_j∈[c_k,c_k+1], we bound the pointwise error e(yj)=[(yj−zj)2]e(y_j)=E[(y_j-z_j)^2] (expectation over the mechanism randomness) using a direct decomposition that avoids the scale modifier WkW_k. Writing yj−zj=(yj−vj)+(vj−zj)y_j-z_j=(y_j-v_j)+(v_j-z_j) and applying (a+b)2≤2a2+2b2(a+b)^2≤ 2a^2+2b^2: e(yj)≤2[(yj−vj)2]+2[(vj−zj)2]. e(y_j)≤ 2\,E[(y_j-v_j)^2]+2\,E[(v_j-z_j)^2]. (61) The first term evaluates exactly as [(yj−vj)2]=(yj−ck)(ck+1−yj)≤Δk24≤Δmax24E[(y_j-v_j)^2]=(y_j-c_k)(c_k+1-y_j)≤ _k^24≤ _ ^24, since it is the variance of stochastic quantization. The second term is bounded by [(vj−zj)2]=pk(yj)Vk+pk+1(yj)Vk+1≤VmaxE[(v_j-z_j)^2]=p_k(y_j)V_k+p_k+1(y_j)V_k+1≤ V_ . Combining: e(yj)≤Δmax22+2Vmax≤2C2B2(2b−1)2+256B2ϵ2.e(y_j)≤ _ ^22+2V_ ≤ 2C^2B^2(2^b-1)^2+ 256B^2ε^2. Taking the average over all coordinates (j)(j) provides an upper bound on the loss ℒMA-SSTQ∗L^*_MA-SSTQ: ℒMA-SSTQ∗≤B2(2C2(2b−1)2+256ϵ2).L^*_MA-SSTQ≤ B^2 ( 2C^2(2^b-1)^2+ 256ε^2 ). (62) Step 4: Upper Bound on the Mean Squared Error (MSEMAMSE_MA). We expand the mean squared error using the bias-variance decomposition: MSEMA=[‖x^‖22]−2xT[x^]+‖x‖22MSE_MA=E[\| x\|_2^2]-2x^TE[ x]+\|x\|_2^2. Since ‖x‖2=1\|x\|_2=1, the final term evaluates to 11. Evaluating the uncentered second moment using the trace property ‖uj‖22=1\|u_j\|_2^2=1 yields: [‖x^‖22] [\| x\|_2^2] =1N∑j=1Nd2[zj2]=d2N∑j=1N([(zj−yj)2]+yj2+2yjr(yj)) = 1N _j=1^Nd^2E[z_j^2]= d^2N _j=1^N (E[(z_j-y_j)^2]+y_j^2+2y_jr(y_j) ) =d2ℒMA-SSTQ∗+d2N‖y‖22+2d2NyT. =d^2L^*_MA-SSTQ+ d^2N\|y\|_2^2+ 2d^2Ny^Tr. Next, we evaluate the cross-term utilizing [x^]=x+dNUTE[ x]=x+ dNU^Tr. Let P=dNUUTP= dNU^T denote the orthogonal projection matrix onto the column space of U. Since x=dNUTyx= dNU^Ty, we apply the mapping xTUT=dNyTUUT=yTPx^TU^T= dNy^TU^T=y^TP. Thus: −2xT[x^]=−2‖x‖22−2dNxTUT=−2−2dNyTP.-2x^TE[ x]=-2\|x\|_2^2- 2dNx^TU^Tr=-2- 2dNy^TPr. Combining these components provides the complete MSE formulation: MSEMA=d2ℒMA-SSTQ∗+(d2N‖y‖22−1)+2dNyT(dIN−P). _MA=d^2L^*_MA-SSTQ+ ( d^2N\|y\|_2^2-1 )+ 2dNy^T(dI_N-P)r. (63) We independently bound each of the three residual terms: 1. Baseline Variance: The Kashin representation enforces the inequality ‖y‖22≤K2\|y\|_2^2≤ K^2. Therefore: d2N‖y‖22−1≤d2K2N−1=dK2ρ−1. d^2N\|y\|_2^2-1≤ d^2K^2N-1= dK^2ρ-1. 2. Loss Contribution: Multiplying the bound in Eq. 62 by d2d^2 and substituting B2=K2ρdB^2= K^2ρ d yields: d2ℒMA-SSTQ∗≤d2B2(2C2(2b−1)2+256ϵ2)=dK2ρ(2C2(2b−1)2+256ϵ2).d^2L^*_MA-SSTQ≤ d^2B^2 ( 2C^2(2^b-1)^2+ 256ε^2 )= dK^2ρ ( 2C^2(2^b-1)^2+ 256ε^2 ). 3. Cross-Correlation Term: Because P is an orthogonal projection matrix, its eigenvalues are bounded in 0,1\0,1\. Consequently, the matrix (dIN−P)(dI_N-P) has a spectral norm of exactly d. Applying the Cauchy-Schwarz inequality provides: |2dNyT(dIN−P)|≤2dN‖y‖2‖dIN−P‖op‖2≤2dN(NB)(d)(Nβmax)=2d2Bβmax. | 2dNy^T(dI_N-P)r |≤ 2dN\|y\|_2\|dI_N-P\|_op\|r\|_2≤ 2dN( NB)(d)( N _ )=2d^2B _ . Substituting βmax≤8Bϵ _ ≤ 8Bε and subsequently evaluating B2=K2ρdB^2= K^2ρ d limits this correlation to: 2d2B(8Bϵ)=16d2B2ϵ=16dK2ρϵ.2d^2B ( 8Bε )= 16d^2B^2ε= 16dK^2ρε. Summing the individual bounds groups the expression under the shared geometric parameter dK2ρ dK^2ρ: MSEMA≤dK2ρ(2C2(2b−1)2+256ϵ2)+(dK2ρ−1)+dK2ρ(16ϵ).MSE_MA≤ dK^2ρ ( 2C^2(2^b-1)^2+ 256ε^2 )+ ( dK^2ρ-1 )+ dK^2ρ ( 16ε ). Factoring out the shared coefficient completes the proof: MSEMA≤dK2ρ(1+2C2(2b−1)2+16ϵ+256ϵ2)−1.MSE_MA≤ dK^2ρ (1+ 2C^2(2^b-1)^2+ 16ε+ 256ε^2 )-1. D.2.3 Proof of Theorem 5.3 Let y∈ℝNy ^N be the exact Kashin representation vector satisfying x=dNUTyx= dNU^Ty, where UTU=NdIdU^TU= NdI_d. The geometric variance bounds dictate B2=K2ρdB^2= K^2ρ d and ‖y‖22≤K2\|y\|_2^2≤ K^2. Step 1: Pointwise Statistics and Mechanism Bounds. For any continuous coordinate yj∈[ck,ck+1]y_j∈[c_k,c_k+1], stochastic quantization maps the input to an intermediate locally unbiased token vj∈ck,ck+1v_j∈\c_k,c_k+1\. The metric-aware mechanism subsequently draws T∼TruncLaplace(ck,4Bϵ,[−B,B])T (c_k, 4Bε,[-B,B]) and outputs the nearest codeword zj=argminci|T−ci|z_j= _c_i|T-c_i|. Define the expected structural drift βk=[zj∣vj=ck]−ck _k=E[z_j v_j=c_k]-c_k and localized variance Vk=[(zj−ck)2∣vj=ck]V_k=E[(z_j-c_k)^2 v_j=c_k]. Since zjz_j is the nearest codeword to T and ckc_k is itself a codeword, the triangle inequality gives |zj−ck|≤2|T−ck||z_j-c_k|≤ 2|T-c_k|, yielding clean bounds as established in (60): βmax:=maxk|βk|≤8Bϵ,andVmax:=maxkVk≤128B2ϵ2. _ := _k| _k|≤ 8Bε, V_ := _kV_k≤ 128B^2ε^2. The pointwise mechanism bias evaluates as r(yj)=[zj]−yj=pk(yj)βk+pk+1(yj)βk+1r(y_j)=E[z_j]-y_j=p_k(y_j) _k+p_k+1(y_j) _k+1, where the expectation is over the mechanism randomness (recall that yjy_j is deterministic). Because this is a strictly convex combination of adjacent drifts, |r(yj)|≤βmax|r(y_j)|≤ _ universally. Thus, the deterministic bias vector ∈ℝNr ^N satisfies ‖22≤Nβmax2\|r\|_2^2≤ N _ ^2. Step 2: Expected Bias (ζ2ζ^2) Bound. Under identity decoding, uniform index sampling yields the expectation [x^∣x]=x+dNUTE[ x x]=x+ dNU^Tr. The squared Euclidean vector bias is ζ2=d2N2TUUTζ^2= d^2N^2r^TU^Tr. Applying the tight frame operator norm ‖UUT‖op=Nd\|U^T\|_op= Nd gives: ζ2≤d2N2(Nd)‖22=dN‖22≤dβmax2.ζ^2≤ d^2N^2 ( Nd )\|r\|_2^2= dN\|r\|_2^2≤ d _ ^2. Substituting βmax≤8Bϵ _ ≤ 8Bε and B2=K2ρdB^2= K^2ρ d produces exactly ζ2≤64K2ρϵ2ζ^2≤ 64K^2ρε^2. Step 3: Upper Bounding the True Operational Loss (ℒMA−SSTQ∗L^*_MA-SSTQ). Similar to (61), we bound the pointwise error using the direct decomposition e(y)≤2[(y−v)2]+2[(v−z)2]e(y)≤ 2\,E[(y-v)^2]+2\,E[(v-z)^2], where the first term is ≤Δk24≤ _k^24 (stochastic quantization variance) for y∈[ck,ck+1]y∈[c_k,c_k+1] and the second term is ≤Vmax≤ V_ . Thus e(y)≤Δk22+2Vmaxe(y)≤ _k^22+2V_ . This way we can avoid the scale modifier WkW_k and bound the loss as: ℒMA−SSTQ∗(Γ) ^*_MA-SSTQ( ) =∑k=1M−1∫ckck+1e(y)fY(y)y = _k=1^M-1 _c_k^c_k+1e(y)f_Y(y)\,dy ≤∑k=1M−1Δk22∫ckck+1fY(y)y+2Vmax. ≤ _k=1^M-1 _k^22 _c_k^c_k+1f_Y(y)\,dy+2V_ \,. (64) Key step. Because Γ∗ ^* globally minimizes the full operational loss ℒMA-SSTQ∗L^*_MA -SSTQ, we have ℒMA-SSTQ∗(Γ∗)≤ℒMA-SSTQ∗(Γ′)L^*_MA -SSTQ( ^*) ^*_MA -SSTQ( ) for any feasible competitor Γ′ . We then apply the pointwise decomposition at the competitor to obtain an explicit upper bound. Remark on feasibility. The zero-sum constraint ∑ici=0 _ic_i=0 is required only for the Flat-R variant (to ensure the unbiasing identity in (5)). The metric-aware variant uses identity decoding and does not require this constraint; therefore the proxy codebooks Γunif _unif and ΓPD _PD constructed below are both feasible competitors. • Uniform Grid Bound: We evaluate the full loss at Γunif _unif with constant gap Δk=2BM−1 _k= 2BM-1. Using (64) and integrating the spatial term over fY(y)f_Y(y): ∑k=1M−1Δk22∫ckck+1fY(y)y=2B2(M−1)2 _k=1^M-1 _k^22 _c_k^c_k+1f_Y(y)\,dy= 2B^2(M-1)^2. Therefore ℒMA-SSTQ∗(Γ∗)≤ℒMA-SSTQ∗(Γunif)≤2B2(M−1)2+2VmaxL^*_MA -SSTQ( ^*) ^*_MA -SSTQ( _unif)≤ 2B^2(M-1)^2+2V_ . This establishes the case C02≤1C_0^2≤ 1. • Discrete Panter–Dite Bound: Let S=∫−BBfY(y)1/3yS= _-B^Bf_Y(y)^1/3\,dy, so that S3=4B2CfS^3=4B^2C_f. We construct ΓPD _PD by partitioning [−B,B][-B,B] so that every interval contains equal mass under the cube-root density: ∫ckck+1fY(y)1/3y=SM−1 _c_k^c_k+1f_Y(y)^1/3\,dy= SM-1. (Since the metric-aware variant does not impose ∑ici=0 _ic_i=0, this proxy is a feasible competitor.) Let Mk=sup[ck,ck+1]fY(y)M_k= _[c_k,c_k+1]f_Y(y) and mk=inf[ck,ck+1]fY(y)m_k= _[c_k,c_k+1]f_Y(y). Bounding the integral of the cube root yields mk1/3Δk≤SM−1⟹Δk≤S(M−1)mk1/3m_k^1/3 _k≤ SM-1 _k≤ S(M-1)m_k^1/3. The spatial integral over the interval is bounded by extracting the supremum: ∫ckck+1(y−ck)(ck+1−y)fY(y)y≤MkΔk36≤S36(M−1)3(Mkmk). _c_k^c_k+1(y-c_k)(c_k+1-y)f_Y(y)\,dy≤ M_k _k^36≤ S^36(M-1)^3 ( M_km_k ). Summing over all M−1M-1 intervals yields the spatial component: SPD:=∑k=1M−1S36(M−1)3(Mkmk)=B2(M−1)2(23CfRM).S_PD:= _k=1^M-1 S^36(M-1)^3 ( M_km_k )= B^2(M-1)^2 ( 23C_fR_M ). Applying the full-loss bound: ℒMA-SSTQ∗(Γ∗)≤ℒMA-SSTQ∗(ΓPD)≤2SPD+2VmaxL^*_MA -SSTQ( ^*) ^*_MA -SSTQ( _PD)≤ 2S_PD+2V_ . Taking the minimum of both competitors, we establish C02≤min(1,23CfRM)C_0^2≤ (1,\; 23C_fR_M ). In both cases, the mechanism variance contributes an additive 2Vmax≤256B2ϵ22V_ ≤ 256B^2ε^2 that is already absorbed into the 256ϵ2 256ε^2 term of the final MSE bound. Thus ℒMA−SSTQ∗(Γ∗)≤2B2C02(2b−1)2+256B2ϵ2L^*_MA-SSTQ( ^*)≤ 2B^2C_0^2(2^b-1)^2+ 256B^2ε^2. Step 4: MSE Expansion. Following the derivation behind (63), we have MSEMA=d2ℒMA−SSTQ∗+(d2N‖y‖22−1)+2dNyT(dIN−P)MSE_MA=d^2L^*_MA-SSTQ+( d^2N\|y\|_2^2-1)+ 2dNy^T(dI_N-P)r, where P=dNUUTP= dNU^T. Substituting M=2bM=2^b and replacing d2B2=dK2ρd^2B^2= dK^2ρ provides: d2ℒMA−SSTQ≤dK2ρ(2C2(2b−1)2+256ϵ2)d^2L_MA-SSTQ≤ dK^2ρ ( 2C^2(2^b-1)^2+ 256ε^2 ). Next by using ‖y‖22≤K2\|y\|_2^2≤ K^2, the constraint ensures d2N‖y‖22−1≤dK2ρ−1 d^2N\|y\|_2^2-1≤ dK^2ρ-1. In addition, applying Cauchy-Schwarz with the operator norm ‖dIN−P‖op=d\|dI_N-P\|_op=d yields: |2dNyT(dIN−P)|≤2dN‖y‖2(d)‖2≤2d2N(K)(N8Bϵ)=16d2KBNϵ=16dK2ρϵ. | 2dNy^T(dI_N-P)r |≤ 2dN\|y\|_2(d)\|r\|_2≤ 2d^2N(K) ( N 8Bε )= 16d^2KB Nε= 16dK^2ρε. Summing these independent components groups the parameters natively by the shared geometric constant dK2ρ dK^2ρ: MSEMA≤dK2ρ(2C2(2b−1)2+256ϵ2)+(dK2ρ−1)+dK2ρ(16ϵ).MSE_MA≤ dK^2ρ ( 2C^2(2^b-1)^2+ 256ε^2 )+ ( dK^2ρ-1 )+ dK^2ρ ( 16ε ). Factoring the common terms extracts the final formalized bound. Appendix E Proofs for Federated Learning Convergence Analysis This appendix provides the proofs for the non-convex Distributed Stochastic Gradient Descent (DSGD) convergence rate established in Theorem 6.2, as well as its specific operational corollaries for our SSTQ framework. E.1 Proof of Theorem 6.2 The proof proceeds in four parts: decomposing the Mean Squared Error (MSE) of the global estimator, establishing the descent lemma with bias, absorbing the bias via Young’s inequality, and telescoping to yield the final convergence rate. Throughout, we let ℱt=σ(w0,g^i,s:i∈[n],s<t)F_t=σ\! (w_0,\; g_i,s:i∈[n],\,s<t ) denote the σ-algebra generated by the initial point and all transmitted gradients prior to step t. Since wtw_t is a deterministic function of (w0,g^i,0,…,g^i,t−1)i=1n(w_0, g_i,0,…, g_i,t-1)_i=1^n, the iterate wtw_t is ℱtF_t-measurable. We write t[⋅]=[⋅∣ℱt]E_t[·]=E[· _t] for the conditional expectation given ℱtF_t. Step 1: Gradient and MSE Decomposition. Define the client-level error Xi,t=g^i,t−∇fi(wt)X_i,t= g_i,t-∇ f_i(w_t). The global estimator error decomposes as g^t−∇F(wt)=1n∑i=1nXi,t. g_t-∇ F(w_t)= 1n _i=1^nX_i,t. Applying the standard bias-variance identity [‖Y‖22]=[‖Y−[Y]‖22]+‖[Y]‖22E[ Y _2^2]=E[ Y-E[Y] _2^2]+ [Y] _2^2 conditionally on ℱtF_t, with Y=1n∑i=1nXi,tY= 1n _i=1^nX_i,t: t[‖1n∑i=1nXi,t‖22]=t[‖1n∑i=1n(Xi,t−t[Xi,t])‖22]+‖t[1n∑i=1nXi,t]‖22.E_t\! [ 1n _i=1^nX_i,t _2^2 ]=E_t\! [ 1n _i=1^n (X_i,t-E_t[X_i,t] ) _2^2 ]+ _t\! [ 1n _i=1^nX_i,t ] _2^2. (65) Variance term. By assumption (v), the centered variables Xi,t−t[Xi,t]X_i,t-E_t[X_i,t] are conditionally independent and mean-zero given ℱtF_t. Hence, for the variance of their average: t[‖1n∑i=1n(Xi,t−t[Xi,t])‖22]=1n2∑i=1nt[‖Xi,t−t[Xi,t]‖22]≤1n2∑i=1nt[‖Xi,t‖22],E_t\! [ 1n _i=1^n (X_i,t-E_t[X_i,t] ) _2^2 ]= 1n^2 _i=1^nE_t\! [ X_i,t-E_t[X_i,t] _2^2 ]≤ 1n^2 _i=1^nE_t\! [ X_i,t _2^2 ], (66) where the inequality uses Var(Z)≤[‖Z‖22]Var(Z) [ Z _2^2] for any random variable Z. Bias term. By linearity, the squared bias equals ‖t[1n∑i=1nXi,t]‖22=‖t[g^t]−∇F(wt)‖22=‖bt‖22≤ζ2a.s., _t\! [ 1n _i=1^nX_i,t ] _2^2= _t[ g_t]-∇ F(w_t) _2^2= b_t _2^2≤ζ^2 .s., by assumption (iv). Combining (65)–(66): t[‖g^t−∇F(wt)‖22]≤1n2∑i=1nt[‖Xi,t‖22]+ζ2.E_t\! [ g_t-∇ F(w_t) _2^2 ]≤ 1n^2 _i=1^nE_t\! [ X_i,t _2^2 ]+ζ^2. (67) Bounding the local MSE. We bound each t[‖Xi,t‖22]E_t[ X_i,t _2^2] by splitting the compression and stochastic errors. Using ‖A+B‖22≤2‖A‖22+2‖B‖22 A+B _2^2≤ 2 A _2^2+2 B _2^2 (which holds for all vectors A,BA,B without any independence requirement): t[‖Xi,t‖22] _t\! [ X_i,t _2^2 ] =t[‖(g^i,t−gi,t)+(gi,t−∇fi(wt))‖22] =E_t\! [ ( g_i,t-g_i,t)+(g_i,t-∇ f_i(w_t)) _2^2 ] ≤2t[‖g^i,t−gi,t‖22]+2t[‖gi,t−∇fi(wt)‖22] ≤ 2\,E_t\! [ g_i,t-g_i,t _2^2 ]+2\,E_t\! [ g_i,t-∇ f_i(w_t) _2^2 ] ≤2ωG2+2σ2=2(ωG2+σ2), ≤ 2ω G^2+2σ^2=2(ω G^2+σ^2), (68) where the last line applies assumptions (i) and (i). Substituting (68) into (67): t[‖g^t−∇F(wt)‖22]≤2(ωG2+σ2)n+ζ2.E_t\! [ g_t-∇ F(w_t) _2^2 ]≤ 2(ω G^2+σ^2)n+ζ^2. (69) Second-moment bound. We additionally bound the conditional second moment of the update direction, which will be needed in Step 2. By the same inequality ‖A+B‖22≤2‖A‖22+2‖B‖22 A+B _2^2≤ 2 A _2^2+2 B _2^2: t[‖g^t‖22] _t\! [ g_t _2^2 ] =t[‖(g^t−∇F(wt))+∇F(wt)‖22] =E_t\! [ ( g_t-∇ F(w_t))+∇ F(w_t) _2^2 ] ≤2t[‖g^t−∇F(wt)‖22]+2‖∇F(wt)‖22 ≤ 2\,E_t\! [ g_t-∇ F(w_t) _2^2 ]+2 ∇ F(w_t) _2^2 ≤2(2(ωG2+σ2)n+ζ2)+2‖∇F(wt)‖22, ≤ 2\! ( 2(ω G^2+σ^2)n+ζ^2 )+2 ∇ F(w_t) _2^2, (70) where the last step substitutes (69). Note that ∇F(wt)∇ F(w_t) is ℱtF_t-measurable and thus passes through t[⋅]E_t[·] as a constant. Step 2: The Descent Lemma with Bias. By L-smoothness (assumption (i)) and the update rule wt+1=wt−ηg^tw_t+1=w_t-η\, g_t: F(wt+1)≤F(wt)−η⟨∇F(wt),g^t⟩+η2L2‖g^t‖22.F(w_t+1)≤ F(w_t)-η\, ∇ F(w_t),\, g_t + η^2L2\, g_t _2^2. (71) Taking the conditional expectation t[⋅]E_t[·] of both sides (noting F(wt)F(w_t) and ∇F(wt)∇ F(w_t) are ℱtF_t-measurable): t[F(wt+1)] _t[F(w_t+1)] ≤F(wt)−η⟨∇F(wt),t[g^t]⟩+η2L2t[‖g^t‖22] ≤ F(w_t)-η\, ∇ F(w_t),\,E_t[ g_t] + η^2L2\,E_t\! [ g_t _2^2 ] =F(wt)−η⟨∇F(wt),∇F(wt)+bt⟩+η2L2t[‖g^t‖22] =F(w_t)-η\, ∇ F(w_t),\,∇ F(w_t)+b_t + η^2L2\,E_t\! [ g_t _2^2 ] =F(wt)−η‖∇F(wt)‖22−η⟨∇F(wt),bt⟩+η2L2t[‖g^t‖22]. =F(w_t)-η\, ∇ F(w_t) _2^2-η\, ∇ F(w_t),\,b_t + η^2L2\,E_t\! [ g_t _2^2 ]. (72) Step 3: Absorbing the Bias via Young’s Inequality. We bound the inner-product bias term using the Cauchy–Schwarz inequality followed by Young’s inequality (ab≤a22+b22ab≤ a^22+ b^22 for a,b≥0a,b≥ 0): −⟨∇F(wt),bt⟩≤‖∇F(wt)‖2‖bt‖2≤12‖∇F(wt)‖22+12‖bt‖22≤12‖∇F(wt)‖22+ζ22,- ∇ F(w_t),\,b_t ≤ ∇ F(w_t) _2\, b_t _2≤ 12 ∇ F(w_t) _2^2+ 12 b_t _2^2≤ 12 ∇ F(w_t) _2^2+ ζ^22, (73) where the last inequality uses ‖bt‖22≤ζ2 b_t _2^2≤ζ^2 a.s. (assumption (iv)). Substituting (73) and the second-moment bound (70) into (72): t[F(wt+1)] _t[F(w_t+1)] ≤F(wt)−η2‖∇F(wt)‖22+ηζ22+η2L2[2‖∇F(wt)‖22+2(2(ωG2+σ2)n+ζ2)] ≤ F(w_t)- η2 ∇ F(w_t) _2^2+ η\,ζ^22+ η^2L2\! [2 ∇ F(w_t) _2^2+2\! ( 2(ω G^2+σ^2)n+ζ^2 ) ] =F(wt)−(η2−η2L)⏟gradient coefficient‖∇F(wt)‖22+ηζ22+η2L(2(ωG2+σ2)n+ζ2). =F(w_t)- ( η2-η^2L )_gradient coefficient ∇ F(w_t) _2^2+ η\,ζ^22+η^2L\! ( 2(ω G^2+σ^2)n+ζ^2 ). (74) Step 4: Telescoping and Convergence. Learning rate constraint. We require η≤14Lη≤ 14L, which ensures η2L≤η4η^2L≤ η4 and hence: η2−η2L≥η2−η4=η4>0. η2-η^2L≥ η2- η4= η4>0. (75) Substituting into (74): t[F(wt+1)]≤F(wt)−η4‖∇F(wt)‖22+ηζ22+η2L(2(ωG2+σ2)n+ζ2).E_t[F(w_t+1)]≤ F(w_t)- η4\, ∇ F(w_t) _2^2+ η\,ζ^22+η^2L\! ( 2(ω G^2+σ^2)n+ζ^2 ). (76) Telescoping. Rearranging (76): η4‖∇F(wt)‖22≤F(wt)−t[F(wt+1)]+ηζ22+η2L(2(ωG2+σ2)n+ζ2). η4\, ∇ F(w_t) _2^2≤ F(w_t)-E_t[F(w_t+1)]+ η\,ζ^22+η^2L\! ( 2(ω G^2+σ^2)n+ζ^2 ). Taking the full (unconditional) expectation on both sides and applying the tower property [t[⋅]]=[⋅]E[E_t[·]]=E[·]: η4[‖∇F(wt)‖22]≤[F(wt)]−[F(wt+1)]+ηζ22+η2L(2(ωG2+σ2)n+ζ2). η4\,E\! [ ∇ F(w_t) _2^2 ] [F(w_t)]-E[F(w_t+1)]+ η\,ζ^22+η^2L\! ( 2(ω G^2+σ^2)n+ζ^2 ). Summing over t=0,1,…,T−1t=0,1,…,T-1 (the right-hand side telescopes): η4∑t=0T−1[‖∇F(wt)‖22]≤F(w0)−[F(wT)]+Tηζ22+Tη2L(2(ωG2+σ2)n+ζ2). η4 _t=0^T-1E\! [ ∇ F(w_t) _2^2 ]≤ F(w_0)-E[F(w_T)]+ Tη\,ζ^22+Tη^2L\! ( 2(ω G^2+σ^2)n+ζ^2 ). Using [F(wT)]≥F∗E[F(w_T)]≥ F^* (assumption (vi)) and dividing both sides by ηT4 η T4: 1T∑t=0T−1[‖∇F(wt)‖22]≤4Δ0ηT+2ζ2+4ηL(2(ωG2+σ2)n+ζ2), 1T _t=0^T-1E\! [ ∇ F(w_t) _2^2 ]≤ 4 _0η T+2ζ^2+4η L\! ( 2(ω G^2+σ^2)n+ζ^2 ), (77) where Δ0:=F(w0)−F∗ _0:=F(w_0)-F^*. Optimal learning rate. Define the noise-plus-bias parameter V:=2(ωG2+σ2)n+ζ2V:= 2(ω G^2+σ^2)n+ζ^2. The bound (77) has the form 4Δ0ηT+2ζ2+4ηLV 4 _0η T+2ζ^2+4η LV. We set η=min14L,Δ0LVTη= \! \ 14L,\; _0LVT \ and consider both cases. Case 1: T≥T0:=16LΔ0/VT≥ T_0:=16L _0/V. In this regime, η∗=Δ0/(LVT)≤14Lη^*= _0/(LVT)≤ 14L, and substituting into (77): 1T∑t=0T−1[‖∇F(wt)‖22] 1T _t=0^T-1E\! [ ∇ F(w_t) _2^2 ] ≤4Δ0Δ0/(LVT)⋅T+2ζ2+4Δ0LVT⋅LV ≤ 4 _0 _0/(LVT)· T+2ζ^2+4 _0LVT· LV =8Δ0LVT+2ζ2. = 8 _0LV T+2ζ^2. (78) Case 2: T<T0T<T_0. Here η=14Lη= 14L, and substituting into (77): 1T∑t=0T−1[‖∇F(wt)‖22] 1T _t=0^T-1E\! [ ∇ F(w_t) _2^2 ] ≤16LΔ0T+2ζ2+V. ≤ 16L _0T+2ζ^2+V. (79) For T<T0T<T_0, we have 8Δ0LVT>8Δ0LVT0=8Δ0LV⋅V4LΔ0=2V 8 _0LV T> 8 _0LV T_0= 8 _0LV· V4 L _0=2V, so the V term in the burn-in bound is dominated by the square-root term in Case 1 evaluated at T. Therefore, the unified bound valid for all T≥1T≥ 1 is: min0≤t≤T−1[‖∇F(wt)‖22]≤16LΔ0T+8Δ0LVT+2ζ2. _0≤ t≤ T-1E\! [ ∇ F(w_t) _2^2 ]≤ 16L _0T+ 8 _0LV T+2ζ^2. (80) Expanding V and simplifying. Recall V=2(ωG2+σ2)n+ζ2V= 2(ω G^2+σ^2)n+ζ^2. Thus V≤2(ωG2+σ2)n+ζ2 V≤ 2(ω G^2+σ^2)n+ ζ^2, where we have used a+b≤a+b a+b≤ a+ b for a,b≥0a,b≥ 0. Substituting: 8Δ0LVT 8 _0LV T ≤8Δ0LT(2(ωG2+σ2)n+ζ) ≤ 8 _0L T ( 2(ω G^2+σ^2)n+ζ ) =82Δ0L⋅ωG2+σ2nT+8Δ0L⋅ζT. = 8 2\, _0L· ω G^2+σ^2 nT+ 8 _0L·ζ T. (81) Combining the unified bound with (81), and using mint≤1T∑t _t≤ 1T _t: min0≤t≤T−1[‖∇F(wt)‖22]≤16LΔ0T+82Δ0L⋅ωG2+σ2nT+8Δ0L⋅ζT+2ζ2. _0≤ t≤ T-1E\! [ ∇ F(w_t) _2^2 ]≤ 16L _0T+ 8 2\, _0L· ω G^2+σ^2 nT+ 8 _0L·ζ T+2ζ^2. (82) Asymptotic simplification. For T≥T0=16LΔ0/VT≥ T_0=16L _0/V, the 16LΔ0T 16L _0T burn-in term is dominated by 8Δ0LVT 8 _0LV T. For the 8Δ0L⋅ζT 8 _0L·ζ T term, we apply the AM–GM inequality ζT≤ζ22+12T ζ T≤ ζ^22+ 12T, giving 8Δ0L⋅ζT≤4Δ0Lζ2+4Δ0LT 8 _0L·ζ T≤ 4 _0L\,ζ^2+ 4 _0LT. Since T≥16LΔ0/V≥1T≥ 16L _0/V≥ 1, the second term is (1/T)O(1/T) and absorbed into the burn-in. The first term is absorbed into (ζ2)O(ζ^2) with the problem-dependent constant 4Δ0L4 _0L. Therefore, the asymptotic rate (for T≥16LΔ0/VT≥ 16L _0/V) is: min0≤t≤T−1[‖∇F(wt)‖22]≤(ωG2+σ2nT+ζ2), _0≤ t≤ T-1E\! [ ∇ F(w_t) _2^2 ] \! ( ω G^2+σ^2 nT+ζ^2 ), (83) where the (⋅)O(·) hides dependence on the problem constants Δ0 _0 and L. This completes the proof. E.2 Proof of Corollary 6.3 Under Flat Randomized Response, the SSTQ mechanism employs the unbiasing scalar 1p−q 1p-q on the server. As established in Theorem 3.1, this renders the global estimator perfectly unbiased in expectation: bt=b_t=0, which mathematically enforces ζ=0ζ=0. By Theorem 3.2 (or more precisely, by Theorem 4.3 when M≥(4(eϵ−1))1/3+1M≥(4(e^ε-1))^1/3+1), the total variance multiplier under Flat R is bounded by ω=(d⋅2b/(ϵ∧ϵ2))ω=O(d· 2^b/(ε ε^2)). Substituting ζ=0ζ=0 and this variance multiplier directly into the general convergence bound of Theorem 6.2 gives: min0≤t≤T−1[‖∇F(wt)‖22]≤(1T+d⋅2b(ϵ∧ϵ2)−1G2+σ2nT). _0≤ t≤ T-1E[ ∇ F(w_t) _2^2] ( 1T+ d· 2^b(ε ε^2)^-1G^2+σ^2 nT ). (84) Because the bias is exactly zero, the gradient norm converges to zero as T→∞T→∞. E.3 Proof of Corollary 6.4 The Metric-Aware Laplace framework trades absolute unbiasedness to address the (2b)O(2^b) Flat R variance inflation. By Theorem 5.2, in this case we have ω=(d(1+ϵ−1+ϵ−2))ω=O(d(1+ε^-1+ε^-2)) and ζ2=(G2ϵ−2)ζ^2=O(G^2ε^-2). Substituting these specific bounds in the non-asymptotic bound of Theorem 6.2 gives: min0≤t≤T−1[‖∇F(wt)‖22]≤(1T+G2d(1+ϵ−1+ϵ−2)+σ2nT+G2ϵ−2). _0≤ t≤ T-1E[ ∇ F(w_t) _2^2] ( 1T+ G^2d(1+ε^-1+ε^-2)+σ^2 nT+G^2ε^-2 ). (85) This confirms that while the optimization trajectory converges to a non-zero stationary neighborhood dictated by ζ2ζ^2, the size of this neighborhood is explicitly independent of the massive parameter scale d. This algebraic decoupling breaks the dimensionality curse, ensuring that the gradient trajectory remains highly robust and computationally viable even for extremely large neural architectures. Appendix F Experimental Details To ensure bounded sensitivity under LDP, we clip client gradients to have ℓ2 _2-norm at most C. In the MSE-scaling experiment (Figure 2), we set C=0.2C=0.2; in the distributed SGD experiments (Figures 3 and 4), we set C=1.0C=1.0. To efficiently implement the high-dimensional transformations required by SQKR-style constructions, we use a randomized partial Hadamard transform, which enables computation over an overcomplete frame of dimension N=2⌈log2(2.5d)⌉N=2 _2(2.5\,d) in O(NlogN)O(N N) time without explicit dense matrix storage. For the Kashin representation, we apply the exact-reconstruction variant of the iterative Lyubarskii–Vershynin algorithm with parameter K=2K=2: we run 3030 truncated iterations (each clipping coefficients to the level B=KC/NB=K\,C/ N) followed by one untruncated final iteration that absorbs the remaining residual, ensuring that the identity dNU⊤y=x dNU y=x holds exactly. The number of truncated iterations is chosen as follows: at each iteration the residual contracts by a factor η<1η<1 determined by the frame geometry, so after r iterations the residual norm satisfies ‖r(t)‖2≤ηr‖x‖2\|r^(t)\|_2≤η^r\|x\|_2. For the randomized partial Hadamard frame with redundancy N/d≈2.5N/d≈ 2.5, we have η≈0.4η≈ 0.4, giving a residual of order η30≈10−12η^30≈ 10^-12 after 3030 iterations—well below machine precision. Consequently, the untruncated final coefficients have magnitude at most η30⋅Bη^30· B, which is negligible, and the effective Kashin level remains K=2K=2 to numerical precision. On the server side, after averaging the W privatized messages, we apply gradient norm clipping with a threshold of 10.010.0 to the aggregate. Because clipping is a nonlinear operation, it can introduce a small bias even when the underlying per-client estimator is unbiased (see Remark 7.1 in the main text). In practice the cap activates infrequently: the client-side clipping at norm C combined with the frame scaling B=K/NB=K/ N keeps the expected aggregate norm well below 10.010.0, so the induced bias is negligible. Remark F.1 (Effect of Learning Rate on High-Variance Mechanisms). A natural question is whether reducing the learning rate can compensate for the high variance introduced by certain privatization mechanisms. The convergence bound in Theorem 6.2 provides a precise answer. With step size η, the averaged gradient norm is bounded by 4Δ0ηT+2ζ2+4ηLV 4 _0η T+2ζ^2+4η LV, where V=2(ωG2+σ2)n+ζ2V= 2(ω G^2+σ^2)n+ζ^2. Reducing η shrinks the variance term 4ηLV4η LV but inflates the optimization term 4Δ0ηT 4 _0η T; the optimal trade-off η∗=Δ0/(LVT)η^*= _0/(LVT) yields a rate of (V/T)O( V/T). Consequently, a mechanism with ω times larger variance multiplier requires Θ(ω) (ω) times more communication rounds to reach the same accuracy. For vqSGD, whose variance scales as Θ(d3/ϵ2) (d^3/ε^2), this translates to an impractical number of rounds in high dimensions, regardless of step-size tuning. For the optimized codebook variant of SSTQ (Flat-R), we solve the loss minimization problem ℒSSTQ(Γ)=∑k=1M−1(ck+1−ck)312B+1eε−1∑i=1Mci2L_SSTQ( )\;=\; _k=1^M-1 (c_k+1-c_k)^312B\;+\; 1e -1 _i=1^Mc_i^2 subject to c1=−B,cM=B,c1≤c2≤⋯≤cM,∑ici=0c_1=-B,\;c_M=B,\;c_1≤ c_2≤·s≤ c_M,\; _ic_i=0, using Sequential Least-Squares Programming (SLSQP). The codebook is precomputed once per configuration (d,b,ε,C)(d,b, ,C) using the worst-case bound B=KC/NB=K\,C/ N, which is constant across all clipped gradients. All experiments were implemented in Python using NumPy and SciPy, and were run on a single CPU. Appendix G Additional Experiments We conduct additional experiments designed to directly test the variance bounds, communication efficiency, and downstream model utility across varying dimensions d and codebook sizes. In these experiments, we compare seven methods: Clean (no privacy), PrivUnit, vqSGD, SQKR, SSTQ (Flat-R with optimized codebook), SSTQ (Flat-R with uniform codebook), and SSTQ (Metric-Aware with uniform codebook). Empirical Variance Scaling (Theorem A.1 vs. Theorem 3.2). In this experiment, we isolate the client-to-server gradient transmission step and focus on computing the raw Mean Squared Error (MSE) between the true vector and the reconstructed estimator. We generate a single gradient vector as g∼(0,Id)g (0,I_d) and normalize it to have norm C=0.2C=0.2. We pass the same vector g into each algorithm, which quantizes the vector, adds LDP noise, and reconstructs an estimated vector g g. We sweep the dimension d over 100, 500, 1000, 5000, 10000\100,\,500,\,1000,\,5000,\,10000\ and plot the MSE [‖g−g^‖22]E[\|g- g\|_2^2] versus d on a log-log scale, by averaging over 1000 independent trials per dimension. All methods use per-round privacy parameter ε=3 =3 and bit budget b=8b=8 (codebook size M=28=256M=2^8=256). The 95% confidence intervals are sufficiently narrow that they are not visually discernible on the log-log scale, reflecting the reliability of the Monte Carlo estimates at this sample size. Figure 2: MSE versus dimension for all methods (per-round ε=3 =3, b=8b=8, M=256M=256, C=0.2C=0.2). Flat-R variants are computed exactly (no Monte Carlo); other methods use 1000 MC trials with 95% confidence bands. The results, reported in Figure 2, confirm the theoretical predictions. vqSGD exhibits devastating cubic O(d3/ε2)O(d^3/ ^2) scaling, with MSE growing from ≈561≈ 561 at d=100d=100 to ≈4.4×108≈ 4.4× 10^8 at d=10,000d=10,000—an increase consistent with the cubic ratio. In contrast, PrivUnit, SQKR, and SSTQ (Metric-Aware) all exhibit linear scaling in d, consistent with the O(d/ε2)O(d/ ^2) bound of Theorem 3.2. Among these, SSTQ (Metric-Aware) achieves the lowest MSE across all dimensions (≈2.0≈ 2.0 at d=100d=100 and ≈171≈ 171 at d=10,000d=10,000), followed by SQKR (≈4.2≈ 4.2 to ≈328≈ 328) and PrivUnit (≈2.9≈ 2.9 to ≈767≈ 767). The two Flat-R variants exhibit substantially higher MSE, now revealed by the exact second-moment computation. SSTQ (Flat-R, uniform codebook) has MSE ranging from ≈446≈ 446 at d=100d=100 to ≈35,746≈ 35,746 at d=10,000d=10,000, reflecting the O(M2)O(M^2) variance inflation from the R debiasing scalar at large M=256M=256. SSTQ (Flat-R, optimized codebook) reduces this to ≈53≈ 53 at d=100d=100 and ≈5,072≈ 5,072 at d=10,000d=10,000—a 77–8×8× improvement over the uniform variant, confirming that codebook optimization mitigates but does not eliminate the R variance. Both Flat-R variants still incur MSE far above the Metric-Aware variant (by 2727–30×30×), demonstrating the decisive advantage of the Metric-Aware Discrete Laplace mechanism in eliminating the exponential 2b2^b dependence. Comparison of LDP mechanisms for linear regression across varying dimensions. We study the convergence of distributed stochastic gradient descent (SGD) on a synthetic least-squares problem with objective L(θ)=12n‖Aθ−b‖22,L(θ)= 12n\|Aθ-b\|_2^2\,, where θ∗∈ℝdθ^* ^d denotes the ground-truth parameter. The design matrix A∈ℝn×dA ^n× d has entries drawn i.i.d. from (0,1/d)N(0,1/d), ensuring stable conditioning across dimensions. We generate θ∗∼(0,Id)θ^* (0,I_d) and set b=Aθ∗b=Aθ^*, yielding a realizable model. We simulate a federated setting with n=4,000n=4,000 samples distributed uniformly across W=200W=200 workers. Each worker computes local gradients on batches of size 2020 over T=100T=100 communication rounds. Gradients are clipped to ‖g‖2≤C=1\|g\|_2≤ C=1, then privatized and transmitted to the server, which performs aggregation and updates using a constant step size η=0.5η=0.5. Performance is measured by the squared estimation error ‖θt−θ∗‖22\| _t-θ^*\|_2^2. All private methods operate under pure ε -LDP with per-round ε=3 =3. We first evaluate convergence at bit budget b=4b=4 across dimensions d∈100,200,500d∈\100,200,500\ (Figure 3). For methods requiring frame representations (SSTQ and SQKR), we use an overcomplete construction with redundancy N=2.5dN=2.5\,d. Figure 3: Distributed SGD convergence under ε -LDP (ε=3 =3, b=4b=4). Comparison of the two variants of our proposed framework—SSTQ (Flat-R) and SSTQ (Metric-Aware)—against other vector quantization algorithms across d∈100,200,500d∈\100,200,500\. Figure 3 illustrates distributed least-squares SGD under pure ε -LDP (ε=3 =3). Consistent with the observations in Section 7, vqSGD exhibits unstable optimization behavior that becomes more pronounced as the dimension increases: the model error increases monotonically, reaching ≈2685≈ 2685 at d=500d=500 compared to ≈432.6≈ 432.6 for the clean baseline. While reducing the learning rate can stabilize individual updates, by Remark F.1 this trades variance reduction against slower optimization: the Θ(d3/ϵ2) (d^3/ε^2) variance multiplier of vqSGD would require a proportionally larger number of communication rounds to converge, rendering it impractical in high dimensions. In contrast, the 1-sparse structure of SSTQ mitigates this dependence on the ambient dimension, resulting in stable and efficient convergence. At b=4b=4 (moderate codebook size M=16M=16), the Flat-R variants converge closely to the clean baseline, with SSTQ (Flat-R, uniform codebook) achieving final error ≈132.8≈ 132.8 at d=200d=200 versus ≈131.7≈ 131.7 for the clean update—a modest overhead. SSTQ (Flat-R, optimized codebook) achieves final error ≈140.5≈ 140.5 at d=200d=200. The Metric-Aware variant converges to a slightly higher error floor of ≈162≈ 162 at d=200d=200, consistent with the non-zero bias ζ2ζ^2 introduced by the identity decoder (Corollary 6.4). PrivUnit tracks the clean baseline most closely (≈130.0≈ 130.0), as it incurs no quantization overhead. Comparison of SSTQ variants across codebook sizes. To isolate the effect of codebook size on the Flat-R variance, we fix d=200d=200 and compare convergence at b=4b=4 (M=16M=16) versus b=8b=8 (M=256M=256) in Figure 4. Figure 4: Flat-R explosion versus Metric-Aware stability at d=200d=200, ε=3 =3. Left: Low bit-width (b=4b=4, M=16M=16). Right: Dense bit-width (b=8b=8, M=256M=256). As shown in Figure 4, increasing the codebook size from M=16M=16 to M=256M=256 causes a dramatic degradation in both Flat-R variants. SSTQ (Flat-R, uniform codebook) sees its final error grow from ≈132.8≈ 132.8 to ≈271.6≈ 271.6 (2.0×2.0× increase), while SSTQ (Flat-R, optimized codebook) grows from ≈140.5≈ 140.5 to ≈226.7≈ 226.7 (1.6×1.6× increase). This is consistent with the predicted O(M2)O(M^2) scaling of the unbiasing factor: the debiasing scalar 1/(p−q)=(eε+M−1)/(eε−1)1/(p-q)=(e +M-1)/(e -1) grows from ≈1.8≈ 1.8 at M=16M=16 to ≈14.4≈ 14.4 at M=256M=256, inflating the variance quadratically. In stark contrast, SSTQ (Metric-Aware) remains essentially unchanged, with final error growing only marginally from ≈162.0≈ 162.0 to ≈163.7≈ 163.7. This stability arises because the Metric-Aware Discrete Laplace mechanism does not require the uniform debiasing correction—its noise distribution concentrates naturally around the true quantization level regardless of M. This behavior highlights the limitations of Flat-R in dense quantization regimes and motivates the use of Metric-Aware estimators for maintaining stable performance at larger codebook sizes.