Myersonian Regression
Authors: Allen Liu, Renato Leme, Jon Schneider
NeurIPS 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main result is a polynomial time approximation scheme (PTAS) using dimensionality reduction. We complement this result by showing that the Myersonian regression problem (MR) is NP-hard using a reduction from 1-IN-3-SAT. In this paper we give the first provable approximation algorithm for the ERM problem without assumptions on the data. We also establish hardness of approximation that complements our algorithmic results. We believe these are the first hardness results for this problem. Even establishing whether exactly solving ERM was NP-hard for a reasonable class of pricing policies was open prior to this work. |
| Researcher Affiliation | Collaboration | MIT cliu568@mit.edu Renato Paes Leme Google Research renatoppl@google.com Jon Schneider Google Research jschnei@google.com |
| Pseudocode | No | The paper describes algorithms and their steps mathematically and through textual explanation within the 'Approximation Algorithms' section, but it does not include formal pseudocode blocks or algorithms labeled as such. |
| Open Source Code | No | The paper does not contain any explicit statements or links indicating that the source code for the described methodology is available. |
| Open Datasets | No | The paper discusses a 'training dataset' in a conceptual sense for the problem (e.g., 'we get to observe a training dataset {(xt, vt)}t=1..m'). However, it does not specify a concrete, publicly available dataset by name, URL, DOI, or formal citation. |
| Dataset Splits | No | The paper discusses training and testing conceptually in the context of contextual learning. However, it does not specify concrete dataset splits (e.g., 70/15/15 percentages, sample counts, or references to predefined splits) needed for reproducibility. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithmic design and complexity analysis. It does not describe any experimental setup or the specific hardware used to run experiments. |
| Software Dependencies | No | The paper is theoretical and does not discuss implementation details that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical, presenting algorithms and proofs rather than empirical experiments. Therefore, it does not provide details on experimental setup such as hyperparameters, training configurations, or system-level settings. |