On Differential Privacy for Adaptively Solving Search Problems via Sketching
Authors: Shiyuan Feng, Ying Feng, George Zhaoqi Li, Zhao Song, David Woodruff, Lichen Zhang
ICML 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | The paper primarily focuses on presenting new algorithms, theoretical frameworks, and proving their properties and complexity bounds. For example, it states, "We give algorithms for each of these problems that achieve similar tradeoffs" and "We now prove the privacy and utility of our algorithm." There are no sections detailing experimental setups, empirical evaluations on datasets, performance metrics, or comparisons to baselines on real-world data. |
| Researcher Affiliation | Academia | All listed affiliations are academic institutions: "1Peking University 2MIT 3Carnegie Mellon University 4University of California, Berkeley." The provided email addresses, EMAIL and EMAIL, are either generic personal emails often used in academia or directly linked to a university domain, confirming an academic setting. |
| Pseudocode | Yes | The paper includes multiple structured algorithm descriptions with clear steps. For instance, in Section B.2, an algorithm for 'Reducing Monte Carlo Search to Selection' is presented with distinct steps under headings like 'Initialization', 'Receive query vector v Rd', 'Output ui...', and 'Receive update vector u Rd'. Similar structured descriptions for algorithms like ADAPTIVEREGDP, ADAPTIVEREGPATH, and ADAPTIVEREGPRECONDITIONER are found in Sections D.2, D.3, and D.4 respectively. |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code, links to code repositories (e.g., GitHub), or mentions of code being available in supplementary materials. The 'Impact Statement' section briefly mentions potential efficiency improvement and reduction in carbon emission but does not discuss code availability. |
| Open Datasets | No | The paper discusses abstract data structures and theoretical concepts using terms like 'n-point dataset' (Definition 1.1) or 'U R n d be the design matrix' (Assumption 1.4). However, it does not refer to any specific named public datasets (e.g., CIFAR-10, MNIST), nor does it provide any links, DOIs, or formal citations to publicly available datasets that would be used for empirical evaluation. |
| Dataset Splits | No | The paper is theoretical, focusing on algorithm design and analysis rather than empirical evaluation. Consequently, there are no experimental setups that would require specifying training, validation, or test dataset splits. The text does not contain any information regarding how datasets are partitioned. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm design, complexity analysis, and proofs. It does not include any experimental results or discussions of computational runtime on specific hardware. Therefore, no details about specific GPU/CPU models, processor types, memory, or cloud computing resources are provided. |
| Software Dependencies | No | The paper is primarily theoretical and does not describe the implementation of its algorithms or any empirical evaluations. While it mentions third-party tools like 'CPLEX' in the related work, it does not specify any software dependencies with version numbers for its own methodology. |
| Experiment Setup | No | The paper is theoretical and concentrates on the design and analysis of algorithms. It does not present any experimental results, and thus, there are no descriptions of specific experimental setups, hyperparameter values, training configurations, or system-level settings. |