betaFeedback

WorksMathematics

Federated Differential Privacy with Batch Contamination

Abstract

We study mean estimation under federated differential privacy (FDP) constraints and batch contamination, considering both Gaussian and heavy-tailed distributions. In the homogeneous setting, where sample sizes and privacy budgets are constant across servers, we show that the costs of privacy and contamination disentangle. Under a bounded vvth moment condition, with v∈(1,∞)v \in (1, \infty), the cost of batch contamination is of order (ε/n)2−2/v∨ε2/n(\varepsilon/n)^{2-2/v}\vee \varepsilon^2/n, where ε\varepsilon is the contamination level and nn is the per-batch sample size. This reveals a phase transition at ε≍n1−v/2\varepsilon\asymp n^{1-v/2}, for v>2v > 2, which is the first of its kind in the literature. We develop a two-stage procedure that achieves the minimax rate up to poly-logarithmic factors. A key component is a private smoothed voting procedure tailored to the FDP setting that provides optimal sensitivity control. For heterogeneous batch sample sizes and privacy budgets, we introduce a batch partitioning framework that groups batches with comparable per-batch sample sizes and privacy budgets. Surprisingly, the minimax rate is determined, up to poly-logarithmic factors, by the most informative group of batches. Consequently, in some regimes, it is minimax optimal to use only an arbitrarily small proportion of the data set. Heterogeneity also introduces interactions between the costs of privacy and contamination, in contrast to their disentanglement in the homogeneous setting. For unknown contamination level, we propose an adaptive, near-minimax optimal Lepski-type extension for the heterogeneous Gaussian setting, designed specifically to prevent privacy leakage by ensuring no repeated use of data points.

Paper details

vlnc:W_r73wepxd
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…