Faster Differentially Private Top-$k$ Selection: A Joint Exponential Mechanism with Pruning
Authors: Hao WU, Hanwen Zhang
NeurIPS 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experimental results show that our algorithm runs orders of magnitude faster than their approach, while achieving similar empirical accuracy. Finally, we perform extensive experiments to Verify the theoretical analysis of our algorithm. Demonstrate that our algorithm runs 10-100 times faster than JOINT on the tested datasets. Show that our algorithm maintains comparable accuracy to JOINT. |
| Researcher Affiliation | Academia | Hao WU University of Waterloo Canada hao.wu1@uwaterloo.ca Hanwen Zhang University of Copenhagen Denmark hazh@di.ku.dk |
| Pseudocode | Yes | Algorithm 1 Subset Sampling... Algorithm 2 Sequence Sampling... Algorithm 3 |
| Open Source Code | Yes | Our Python implementation is available publicly.3 Footnote 3: https://github.com/wuhao-wu-jiang/Differentially-Private-Top-k-Selection |
| Open Datasets | Yes | We utilize six publicly available datasets: Games (Steam video games with purchase counts) (Tamber, 2016), Books (Goodreads books with review counts) (Soumik, 2019), News (Mashable articles with share counts) (Fernandes et al., 2015), Tweets (Tweets with like counts) (Bin Tareaf, 2017), Movies (Movies with rating counts) (Harper and Konstan, 2016) and Foods (Amazon grocery and gourmet foods with review counts) (Mc Auley et al., 2015). |
| Dataset Splits | No | The paper does not explicitly mention training/validation/test dataset splits. It lists datasets used for experiments but does not define a separate validation set or split. |
| Hardware Specification | Yes | The experiments are conducted on mac OS system with M2 CPU and 24GB memory. |
| Software Dependencies | No | The paper mentions 'Python implementation' and 'Num Py' but does not specify any version numbers for Python or any libraries. |
| Experiment Setup | Yes | Parameter Ranges. The parameter ranges tested are as follows: k = 10, 20, . . . , 100, . . . , 200, ε = 1/4, 1/2, 1, 2, 4, β = 2 6, 2 8, 2 10, 2 12, 2 14. All experiments are repeated 200 times. The (ε, δ)-DP mechanism CDP-PEEL is configured with a δ parameter of 10 6. |