Testing Juntas Optimally with Samples

2025-05-07 · Lorenzo Beretta, Nathaniel Harms, Caleb Koch

We prove tight upper and lower bounds of $\Theta\left(\tfrac{1}{\epsilon}\left( \sqrt{2^k \log\binom{n}{k} } + \log\binom{n}{k} \right)\right)$ on the number of samples required for distribution-free $k$-junta testing. This is the first tight bound for testing a natural class of Boolean functions in the distribution-free sample-based model. Our bounds also hold for the feature selection problem, showing that a junta tester must learn the set of relevant variables. For tolerant junta testing, we prove a sample lower bound of $\Omega(2^{(1-o(1)) k} + \log\binom{n}{k})$ showing that, unlike standard testing, there is no large gap between tolerant testing and learning.

📄 PDF Abstract BibTeX arXiv:2505.04604

Code (0)

등록된 구현이 없습니다.

Tasks

feature selection

Methods 이 논문이 사용한 방법론

Feature Selection Feature selection, also known as variable selection, attribute selection or variable subset selection, is the process of selecting a subset of relevant features (variables,…

SET Dynamic Sparse Training method where weight mask is updated randomly periodically

VC Dimension and Distribution-Free Sample-Based Testing

2020-12-07 · Eric Blais, Renato Ferreira Pinto Jr., Nathaniel Harms

We consider the problem of determining which classes of functions can be tested more efficiently than they can be learned, in the distribution-free sample-based model that corresponds to the standard PAC learning setting…

PAC learning

The Benefits of Temporal Correlations: SGD Learns k-Juntas from Random Walks Efficiently

2026-05-11 · Elisabetta Cornacchia, Dan Mikulincer, Elchanan Mossel arxiv

We study how temporal correlations in the data can make certain sparse learning problems efficiently learnable by gradient-based methods. Our focus is on Boolean k-juntas, a canonical sparse learning problem known to pos…

Sparse Learning

Robust testing of low-dimensional functions

2020-04-24 · Anindya De, Elchanan Mossel, Joe Neeman

A natural problem in high-dimensional inference is to decide if a classifier $f:\mathbb{R}^n \rightarrow \{-1,1\}$ depends on a small number of linear directions of its input data. Call a function $g: \mathbb{R}^n \right…

Model Compression

Exact Learning of Juntas from Membership Queries

2017-06-21 · Nader H. Bshouty, Areej Costa

In this paper, we study adaptive and non-adaptive exact learning of Juntas from membership queries. We use new techniques to find new bounds, narrow some of the gaps between the lower bounds and upper bounds and find new…

A Faster Algorithm Enumerating Relevant Features over Finite Fields

2019-03-15 · Mikito Nanashima

We consider the problem of enumerating relevant features hidden in other irrelevant information for multi-labeled data, which is formalized as learning juntas. A $k$-junta function is a function which depends on only $k$…