Robust Algorithms on Adaptive Inputs from Bounded Adversaries
Authors: Yeshwanth Cherapanamjeri, Sandeep Silwal, David Woodruff, Fred Zhang, Qiuyi Zhang, Samson Zhou
ICLR 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Finally, we complement our theoretical results with additional empirical evaluations. ... Finally, we supplement our theoretical results with a number of empirical evaluations, which are in the appendix. |
| Researcher Affiliation | Collaboration | Yeshwanth Cherapanamjeri UC Berkeley yeshwanth@berkeley.edu Sandeep Silwal MIT silwal@mit.edu David P. Woodruff Carnegie Mellon University dwoodruf@andrew.cmu.edu Fred Zhang UC Berkeley z0@berkeley.edu Qiuyi (Richard) Zhang Google Research qiuyiz@google.com Samson Zhou UC Berkeley and Rice University samsonzhou@gmail.com |
| Pseudocode | Yes | Algorithm 1 Initialize the data structure, i.e., preprocessing ... Algorithm 2 Update data structure and maintain regression cost ... Algorithm 3 Preprocessing step for Algorithm 4 ... Algorithm 4 Dynamic algorithm for maintaining regression cost under adaptive updates ... Algorithm 5 A simple SVD-based algorithm for dynamic regression ... Algorithm 6 Adaptive Algorithm Interaction ... Algorithm 7 Adaptive Distance Estimation ... Algorithm 8 Adaptive Distance Estimation with SRHTs ... Algorithm 9 Adaptive Kernel Density Estimation |
| Open Source Code | No | The paper mentions using and citing external open-source libraries (e.g., "The Hadamard transform code is from Andoni et al. (2015)", "we use Google’s differential privacy library"). However, it does not state that the source code for the methodology or specific implementations described within this paper are made publicly available by the authors. |
| Open Datasets | No | The paper describes how the adaptive queries are generated for the experiment: "Our input queries are the same adaptive queries used in Cherapanamjeri & Nelson (2020). To summarize, let Π denote the map used in the JL benchmark stated above. The i-th query for 1 ≤ i ≤ 5000 will be of the form qi = Σj=1^i (-1)^Wj zj, which we then normalize to have unit norm. The zj are standard Gaussian vectors." This describes a data generation process rather than referring to a specific, publicly available dataset with concrete access information (e.g., a link or a formal citation to a dataset repository). |
| Dataset Splits | No | The paper does not specify distinct training, validation, and test dataset splits. The experimental evaluation is conducted on a sequence of 5000 adaptive queries, where the inputs are dynamically generated rather than partitioned from a fixed dataset. |
| Hardware Specification | Yes | Our experiments are done on a 2021 M1 Macbook Pro with 32 gigabytes of RAM. |
| Software Dependencies | Yes | We implemented all algorithms in Python 3.5 using Numpy. The Hadamard transform code is from Andoni et al. (2015)1 and we use Google’s differential privacy library2 for the private median implementation. |
| Experiment Setup | Yes | In our experiments, d = 4096, m = 250, r = 200, and k = 5. These are exactly the parameters chosen in prior works Cherapanamjeri & Nelson (2020). We will have 5000 adaptive queries qi which are described shortly. |