1 Introduction↩︎

A growing class of high-stakes applications would benefit from a language model trained on data that cannot be centralized (regulation, consent, institutional policy) and exchanged over uplinks too narrow to carry full-precision gradients or weights. As a running example, each hospital in a clinical consortium fine-tunes a small local language model (weak in isolation) on its private patient records and exchanges only bandwidth-limited summaries over an existing low-rate WAN. Prior work [1] sets up the full pipeline (federated training plus inference-time conformal coverage) and proves a high-probability KL-consistency rate for the Federated Probe-Logit Distillation (FPLD) training-time protocol, in which each node transmits scalar-quantized logits on a public probe set and the aggregator distills a global parametric student.

1.0.0.1 Statistical reading of the rate.

The FPLD upper bound recapped in Section 3 (Theorem 1) takes the form \(O\bigl(d/(Kn) + \rho\sqrt{V \log(V/\delta)/m} + K^{-1} \cdot 2^{-2B/V}\bigr)\) plus optimization slack, with \(K\) nodes, \(n\) samples per node, probe set size \(m\), vocabulary size \(V\), and per-node uplink budget \(B\). The first two terms are classical: \(d/(Kn)\) is the pooled parametric-MLE rate on \(Kn\) effective samples, and \(\rho\sqrt{V \log(V/\delta)/m}\) is a Rademacher-type uniform-convergence rate for the aggregator’s softmax-linear fit on \(m\) probe contexts, with \(\rho\) the Radon–Nikodym ratio that pays for probing under a public marginal \(Q\) instead of \(P^\star_X\). The bandwidth term \(K^{-1} \cdot 2^{-2B/V}\) is the new statistical object: \(K\)-fold averaging of independent dithered errors at the aggregator delivers the \(1/K\) pickup, the same as in classical distributed estimation under communication constraints [2]–[5]. The cited prior work leaves two questions about this piece open: (i) is the rate tight as a matching lower bound, or could a smarter encoder strictly improve? (ii) when uplinks are heterogeneous and node \(i\) transmits at most \(B_i\) bits, what is the optimal allocation of a fixed aggregate budget \(B_{\mathrm{tot}} = \sum_i B_i\)? The present paper answers both via a single technical idea, the softmax-Hessian trace bound \(\mathrm{tr}(H_\mathrm{soft}) \le 1\) applied to the exact cumulant expansion of softmax-KL, which underpins both the upper bound (Theorem 1) and a matching lower bound for the dithered construction (pinning the rate at \(\Theta(K^{-1} \cdot 2^{-2B/V})\)); the same machinery extends per-node to give a closed-form optimal allocation under heterogeneous budgets with an adaptive plug-in variant.

1.0.0.2 Contributions.

1. Matching lower bound and multi-round achievability (Theorems 2 and 3). The dithered FPLD construction has a matching lower bound \(\Omega(K^{-1} \cdot 2^{-2B/V})\) under non-degeneracy (Theorem 2), pinning the single-round bandwidth-axis rate of the construction at \(\Theta(K^{-1} \cdot 2^{-2B/V})\). Sequential refinement with nested/scaled residual quantizers sharpens the achievable rate to \(O(K^{-1} \cdot 2^{-2TB/V})\) in \(T\) rounds; vanilla FPLD’s bandwidth term is \(T\)-independent and is therefore strictly suboptimal for every \(T > 1\), identifying a concrete protocol-design improvement available within the same scalar-quantization channel (Theorem 3).

2. Heterogeneous-bandwidth upper bound and optimal allocation (Theorems 4 and 5). The FPLD upper bound generalizes to per-node \(B_i\), with the bandwidth term becoming \((c_3/K^2)\sum_i 2^{-2B_i/V}\). Subject to \(\sum_i B_i \le B_{\mathrm{tot}}\) and per-node weights \(w_i\), the minimizer is a log-tilted water-filling \(B_i^\star = B_{\mathrm{tot}}/K + (V/2)\log_2(w_i / \bar w_g)\) with \(\bar w_g\) the geometric mean of the weights.

3. Adaptive plug-in allocation (Corollary 1, Algorithm 2). A two-stage protocol estimates the weights \(\hat{w}_i\) from \(T_0\) warm-up rounds at the uniform pilot allocation and then runs the plug-in water-filling on \(\hat{w}_i\). The resulting allocation is \(1 + O(\sqrt{\log(K/\delta)/(m T_0)})\)-suboptimal in the bandwidth term with high probability, requiring no extra channel and no a-priori knowledge of \(L_{\ell,i}\).

4. Numerical illustrations. On a synthetic n-gram FPLD simulator, empirical expected KL is sandwiched between the upper and lower bounds across both \(K\) and \(B\) sweeps (Figure 3); the optimal allocation strictly dominates uniform and an inverse-weighted baseline under heterogeneous per-node clip levels (Figure 4).

1.0.0.3 Scope.

This is a focused statistical study of FPLD’s training-time KL rate. Prior work [1] develops the full FPLD protocol (recapped as Algorithm 1), the inference-time conformal coverage results (FC-RAG), and the proof of Theorem 1. Inference-time coverage, real-LM evaluation, privacy, and Byzantine robustness are out of scope for this paper. The multi-round case is treated as an upper-bound/achievability result for nested/scaled residual quantization (Section 4.1); unrestricted multi-round minimax lower bounds are left open, alongside extension to non-parametric students and a streaming-update variant of Algorithm 2 for non-stationary weights.

2 Setup↩︎

2.0.0.1 Vocabulary, contexts, predictors.

Let \(\mathcal{V}\) be a finite vocabulary of size \(V\) and \(\mathcal{X} = \mathcal{V}^{\le L}\) contexts of length at most \(L\). A predictor is a map \(\mathcal{X} \to \Delta(\mathcal{V})\), where \(\Delta(\mathcal{V})\) is the simplex over tokens.

2.0.0.2 Nodes and data.

