论文标题
用于测试和学习产品分布的采样
Downsampling for Testing and Learning in Product Distributions
论文作者
论文摘要
我们研究了无分配的属性测试和学习问题，其中未知的概率分布是$ \ mathbb {r}^d $的产品分布。对于许多重要类别的功能类别，例如半空间的交集，多项式阈值函数，凸集和$ k $ - 偏置功能，已知的算法要么具有复杂性，取决于分布的支持大小，要么仅用于产品分布的特定示例。我们介绍了一种通用方法，我们称之为下采样，可以解决这些问题。下采样使用“直线等法”的概念进行产品分布，从而进一步加强了等级，测试和学习之间的联系。使用此技术，我们在$ \ mathbb {r}^d $上获得了产品分布下的新有效分发算法： 1。简单的证明功能的非自适应，单方面的单调单调性测试$ [n]^d \ to \ {0,1 \} $，以及改进的样品复杂性，用于对未知产品分布的单调性进行测试，$ O（d^7）$（d^7）$（black，black，black，chakrabarty，chakrabarty，＆seshadhri，$ o（$ o），$ o（$ o（Seshadhri）$ o（$ o）。 2。用于恒定数量半空间的函数和恒定度多项式阈值函数的多项式不可知学习算法。 3。$ \ exp（o（d \ log（dk）））$ - 时间不可知的学习算法和$ \ exp（o（d \ log（dk））$ - 样本公差测试仪，用于$ K $ convex sets的功能；以及$ 2^{\ widetilde o（d）} $基于样本的凸集的单面测试仪。 4。$ \ exp（\ wideTilde o（k \ sqrt d））$ - $ k $ - 偏置功能的时间不可知论学习算法，以及具有相同复杂性的基于样本的耐受性测试仪。
We study distribution-free property testing and learning problems where the unknown probability distribution is a product distribution over $\mathbb{R}^d$. For many important classes of functions, such as intersections of halfspaces, polynomial threshold functions, convex sets, and $k$-alternating functions, the known algorithms either have complexity that depends on the support size of the distribution, or are proven to work only for specific examples of product distributions. We introduce a general method, which we call downsampling, that resolves these issues. Downsampling uses a notion of "rectilinear isoperimetry" for product distributions, which further strengthens the connection between isoperimetry, testing, and learning. Using this technique, we attain new efficient distribution-free algorithms under product distributions on $\mathbb{R}^d$: 1. A simpler proof for non-adaptive, one-sided monotonicity testing of functions $[n]^d \to \{0,1\}$, and improved sample complexity for testing monotonicity over unknown product distributions, from $O(d^7)$ [Black, Chakrabarty, & Seshadhri, SODA 2020] to $\widetilde O(d^3)$. 2. Polynomial-time agnostic learning algorithms for functions of a constant number of halfspaces, and constant-degree polynomial threshold functions. 3. An $\exp(O(d \log(dk)))$-time agnostic learning algorithm, and an $\exp(O(d \log(dk)))$-sample tolerant tester, for functions of $k$ convex sets; and a $2^{\widetilde O(d)}$ sample-based one-sided tester for convex sets. 4. An $\exp(\widetilde O(k \sqrt d))$-time agnostic learning algorithm for $k$-alternating functions, and a sample-based tolerant tester with the same complexity.
