Empirical Risk Minimization in the Non-interactive Local Model of Differential Privacy
Authors: Di Wang, Marco Gaboardi, Adam Smith, Jinhui Xu
JMLR 2020 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we study the Empirical Risk Minimization (ERM) problem in the noninteractive Local Differential Privacy (LDP) model. Previous research on this problem (Smith et al., 2017) indicates that the sample complexity, to achieve error alpha, needs to be exponentially depending on the dimensionality p for general loss functions. In this paper, we make two attempts to resolve this issue by investigating conditions on the loss functions that allow us to remove such a limit. In our first attempt, we show that if the loss function is ( , T)-smooth, by using the Bernstein polynomial approximation we can avoid the exponential dependency in the term of alpha. We then propose player-efficient algorithms with 1-bit communication complexity and O(1) computation cost for each player. The error bound of these algorithms is asymptotically the same as the original one. With some additional assumptions, we also give an algorithm which is more efficient for the server. In our second attempt, we show that for any 1-Lipschitz generalized linear convex loss function, there is an (epsilon, delta)-LDP algorithm whose sample complexity for achieving error alpha is only linear in the dimensionality p. Our results use a polynomial of inner product approximation technique. Finally, motivated by the idea of using polynomial approximation and based on different types of polynomial approximations, we propose (efficient) non-interactive locally differentially private algorithms for learning the set of k-way marginal queries and the set of smooth queries. |
| Researcher Affiliation | Academia | Di Wang EMAIL Department of Computer Science and Engineering University at Buffalo, SUNY Buffalo, NY 14260, USA Marco Gaboardi EMAIL Department of Computer Science Boston University Boston, MA 02215, USA Adam Smith EMAIL Department of Computer Science Boston University Boston, MA 02215, USA Jinhui Xu EMAIL Department of Computer Science and Engineering University at Buffalo, SUNY Buffalo, NY 14260, USA |
| Pseudocode | Yes | Algorithm 1 1-dim LDP-AVG ... Algorithm 2 Local Bernstein Mechanism ... Algorithm 3 Player-Efficient Local Bernstein Mechanism with 1-bit communication per player ... Algorithm 4 Hinge Loss-LDP ... Algorithm 5 General Linear-LDP ... Algorithm 6 Local Chebyshev Mechanism for Qdisj,k ... Algorithm 7 Local Trigonometry Mechanism for QCh T ... Algorithm 8 Player-Efficient Local Bernstein Mechanism with O(log log n) bits communication complexity. ... Algorithm 9 Stochastic Intermediate Gradient Method |
| Open Source Code | No | The paper includes a license statement for the paper itself ('License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/. Attribution requirements are provided at http://jmlr.org/papers/v21/19-253.html.') but does not provide any explicit statements or links to source code for the methodology described in the paper. |
| Open Datasets | No | The paper discusses theoretical concepts using a generic 'data universe D' and 'dataset D = {(x1, y1), (x2, y2), ..., (xn, yn)} Dn'. In Section 6, it refers to data records as {0, 1}p or [ -1, 1]p for k-way marginals and smooth queries, but does not specify or provide access information for any publicly available or open datasets by name, link, or citation. |
| Dataset Splits | No | The paper focuses on theoretical analysis of sample complexity and error bounds. It refers to a generic 'dataset D' but does not provide specific details about training, validation, or test dataset splits for experimental reproduction. |
| Hardware Specification | No | The paper is theoretical, focusing on algorithms, privacy models, and sample complexity. It does not describe any experimental evaluations that would require specific hardware, thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper discusses mathematical and algorithmic concepts such as 'Bernstein polynomial approximation', 'Chebyshev polynomial approximation', and refers to existing algorithms like 'Stochastic Inexact Gradient Descent algorithm (Dvurechensky and Gasnikov, 2016)'. However, it does not specify any software libraries, platforms, or programming languages with version numbers required to reproduce experiments. |
| Experiment Setup | No | The paper focuses on theoretical contributions, including algorithm design and analysis of sample complexity and error bounds. It does not describe an experimental setup with specific hyperparameters, training configurations, or other system-level settings for empirical evaluation. |