ECCC-Report TR21-005https://eccc.weizmann.ac.il/report/2021/005Comments and Revisions published for TR21-005en-usWed, 13 Jan 2021 01:28:41 +0200
Paper TR21-005
| Robust testing of low-dimensional functions |
Anindya De,
Elchanan Mossel,
Joe Neeman
https://eccc.weizmann.ac.il/report/2021/005A 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 $\epsilon$-far from any linear $k$-junta with surface area $(1+\epsilon)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$, $\epsilon>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-\epsilon$ with any linear $k$-junta with surface area at most $s$. The query complexity of our tester is $k^{\mathrm{poly}(s/\epsilon)}$.
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(\mathrm{poly}(\log k/\epsilon))}$ 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.Wed, 13 Jan 2021 01:28:41 +0200https://eccc.weizmann.ac.il/report/2021/005