arXiv:2505.04604
Testing Juntas Optimally with Samples
원문 초록
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.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Interpretable Bayesian Tensor Network Kernel Machines with Automatic Rank and Feature Selection
Malware Classification Leveraging NLP & Machine Learning for Enhanced Accuracy
Simple is what you need for efficient and accurate medical image segmentation
Permutation-Free High-Order Interaction Tests
Scalable unsupervised feature selection via weight stability
FailureSensorIQ: A Multi-Choice QA Dataset for Understanding Sensor Relationships and Failure Modes
토론
이 논문과 연결된 포럼 글이 아직 없습니다.