\(K\) nodes; node \(i \in \{1, \dots, K\}\) holds an i.i.d.dataset \(\mathcal{D}_i = \{(x_j^{(i)}, y_j^{(i)})\}_{j=1}^n\) drawn from \(P^\star\) on \(\mathcal{X} \times \mathcal{V}\). Raw data never leaves a node.

2.0.0.3 Public probe set.

\(X_{\mathrm{probe}} = \{x^{(l)}\}_{l=1}^m\), i.i.d.from a probe marginal \(Q\) that covers \(P^\star_X\) in the bounded-Radon–Nikodym sense \(\rho = \operatorname{ess\,sup}_x dP^\star_X / dQ < \infty\).

2.0.0.4 Communication.

Bandwidth is charged on uplink only. In the homogeneous case (Section 3), every node transmits at most \(B\) bits per probe context per round; in the heterogeneous case (Section 5), node \(i\) transmits at most \(B_i\) bits. Downlink broadcast of the aggregated student is uncharged, matching standard federated convention.

2.0.0.5 Estimand.

The aggregator produces a global student \(\hat{P} : \mathcal{X} \to \Delta(\mathcal{V})\) approximating \(P^\star\); the risk is \(\mathbb{E}_{X \sim P^\star_X}\bigl[\mathrm{KL}(P^\star(\cdot \mid X) \,\|\, \hat{P}(\cdot \mid X))\bigr]\).

3 FPLD Protocol and Upper-Bound Recap↩︎

Federated Probe-Logit Distillation (FPLD) replaces gradient or weight exchange with the exchange of quantized logits on a public probe set. All nodes initialize from a shared pretrained base \(\hat{P}^{(0)}\). In each of \(T\) rounds, a node fine-tunes locally on its private dataset, evaluates its updated model on the probe set, and transmits a per-coordinate scalar-quantized logit vector at \(B/V\) bits per coordinate. The aggregator averages the \(K\) quantized logit vectors coordinate-wise and distills a global student on the averaged logits, then broadcasts the student back to all nodes. Total uplink is \(O(K T m B)\); downlink is uncharged.

We adopt six assumptions on the parametric family (2), the probe distribution (3), homogeneous data (4), local-optimization slack (5), the uniform quantization channel (6), and the aggregator’s distillation fit (7); full statements are in Appendix 8.

3.0.0.1 Interpretation.

The four terms reflect, respectively, pooled parametric-MLE convergence on the \(Kn\) effective samples; probe generalization at rate \(1/\sqrt m\) with a coverage penalty \(\rho\); exponentially decaying quantization distortion in bits-per-coordinate; and controllable optimization slack. The \(1/K\) prefactor of the quantization term comes from averaging \(K\) independent dithered errors at the aggregator; the factor of \(V\) one might naively expect from summing per-coordinate variances is absorbed by the softmax-Hessian trace bound (Appendix 9). The bandwidth term depends on \(B\) but not on \(T\): vanilla FPLD does not exploit multi-round refinement to sharpen its quantization rate. Section 4.1 shows this is strictly suboptimal for \(T > 1\).

3.0.0.2 What this paper contributes on top.

Theorem 1 is the upper-bound half of an analysis already developed in prior work [1]. The present paper extends it along two axes: a matching lower bound for the dithered FPLD construction plus a multi-round sequential-refinement achievability result (Section 4, Theorems 2 and 3); and a heterogeneous-bandwidth generalization with closed-form optimal allocation and an adaptive plug-in variant (Section 5, Theorems 4 and 5, Corollary 1).

4 Matching Lower Bound and Multi-Round Achievability↩︎

Given Theorem 1’s upper bound at \(c_3 K^{-1} \cdot 2^{-2B/V}\), two natural questions follow: (i) is this rate tight as a matching lower bound, and (ii) can it sharpen further across multiple rounds? We answer both within the dithered-FPLD construction. Theorem 2 establishes a single-round matching lower bound, pinning the bandwidth-axis rate of the construction at \(\Theta(K^{-1} \cdot 2^{-2B/V})\). Theorem 3 gives a multi-round achievability rate \(O(K^{-1} \cdot 2^{-2TB/V})\) via sequential refinement with nested/scaled residual quantizers; vanilla FPLD’s bandwidth term is \(T\)-independent and is therefore strictly suboptimal for every \(T > 1\), identifying a concrete protocol-design improvement available within the same scalar-quantization channel.

4.0.0.1 Protocol class.

The single-round FPLD-class protocols \(\mathcal{P}_B^{\mathrm{FPLD}}\) consist of those in which each node \(i\) observes its local dataset \(\mathcal{D}_i\) and the public probe set \(X_{\mathrm{probe}}\), applies a per-coordinate clipped scalar quantizer at \(B/V\) bits with subtractive dithering (Assumption 6), and the aggregator forms an unbiased \(K\)-fold average. The target class \(\mathcal{P}^\star\) is the parametric family of conditional distributions \(P^\star\) for which some \(\theta^\star \in \mathrm{int}(\Theta)\) realizes \(P^\star = P_{\theta^\star}\) and the per-coordinate logit values lie in \([-L_\ell, L_\ell]\). Both match the operating regime of Theorem 1. An unconditional minimax lower bound over the larger class \(\mathcal{P}_B\) of arbitrary \(B\)-bit-per-node protocols is left open (Section 7).

Combined with Theorem 1’s upper bound, the bandwidth-axis rate of the dithered FPLD construction is \(\Theta(K^{-1} \cdot 2^{-2B/V})\) up to absolute constants: \(c_{\mathrm{lb}} = c_p L_\ell^2 / 12\) on the lower-bound side and \(c_3\) on the upper-bound side. The proof, in Appendix 9, is a direct computation of the dither variance composed with the softmax-KL cumulant expansion and the trace bound \(\mathrm{tr}(H_\mathrm{soft}) \le 1\).

4.1 Multi-round sequential-refinement achievability↩︎

Theorem 2’s rate is for a single round. Using the bit budget across rounds with nested/scaled residual quantization sharpens the exponent linearly in \(T\).

