Extending the one-local-epoch optimality of locally differentially private federated learning beyond homogeneous, i.i.d., full-participation DP-SGD

In the local-differential-privacy model of federated learning studied by Bhaskar, Srivastava, Vummintala, Manwani, and Gujar (arXiv:2501.14453, 2025), each client trains with DP-SGD on its own data under an untrusted server, and models are aggregated by FedAvg. Under a fixed total budget $T$ of gradient updates split as $T=E\cdot R$ ($E$ local epochs per global round, $R$ global rounds), the paper proves that $E=1$ minimizes its derived upper bound on performance degradation, shows the aggregated model's privacy follows from parallel composition of the per-client guarantees, and derives a $U_l\sim 1-O(1/(l^2k))$ utility scaling with the number of clients $k$. All three guarantees rest on idealized assumptions: homogeneous clients with disjoint i.i.d. per-client datasets and full participation every round. The open problem is to prove or refute the two relaxation-sensitive guarantees (the $E=1$ optimality and the $U_l$ utility scaling) for clients with heterogeneous, non-i.i.d. data distributions and with partial participation; to prove or refute the authors' conjecture that $E=1$ optimality extends to any privacy mechanism with $\epsilon\cdot\sigma\propto\mathrm{Poly}(T)$ and per-update noise addition; and to determine whether the utility benefit of $E=1$ can be preserved under communication constraints at the same $(\epsilon,\delta)$ budget.

Background

Federated learning (FL) is a distributed training paradigm in which a server coordinates $k$ clients that never share their raw data: each client trains a model locally for $E$ local epochs and sends the resulting parameters to the server, which aggregates them (typically by averaging, the FedAvg rule of McMahan et al., 2017) and redistributes the global model, repeating for $R$ global rounds. Because shared model parameters leak information about training data through inference attacks, privacy-preserving FL adds differential privacy (DP), which requires the output distribution of the training algorithm to be nearly unchanged when any single data record is altered, parametrized by a privacy budget $(\epsilon,\delta)$. DP-SGD (Abadi et al., 2016) achieves this by clipping per-example gradients and adding Gaussian noise with standard deviation $\sigma$ to each gradient update; its accounting gives the relation $\sigma\cdot\epsilon\propto\sqrt{T}$ between noise scale, budget, and the total number of updates $T$. In the local-DP federated learning setting of the source paper, the server is adversarial: every client independently runs DP-SGD to guarantee $(\epsilon,\delta)$-DP for its own dataset before sharing its model, and only then is FedAvg applied. The source paper analyzes this framework under three results. First, privacy of the aggregated model: since per-client datasets are disjoint and modeled as i.i.d. samples from a common distribution, parallel composition (Smith et al., 2021 — the DP fact that mechanisms applied to disjoint datasets compose at the worst individual budget, $\max\{\epsilon_1,\ldots,\epsilon_k\}$) implies the FedAvg-aggregated model is at least as private as each client model when the per-client budgets are equal. Second, aggregation frequency: for a fixed budget $T=E\cdot R$ of gradient updates, the paper bounds the performance degradation $\Delta$ — the deviation between the DP-SGD+FedAvg trajectory and the non-private SGD+FedAvg trajectory — and shows this bound is minimized at $E=1$ (Theorem 2), i.e., communicating with the server after every local epoch is optimal; the bound's noise term involves the expected norm of the Gaussian noise in the $N$-dimensional parameter space, $E[\|\eta_t\|]=\sqrt{2}\,\sigma C\,\Gamma((N+1)/2)/\Gamma(N/2)$, so it grows with both $E$ and $N$. Third, client scaling: defining the $l$-utility $U_l$ as the probability that the expected empirical-risk gap to the ideal model stays below $l$, the paper derives $U_l\sim 1-O(1/(l^2k))$ (Theorem 3, via a Chebyshev inequality: averaging $k$ i.i.d. client models shrinks the noise scale to $\sigma/\sqrt{k}$), so utility improves as more clients participate at a fixed per-client privacy budget. All three proofs, and the experiments (MNIST, Fashion-MNIST, CIFAR-10), assume homogeneous clients (same architecture and loss), disjoint i.i.d. per-client datasets, and full participation of all $k$ clients in every global round. The authors state that the analysis 'can be extended for other privacy-preserving learning techniques' satisfying $\epsilon\cdot\sigma\propto\mathrm{Poly}(T)$ with noise added during gradient updates, but prove this only for DP-SGD. Related literature sharpens why the general question is nontrivial: Wei et al. (2020) and Kairouz et al. (2021) analyze distributed-DP FL where noise is added after secure aggregation — a different trust model in which per-step communication is required for their privacy amplification; Heikkilä (TMLR 2025) shows that with secure aggregation, multiple local steps can retain formal privacy guarantees with higher utility; Hou et al. (2023) show the optimal local-step count for a drift-corrected method (DP-ScaffNew) need not equal 1; and ALI-DPFL (Ling et al., WoWMoM 2024) derives an optimal local DP-SGD iteration count that equals 1 only when communication rounds are unconstrained. Whether the specific guarantees of the source paper — $E=1$ optimality and the $U_l$ scaling — survive realistic heterogeneity, partial participation, and other privacy mechanisms remains unsettled.

