论文标题
学习和测试用子立方体调节的术语分布
Learning and Testing Junta Distributions with Subcube Conditioning
论文作者
论文摘要
我们研究了$ \ { - 1,1 \}^n $在均匀分布上学习和测试junta发行的问题，如果$ k $ -junta的分布$ p $是$ k $ -junta，如果其概率质量函数$ p（x）$取决于大多数$ k $ variables的子集。主要贡献是一种算法，用于在$ k $ -junta分布中找到相关的坐标[BC18，CCKLW20]。我们提供两个申请： 1。学习$ k $ -junta分布的算法，带有$ \ tilde {o}（k/ε^2）\ log n + o（2^k/ε^2）$ 2。用于测试$ k $ -junta发行算法的算法，该算法具有$ \ tilde {o}（（（k + \ sqrt {n}）/ε^2）$ subcube sublcube rateeding查询。 我们所有的算法都是最佳的多同源因素。 我们的结果表明，与标准采样模型相比，Sub-Cuber条件是一种用于访问高维分布的自然模型，可节省大量的学习和测试Junta分布。这解决了Aliakbarpour，Blais和Rubinfeld [ABR17]提出的一个公开问题。
We study the problems of learning and testing junta distributions on $\{-1,1\}^n$ with respect to the uniform distribution, where a distribution $p$ is a $k$-junta if its probability mass function $p(x)$ depends on a subset of at most $k$ variables. The main contribution is an algorithm for finding relevant coordinates in a $k$-junta distribution with subcube conditioning [BC18, CCKLW20]. We give two applications: 1. An algorithm for learning $k$-junta distributions with $\tilde{O}(k/ε^2) \log n + O(2^k/ε^2)$ subcube conditioning queries, and 2. An algorithm for testing $k$-junta distributions with $\tilde{O}((k + \sqrt{n})/ε^2)$ subcube conditioning queries. All our algorithms are optimal up to poly-logarithmic factors. Our results show that subcube conditioning, as a natural model for accessing high-dimensional distributions, enables significant savings in learning and testing junta distributions compared to the standard sampling model. This addresses an open question posed by Aliakbarpour, Blais, and Rubinfeld [ABR17].
