Streaming Submodular Maximization with Differential Privacy
Authors: Anamay Chaturvedi, Huy Nguyen, Thy Dinh Nguyen
ICML 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Finally, we complement our theoretical analysis with experimental corroboration.In this section, we empirically evaluate our approach on a practical instance of private submodular maximization, k-medians clustering.We compare the performance of Algorithm 3 with Laplace and Gumbel noise on two data sets.In Figure 3 and Figure 6 we graph the clustering cost versus the cardinality constraint k on the Taxi and Synthetic data sets respectively. |
| Researcher Affiliation | Academia | 1Khoury College of Computer Science, Northeastern University, Boston, USA. |
| Pseudocode | Yes | Algorithm 1 Streaming algorithm for monotone submodular maximization subject to a cardinality constraint, Badanidiyuru et al. (2014)input Monotonic submodular function f, cardinality constraint parameter k, element stream V , approximation parameter θ, estimate O of the optimum cost f(OPT)S for e V do if f(e|S) O/(2k) and |S| < k then S S {e} end if end for output S |
| Open Source Code | Yes | The code used to run all experiments may be found at www.github.com/thydnguyen/Priv Submodular Opt. |
| Open Datasets | Yes | First, following Mitrovic et al. (2017); Chaturvedi et al. (2021) we use the Uber data set (Five Thirty Eight, 2019) of Uber cab pick ups in Manhattan for the month of April 2014;... URL https://www.kaggle.com/datasets/fivethirtyeight/uber-pickups-in-new-york-city. |
| Dataset Splits | No | The paper does not provide specific train/validation/test dataset splits with percentages, counts, or a detailed splitting methodology for their own experiments. |
| Hardware Specification | Yes | All experiments were performed on a PC with 5.2 GHz i9 chip and 64 GB RAM. |
| Software Dependencies | No | The paper does not explicitly list specific software dependencies with version numbers (e.g., Python, PyTorch, TensorFlow versions). |
| Experiment Setup | Yes | For both data sets, we set δ = 1/|P|1.5 and θ = 0.2.We set E = min (k log n/ε, |P|/2) for the private algorithms, and E = min(maxei V f(ei), k log n/ε, |P|/2) for the non-private algorithm.For this experiment, we apply basic composition and set ε = ε/T, δ = δ/T. |