Optimal Hypothesis Selection in (Almost) Linear Time
Authors: Maryam Aliakbarpour, Mark Bun, Adam Smith
NeurIPS 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present the first algorithm that operates in almost linear time ( O(n/ϵ3)) and achieves α = 3. This result improves upon a long line of hypothesis selection research. Previously known algorithms had either worse time complexity, a larger α factor, or additional assumptions about the problem setting. Additionally, we provide another (almost) linear-time algorithm with better dependency on the additive accuracy parameter ϵ, albeit with a slightly worse accuracy parameter of α = 4. We do not have any experimental results. |
| Researcher Affiliation | Academia | Maryam Aliakbarpour Department of Computer Science Rice University Houston, TX 77005 maryama@rice.edu Mark Bun Department of Computer Science Boston University Boston, MA 02215 mbun@bu.edu Adam Smith Department of Computer Science Boston University Boston, MA 02215 ads22@bu.edu |
| Pseudocode | Yes | Algorithm 1 An algorithm for hypothesis selection with α = 3. Algorithm 2 An algorithm to identify a prompting hypothesis (simple version). Algorithm 3 An algorithm to identify a prompting hypothesis. Algorithm 4 finds a hypothesis that is 4 max (σ, OPT) + ϵ close to P. Algorithm 5 finds a (σ + ϵ , 3 σ + 3 ϵ , m)-seed Algorithm 6 aims to find a better seed. Algorithm 7 computes W(Hi). |
| Open Source Code | No | The paper describes theoretical algorithms and does not mention releasing code or provide repository links. The NeurIPS Paper Checklist states 'We do not have any experimental results.' for questions regarding code. |
| Open Datasets | No | The paper is purely theoretical and does not involve experimental evaluation on datasets. The NeurIPS Paper Checklist explicitly states 'We do not have any experimental results.' for data-related questions. |
| Dataset Splits | No | The paper is purely theoretical and does not involve experimental evaluation on datasets. The NeurIPS Paper Checklist explicitly states 'We do not have any experimental results.' for data-related questions. |
| Hardware Specification | No | The paper is purely theoretical and does not describe any experiments requiring hardware. The NeurIPS Paper Checklist explicitly states 'We do not have any experimental results.' for questions regarding computer resources. |
| Software Dependencies | No | The paper describes theoretical algorithms and does not mention any specific software dependencies or versions. The NeurIPS Paper Checklist explicitly states 'We do not have any experimental results.' for questions regarding software. |
| Experiment Setup | No | The paper is theoretical and does not involve experimental setup details such as hyperparameters or training configurations. The NeurIPS Paper Checklist explicitly states 'We do not have any experimental results.' for questions regarding experimental settings. |