Collect at Once, Use Effectively: Making Non-interactive Locally Private Learning Possible

By Wenlong Mou, Liwei Wang. 2017

43 citations recorded by the source corpus.

Non-interactive Local Differential Privacy (LDP) requires data analysts to collect data from users through noisy channel at once. In this paper, we extend the frontiers of Non-interactive LDP learning and estimation from several aspects. For learning with smooth generalized linear losses, we propose an approximate stochastic gradient oracle estimated from non-interactive LDP channel, using Chebyshev expansion. Combined with inexact gradient methods, we obtain an efficient algorithm with quasi-polynomial sample complexity bound. For the high-dimensional world, we discover that under $\ell_2$-norm assumption on data points, high-dimensional sparse linear regression and mean estimation can be achieved with logarithmic dependence on dimension, using random projection and approximate recovery. We also extend our methods to Kernel Ridge Regression. Our work is the first one that makes learning and estimation possible for a broad range of learning tasks under non-interactive LDP model.

Subfields: Artificial Intelligence

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

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).”
Empirical Risk Minimization in Non-interactive Local Differential Privacy Revisited (2018, methodology): “[26] showed that for logistic regression, if the sample complexity satisfies n > O ( p( 8r α ) 4r log ( 4r ) 2cr ( 1 α2 2 ) ) , where c and r are independent of p, then there is a non-interactive ( , δ)-LDP algorithm with ErrP(θpriv) ≤ α.”
Consistent and Accurate Frequency Oracles under Local Differential Privacy (2019, background): “[41]) apply Gaussian noise, which can be shown to give worse utility.”
Estimating Smooth GLM in Non-interactive Local Differential Privacy Model with Public Unlabeled Data (2019, background): “Also, we note that the error bounds in Theorems 5 and 6 are dependent on the `1-norm of the upper bound of xi, while such a dependency is on the `2-norm in previous work such as (Smith et al., 2017; Zheng et al., 2017).”
CALM: Consistent Adaptive Local Marginal for Marginal Release under Local Differential Privacy (2018, background): “The problem of empirical risk minimization also attracts lots of investigation, both from the theoretically [33, 36, 42] and empirically [26].”