A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913803470372864 |
|---|---|
| author | Chen, Xi Patel, Shyamal Servedio, Rocco A. |
| author_facet | Chen, Xi Patel, Shyamal Servedio, Rocco A. |
| contents | The main conceptual contribution of this paper is identifying a previously unnoticed connection between two central problems in computational learning theory and property testing: agnostically learning conjunctions and tolerantly testing juntas. Inspired by this connection, the main technical contribution is a pair of improved algorithms for these two problems.
In more detail,
- We give a distribution-free algorithm for agnostically PAC learning conjunctions over $\{\pm 1\}^n$ that runs in time $2^{\widetilde{O}(n^{1/3})}$, for constant excess error $\varepsilon$. This improves on the fastest previously published algorithm, which runs in time $2^{\widetilde{O}(n^{1/2})}$ [KKMS08].
- Building on the ideas in our agnostic conjunction learner and using significant additional technical ingredients, we give an adaptive tolerant testing algorithm for $k$-juntas that makes $2^{\widetilde{O}(k^{1/3})}$ queries, for constant "gap parameter" $\varepsilon$ between the "near" and "far" cases. This improves on the best previous results, due to [ITW21, NP24], which make $2^{\widetilde{O}(\sqrt{k})}$ queries. Since there is a known $2^{\widetildeΩ(\sqrt{k})}$ lower bound for non-adaptive tolerant junta testers, our result shows that adaptive tolerant junta testing algorithms provably outperform non-adaptive ones. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_16065 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions Chen, Xi Patel, Shyamal Servedio, Rocco A. Data Structures and Algorithms The main conceptual contribution of this paper is identifying a previously unnoticed connection between two central problems in computational learning theory and property testing: agnostically learning conjunctions and tolerantly testing juntas. Inspired by this connection, the main technical contribution is a pair of improved algorithms for these two problems. In more detail, - We give a distribution-free algorithm for agnostically PAC learning conjunctions over $\{\pm 1\}^n$ that runs in time $2^{\widetilde{O}(n^{1/3})}$, for constant excess error $\varepsilon$. This improves on the fastest previously published algorithm, which runs in time $2^{\widetilde{O}(n^{1/2})}$ [KKMS08]. - Building on the ideas in our agnostic conjunction learner and using significant additional technical ingredients, we give an adaptive tolerant testing algorithm for $k$-juntas that makes $2^{\widetilde{O}(k^{1/3})}$ queries, for constant "gap parameter" $\varepsilon$ between the "near" and "far" cases. This improves on the best previous results, due to [ITW21, NP24], which make $2^{\widetilde{O}(\sqrt{k})}$ queries. Since there is a known $2^{\widetildeΩ(\sqrt{k})}$ lower bound for non-adaptive tolerant junta testers, our result shows that adaptive tolerant junta testing algorithms provably outperform non-adaptive ones. |
| title | A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.16065 |