The source paper (arXiv:2305.04288) proves that horizontal federated learning protected by parameter distortion can achieve near-optimal utility under a privacy constraint: utility loss is bounded via a bias-variance decomposition plus a total-variation term, the Gaussian noise variance and sampling probability are constructed from divergence relations, and an upper bound matches a no-free-lunch lower bound. However, the guarantee is confined to a narrow regime: bounded parameter norms and bounded bias with unspecified constants, a small-bias approximation introduced only 'for facility of expression', a small-gap condition (0<C1,t−τ<0.010<C_{1,t}-\tau<0.01) behind the constructive noise-variance formula, no estimation procedures for the utility-side constants governing the optimal trade-off, and analysis only for isotropic Gaussian noise with independent Bernoulli sampling. The open problem is to determine the reach of the near-optimal utility guarantee under realistic and verifiable conditions: characterize or relax the structural assumptions, establish whether the small-gap restriction can be removed, supply estimators with error guarantees for the problem-dependent constants entering the optimality conditions, and establish whether the analysis extends to broader distortion mechanisms and sampling schemes.

Background

Federated learning (FL) lets many clients collaboratively train a global model by exchanging model updates instead of raw data, typically in the horizontal setting where clients hold disjoint samples of the same feature space. Exchanged updates leak private information: gradient-inversion attacks such as Deep Leakage from Gradients (DLG), which reconstruct training data from shared gradients, demonstrate this concretely. Protection mechanisms therefore distort what is released — the randomization mechanism adds noise to model parameters, and compression mechanisms sparsify or quantize them — at the cost of utility, here measured by the gap between the model parameter obtained from unprotected and protected training. The source framework (Zhang, Chen, and Yang, arXiv:2305.04288) quantifies both sides information-theoretically. Privacy leakage is measured as the Jensen-Shannon (JS) divergence — a symmetric, bounded information divergence between two distributions — between the adversary's belief distribution over a client's private data before and after seeing the released parameter; total variation (TV) distance — the maximum difference in probability mass assigned by two distributions — links parameter distortion to belief shifts. The No Free Lunch theorem for security and utility in FL (Zhang, Gu, Fan, Chen, and Yang, ACM TIST, DOI 10.1145/3563219) gives a matching lower bound: privacy loss plus utility loss weighted by a constant CdC_d cannot fall below a problem-dependent constant. On top of this, the source paper proves: (i) an upper bound on utility loss ϵu,t≤−E(Var[W~t(k)∣Wt−1(k)])+C6⋅TV(Pt(k)∥P~t(k))\epsilon_{u,t}\le -\mathbb{E}(\mathrm{Var}[\widetilde{W}_t^{(k)}|W_{t-1}^{(k)}])+C_6\cdot\mathrm{TV}(P_t^{(k)}\Vert\widetilde{P}_t^{(k)}), where W~\widetilde{W} is the distorted parameter, the first (variance-reduction) term reflects mini-batch stochastic gradient descent, and C6C_6 is an unspecified positive constant; (ii) a constructive procedure that sets the variance of isotropic Gaussian additive noise and the mini-batch sampling probability pp of independent per-datum Bernoulli sampling (each datum of a client's dataset enters the mini-batch independently with probability pp) so the privacy constraint is met while utility loss stays near optimal; and (iii) an upper bound for the privacy-utility trade-off that, together with the No Free Lunch lower bound, yields equality conditions under which the optimal trade-off is achieved. The force of these results is, however, conditional. The bounds assume parameter norms bounded by a constant C3C_3 (Assumption 6.1 in arXiv v1 = 5.1 in v3) and estimator bias bounded by C4C_4 (Assumption 6.2/5.2); the proof additionally introduces, 'for facility of expression', a small-bias approximation Bias(Wt(k))≤C5⋅TV(Pt(k)∥P~t(k))\mathrm{Bias}(W_t^{(k)})\le C_5\cdot\mathrm{TV}(P_t^{(k)}\Vert\widetilde{P}_t^{(k)}). The constructive noise-variance formula σε2=100σ2(C1,t−τp,t(k))/d\sigma_\varepsilon^2=100\sigma^2(C_{1,t}-\tau_{p,t}^{(k)})/\sqrt{d} (Lemma 6.8/5.8, with dd the parameter dimension and σ2\sigma^2 the original parameter variance) is proven only under the small-gap condition 0<C1,t−τp,t(k)<0.010<C_{1,t}-\tau_{p,t}^{(k)}<0.01, where C1,t=1K∑k=1KC1,t(k)C_{1,t}=\frac{1}{K}\sum_{k=1}^{K}C_{1,t}^{(k)} (with KK the number of clients) is the client-averaged square root of the JS divergence between the adversary's belief distributions, C1,t(k)=JS(Ft(k)∥F~t(k))C_{1,t}^{(k)}=\sqrt{\mathrm{JS}(F_t^{(k)}\Vert\widetilde{F}_t^{(k)})} is its per-client counterpart (Ft(k)F_t^{(k)} and F~t(k)\widetilde{F}_t^{(k)} being the adversary's beliefs about client kk's private data before and after observing the released parameter), and τp,t(k)\tau_{p,t}^{(k)} is the privacy-leakage tolerance, i.e. the maximum leakage allowed for client kk at round tt. The optimal trade-off (Theorem 6.14/5.14) is a sufficiency statement: in the scenario where Cd=C2/C6C_d=C_2/C_6, if C1,t(k)=(C2/C6) E[Var[W~t(k)∣Wt−1(k)]]C_{1,t}^{(k)}=(C_2/C_6)\,\mathbb{E}[\mathrm{Var}[\widetilde{W}_t^{(k)}|W_{t-1}^{(k)}]], then the optimal trade-off is achieved; here C2=12(e2ξ−1)C_2=\frac{1}{2}(e^{2\xi}-1) is a privacy constant determined by ξ\xi, the maximum log-density ratio between the adversary's belief distributions before and after observing any released information, and CdC_d is the weight on utility loss in the No Free Lunch trade-off. Necessity of the equalities is not proved, and no criteria or procedures are given for verifying or enforcing them. None of the constants C3,C4,C5,C6C_3,C_4,C_5,C_6 or the belief divergences comes with an estimation protocol, and the entire construction is specific to isotropic Gaussian noise and independent Bernoulli sampling.

Problem Statement

Determine, for horizontal federated learning protected by parameter distortion, under what realistic and verifiable conditions a near-optimal utility guarantee of the source paper's type (bias-variance/total-variation upper bound, constructive protection-parameter setting, and matching against the no-free-lunch lower bound) can be established. Concretely: (1) characterize when the structural assumptions — parameter norms bounded by C3C_3, estimator bias bounded by C4C_4, and the small-bias approximation Bias(Wt(k))≤C5⋅TV(Pt(k)∥P~t(k))\mathrm{Bias}(W_t^{(k)})\le C_5\cdot\mathrm{TV}(P_t^{(k)}\Vert\widetilde{P}_t^{(k)}) — are satisfied with small constants in realistic neural-network training, and derive bounds on utility loss that are robust to their violation; (2) determine whether the small-gap condition 0<C1,t−τp,t(k)<0.010<C_{1,t}-\tau_{p,t}^{(k)}<0.01 under which the constructive Gaussian noise-variance formula σε2=100σ2(C1,t−τp,t(k))/d\sigma_\varepsilon^2=100\sigma^2(C_{1,t}-\tau_{p,t}^{(k)})/\sqrt{d} guarantees the privacy constraint can be removed or how far it can be widened, or establish that it is necessary; (3) give verifiable criteria and estimation procedures, with error guarantees, for the utility-side constants — in particular C6C_6 and the equality conditions Cd=C2/C6C_d=C_2/C_6 and C1,t(k)=(C2/C6) E[Var[W~t(k)∣Wt−1(k)]]C_{1,t}^{(k)}=(C_2/C_6)\,\mathbb{E}[\mathrm{Var}[\widetilde{W}_t^{(k)}|W_{t-1}^{(k)}]] under which the source's optimal-trade-off theorem guarantees the optimal privacy-utility trade-off; and (4) determine whether the near-optimality analysis extends to distortion mechanisms beyond isotropic Gaussian additive noise (for instance compression, or structured or correlated perturbations) and to sampling schemes beyond independent per-datum Bernoulli sampling. The four facets are sub-objectives of one research objective — making the claimed near-optimal privacy-utility boundary of parameter-distortion protection valid, constructively attainable, and verifiable outside the narrow regime in which it is currently proven — and each has independent standing.

References

  1. Xiaojin Zhang, Kai Chen, and Qiang Yang. Towards Achieving Near-optimal Utility for Privacy-Preserving Federated Learning via Data Generation and Parameter Distortion. arXiv:2305.04288 (2023; v3 March 2024). DOI: 10.48550/arXiv.2305.04288, https://arxiv.org/abs/2305.04288
  2. Xiaojin Zhang, Hanlin Gu, Lixin Fan, Kai Chen, and Qiang Yang. No Free Lunch Theorem for Security and Utility in Federated Learning. ACM Transactions on Intelligent Systems and Technology 14(1):1-35 (published online November 2022). DOI: 10.1145/3563219, https://doi.org/10.1145/3563219
  3. Xiaojin Zhang, Yan Kang, Lixin Fan, Kai Chen, and Qiang Yang. A Meta-Learning Framework for Tuning Parameters of Protection Mechanisms in Trustworthy Federated Learning. ACM Transactions on Intelligent Systems and Technology 15(3):1-36 (2024). DOI: 10.1145/3652612, https://doi.org/10.1145/3652612
  4. Xiaojin Zhang, Mingcong Xu, and Wei Chen. A Unified Learn-to-Distort-Data Framework for Privacy-Utility Trade-off in Trustworthy Federated Learning. arXiv:2407.04751 (2024). DOI: 10.48550/arXiv.2407.04751, https://arxiv.org/abs/2407.04751
  5. Xiaojin Zhang and Wei Chen. Theoretical Analysis of Privacy Leakage in Trustworthy Federated Learning: A Perspective from Linear Algebra and Optimization Theory. arXiv:2407.16735 (2024). DOI: 10.48550/arXiv.2407.16735, https://arxiv.org/abs/2407.16735
  6. Xiaojin Zhang, Mingcong Xu, Yiming Li, Wei Chen, and Qiang Yang. Deciphering the Interplay between Attack and Protection Complexity in Privacy-Preserving Federated Learning. arXiv:2508.11907 (2025). DOI: 10.48550/arXiv.2508.11907, https://arxiv.org/abs/2508.11907
  7. Xiaojin Zhang, Wenjie Li, Yiming Li, Wei Chen, Shutao Xia, and Qiang Yang. Theoretically Principled Federated Learning for Balancing Privacy and Utility. arXiv:2305.15148 (2023). DOI: 10.48550/arXiv.2305.15148, https://arxiv.org/abs/2305.15148