Abstract

In this paper, we study the Empirical Risk Minimization problem in thenon-interactive local model of differential privacy. We first show that if theERM loss function is $(\infty, T)$-smooth, then we can avoid a dependence ofthe sample complexity, to achieve error $\alpha$, on the exponential of thedimensionality $p$ with base $1/\alpha$ ({\em i.e.,} $\alpha^{-p}$), whichanswers a question in \cite{smith2017interaction}. Our approach is based onBernstein polynomial approximation. Then, we propose player-efficientalgorithms with $1$-bit communication complexity and $O(1)$ computation costfor each player. The error bound is asymptotically the same as the originalone. Also with additional assumptions we show a server efficient algorithm withpolynomial running time. At last, we propose (efficient) non-interactivelocally differential private algorithms, based on different types of polynomialapproximations, for learning the set of k-way marginal queries and the set ofsmooth queries.

 

Introduction (beta)

None

 

Conclusion (beta)

None