Robust testing of low dimensional functions
Anindya De, Elchanan Mossel, Joe Neeman · 2021
A 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.