4.1.0.1 Multi-round protocol class.

Let \(\mathcal{P}_{B,T}^{\mathrm{FPLD\text{-}ref}}\) denote the class of \(T\)-round FPLD-class protocols in which each round transmits \(B\) bits per node and each node uses a nested/scaled residual quantizer: in round \(t\), the quantizer step size is scaled to the residual range from round \(t-1\), equivalently producing an effective \((TB/V)\)-bit scalar quantizer per coordinate after \(T\) rounds. A fixed-step residual quantizer that does not rescale across rounds stalls at \(O(K^{-1} \cdot 2^{-2B/V})\) regardless of \(T\); the rescaling is what unlocks the multi-round gain.

The take-away is operational: the \(T\)-fold sharpening requires only a change in the per-round residual encoder, not a change in the bit budget or channel structure. Vanilla FPLD as specified in Algorithm 1 does not exploit this; sequential refinement does. The proof iterates the single-round bound on the residual at each round (Appendix 9.4).

5 Heterogeneous Bandwidth and Optimal Allocation↩︎

The upper bound recapped in Section 3 assumes a uniform per-node bandwidth budget \(B\). Real federated deployments give different nodes different uplinks: hospitals on a metropolitan WAN have one rate; a regional clinic on satellite has another. We drop the uniform-\(B\) assumption and let node \(i\) transmit at most \(B_i\) bits per probe context, then ask how the upper bound generalizes and how a network operator should allocate a fixed aggregate budget \(\sum_i B_i \le B_{\mathrm{tot}}\).

Assumption 6 (uniform scalar quantization) is replaced by a per-node version.

5.0.0.1 Sanity check.

