Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Replicable Uniformity Testing
Authors: Sihan Liu, Christopher Ye
NeurIPS 2024 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we revisit uniformity testing under the framework of algorithmic replicability [STOC 22], requiring the algorithm to be replicable under arbitrary distributions. While replicability typically incurs a Ļ 2 factor overhead in sample complexity, we obtain a replicable uniformity tester using only O( nĪµ 2Ļ 1) samples. To our knowledge, this is the first replicable learning algorithm with (nearly) linear dependence on Ļ. Lastly, we consider a class of symmetric" algorithms [FOCS 00] whose outputs are invariant under relabeling of the domain [n], which includes all existing uniformity testers (including ours). For this natural class of algorithms, we prove a nearly matching sample complexity lower bound for replicable uniformity testing. |
| Researcher Affiliation | Academia | Sihan Liu University of California San Diego La Jolla, CA EMAIL Christopher Ye University of California San Diego La Jolla, CA EMAIL |
| Pseudocode | Yes | Algorithm 1 RUNIFORMITYTESTER(p, Īµ, Ļ) Input :Sample access to distribution p on domain [n] Parameters :Īµ tolerance, Ļ replicability Output :ACCEPT if p Un is uniform, REJECT if d T V (p, Un) Īµ |
| Open Source Code | No | The paper is theoretical and presents algorithms and proofs. It does not mention providing open-source code for its methodology. The NeurIPS checklist also indicates 'NA' for questions related to code and data availability, confirming no code is provided. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments with datasets, thus no information about public datasets or their access is provided. |
| Dataset Splits | No | The paper is theoretical and does not report on experimental validation, thus no dataset split information for training, validation, or testing is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments that would require hardware specifications. Therefore, no hardware details are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not implement or describe any software requiring specific dependencies or version numbers. |
| Experiment Setup | No | The paper is purely theoretical and does not include any experimental setup details such as hyperparameters or training configurations. |