Is your function low-dimensional?
share
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 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 : R^n →{0,1}, is a linear k-junta or ϵ-far from all linear k-juntas, where the closeness is measured with respect to the Gaussian measure on 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) 1. k- juntas which are functions on the Boolean cube which depend on at most k of the variables and 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 poly(k · s/ϵ)-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 · k)^O(k)-query non-adaptive algorithm to learn the function up to a rotation of the basis. In particular, this implies that we can test the class of intersections of k halfspaces in R^n with query complexity independent of n.
READ FULL TEXT