Problem Statement

In the local-differential-privacy federated learning framework of Bhaskar et al. (arXiv:2501.14453) — $k$ clients, each independently training a shared homogeneous model on its own dataset with DP-SGD guaranteeing $(\epsilon,\delta)$-DP per client under an untrusted server, aggregated by FedAvg, with a fixed total budget $T=E\cdot R$ of gradient updates — determine the status of the paper's guarantees and conjectured extensions outside its idealized setting. Specifically: (1) For each of the paper's two relaxation-sensitive guarantees — the optimality of $E=1$ aggregation frequency (Theorem 2) and the $U_l\sim 1-O(1/(l^2k))$ utility scaling (Theorem 3) — and for each relaxation of the idealized setting on which the paper relies — (a) statistically heterogeneous, non-i.i.d. per-client datasets (still disjoint, but no longer modeled as i.i.d. samples from a common distribution), (b) partial client participation across global rounds, or (c) both together — prove or refute that the guarantee continues to hold at the same per-client $(\epsilon,\delta)$ budget, in the same formal sense as in the source (for Theorem 2, that the $E=1$ schedule still minimizes the deviation bound with its stated dependence on the number of local epochs; for Theorem 3, that the $U_l\sim 1-O(1/(l^2k))$ rate is retained), with a merely qualitative weakening counting as a refutation rather than a proof. These cells are not independent: (c) is the most relaxed setting, so a proof for (c) also settles (a) and (b), and a counterexample in (a) or (b) also refutes (c), while the converse implications do not hold. The parallel-composition privacy of the aggregated model is not one of these cells: it is insensitive to the above relaxations — it rests only on the disjointness of the per-client datasets and the post-processing property of FedAvg — and so continues to hold under each of (a), (b), and (c). Heterogeneity here refers to the clients' local data distributions: the model remains shared and homogeneous (same architecture and loss), as required for the FedAvg aggregate and for the paper's deviation quantity $\Delta$ and utility $U_l$ to be defined. (2) Prove or refute the authors' conjecture that $E=1$ optimality extends to any privacy-preserving learning technique beyond DP-SGD that satisfies $\epsilon\cdot\sigma\propto\mathrm{Poly}(T)$ and adds noise during each gradient update, within the paper's local-DP framework in which each client's own technique provides $(\epsilon,\delta)$-DP before sharing. (3) Determine whether the utility benefit of $E=1$ can be preserved under a communication constraint (a bounded number of global rounds) at the same per-client $(\epsilon,\delta)$ budget, addressing the performance–communication tradeoff that the paper notes in §6.1. All items are posed in the source's local-DP trust model (untrusted server; per-client $(\epsilon,\delta)$-DP; plain FedAvg post-processing); the adjacent literature shows that the optimal aggregation frequency is regime-dependent (rounds free vs. constrained), and analyses in other trust models (e.g., distributed DP with secure aggregation) are relevant context rather than substitutes for conclusions in the source's framework.

