Tight Bounds for Learning RUMs from Small Slates
Authors: Flavio Chierichetti, Mirko Giacchini, Ravi Kumar, Alessandro Panconesi, Andrew Tomkins
NeurIPS 2024 | Conference 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 flavio@di.uniroma1.it Mirko Giacchini Sapienza University of Rome giacchini@di.uniroma1.it Ravi Kumar Google, Mountain View ravi.k53@gmail.com Alessandro Panconesi Sapienza University of Rome ale@di.uniroma1.it Andrew Tomkins Google, Mountain View atomkins@gmail.com |
| 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. |