pith. sign in

arxiv: 2605.19813 · v1 · pith:UG7NMCWTnew · submitted 2026-05-19 · 💻 cs.LG · math.ST· stat.TH

General Lower Bounds for Differentially Private Federated Learning with Arbitrary Public-Transcript Interactions

Yicheng Li This is my paper

Pith reviewed 2026-05-20 07:12 UTC · model grok-4.3

classification 💻 cs.LG math.STstat.TH
keywords differentially private federated learninglower boundszero-concentrated differential privacyvan Trees inequalityparameter estimationmean estimationlinear regressionnonparametric regression
2
0 comments X

The pith

Differentially private federated estimators obey a van Trees lower bound on squared error even with arbitrary adaptive interactions and data reuse.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves a general lower bound that applies to any differentially private federated learning protocol whose public transcript satisfies a total clientwise sample-level zero-concentrated differential privacy constraint. The bound holds for parameter estimation under squared ell-two loss and covers protocols that use any number of adaptive rounds together with reuse of each client's local samples. A sympathetic reader would care because the result supplies a concrete information-theoretic limit that remains valid across the practical settings of mean estimation, linear regression, and nonparametric regression.

Core claim

We establish a federated van Trees lower bound for every estimator satisfying a total clientwise sample-level zero-concentrated differential privacy (zCDP) constraint. The proof proceeds from a privacy-information contraction inequality that relates the mutual information between the unknown parameter and the complete public transcript to the total privacy budget, and this inequality is shown to hold for arbitrary adaptive interactions and arbitrary reuse of local samples across rounds.

What carries the argument

The privacy-information contraction inequality for complete public transcripts, which upper-bounds the mutual information available to any estimator under the zCDP constraint and thereby enables direct application of the van Trees inequality in the federated setting.

If this is right

  • The same lower bound immediately specializes to mean estimation and supplies an explicit rate in terms of the total privacy budget and the number of clients.
  • The bound extends without change to linear regression and nonparametric regression under the same privacy model.
  • The result remains valid for any finite number of communication rounds and any pattern of sample reuse across rounds.
  • The contraction inequality supplies a modular tool that can be inserted into other information-theoretic arguments for private distributed estimation.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The bound suggests that increasing the number of rounds or allowing sample reuse cannot circumvent the fundamental privacy-accuracy tradeoff once the total zCDP budget is fixed.
  • The same contraction technique may be reusable for other privacy notions such as approximate differential privacy or Renyi differential privacy in federated settings.
  • Practical algorithm designers can use the bound to decide whether further rounds or more sophisticated interaction patterns are worth the implementation cost.

Load-bearing premise

The privacy-information contraction inequality continues to hold when the protocol uses arbitrary adaptive rounds and reuses each client's samples across rounds.

What would settle it

Construct a simple two-client mean-estimation task with two adaptive rounds and sample reuse; exhibit an estimator whose mean-squared error falls below the numerical value of the federated van Trees bound while still obeying the stated total clientwise zCDP budget.

Figures

Figures reproduced from arXiv: 2605.19813 by Yicheng Li.

