Name
Abstract | ||
|---|---|---|
We study the problem of testing if a function depends on a small number of linear directions of its input data. We call a function $f$ a \emph{linear $k$-junta} if it is completely determined by some $k$-dimensional subspace of the input space. In this paper, we study the problem of testing whether a given $n$ variable function $f : \mathbb{R}^n \to \{0,1\}$, is a linear $k$-junta or $\epsilon$-far from all linear $k$-juntas, where the closeness is measured with respect to the Gaussian measure on $\mathbb{R}^n$. Linear $k$-juntas are a common generalization of two fundamental classes from Boolean function analysis (both of which have been studied in property testing) \textbf{1.} $k$- juntas which are functions on the Boolean cube which depend on at most k of the variables and \textbf{2.} intersection of $k$ halfspaces, a fundamental geometric concept class. We show that the class of linear $k$-juntas is not testable, but adding a surface area constraint makes it testable: we give a $\mathsf{poly}(k \cdot s/\epsilon)$-query non-adaptive tester for linear $k$-juntas with surface area at most $s$. We show that the polynomial dependence on $s$ is necessary. Moreover, we show that if the function is a linear $k$-junta with surface area at most $s$, we give a $(s \cdot k)^{O(k)}$-query non-adaptive algorithm to learn the function \emph{up to a rotation of the basis}. In particular, this implies that we can test the class of intersections of $k$ halfspaces in $\mathbb{R}^n$ with query complexity independent of $n$. |
Year | Venue | Field |
|---|---|---|
2019 | COLT | Computer science,Artificial intelligence,Machine learning |
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 |