References

1. Uday Bhaskar, Varul Srivastava, Avyukta Manjunatha Vummintala, Naresh Manwani, Sujit Gujar. Optimal Strategies for Federated Learning Maintaining Client Privacy. arXiv:2501.14453, 2025. DOI: 10.48550/arXiv.2501.14453. https://arxiv.org/abs/2501.14453
2. Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, Li Zhang. Deep Learning with Differential Privacy. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS 2016), pp. 308–318. DOI: 10.1145/2976749.2978318. arXiv:1607.00133. https://arxiv.org/abs/1607.00133
3. H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, Blaise Agüera y Arcas. Communication-Efficient Learning of Deep Networks from Decentralized Data. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), PMLR 54:1273–1282, 2017. arXiv:1602.05629. https://arxiv.org/abs/1602.05629
4. Josh Smith, Hassan Jameel Asghar, Gianpaolo Gioiosa, Sirine Mrabet, Serge Gaspers, Paul Tyler. Making the Most of Parallel Composition in Differential Privacy. arXiv:2109.09078, 2021. https://arxiv.org/abs/2109.09078
5. Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H. Yang, Farhad Farokhi, Shi Jin, Tony Q. S. Quek, H. Vincent Poor. Federated Learning With Differential Privacy: Algorithms and Performance Analysis. IEEE Transactions on Information Forensics and Security, 15:3454–3469, 2020. DOI: 10.1109/TIFS.2020.2988575. https://doi.org/10.1109/TIFS.2020.2988575
6. Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, Zheng Xu. Practical and Private (Deep) Learning without Sampling or Shuffling. Proceedings of the 38th International Conference on Machine Learning (ICML 2021), PMLR 139:5213–5225, 2021. arXiv:2103.00039. https://arxiv.org/abs/2103.00039
7. Xinpeng Ling, Jie Fu, Kuncan Wang, Haitao Liu, Zhili Chen. ALI-DPFL: Differentially Private Federated Learning with Adaptive Local Iterations. 2024 IEEE 25th International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM), 2024. DOI: 10.1109/WoWMoM60985.2024.00062. arXiv:2308.10457. https://arxiv.org/abs/2308.10457
8. Mikko A. Heikkilä. On Using Secure Aggregation in Differentially Private Federated Learning with Multiple Local Steps. Transactions on Machine Learning Research (TMLR), 2025. arXiv:2407.19286. https://arxiv.org/abs/2407.19286
9. Xiangjian Hou, Sarit Khirirat, Mohammad Yaqub, Samuel Horvath. Balancing Privacy and Performance for Private Federated Learning Algorithms. arXiv:2304.05127, 2023. https://arxiv.org/abs/2304.05127
10. Arnab Auddy, Xiangni Peng, Subhadeep Paul. Statistical Limits and Efficient Algorithms for Differentially Private Federated Learning. arXiv:2605.18656, 2026. https://arxiv.org/abs/2605.18656
11. Jiahao Xu, Rui Hu, Olivera Kotevska. Optimal Client Sampling in Federated Learning With Client-Level Heterogeneous Differential Privacy. IEEE Internet of Things Journal, 2026. DOI: 10.1109/JIOT.2026.3661913. https://doi.org/10.1109/JIOT.2026.3661913
12. Guogang Zhu, Xuefeng Liu, Jianwei Niu, Shaojie Tang, Xinghao Wu. The Other Side of the Coin: Unveiling the Downsides of Model Aggregation in Federated Learning from a Layer-peeled Perspective. arXiv:2502.03231, 2025. https://arxiv.org/abs/2502.03231