Empirical Risk Minimization in Non-interactive Local Differential Privacy Revisited
Authors: Di Wang, Marco Gaboardi, Jinhui Xu
NeurIPS 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we revisit the Empirical Risk Minimization problem in the noninteractive 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]." and "Table 1: Comparisons with existing results in [19] (we assume p is a constant). When the error α O( 1 p), the sample complexity of (8, T)-smooth loss functions is less than the existing result. When the error α O( 1 16p ), the sample complexity for ( , T)-smooth loss functions is less than the previous results. |
| Researcher Affiliation | Academia | Di Wang Marco Gaboardi Jinhui Xu Department of Computer Science and Engineering State University of New York at Buffalo Buffalo, NY, 14260 Email:{dwang45,gaboardi,jinhui}@buffalo.edu |
| 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 DR-ERM-LDP |
| Open Source Code | No | The paper does not provide any statement or link for the release of source code for the methodology described. |
| Open Datasets | No | The paper refers to abstract datasets (e.g., "A dataset D = {x1, x2 , xn} Dn") and general data characteristics (e.g., "player i [n] holding data vi [0, b]"), but does not mention or provide access information (links, DOIs, specific citations) for any publicly available or open dataset used in experiments. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments that would require explicit training, validation, or test dataset splits. Therefore, no such information is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe experiments, therefore no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe experiments or implementations that would require specific software dependencies with version numbers. No such information is provided. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup, therefore no specific hyperparameter values or system-level training settings are provided. |