Feature Selection and Junta Testing are Statistically Equivalent

2025/05/07 by Lorenzo Beretta, Beretta, Lorenzo, Nathaniel Harms +3 · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Statistical Methods and Inference

paper · pdf · doi:10.48550/arxiv.2505.04604

openalex publication_date 2025/05/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For a function f \colon \0,1\ⁿ → \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 Θ(\frac 1 ε ( √2^k log n \choose k + log n \choose k)).

Cited by

• Computational Complexity in Property Testing

Related

• Near-Optimal Algorithm for Distribution-Free Junta Testing
• Testing Junta Truncation
• Almost Optimal Distribution-free Junta Testing
• Distribution-free Junta Testing
• Testing Juntas and Junta Subclasses with Relative Error