Feature Selection and Junta Testing are Statistically Equivalent

For a function \(f : \{0, 1\}^n \rightarrow \{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 \begin{align} \Theta\left( \frac{1}{\varepsilon} \left(\sqrt{2^{k} \log\binom{n}{k}} + \log\binom{n}{k} \right) \right).\end{align}