Empirical risk minimization in non-interactive local differential privacy revisited

Di Wang, Marco Gaboardi, Jinhui Xu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

35 Scopus citations


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 n), we first show that if the loss function is (∞, T)-smooth, we can avoid a dependence of the sample complexity, to achieve error α, on the exponential of the dimensionality p with base 1/α (i.e., α−p), which answers a question in [19]. 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 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 [19].
Original languageEnglish (US)
Title of host publicationAdvances in Neural Information Processing Systems
PublisherNeural information processing systems foundation
Number of pages10
StatePublished - Jan 1 2018
Externally publishedYes


Dive into the research topics of 'Empirical risk minimization in non-interactive local differential privacy revisited'. Together they form a unique fingerprint.

Cite this