Local Privacy and Statistical Minimax Rates

By John C. Duchi, Michael I. Jordan, Martin J. Wainwright. 2013

1,307 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Statistics and Probability, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

In Privacy & Security

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “While LDP protocols are effective at enforcing privacy and have theoretical justifications [156, 135, 136], a number of results have shown that achieving local differential privacy while preserving utility is challenging particularly, especially in high-dimensional data settings [229, 388, 219, 51, ”
Practical and Private (Deep) Learning without Sampling or Shuffling (2021, background): “Although not stated formally in the literature, a simple argument shows that locally private SGD (Duchi et al., 2013) can achieve the same regret as in (Smith & Thakurta, 2013).”
The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation (2021, background): “However, it is now well-established that local DP usually leads to a steep hit in accuracy (Kasiviswanathan et al., 2011; Duchi et al., 2013; Kairouz et al., 2016).”
Privacy Amplification by Decentralization (2020, background): “The strongest model is local differential privacy (LDP) [25, 13], where each participant (user) does not trust anyone and assumes that an adversary may observe everything that she/he shares with anyone.”
On Distributed Differential Privacy and Counting Distinct Elements (2020, background): “The i th user has an input x i ∈ { 0 , 1 } D and the goal is to output an index j ∈ Selection is well-studied in DP (e.g., [17, 40, 41]) and its variants are useful primitives for several statistical and algorithmic problems including feature selection, hypothesis testing and clustering.”
AdaCliP: Adaptive Clipping for Private SGD (2019, methodology): “In input perturbation, the dataset D is first modified using Laplace or Gaussian mechanism and the resulting perturbed dataset is used to train the machine learning model [23].”
Federated Heavy Hitters Discovery with Differential Privacy (2019, background): “…of fundamental work shows that in the context of learning distributions and heavy hitters, local DP often leads to a signiﬁcant reduction in utility (Kairouz et al., 2014; Wang et al., 2017; Bassily et al., 2017; Kairouz et al., 2016; Ye and Barg, 2018; Duchi et al., 2013; Cormode et al., 2018).”
Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction (2018, background): “Distribution learning under LDP constraints has been studied in [4], [21], [37], [52], [56], all providing sample-optimal schemes with different merits.”
Protection Against Reconstruction and Its Applications in Private Federated Learning (2018, methodology): “In Figure 2, we give a visual representation comparing the approach of Duchi et al. [30] and our mechanism, which we term PrivUnit 2 (see Algorithm 1); in the next subsection we demonstrate the choices of γ and scaling factors to make the scheme diﬀerentially private and unbiased.”
The Power of the Hybrid Model for Mean Estimation (2018, background): “However, DP mean estimation of distributions under both the TCM and LM has been studied since the models’ introductions [17, 21, 56], and continues to be actively studied to this day [2, 15, 18, 20, 22, 28, 29, 32, 37, 39–42].”
The structure of optimal private tests for simple hypotheses (2018, background): “s a signiﬁcant cost, even for relaxed deﬁnitions of privacy (e.g. [BUV14, DSS+15]), and we remain far from a general characterization of the statistical cost of privacy. Duchi, Jordan, and Wainwright [DJW13] give a characterization for the special case of simple tests by local differentially private”
Privacy Amplification by Iteration (2018, neutral): “Noisy SGD [20], [25] Õ (√ d ε2n ) Õ (√ dk ε2n ) ε”
Distributed Differential Privacy via Shuffling (2018, background): “[12] extended this lower bound to a wide range of natural problems, showing that the error must blowup by at least Ω( √ n), and often by an additional factor growing with the data dimension.”
Distributed Simulation and Distributed Inference (2018, background): “Closer to our work is the distributed parameter estimation and functional estimation that has gained signiﬁcant attention in recent years (see e.g. [DJW13, GMN14, BGM + 16, Wat18]).”
Geometric Lower Bounds for Distributed Parameter Estimation Under Communication Constraints (2018, background): “Distributed parameter estimation and function computation has been considered in many recent works; we refer to Duchi et al. (2013); Zhang et al. (2013); Shamir (2014); Garg et al. (2014); Braverman et al. (2016); Xu and Raginsky (2017) and the references therein for an overview.”