We study the problem of computing a U-statistic with a kernel function f of degree k ≥ 2, i.e., the average of some function f over all k-tuples of instances, in a federated learning setting. Ustatistics of degree 2 include several useful statistics such as Kendall's τ coefficient, the Area under the Receiver-Operator Curve and the Gini mean difference. Existing methods provide solutions only under the lower-utility local differential privacy model and/or scale poorly in the size of the domain discretization. In this work, we propose a protocol that securely computes U-statistics of degree k ≥ 2 under central differential privacy by leveraging Multi Party Computation (MPC). Our method substantially improves accuracy when compared to prior solutions. We provide a detailed theoretical analysis of its accuracy, communication and computational properties. We evaluate its performance empirically, obtaining favorable results, e.g., for Kendall's τ coefficient, our approach reduces the Mean Squared Error by up to four orders of magnitude over existing baselines.
Figure 1: Online total communication cost (left) and MSE (right) as a function of the number of parties n . for the computation of Gini mean difference for ϵ=1 . The number of discretization bins is set to t=256 . Each data point xi is uniformly drawn from [0,1] . For Umpc , we sample 2n edges for ∣E∣ .
Figure 2: Online per-party computation cost (left) and online server computation cost (right) as a function of the number of parties, for the computation of Gini mean difference for ϵ=1 . The number of discretization bins is t=256 . Each data point xi is uniformly drawn from [0,1] . For Umpc , we sample 2n pairs for ∣E∣ .
Figure 3: Online total communication cost (left) and online total computation cost (right) for computing the Kendall’s τ coefficient over the number of discretization bins t . The total computation cost is defined as the sum of the server computation and n times the per-party computation cost. The communication and computation costs vary with ϵ={0,1} only for Ghazi and GhaziSM . The dataset is taken from ( Moro & Cortez, 2014 ) and contains n=4521 entries. For Umpc , we sample 2n pairs for ∣E∣ , i.e., ∣E∣=9042 .
Figure 4: MSE over the number of discretization bins t (left) and MSE over the online communication cost (right) for computing the Kendall’s τ coefficient for ϵ={0.1,1} . The dataset is taken from ( Moro & Cortez, 2014 ) and contains n=4521 entries. For Umpc , we sample 2n pairs for ∣E∣ , i.e., ∣E∣=9042 .
Balanced ϵ=1
2.210−6
Uniform ϵ=1
2.710−6
Bernoulli ϵ=1
9.110−6
Table 2: MSE comparison for protocol Umpc when E is sampled using BalancedSamp (Algorithm 1 ), Bernoulli sampling and sampling without replacement for computing the duplicate pair ratio over the size of the edge set E for ϵ=1 . The dataset is taken from ( Moro & Cortez, 2014 ) and contains n=4521 data points.
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Protocol
Population MSE
Sample MSE
Bell
O(nϵ2t2+t2Lf2)
O(nϵ2t2+t2Lf2)
Ghazi
O(nϵ2t2Lf2logt+t2Lf2)
O(nϵ2t2Lf2logt+t2Lf2)
We
O(n1)
O(∣E∣1+n2ϵ21)
Appendix
Table 3: Summary of the MSE for the compared protocols
Figure 5: Online total communication cost, MSE, per-party and server computation costs comparison for computing the Kendall’s τ coefficient with protocols Bell , Ghazi , GhaziSM and Umpc for ϵ=1 and t=64 . The dataset is taken from ( Janosi Andras & Robert, 1989 ) . For Umpc , we sample 2n edgesfor ∣E∣ .
Figure 6: Online total communication cost, MSE, per-party and server computation costs comparison for computing Uf with f(x,y)=I[x=y] with ϵ=1 and t=64 . Data represents the diagnosis of heart diseases of patients from ( Janosi Andras & Robert, 1989 ) . For Umpc , we sample 2n edges for ∣E∣ .
Federated Learning is a leading framework for training ML and AI models collaboratively across numerous user devices or databases. We study the trade-offs among estimation accuracy, privacy constraints, and communication cost for differentially private (DP) federated M estimation. The two standard methods in the literature are FedAvg, which may suffer from high federation bias, and FedSGD, which can incur high communication cost. Aimed at improving accuracy at a reduced communication cost, we propose FedHybrid, which uses FedSGD starting with an improved initialization by the FedAvg estimator. We propose FedNewton, which averages local Newton iterations to reduce bias in FedAvg, achieving an estimation accuracy comparable to FedSGD with much fewer communication rounds when the number of clients grows sufficiently slowly. We establish finite sample upper bounds on the mean-squared error rates of the DP versions of these estimators as functions of the number of clients, local sample sizes, privacy budget, and number of iterations. We further derive a minimax lower bound on the MSE of any iterative private federated procedure that provides a benchmark to assess the optimality gap of these methods. We numerically evaluate our methods for training a logistic regression and a neural network on the computer vision datasets MNIST and CIFAR-10.
Arnab Auddy, Xiangni Peng, Subhadeep Paul
Department of Statistics · The Ohio State University
We consider differentially private (DP) optimization in the federated setting, where a DP estimate of the feature covariance matrix serves as a Hessian approximation for generalized linear models. Existing central DP methods for covariance estimation have communication cost that grows quadratically in the data dimension, while existing baselines with linear communication cost are only locally private and degrade as the number of clients increases. As a remedy, we propose a federated DP-PCA framework that achieves linear communication cost while providing central DP guarantees under secure aggregation. It consists of a DP rank selection step, a DP power method, and a noisy release of the covariance projected onto the selected low-dimensional subspace. We give error bounds for this covariance estimate and for the resulting low-communication preconditioned DP gradient descent. Empirically, our proposed DP optimization method matches a centralized baseline with quadratic communication cost at a fraction of the communication.
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.
T. Tony Cai, Yicheng Li
Department of Statistics and Data Science, The Wharton School, University of Pennsylvania, Philadelphia, PA, USA. · KLATASDS-MOE, School of Statistics, East China Normal University, Shanghai, China.