Tight Bounds for Learning RUMs from Small Slates
Authors: Flavio Chierichetti, Mirko Giacchini, Ravi Kumar, Alessandro Panconesi, Andrew Tomkins
NeurIPS 2024 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our contributions. We present two main results representing paired upper and lower bounds for this question. The upper bound shows that... Our new algorithm learns any RUM to within an ℓ -error (resp., ℓ1-error) of ϵ > 0 in ϵ (resp., n O( ϵ )). Our near-matching lower bound shows that... Based on this lower bound, we also obtain lower bounds to fractional extensions of the well-studied k-deck and trace reconstruction problems. (Introduction) Also, in Neur IPS Paper Checklist, question 4 asks: 'Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?' Answer: [NA] Justification: the paper does not include experiments. |
| Researcher Affiliation | Collaboration | Flavio Chierichetti Sapienza University of Rome EMAIL Mirko Giacchini Sapienza University of Rome EMAIL Ravi Kumar Google, Mountain View EMAIL Alessandro Panconesi Sapienza University of Rome EMAIL Andrew Tomkins Google, Mountain View EMAIL |
| Pseudocode | No | Appendix D provides a description of how coefficients can be computed, noting 'it is easy to devise a dynamic programming algorithm' but it is presented in prose, not as a formally structured pseudocode or algorithm block. |
| Open Source Code | No | The Neur IPS Paper Checklist states: 'Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [NA] Justification: the paper does not include experiments requiring code.' |
| Open Datasets | No | The paper is theoretical and does not use any datasets. |
| Dataset Splits | No | The paper is theoretical and does not perform experiments requiring data splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental hardware. |
| Software Dependencies | No | The paper is theoretical and does not list specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not include an experimental setup or hyperparameters. |