Is your function low dimensional?
[edit]
Proceedings of the ThirtySecond Conference on Learning Theory, PMLR 99:979993, 2019.
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 nonadaptive 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 nonadaptive 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$.
Related Material


