Empirical Risk Minimization in Non-interactive Local Differential Privacy Revisited

By Di Wang, Marco Gaboardi, Jinhui Xu. 2018

68 citations recorded by the source corpus.

In this paper, we revisit the Empirical Risk Minimization problem in the non-interactive local model of differential privacy. In the case of constant or low dimensions ($p\ll n$), we first show that if the loss function is $(\infty, T)$-smooth, we can avoid a dependence of the sample complexity, to achieve error $\alpha$, on the exponential of the dimensionality $p$ with base $1/\alpha$ ({\em i.e.,} $\alpha^{-p}$), which answers a question in \cite{smith2017interaction}. Our approach is based on polynomial approximation. Then, we propose player-efficient algorithms with $1$-bit communication complexity and $O(1)$ computation cost for each player. The error bound is asymptotically the same as the original one. With some additional assumptions, we also give an efficient algorithm for the server. In the case of high dimensions ($n\ll p$), we show that if the loss function is a convex generalized linear function, the error can be bounded by using the Gaussian width of the constrained set, instead of $p$, which improves the one in \cite{smith2017interaction}.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

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

1. Tianhao Wang
2. Huanyu Zhang
3. Ninghui Li
4. Somesh Jha
5. Edwige Cyffers
6. Marco Gaboardi
7. Aurélien Bellet
8. Di Wang

In Computational Theory and Mathematics

1. Marco Gaboardi
2. Huanyu Zhang
3. Di Wang
4. Jinhui Xu
5. Somesh Jha
6. Aurélien Bellet
7. Ninghui Li
8. Edwige Cyffers

Citations in the corpus

• Privacy Amplification by Decentralization (2020, background): “The fundamental limits of machine learning under LDP have been studied by Zheng et al. (2017) and Wang et al. (2018).”
• Distributed Differentially Private Averaging with Improved Utility and Robustness to Malicious Parties (2020, background): “This very strong model of privacy comes at a significant cost in terms of the accuracy of the resulting estimates, see [70, 66] for the limits of machine learning in the local model.”
• Locally Differentially Private Heavy Hitter Identification (2017, background): “For example, mean estimation [11], [27], frequent itemset mining [29], [37], releasing marginals under LDP [10], [30], [41], key-value pair estimation [40], evolving data monitoring [15], [22], and empirical risk minimization [31], [32].”
• Consistent and Accurate Frequency Oracles under Local Differential Privacy (2019, background): “, finding heavy hitters [5–7, 17, 35], frequent itemset mining [27, 36], releasing marginals under LDP [9, 28, 40], keyvalue pair estimation [39], evolving data monitoring [15, 20], and empirical risk minimization [30, 31].”
• Estimating Smooth GLM in Non-interactive Local Differential Privacy Model with Public Unlabeled Data (2019, methodology): “This is a quite common assumption in related works such as (Wang et al., 2018, 2019a).”