期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：A natural problem in high-dimensional inference is to decide if a classifier f:Rn−11 depends on a small number of linear directions of its input data. Call a function g:Rn−11 , 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:Rn−11 which is a linear k-junta with surface area s, 2. f is -far from any linear k-junta with surface area (1+)s, where 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 c0, 0, distinguishes between 1. f:Rn−11 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 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.
