Feature Selection and Junta Testing are Statistically Equivalent
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913951892111360 |
|---|---|
| author | Beretta, Lorenzo Harms, Nathaniel Koch, Caleb |
| author_facet | Beretta, Lorenzo Harms, Nathaniel Koch, Caleb |
| contents | For a function $f \colon \{0,1\}^n \to \{0,1\}$, the junta testing problem asks whether $f$ depends on only $k$ variables. If $f$ depends on only $k$ variables, the feature selection problem asks to find those variables. We prove that these two tasks are statistically equivalent. Specifically, we show that the ``brute-force'' algorithm, which checks for any set of $k$ variables consistent with the sample, is simultaneously sample-optimal for both problems, and the optimal sample size is \[ Θ\left(\frac 1 \varepsilon \left( \sqrt{2^k \log {n \choose k}} + \log {n \choose k}\right)\right). \] |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_04604 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Feature Selection and Junta Testing are Statistically Equivalent Beretta, Lorenzo Harms, Nathaniel Koch, Caleb Machine Learning Computational Complexity Data Structures and Algorithms For a function $f \colon \{0,1\}^n \to \{0,1\}$, the junta testing problem asks whether $f$ depends on only $k$ variables. If $f$ depends on only $k$ variables, the feature selection problem asks to find those variables. We prove that these two tasks are statistically equivalent. Specifically, we show that the ``brute-force'' algorithm, which checks for any set of $k$ variables consistent with the sample, is simultaneously sample-optimal for both problems, and the optimal sample size is \[ Θ\left(\frac 1 \varepsilon \left( \sqrt{2^k \log {n \choose k}} + \log {n \choose k}\right)\right). \] |
| title | Feature Selection and Junta Testing are Statistically Equivalent |
| topic | Machine Learning Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2505.04604 |