If \(B_i \equiv B\) for all \(i\), the heterogeneous bandwidth term reduces to \(\frac{c_3}{K^2}\cdot K \cdot 2^{-2B/V} = c_3 \tfrac{1}{K} 2^{-2B/V}\), recovering Theorem 1’s sharpened form. The conservative Euclidean route would give \((c_3' V/K^2)\sum_i 2^{-2B_i/V}\) with \(c_3' = C_q/(2\lambda_{\min}(I(\theta^\star)))\), a factor of \(V \cdot c_3'/c_3 = V/\lambda_{\min}(I(\theta^\star))\) looser than the trace-sharpened form stated here (see App. 9.5 for the comparison).

With the upper bound generalized, the natural question is: under a fixed total uplink budget \(B_{\mathrm{tot}} = \sum_i B_i\), how should an operator allocate bits across nodes? Theorem 5 answers this for the quantization term of Theorem 4; the statistical and probe-generalization terms do not depend on the \(B_i\).

5.0.0.2 Interpretation.

The allocation is \(\log_2\)-tilted by the weight ratio: a node with double the weight gets \(V/2\) extra bits. Because the weight \(w_i\) in our setting tracks per-node logit variance, the allocation gives more bits to noisier nodes. This is the same direction as classical reverse-water-filling for distortion-rate optimization, applied per-node rather than per-source.

5.0.0.3 What the weights \(w_i\) should be.

Theorem 5 treats \(w_i\) as given. The natural choice in our setting is the per-node contribution to the quantization-term constant of Theorem 4. Under Assumption 1’s uniform clip \(L_\ell\), every node has \(w_i = 1\) and the optimal allocation is uniform. If clipping levels differ across nodes (e.g., a node with calibrated logit range \(L_{\ell,i}\)), then \(w_i \propto L_{\ell,i}^2\) and the bit allocation tilts proportionally. We use this clip-variance formulation in the experiments (Section 6). The proof of Theorem 5 is one Lagrangian (Appendix 9.6).

5.1 Adaptive bandwidth allocation↩︎

Theorem 5 treats the per-node weights \(w_i\) as inputs. In practice, an operator rarely knows them in advance: per-node clip levels and logit-magnitude profiles vary across deployments and across rounds. We close this gap with a two-stage protocol that estimates \(w_i\) from warm-up-round quantized probe logits and then applies the plug-in water-filling allocation. The construction requires no extra channel and no a-priori knowledge of \(L_{\ell,i}\).

5.1.0.1 Estimator.

Run the protocol for \(T_0 \ge 1\) warm-up rounds at the uniform pilot allocation \(B_i = B_{\mathrm{tot}}/K\). The aggregator records the received quantized probe logits \(\tilde{\ell}_{i,v}^{(l,t)}\) and forms \[\hat{w}_i \;=\; \frac{1}{T_0\, m\, V} \sum_{t=1}^{T_0}\sum_{l=1}^{m}\sum_{v=1}^{V} \bigl(\tilde{\ell}_{i,v}^{(l,t)}\bigr)^2, \qquad w_i \;:=\; \mathbb{E}\!\left[\tfrac{1}{V}\|\tilde{\ell}_i\|_2^2\right].\] This estimates the population per-node second moment \(w_i\) (the quantity tracked by “weight \(\propto\) logit variance” in the discussion after Theorem 5) entirely from data the aggregator already receives under Assumption 1.

5.1.0.2 Proof sketch.

(i) Relative-error transfer. Direct substitution of \(\hat{B}_i^\star\) into the per-node objective gives \(F(\hat{B}^\star)/F(B^\star) = K^{-1}\sum_i (w_i/\hat{w}_i)(\hat{w}_g/\bar w_g) \le 1 + 2\eta + 4\eta^2\) when \(|\hat{w}_i - w_i| \le \eta\, w_i\) holds uniformly in \(i\) (full derivation in Lemma 2). (ii) Concentration. Let \(S_{i,t,l} := \tfrac{1}{V}\sum_v (\tilde{\ell}_{i,v}^{(l,t)})^2\) be the per-context block average for node \(i\) at round \(t\) and probe \(l\), taking values in \([0, R_\ell^2]\) with post-quantization range \(R_\ell := L_\ell(1 + 2^{-B_{\mathrm{tot}}/(KV)}) \le 2 L_\ell\) (this \(R_\ell\) absorbs the subtractively dithered quantizer’s worst-case overshoot beyond the input clip). The \(\{S_{i,t,l}\}\) are i.i.d.across \((t, l)\) for each fixed \(i\) by Assumption 1 and the i.i.d.probe draw, so Hoeffding plus a \(K\)-fold union bound gives \(|\hat{w}_i - w_i| \le R_\ell^2 \sqrt{\log(2K/\delta)/(2 m T_0)}\) uniformly. Composing (i) and (ii) yields the claim; the full proof is in Appendix 9.7.

6 Numerical Illustrations↩︎

We test Theorems 1, 2, 4, and 5 on a synthetic n-gram FPLD simulator. Each node observes a noisy logit estimate of a fixed common \(P^\star\) over \(V = 256\) tokens (estimation noise variance \(1/n\) per coordinate, \(n = 30{,}000\)), and transmits scalar-quantized logits at \(B/V\) (or \(B_i/V\)) bits per coordinate via a subtractively dithered uniform quantizer. The aggregator averages quantized logits coordinate-wise and emits the softmax student. Empirical KL is reported across \(30\) seeds per point for Figure 3 and \(100\) for Figure 4; both use a single fixed \(P^\star\) so per-axis variability isolates the bandwidth effect. The simulator is a controlled sandbox designed to verify the predicted rate shapes (\(1/K\) shrinkage, \(2^{-2B/V}\) decay, water-filling dominance) on a setting where the dithered-quantization channel is exact; end-to-end evaluation on real language-model training is out of scope (§ 1).

6.0.0.1 Bound bracketing (Figure 3).

Empirical FPLD KL is bracketed by Theorem 1’s upper bound and Theorem 2’s matching lower bound, both at the \(K^{-1} \cdot 2^{-2B/V}\) rate: the \(K\)-sweep at \(B/V = 4\) shows the predicted \(1/K\) shrinkage, and the \(B\)-sweep at \(K = 4\) shows the predicted exponential decay in \(B/V\) (KL roughly quartering with each additional bit per coordinate). The bracketing is the qualitative claim; the specific multiplicative constants \(c_3\) and \(c_{\mathrm{lb}}\) are illustrative.

6.0.0.2 Allocation policy (Figure 4).

With \(K = 4\) nodes and heterogeneous per-node clip levels \(L = (1, 1, 4, 4)\) (weights \(w_i = L_i^2 = (1, 1, 16, 16)\), mirroring the running example with two metropolitan-WAN hospitals at wider uplink paired with two satellite clinics at narrower uplink), the optimal allocation (Theorem 5) strictly dominates uniform at every aggregate budget where bandwidth matters: at \(B_{\mathrm{tot}}/V = 8\) the optimal achieves KL \(\approx 1.1{\times}10^{-2}\), roughly half of uniform’s \(2.3{\times}10^{-2}\), and the gap persists at higher budgets. Inverse-weighted plateaus at \(\approx 8{\times}10^{-2}\) across the full range (roughly an order of magnitude above the optimal), validating that the qualitative direction of Theorem 5 (more bits to higher-variance nodes) is correct.

7 Discussion↩︎

7.0.0.1 Position vs distributed estimation.

Theorems 2 and 3 parallel the classical lower-bound and achievability program for communication-constrained distributed estimation [2]–[5], specialized here to the per-coordinate scalar-quantization channel on logit vectors over a shared probe set. The technique differs: we apply the softmax-Hessian trace bound to the exact cumulant expansion under independent mean-zero dithering. Our sequential-refinement achievability improves the bandwidth-axis rate linearly in \(T\) within the FPLD-class scheme; an unconditional minimax lower bound over arbitrary \(B\)-bit-per-node protocols remains open.

7.0.0.2 Position vs federated distillation.

FedFD [6] and FedDF [7] demonstrate federated distillation in practice but prove no rate; our heterogeneous-bandwidth result (Theorem 4) closes that gap and pairs it with a closed-form allocation rule.

8 Assumption block↩︎

9 Proofs↩︎

This appendix collects the proofs deferred from the main text. § 9.1 states the softmax-Hessian trace bound used throughout. § 9.2 derives the bandwidth-term form of Theorem 1 via the trace bound (paralleling the analogous derivation in the companion paper [1]). The remaining subsections follow the order of the corresponding statements in the body: § 9.3 proves the matching lower bound of Theorem 2; § 9.4 proves the sequential-refinement achievability of Theorem 3; § 9.5 proves the heterogeneous-bandwidth upper bound of Theorem 4; § 9.6 proves the optimal-allocation closed form of Theorem 5; § 9.7 proves the adaptive-allocation Corollary 1.

9.1 Softmax-Hessian trace bound↩︎

9.2 Bandwidth-term form of Theorem 1↩︎

For the FPLD scheme under Assumption 6, we derive the trace-sharpened upper bound directly from the exact softmax-KL formula. Throughout the derivation we assume the small-error condition \[\label{eq:SE} \boldsymbol{(SE)}\qquad 2^{-B/V}(\log V)^{3/2}/\sqrt{K} \;\le\; c_0(L_\ell, C),\tag{1}\] where \(C\) is the cubic-remainder constant depending only on \(\|H_\mathrm{soft}\|_\mathrm{op} \le 1/2\) and \(c_0(L_\ell, C)\) is chosen so the cumulant-expansion cubic remainder is dominated by the quadratic term. Use the exact identity: \[{!}{\displaystyle \begin{align} \mathrm{KL}(\mathrm{softmax}(\ell^\star) \,\|\, \mathrm{softmax}(\ell^\star + \eta)) &= \log Z(\ell^\star + \eta) - \log Z(\ell^\star) - p^{\star\top}\eta && \bigl[\,\parbox[t]{0.32\linewidth}{\raggedright direct calculation from KL definition}\,\bigr] \\ &= \log \mathbb{E}_{Y \sim p^\star}[e^{\eta_Y}] - p^{\star\top}\eta && \bigl[\,\parbox[t]{0.32\linewidth}{\raggedright Z(\ell^\star + \eta)/Z(\ell^\star) = \mathbb{E}_Y[e^{\eta_Y}]}\,\bigr] \end{align} }\] Set \(\eta = \bar\varepsilon = (1/K)\sum_i \varepsilon_i\) and take expectation over \(\bar\varepsilon\): \[\begin{align} \mathbb{E}_{\bar\varepsilon}[\mathrm{KL}] &= \mathbb{E}_{\bar\varepsilon}\!\bigl[\log \mathbb{E}_Y[e^{\bar\varepsilon_Y}]\bigr] - p^{\star\top} \mathbb{E}_{\bar\varepsilon}[\bar\varepsilon] && [\text{linearity}] \\ &= \mathbb{E}_{\bar\varepsilon}\!\bigl[\log \mathbb{E}_Y[e^{\bar\varepsilon_Y}]\bigr] && [\mathbb{E}[\bar\varepsilon] = 0 \text{ by Assumption~\ref{ass:A5}}] \end{align}\] Cumulant-expand the log-MGF \(M(\eta) := \log \mathbb{E}_Y[e^{\eta_Y}]\): \[\begin{align} M(\eta) &= \mathbb{E}_Y[\eta_Y] + \tfrac{1}{2}\mathrm{Var}_Y(\eta_Y) + \kappa_3(\eta) && \bigl[\,\parbox[t]{0.32\linewidth}{\raggedright cumulant expansion: mean + half-variance + cubic remainder}\,\bigr] \\ &= p^{\star\top}\eta + \tfrac{1}{2}\, \eta^\top H_\mathrm{soft}(p^\star)\, \eta + \kappa_3(\eta) && [\mathrm{Var}_Y(\eta_Y) = \eta^\top H_\mathrm{soft}(p^\star)\, \eta] \end{align}\] where \(|\kappa_3(\eta)| \le C\|\eta\|_\infty^3\) for an absolute constant \(C\) depending only on \(\|H_\mathrm{soft}\|_\mathrm{op} \le 1/2\).

Take expectation: \[\begin{align} \mathbb{E}_{\bar\varepsilon}[M(\bar\varepsilon)] &= p^{\star\top}\mathbb{E}[\bar\varepsilon] + \tfrac{1}{2}\mathbb{E}\!\bigl[\bar\varepsilon^\top H_\mathrm{soft}(p^\star)\bar\varepsilon\bigr] + \mathbb{E}[\kappa_3(\bar\varepsilon)] && [\text{linearity}] \\ &= 0 + \tfrac{1}{2}\, \mathrm{tr}\!\bigl(H_\mathrm{soft}(p^\star) \cdot \mathrm{Cov}(\bar\varepsilon)\bigr) + \mathbb{E}[\kappa_3(\bar\varepsilon)] && [\mathbb{E}[\eta^\top A \eta] = \mathrm{tr}(A \cdot \mathrm{Cov}(\eta)) \text{ for } \mathbb{E}[\eta] = 0] \end{align}\] Bound the dither covariance: \[\begin{align} \mathrm{Cov}(\bar\varepsilon)_{vv} &= \mathrm{Var}\!\Bigl(\tfrac{1}{K}\textstyle\sum_{i=1}^K \varepsilon_{i,v}\Bigr) && [\text{average across K nodes}] \\ &= \tfrac{1}{K^2}\, \textstyle\sum_{i=1}^K \mathrm{Var}(\varepsilon_{i,v}) && [\text{independence across nodes; no cross terms}] \\ &\le \tfrac{1}{K^2}\cdot K \cdot C_q \cdot 2^{-2B/V} && [\text{Assumption~\ref{ass:A5} per-coordinate dither variance bound}] \\ &= \tfrac{C_q}{K}\cdot 2^{-2B/V} && [\text{simplify}] \\ \mathrm{Cov}(\bar\varepsilon)_{vv'} &= 0 \quad \text{for } v \ne v' && [\text{independence across coordinates by Assumption~\ref{ass:A5}}] \end{align}\] So \(\mathrm{Cov}(\bar\varepsilon) \preceq \sigma^2 I_V\) with \(\sigma^2 := C_q \cdot 2^{-2B/V}/K\).

Apply the trace bound: \[\begin{align} \mathrm{tr}\!\bigl(H_\mathrm{soft}(p^\star) \cdot \mathrm{Cov}(\bar\varepsilon)\bigr) &\le \sigma^2 \cdot \mathrm{tr}(H_\mathrm{soft}(p^\star)) && \bigl[\,\parbox[t]{0.32\linewidth}{\raggedright \mathrm{tr}(AB) \le \mathrm{tr}(A)\cdot \|B\|_\mathrm{op} for A \succeq 0; \|\mathrm{Cov}(\bar\varepsilon)\|_\mathrm{op} \le \sigma^2}\,\bigr] \\ &\le \sigma^2 && [\text{Lemma~\ref{lem:soft-trace}: } \mathrm{tr}(H_\mathrm{soft}) \le 1] \end{align}\] Bound the cubic remainder: \[\begin{align} \mathbb{E}\|\bar\varepsilon\|_\infty^3 &\le C' \sigma^3 (\log V)^{3/2} && [\text{maximum of V sub-Gaussians; standard tail bound}] \\ |\mathbb{E}[\kappa_3(\bar\varepsilon)]| &\le C \cdot C' \sigma^3 (\log V)^{3/2} && [\text{cubic remainder absolute bound}] \\ &= C'' \cdot \tfrac{(\log V)^{3/2}}{K^{3/2}}\cdot 2^{-3B/V} && [\sigma = \sqrt{C_q/K}\cdot 2^{-B/V}] \end{align}\] Combine: \[\begin{align} \mathbb{E}_{\bar\varepsilon}[\mathrm{KL}] &= \tfrac{1}{2}\, \mathrm{tr}\!\bigl(H_\mathrm{soft}(p^\star) \cdot \mathrm{Cov}(\bar\varepsilon)\bigr) + \mathbb{E}[\kappa_3(\bar\varepsilon)] && [\text{from the expectation chain above}] \\ &\le \tfrac{1}{2}\sigma^2 + C''\, \tfrac{(\log V)^{3/2}}{K^{3/2}}\cdot 2^{-3B/V} && [\text{trace bound + cubic remainder bound}] \\ &= \tfrac{C_q}{2K}\cdot 2^{-2B/V} + O\!\Bigl(\tfrac{(\log V)^{3/2}}{K^{3/2}}\cdot 2^{-3B/V}\Bigr) && [\text{substitute } \sigma^2 = C_q \cdot 2^{-2B/V}/K] \end{align}\] Setting \(c_3 = C_q/2\) recovers the theorem statement under (SE). The \(V\)-factor cancellation arises directly from \(\mathrm{tr}(H_\mathrm{soft}) \le 1\) in the second step of the trace bound; in contrast, the conservative Euclidean-logit bound uses \(\mathbb{E}\|\bar\varepsilon\|_2^2 = V\sigma^2\) and the operator norm \(\|H_\mathrm{soft}\|_\mathrm{op} \le 1/2\), which produces the \(V/K\) form. 0◻

9.3 Proof of Theorem 2↩︎

We prove Theorem 2: under Assumptions 2–7 together with (ND) and (SE’) \(2^{-B/V}(\log V)^{3/2}/\sqrt{K} \le c_0(c_p, L_\ell, C)\) where \(c_0\) is chosen so \(C \cdot \sigma(\log V)^{3/2} \le c_p/4\), the bandwidth contribution of the dithered FPLD construction satisfies \(\mathbb{E}[\mathrm{KL}(P^\star \,\|\, \hat{P}_{\mathrm{FPLD}})]_{\mathrm{bandwidth}} \ge c_p L_\ell^2/(12 K) \cdot 2^{-2B/V}\).

9.3.0.1 Remark on scope.

Theorem 2 is a lower bound for the subtractively dithered FPLD construction (Assumption 6); the unconditional minimax bandwidth-axis lower bound over the larger class \(\mathcal{P}_B\) of arbitrary \(B\)-bit-per-node protocols (alternative quantizers such as biased, vector, learned-codebook, or adaptive ones lie outside Assumption 6) remains open (see § 7).

9.4 Proof of Theorem 3↩︎

Theorem 3 is an achievability statement: sequential refinement with nested/scaled residual quantizers and \(B\) bits per round per node achieves \(O(K^{-1} \cdot 2^{-2TB/V})\). The proof iterates the single-round trace-sharpened upper bound of Theorem 1 over the residual at each round.

9.4.0.1 Setup.

In round \(t \in \{1, \dots, T\}\), each node \(i\) holds the residual \(r^{(t-1)}(X) := \ell^\star(X) - \hat{\ell}^{(t-1)}(X)\), where \(\hat{\ell}^{(0)}(X) = 0\) (or any common initialization) and \(\hat{\ell}^{(t-1)}(X) = (1/K)\sum_i \tilde{r}_i^{(t-1)}(X)\) is the aggregator’s broadcast after round \(t-1\). The nested/scaled quantizer of round \(t\) uses step size \[\begin{align} \Delta_t &= 2 L_\ell^{(t)} \cdot 2^{-B/V} && [\text{rescaled to round-t residual range}] \\ L_\ell^{(t)} &\asymp L_\ell \cdot 2^{-(t-1)B/V} && [\text{residual range after t-1 rounds of refinement}] \end{align}\]

The post-aggregation residual variance per coordinate, \(\sigma_t^2 := \mathrm{Var}(\hat{\ell}^{(t)}_v - \ell^\star_v \mid X)\), satisfies a geometric recursion: \[\begin{align} \sigma_t^2 &\asymp \frac{\Delta_t^2}{12 K} && \bigl[\,\parbox[t]{0.32\linewidth}{\raggedright trace-sharpened upper bound applied to round-t residual, K-fold averaged}\,\bigr] \\ &= \frac{(L_\ell^{(t)})^2}{3 K}\cdot 2^{-2B/V} && [\text{substitute } \Delta_t = 2 L_\ell^{(t)} \cdot 2^{-B/V}] \\ &\asymp \frac{L_\ell^2 \cdot 2^{-2(t-1)B/V}}{3 K}\cdot 2^{-2B/V} && [\text{substitute } L_\ell^{(t)} \asymp L_\ell \cdot 2^{-(t-1)B/V}] \\ &= \frac{L_\ell^2}{3 K}\cdot 2^{-2tB/V} && [\text{combine exponents}] \end{align}\] After \(T\) rounds, \(\sigma_T^2 \asymp L_\ell^2/(3K) \cdot 2^{-2TB/V}\). Applying the trace bound from Lemma 1 to the final aggregated residual: \[{!}{\displaystyle \begin{align} \mathbb{E}\bigl[\mathrm{KL}(P^\star \,\|\, \hat{P}_{\mathrm{seq\text{-}ref}})\bigr]_{\mathrm{bandwidth}} &\le \tfrac{1}{2}\,\sigma_T^2 \cdot \mathrm{tr}(H_\mathrm{soft}) + \text{cubic remainder} && \bigl[\,\parbox[t]{0.32\linewidth}{\raggedright Trace-sharpened cumulant chain (\S~\ref{sec:ssec:trace-upper}) applied at round T}\,\bigr] \\ &\le \tfrac{1}{2}\,\sigma_T^2 + O(\sigma_T^3 (\log V)^{3/2}) && \bigl[\,\parbox[t]{0.32\linewidth}{\raggedright \mathrm{tr}(H_\mathrm{soft}) \le 1}\,\bigr] \\ &= \frac{C_3'}{K}\cdot 2^{-2TB/V} + O\!\Bigl(\tfrac{(\log V)^{3/2}}{K^{3/2}}\cdot 2^{-3TB/V}\Bigr) && \bigl[\,\parbox[t]{0.32\linewidth}{\raggedright substitute \sigma_T^2 = L_\ell^2/(3K) \cdot 2^{-2TB/V}; set C_3' := L_\ell^2/6}\,\bigr] \end{align} }\] Here \(C_3'\) is a possibly different constant from Theorem 1’s \(c_3\), depending only on the same scalar-quantizer / dither convention (the two coincide when \(C_q = L_\ell^2/3\), the standard subtractive-uniform dither variance under Assumption 6, in which case \(C_3' = c_3\)). The vanilla FPLD comparison is the special case where each round re-quantizes the full \(\ell^\star\) at full range \(L_\ell\) (rather than the shrinking residual), so \(\sigma_t^2\) does not decrease across rounds and the bandwidth term stalls at \(L_\ell^2/(6K) \cdot 2^{-2B/V}\) for every \(T\). 0◻

9.4.0.2 Note on protocol class.

The above proof relies on each round being an FPLD-class protocol on the residual, with the quantizer step rescaled to the residual range. A matching unconditional multi-round minimax lower bound over arbitrary \(B\)-bit interactive protocols is not claimed. Within the same scalar-refinement FPLD multi-round class under (ND) and (SE’), Theorem 2’s dither-variance chain applied at round \(T\) gives a fixed-scheme lower bound \(\Omega(K^{-1} \cdot 2^{-2TB/V})\).

9.5 Proof of Theorem 4↩︎

The aggregator’s averaged quantized logits are \(\bar\ell(x) = \tfrac{1}{K}\sum_i \tilde{\ell}_i(x)\) where \(\tilde{\ell}_i = \ell_i + \xi_i\), with \(\ell_i\) the empirical logit produced by node \(i\)’s local optimizer and \(\xi_i\) the dithered quantization noise (zero-mean and independent across nodes/coordinates, Assumption 1). The student \(\hat{P}\) fits the soft-max of \(\bar\ell\) within \(\varepsilon_{\mathrm{fit}}\) (Assumption 7), and local optimizers terminate within \(\varepsilon_{\mathrm{opt}}\) of the local MLE (Assumption 5).

The proof follows the same structure as the homogeneous-bandwidth case (Theorem 1; full derivation in the companion paper [1]), with the sole modification being that the per-node budgets \(B_i\) replace the uniform \(B\) in the bandwidth term. The data, probe-generalization, and distillation-fit terms are inherited unchanged from that derivation. We record below the only step that changes: the cumulant-trace bound on the bandwidth contribution.

9.5.0.1 Cumulant-trace decomposition.

Write \(\bar\ell - \ell^\star = (\bar\ell^{\mathrm{emp}} - \ell^\star) + \bar\xi\), with \(\bar\ell^{\mathrm{emp}} = \tfrac{1}{K}\sum_i \ell_i\) the average of node logits before quantization and \(\bar\xi = \tfrac{1}{K}\sum_i \xi_i\) the averaged dither. By Assumption 1, \(\bar\xi\) is independent of \(\bar\ell^{\mathrm{emp}} - \ell^\star\) and has zero mean. Expanding the softmax-KL via the exact cumulant identity of § 9.2 and taking expectations, \[\mathbb{E}\bigl[\mathrm{KL}(P^\star \,\|\, \hat{P})\bigr] \;=\; \tfrac{1}{2}\,\mathrm{tr}\!\bigl(H_\mathrm{soft}(p^\star) \cdot \mathrm{Cov}(\bar\ell - \ell^\star)\bigr) \;+\; \varepsilon_{\mathrm{opt}} + \varepsilon_{\mathrm{fit}} \;+\; O\!\Bigl(\tfrac{(\log V)^{3/2}}{K^{3/2}}\Bigr).\] By independence and zero-mean of \(\bar\xi\), cross-cumulants vanish at second order and the covariance splits additively: \(\mathrm{Cov}(\bar\ell - \ell^\star) = \mathrm{Cov}(\bar\ell^{\mathrm{emp}} - \ell^\star) + \mathrm{Cov}(\bar\xi)\). The trace pulls through, separating the KL bound into a data-fluctuation contribution and a bandwidth contribution.

9.5.0.2 Term (I): data and probe contributions.

\(\tfrac{1}{2}\,\mathrm{tr}\!\bigl(H_\mathrm{soft}(p^\star) \cdot \mathrm{Cov}(\bar\ell^{\mathrm{emp}} - \ell^\star)\bigr)\) is the same data-fluctuation contribution that appears in the homogeneous case. It is bounded by \(c_1 d/(K n)\) (pooled parametric-MLE convergence on \(K n\) effective samples plus the local quadratic expansion of KL at \(\theta^\star\)) and \(c_2\rho\sqrt{V\log(V/\delta)/m}\) (Rademacher uniform convergence of the softmax-linear class over the \(m\) probe contexts), exactly as in the homogeneous case; the per-node \(B_i\) do not enter this term.

9.5.0.3 Term (II): bandwidth.

Under Assumption 1’s coordinate-wise independence, \(\mathrm{Cov}(\bar\xi)\) is diagonal with \(v\)-th entry \((1/K^2)\sum_{i=1}^K \mathrm{Var}(\xi_{i,v}) \le (1/K^2)\sum_i C_q\,2^{-2B_i/V}\). Hence \(\mathrm{Cov}(\bar\xi) \preceq \sigma^2 I_V\) with \[\sigma^2 \;:=\; \frac{1}{K^2}\sum_{i=1}^{K} C_q\,2^{-2B_i/V}.\] Applying Lemma 1’s trace bound \(\mathrm{tr}(H_\mathrm{soft}) \le 1\) together with the standard inequality \(\mathrm{tr}(AB) \le \|B\|_\mathrm{op}\,\mathrm{tr}(A)\) for \(A \succeq 0\), \[\tfrac{1}{2}\,\mathrm{tr}\!\bigl(H_\mathrm{soft}(p^\star) \cdot \mathrm{Cov}(\bar\xi)\bigr) \;\le\; \frac{\sigma^2}{2} \;=\; \frac{C_q}{2K^2}\sum_{i=1}^{K} 2^{-2B_i/V}.\] Setting \(c_3 = C_q/2\) recovers the bandwidth term \((c_3/K^2)\sum_i 2^{-2B_i/V}\) stated in Theorem 4. The cubic remainder is dominated under (SE) by the same argument as in § 9.2.

Combining Term (I), Term (II), and the slack terms yields the bound stated in Theorem 4. 0◻

9.5.0.4 Remark (heterogeneous clip levels).

The argument extends directly to per-node clip levels \(L_{\ell,i}\) (replacing the uniform \(L_\ell\) in Assumption 1). With per-node dither variance bound \(C_{q,i} = L_{\ell,i}^2/3\), the bandwidth term takes the form \((1/(2K^2))\sum_i C_{q,i}\cdot 2^{-2B_i/V} = (1/(6K^2))\sum_i L_{\ell,i}^2\cdot 2^{-2B_i/V}\). This fits Theorem 5’s objective \((1/K^2)\sum_i w_i\cdot 2^{-2B_i/V}\) with \(w_i = L_{\ell,i}^2\) (an overall constant drops out of the water-filling formula, since it depends on \(w_i\) only through the ratio \(w_i/\bar w_g\)). This is the form tested in Figure 4 with per-node clips \(L_i = (1, 1, 4, 4)\).

9.6 Proof of Theorem 5↩︎

The objective \(F\) is convex in each \(B_i\): it is the sum of decaying exponentials in a positive linear function of \(B_i\), weighted by \(w_i > 0\). The constraint set is a simplex slice \(\{B \in \mathbb{R}_{\ge 0}^K : \sum_i B_i = B_{\mathrm{tot}}\}\), which is convex. Form the Lagrangian \[\mathcal{L}(B, \lambda) \;=\; \frac{1}{K^2}\sum_{i=1}^{K} w_i 2^{-2B_i/V} \;+\; \lambda\!\left(\sum_{i=1}^{K} B_i - B_{\mathrm{tot}}\right).\] Stationarity, \(\partial \mathcal{L}/\partial B_i = 0\), gives \[-\frac{2 \ln 2}{V K^2}\, w_i \cdot 2^{-2B_i/V} \;+\; \lambda \;=\; 0 \quad\Longleftrightarrow\quad 2^{-2B_i/V} \;=\; \frac{\lambda V K^2}{2 w_i \ln 2}.\] Taking \(\log_2\), \[B_i \;=\; -\frac{V}{2}\log_2\!\left(\frac{\lambda V K^2}{2 w_i \ln 2}\right) \;=\; \frac{V}{2}\log_2(w_i) \;+\; \mathrm{const}(\lambda).\] Imposing \(\sum_i B_i = B_{\mathrm{tot}}\) pins down the constant: \[B_i^\star \;=\; \frac{B_{\mathrm{tot}}}{K} \;+\; \frac{V}{2}\log_2(w_i) \;-\; \frac{V}{2K}\sum_{j=1}^{K} \log_2(w_j) \;=\; \frac{B_{\mathrm{tot}}}{K} \;+\; \frac{V}{2}\log_2\!\left(\frac{w_i}{\bar w_g}\right),\] where \(\bar w_g = \exp\!\bigl(\tfrac{1}{K}\sum_j \log w_j\bigr) = (\prod_j w_j)^{1/K}\) is the geometric mean. When all \(w_i\) are equal, \(\log_2(w_i/\bar w_g) = 0\) and the optimal allocation is uniform.

The clipped variant (\(B_i \in [0, B_{\max}]\)) is standard water-filling: solve unconstrained, identify saturated coordinates, fix them at boundary, redistribute residual budget among unsaturated coordinates by re-solving the reduced problem. 0◻

9.7 Proof of Corollary 1↩︎

The proof is a deterministic relative-error transfer lemma followed by an empirical-second-moment concentration bound; their composition gives the stated rate.

9.7.0.1 Relative-error transfer.

9.7.0.2 Concentration of the empirical-second-moment estimator.

9.7.0.3 Composition.

Set \(\eta := (R_\ell^2 / w_{\min}) \sqrt{\log(2K/\delta)/(2 m T_0)}\) and assume the warm-up sample size \(m T_0\) is large enough that \(\eta \le 1/2\) (otherwise the bound is vacuous). Lemma 3 gives \(|\hat{w}_i - w_i| \le \eta\, w_i\) uniformly in \(i\) with probability \(\ge 1 - \delta\). Lemma 2 then yields \(F(\hat{B}^\star) \le (1 + 2\eta + 4\eta^2)\, F(B^\star) \le (1 + 3\eta) F(B^\star)\) for \(\eta \le 1/4\), and \[3\eta \;=\; \frac{3 R_\ell^2}{w_{\min}} \sqrt{\frac{\log(2K/\delta)}{2\, m\, T_0}} \;\le\; c_{\mathrm{ad}} \sqrt{\log(K/\delta)/(m T_0)}, \qquad c_{\mathrm{ad}} \;:=\; \frac{3 R_\ell^2}{w_{\min}}\sqrt{\tfrac{\log 2 + 1}{2}},\] using \(\log(2K/\delta) \le (\log 2 + 1) \log(K/\delta)\) for \(K/\delta \ge e\). The post-quantization range \(R_\ell\) exceeds the input clip \(L_\ell\) by a factor \((1 + 2^{-b_0})\) that is bounded by \(2\) for any \(b_0 \ge 0\) (and approaches \(1\) as the warm-up bit budget grows); the constant \(c_{\mathrm{ad}}\) is therefore at most \(4 \times\) what it would be under the (incorrect) assumption \(R_\ell = L_\ell\), and the \(1 + O(\sqrt{\log(K/\delta)/(m T_0)})\) relative-suboptimality rate of Corollary 1 is unchanged. 0◻

References↩︎