Name
Abstract | ||
|---|---|---|
ABSTRACTA natural problem in high-dimensional inference is to decide if a classifier f:ℝn → {−1,1} depends on a small number of linear directions of its input data. Call a function g: ℝn → {−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: ℝn → {−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. 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: ℝn → {−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 kpoly(s/є). Using our techniques, we also obtain a fully noise tolerant tester with the same query complexity for any class C of linear k-juntas with surface area bounded by s. As a consequence, we obtain a fully noise tolerant tester with query complexity kO(poly(logk/є)) 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. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1145/3406325.3451115 | ACM Symposium on Theory of Computing |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anindya De | 1 | 239 | 24.77 |
| Elchanan Mossel | 2 | 1725 | 145.16 |
| Joe Neeman | 3 | 254 | 14.51 |