论文标题
低维功能的强大测试
Robust testing of low-dimensional functions
论文作者
论文摘要
高维推断中的一个自然问题是确定分类器$ f：\ mathbb {r}^n \ rightarrow \ { - 1,1 \} $是否取决于其输入数据的少量线性方向。调用函数$ g：\ mathbb {r}^n \ rightArrow \ { - 1,1 \} $，如果由某些$ k $ - 二维子空间完全确定，则是线性$ k $ -junta。作者的最新作品表明，线性$ k $ -juntas是可测试的。因此，存在一种算法来区分以下算法：1。$ f：\ mathbb {r}^n \ rightarrow \ { - 1,1 \} $，是一个线性$ k $ -junta，带有表面积$ s $，2。$ f $ $ f $ is $ε$ - $ε$ $ k $ k $ k $ k $ k $ k $ k $ k $ k $ - 算法独立于环境尺寸$ n $。 在对弱化噪声属性测试的兴趣激增之后，在本文中，我们证明了该结果的噪声（或健壮）版本。也就是说，我们给出了一种算法，该算法给出了任何$ c> 0 $，$ε> 0 $，区分1。$ f：$ f：\ mathbb {r}^n \ rightArrow \ { - 1,1 \} $具有至少$ c $的$ c $，与某些线性$ k $ -junta与表面积$ k $ s $。 2。$ f $最多具有$ c-ε$与任何线性$ k $ -junta具有表面积最多$ s $的相关性。我们测试仪的查询复杂性是$ k^{\ mathsf {poly}（s/ε）} $。 使用我们的技术，我们还获得了一个完全噪声的测试仪，对于任何类$ \ MATHCAL {C} $的$ k $ -juntas的$ \ mathcal {c} $具有相同的查询复杂性，其表面积为$ s $。结果，我们获得了具有查询复杂性的完全噪声耐受性测试仪$ k^{o（\ mathsf {poly}（\ log log k/ε））} $用于$ k $ -HALFSPACES（对于常数$ k $）在高斯空间上的交点的类别。我们的查询复杂性独立于环境尺寸$ n $。以前，即使在一个半空间中，也没有众所周知的非平凡的噪声测试仪。
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 \rightarrow \{-1,1\}$, a linear $k$-junta if it is completely determined by some $k$-dimensional subspace of the input space. A recent work of the authors showed that linear $k$-juntas are testable. Thus there exists an algorithm to distinguish between: 1. $f: \mathbb{R}^n \rightarrow \{-1,1\}$ which is a linear $k$-junta with surface area $s$, 2. $f$ is $ε$-far from any linear $k$-junta with surface area $(1+ε)s$, where the query complexity of the algorithm is independent of the ambient dimension $n$. Following the surge of interest in noise-tolerant property testing, in this paper we prove a noise-tolerant (or robust) version of this result. Namely, we give an algorithm which given any $c>0$, $ε>0$, distinguishes between 1. $f: \mathbb{R}^n \rightarrow \{-1,1\}$ has correlation at least $c$ with some linear $k$-junta with surface area $s$. 2. $f$ has correlation at most $c-ε$ with any linear $k$-junta with surface area at most $s$. The query complexity of our tester is $k^{\mathsf{poly}(s/ε)}$. Using our techniques, we also obtain a fully noise tolerant tester with the same query complexity for any class $\mathcal{C}$ of linear $k$-juntas with surface area bounded by $s$. As a consequence, we obtain a fully noise tolerant tester with query complexity $k^{O(\mathsf{poly}(\log k/ε))}$ for the class of intersection of $k$-halfspaces (for constant $k$) over the Gaussian space. Our query complexity is independent of the ambient dimension $n$. Previously, no non-trivial noise tolerant testers were known even for a single halfspace.