Figure 1
Figure 1. Figure 1: One round of an interactive public-transcript federated protocol. At round [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
read the original abstract

We prove a general lower bound for differentially private federated learning protocols with arbitrary public-transcript interactions. The protocol may use any number of adaptive rounds, and each client's local samples may be reused across rounds. For parameter estimation under squared \(\ell_2\) loss, we establish a federated van Trees lower bound for every estimator satisfying a total clientwise sample-level zero-concentrated differential privacy (zCDP) constraint. The main technical ingredient is a privacy-information contraction inequality for complete public transcripts. We illustrate the bound through applications to mean estimation, linear regression, and nonparametric regression.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript establishes general lower bounds for differentially private federated learning protocols allowing arbitrary public-transcript interactions, including any number of adaptive rounds and reuse of each client's local samples. For parameter estimation under squared ℓ₂ loss, it derives a federated van Trees lower bound that applies to every estimator obeying a total clientwise sample-level zero-concentrated differential privacy (zCDP) constraint. The central technical step is a new privacy-information contraction inequality relating the mutual information between the unknown parameter and the complete public transcript to the zCDP budget; this is then applied to obtain concrete bounds illustrated on mean estimation, linear regression, and nonparametric regression.

Significance. If the contraction inequality is shown to hold uniformly over adaptive transcript mechanisms and sample reuse, the result would meaningfully strengthen the literature on privacy-utility trade-offs in federated settings by removing common restrictions to non-adaptive or non-reusing protocols. The explicit use of the van Trees inequality to obtain a federated lower bound is a constructive contribution that yields falsifiable rate predictions for the listed applications.

major comments (1)
  1. Main technical section (contraction inequality): the proof of the privacy-information contraction must explicitly address arbitrary adaptive query selection and reuse of the same local samples across rounds. If the argument relies on fixed sample partitions, non-adaptive query ordering, or an independence assumption violated by reuse, the inequality does not support the claimed generality and the subsequent van Trees application fails for realistic multi-round protocols.
minor comments (2)
  1. Notation for the total zCDP budget and its clientwise decomposition should be introduced with a single displayed equation early in the preliminaries to avoid repeated inline definitions.
  2. In the applications section, the dependence of the lower bound on the number of rounds and the reuse factor should be stated explicitly rather than left implicit in the general expression.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for recognizing the potential contribution of the privacy-information contraction inequality and its application via the van Trees inequality. We address the major comment below.

read point-by-point responses

  1. Referee: Main technical section (contraction inequality): the proof of the privacy-information contraction must explicitly address arbitrary adaptive query selection and reuse of the same local samples across rounds. If the argument relies on fixed sample partitions, non-adaptive query ordering, or an independence assumption violated by reuse, the inequality does not support the claimed generality and the subsequent van Trees application fails for realistic multi-round protocols.

    Authors: We thank the referee for this observation. The proof of the contraction inequality is written to apply to arbitrary (possibly adaptive) public-transcript mechanisms and does not rely on fixed sample partitions, non-adaptive ordering, or independence assumptions that would be violated by reuse. It proceeds from the zCDP definition via the chain rule for mutual information and the fact that zCDP is preserved under adaptive composition and post-processing; these properties hold irrespective of how queries are chosen or whether local samples are reused. To address the concern that this generality may not be sufficiently visible, we will add an explicit paragraph and a remark in the revised technical section that walks through the argument under adaptive query selection and sample reuse. revision: yes

Circularity Check

0 steps flagged

No significant circularity; new contraction inequality is proven internally

full rationale

The paper's central contribution is a federated van Trees lower bound derived from a privacy-information contraction inequality that it proves for arbitrary adaptive public transcripts and sample reuse. This inequality is introduced and established within the manuscript as the main technical step, rather than being fitted to data, renamed from a known result, or justified solely via self-citation. The subsequent application to mean estimation, linear regression, and nonparametric regression follows from standard information-theoretic arguments without reducing the claimed bound to its inputs by construction. No load-bearing self-citations or ansatzes are present.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the standard van Trees inequality and the zCDP definition, plus the newly introduced contraction inequality; no free parameters or invented entities are indicated in the abstract.

axioms (2)
  • standard math Van Trees inequality applies to the parameter estimation problem under squared l2 loss
    Invoked to obtain the lower bound on estimator error from the information in the transcript.
  • domain assumption Total clientwise sample-level zCDP is the privacy constraint that must be respected by the protocol
    The bound is stated for every estimator satisfying this specific privacy notion.

pith-pipeline@v0.9.0 · 5619 in / 1290 out tokens · 42053 ms · 2026-05-20T07:12:11.190825+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

43 extracted references · 43 canonical work pages · 7 internal anchors

  1. [1]

    Differentially Private Assouad, Fano, and Le Cam, November 2020

    Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially Private Assouad, Fano, and Le Cam, November 2020. URLhttp://arxiv.org/abs/2004.06830

    work page arXiv 2020

  2. [2]

    Discrete Distribution Estimation under User-Level Local Differential Privacy, November 2022

    Jayadev Acharya, Yuhan Liu, and Ziteng Sun. Discrete Distribution Estimation under User-Level Local Differential Privacy, November 2022. URLhttp://arxiv.org/abs/2211.03757

    work page arXiv 2022

  3. [3]

    Canonne, Ziteng Sun, and Himanshu Tyagi

    Jayadev Acharya, Cl´ ement L. Canonne, Ziteng Sun, and Himanshu Tyagi. Unified lower bounds for inter- active high-dimensional estimation under information constraints.Advances in Neural Information Pro- cessing Systems, 36:51133–51165, 2023. URLhttps://proceedings.neurips.cc/paper_files/paper/ 2023/hash/a07e87ecfa8a651d62257571669b0150-Abstract-Conference.html

    work page 2023

  4. [4]

    On the privacy- robustness-utility trilemma in distributed learning

    Youssef Allouah, Rachid Guerraoui, Nirupam Gupta, Rafa¨ el Pinot, and John Stephan. On the privacy- robustness-utility trilemma in distributed learning. InInternational Conference on Machine Learning, pages 569–626. PMLR, 2023. URLhttps://proceedings.mlr.press/v202/allouah23a.html

    work page 2023

  5. [5]

    Minimax and adaptive transfer learn- ing for nonparametric classification under distributed differential privacy constraints.arXiv preprint arXiv:2406.20088,

    Arnab Auddy, T. Tony Cai, and Abhinav Chakraborty. Minimax and adaptive transfer learning for nonparametric classification under distributed differential privacy constraints, June 2024. URLhttp: //arxiv.org/abs/2406.20088

    work page arXiv 2024

  6. [6]

    Rina Foygel Barber and John C. Duchi. Privacy and Statistical Risk: Formalisms and Minimax Bounds, December 2014. URLhttp://arxiv.org/abs/1412.4451

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  7. [7]

    Fisher information for dis- tributed estimation under a blackboard communication protocol

    Leighton Pate Barnes, Yanjun Han, and Ayfer ¨Ozg¨ ur. Fisher information for dis- tributed estimation under a blackboard communication protocol. In2019 IEEE Inter- national Symposium on Information Theory (ISIT), pages 2704–2708. IEEE, 2019. URL https://ieeexplore.ieee.org/abstract/document/8849821/?casa_token=hFpaAL2HovQAAAAA: _Mz3cYvJ-kRVnI37iigiyp3woOz...

    work page arXiv 2019

  8. [8]

    Fisher Information Under Local Differential Privacy.IEEE Journal on Selected Areas in Information Theory, 1(3):645–659, November 2020

    Leighton Pate Barnes, Wei-Ning Chen, and Ayfer ¨Ozg¨ ur. Fisher Information Under Local Differential Privacy.IEEE Journal on Selected Areas in Information Theory, 1(3):645–659, November 2020. ISSN 2641-

    work page 2020

  9. [9]

    URLhttps://ieeexplore.ieee.org/abstract/document/ 9264231

    doi: 10.1109/JSAIT.2020.3039461. URLhttps://ieeexplore.ieee.org/abstract/document/ 9264231

    work page doi:10.1109/jsait.2020.3039461 2020

  10. [10]

    Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds

    Raef Bassily, Adam Smith, and Abhradeep Thakurta. Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds, October 2014. URLhttp://arxiv.org/abs/1405.7085

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  11. [11]

    Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds

    Mark Bun and Thomas Steinke. Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds, May 2016. URLhttp://arxiv.org/abs/1605.02065

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  12. [12]

    Fingerprinting Codes and the Price of Approximate Differential Privacy

    Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting Codes and the Price of Approximate Differential Privacy. InProceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 1–10, New York, NY, USA, May 2014. Association for Computing Machinery

    work page 2014

  13. [13]

    Local differ- ential privacy: Elbow effect in optimal density estimation and adaptation over Besov el- lipsoids.Bernoulli, 26(3):1727–1764, August 2020

    Cristina Butucea, Amandine Dubois, Martin Kroll, and Adrien Saumard. Local differ- ential privacy: Elbow effect in optimal density estimation and adaptation over Besov el- lipsoids.Bernoulli, 26(3):1727–1764, August 2020. ISSN 1350-7265. doi: 10.3150/ 19-BEJ1165. URLhttps://projecteuclid.org/journals/bernoulli/volume-26/issue-3/ Local-differential-privacy...

    work page 2020

  14. [14]

    Interactive versus non-interactive locally differentially private estimation: Two elbows for the quadratic functional, July 2022

    Cristina Butucea, Angelika Rohde, and Lukas Steinberger. Interactive versus non-interactive locally differentially private estimation: Two elbows for the quadratic functional, July 2022. URLhttp: //arxiv.org/abs/2003.04773

    work page arXiv 2022

  15. [15]

    Nonparametric spectral density esti- mation using interactive mechanisms under local differential privacy, April 2025

    Cristina Butucea, Karolina Klockmann, and Tatyana Krivobokova. Nonparametric spectral density esti- mation using interactive mechanisms under local differential privacy, April 2025. URLhttp://arxiv.org/ abs/2504.00919

    work page arXiv 2025

  16. [16]

    Tony Cai and Yicheng Li

    T. Tony Cai and Yicheng Li. Minimax and adaptive covariance matrix estimation under differential privacy, March 2026. URLhttp://arxiv.org/abs/2603.19703. 9

    work page arXiv 2026

  17. [17]

    Tony Cai, Yichen Wang, and Linjun Zhang

    T. Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for param- eter estimation with differential privacy.The Annals of Statistics, 49(5), October 2021. ISSN 0090-5364. doi: 10.1214/21-AOS2058. URLhttps://projecteuclid.org/journals/annals-of-statistics/ volume-49/issue-5/The-cost-of-privacy--Optimal-rates-of-conver...

    work page doi:10.1214/21-aos2058 2021

  18. [18]

    Tony Cai, Abhinav Chakraborty, and Lasse Vuursteen

    T. Tony Cai, Abhinav Chakraborty, and Lasse Vuursteen. Federated nonparametric hypothesis testing with differential privacy constraints: Optimal rates and adaptive tests, June 2024. URLhttp://arxiv. org/abs/2406.06749

    work page arXiv 2024

  19. [19]

    Optimal federated learning for non- parametric regression with heterogeneous distributed differential privacy constraints.arXiv preprint arXiv:2406.06755,

    T. Tony Cai, Abhinav Chakraborty, and Lasse Vuursteen. Optimal federated learning for nonparametric regression with heterogeneous distributed differential privacy constraints, June 2024. URLhttp://arxiv. org/abs/2406.06755

    work page arXiv 2024

  20. [20]

    Tony Cai, Abhinav Chakraborty, and Lasse Vuursteen

    T. Tony Cai, Abhinav Chakraborty, and Lasse Vuursteen. The cost of adaptation under differential pri- vacy: Optimal adaptive federated density estimation, December 2025. URLhttp://arxiv.org/abs/2512. 14337

    work page 2025

  21. [21]

    Tony Cai, Yichen Wang, and Linjun Zhang

    T. Tony Cai, Yichen Wang, and Linjun Zhang. Score attack: A lower bound technique for optimal differentially private learning, July 2025. URLhttp://arxiv.org/abs/2303.07152

    work page arXiv 2025

  22. [22]

    Wei-Ning Chen and Ayfer ¨Ozg¨ ur.Lq lower bounds on distributed estimation via fisher information, April

    work page

  23. [23]

    URLhttp://arxiv.org/abs/2402.01895

    work page arXiv

  24. [24]

    Wainwright, and Michael I

    John Duchi, Martin J. Wainwright, and Michael I. Jordan. Local privacy and minimax bounds: Sharp rates for probability estimation.Advances in Neural Information Process- ing Systems, 26, 2013. URLhttps://proceedings.neurips.cc/paper_files/paper/2013/hash/ 5807a685d1a9ab3b599035bc566ce2b9-Abstract.html

    work page 2013

  25. [25]

    Local Privacy, Data Processing Inequalities, and Statistical Minimax Rates

    John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. Local Privacy, Data Processing Inequalities, and Statistical Minimax Rates, August 2014. URLhttp://arxiv.org/abs/1302.3203

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  26. [26]

    Journal of the American Statistical Association , author =

    John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. Minimax Optimal Procedures for Locally Private Estimation.Journal of the American Statistical Association, 113(521):182–201, January 2018. ISSN 0162-1459, 1537-274X. doi: 10.1080/01621459.2017.1389735. URLhttps://www.tandfonline.com/doi/ full/10.1080/01621459.2017.1389735

    work page doi:10.1080/01621459.2017.1389735 2018

  27. [27]

    The algorithmic foundations of differential privacy.Foundations and Trends®in Theoretical Computer Science, 9(3–4):211–407, 2014

    Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy.Foundations and Trends®in Theoretical Computer Science, 9(3–4):211–407, 2014. URLhttps://www.nowpublishers. com/article/Details/TCS-042

    work page 2014

  28. [28]

    Concentrated Differential Privacy

    Cynthia Dwork and Guy N. Rothblum. Concentrated Differential Privacy, March 2016. URLhttp: //arxiv.org/abs/1603.01887

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  29. [29]

    Calibrating noise to sensitivity in private data analysis,

    Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. InTheory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265–284. Springer, 2006. doi: 10.1007/11681878 14

    work page doi:10.1007/11681878 2006

  30. [30]

    Robust Traceability from Trace Amounts

    Cynthia Dwork, Adam Smith, Thomas Steinke, Jonathan Ullman, and Salil Vadhan. Robust Traceability from Trace Amounts. InProceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, pages 650–669. IEEE Computer Society, October 2015

    work page 2015

  31. [31]

    Elly K. H. Hung and Yi Yu. Optimal Cox Regression under federated differential privacy: Coefficients and cumulative hazards, August 2025. URLhttp://arxiv.org/abs/2508.19640

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  32. [32]

    New lower bounds for private esti- mation and a generalized fingerprinting lemma.Advances in neural information processing sys- tems, 35:24405–24418, 2022

    Gautam Kamath, Argyris Mouzakis, and Vikrant Singhal. New lower bounds for private esti- mation and a generalized fingerprinting lemma.Advances in neural information processing sys- tems, 35:24405–24418, 2022. URLhttps://proceedings.neurips.cc/paper_files/paper/2022/hash/ 9a6b278218966499194491f55ccf8b75-Abstract-Conference.html

    work page 2022

  33. [33]

    Berrett, and Yi Yu

    Alexander Kent, Thomas B. Berrett, and Yi Yu. Rate optimality and phase transition for user-level local differential privacy, May 2024. URLhttp://arxiv.org/abs/2405.11923. 10

    work page arXiv 2024

  34. [34]

    Nonparametric spectral density estimation under local differential privacy.Statisti- cal Inference for Stochastic Processes, 27(3):725–759, October 2024

    Martin Kroll. Nonparametric spectral density estimation under local differential privacy.Statisti- cal Inference for Stochastic Processes, 27(3):725–759, October 2024. ISSN 1572-9311. doi: 10.1007/ s11203-024-09308-3. URLhttps://doi.org/10.1007/s11203-024-09308-3

    work page doi:10.1007/s11203-024-09308-3 2024

  35. [35]

    Tony Cai, Dong Xia, and Anru R

    Jingyang Li, T. Tony Cai, Dong Xia, and Anru R. Zhang. Federated PCA and Estimation for Spiked Covariance Matrices: Optimal Rates and Efficient Algorithm, November 2024. URLhttp://arxiv.org/ abs/2411.15660

    work page arXiv 2024

  36. [36]

    Federated Transfer Learning with Differential Privacy, April

    Mengchu Li, Ye Tian, Yang Feng, and Yi Yu. Federated Transfer Learning with Differential Privacy, April

    work page

  37. [37]

    URLhttp://arxiv.org/abs/2403.11343

    work page internal anchor Pith review Pith/arXiv arXiv

  38. [38]

    Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Losses, November 2024

    Andrew Lowy and Meisam Razaviyayn. Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Losses, November 2024. URLhttp://arxiv.org/abs/2106.09779

    work page arXiv 2024

  39. [39]

    Asadi, Varun Jog, and Po-Ling Loh

    Ankit Pensia, Amir R. Asadi, Varun Jog, and Po-Ling Loh. Simple Binary Hypothesis Testing Under Local Differential Privacy and Communication Constraints.IEEE Transactions on Information Theory, 71(1): 592–617, January 2025. ISSN 1557-9654. doi: 10.1109/TIT.2024.3461361. URLhttps://ieeexplore. ieee.org/abstract/document/10680565

    work page doi:10.1109/tit.2024.3461361 2025

  40. [40]

    Smooth Lower Bounds for Differentially Private Algo- rithms via Padding-and-Permuting Fingerprinting Codes, July 2024

    Naty Peter, Eliad Tsfadia, and Jonathan Ullman. Smooth Lower Bounds for Differentially Private Algo- rithms via Padding-and-Permuting Fingerprinting Codes, July 2024. URLhttp://arxiv.org/abs/2307. 07604

    work page 2024

  41. [41]

    Optimal estimation in private distributed functional data analysis.arXiv preprint arXiv:2412.06582,

    Gengyu Xue, Zhenhua Lin, and Yi Yu. Optimal estimation in private distributed functional data analysis, December 2024. URLhttp://arxiv.org/abs/2412.06582

    work page arXiv 2024

  42. [42]

    Differentially Private Federated Learning: Servers Trust- worthiness, Estimation, and Statistical Inference, April 2024

    Zhe Zhang, Ryumei Nakada, and Linjun Zhang. Differentially Private Federated Learning: Servers Trust- worthiness, Estimation, and Statistical Inference, April 2024. URLhttp://arxiv.org/abs/2404.16287

    work page arXiv 2024

  43. [43]

    Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model, October 2023

    Liyang Zhu, Meng Ding, Vaneet Aggarwal, Jinhui Xu, and Di Wang. Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model, October 2023. URLhttp://arxiv.org/abs/2310.07367. 11

    work page arXiv 2023