Feature Selection and Junta Testing are Statistically Equivalent

For a function $f\text{\hspace{0.17em}⁣}:\{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 $$\mathrm{\Theta }\left(\frac{1}{\epsilon }(\sqrt{2^k\log \left(\genfrac{}{}{0px}{}{n}{k}\right)}+\log \left(\genfrac{}{}{0px}{}{n}{k}\right))\right)\mathrm{.}$$