首次建立交互式联邦差分隐私下的信息理论下界,揭示重复使用数据不提升性能
A Van Trees Lower Bound for Fully Interactive Differentially Private Federated Learning
- 基于公开转录本构建联邦van Trees不等式,覆盖任意交互协议
- 在均值估计等任务中,交互与重用数据无法突破现有最优速率
- 适用于异构数据场景,保留方向性费雪信息几何结构
联邦差分隐私协议可进行多轮自适应通信并重复使用客户端本地样本。现有联邦差分隐私的下界分析通常局限于非交互协议或新批次分解,因此完全交互协议下的参数估计信息论极限仍未知。本文建立了在满足客户端层面zCDP约束、任意完整公开转录本条件下的联邦van Trees不等式。标量迹形式适用于同质实验,矩阵形式则在异质实验中保持方向性费雪几何结构。结合已有上界,该结果确定了包括均值估计、线性回归、非参数回归及函数均值估计在内的多种统计问题的极小极大速率。对于这些问题,任意公共交互和重复样本使用均无法超越更简单受限协议的速率。论文关键技术在于转录本中费雪信息的压缩不等式:每个客户端的贡献同时受其局部实验费雪信息和总隐私预算的约束。
原文摘要 · Abstract (English)
Federated differentially private protocols can communicate over many adaptive rounds and reuse each client's local samples. Existing lower bound arguments for federated DP are often restricted to noninteractive protocols or fresh batch decompositions, so the fundamental information-theoretic limit of estimation under fully interactive protocols remains unknown. We establish a federated van Trees inequality for parameter estimation under squared \ell_2 loss from any complete public transcript satisfying a clientwise zCDP constraint at the sample level. A scalar trace form covers homogeneous experiments, while a matrix form preserves directional Fisher geometry in heterogeneous experiments where different clients are informative in different subspaces. Together with existing upper bounds for the corresponding problems, these results identify the minimax rates for various statistical problems including mean estimation, linear regression, nonparametric regression, and functional mean estimation over the full class of interactive public-transcript protocols. For these problems, arbitrary public interaction and repeated sample reuse do not improve the rate over simpler restricted protocols. The key technical ingredient in our paper is a contraction inequality for the Fisher information in the transcript: each client's contribution is bounded both by the Fisher information in its local experiment and by its total privacy budget.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。