Robust testing of low dimensional functions

DOI10.1145/3406325.3451115MaRDI QIDQ6087028zbMATH OpenOpenAlexFDO

Authors Anindya De, Elchanan Mossel, Joe Neeman

Publication date 14 November 2023

Published in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.11642, https://hdl.handle.net/1721.1/145927

zbMATH Keywords

property testingGaussian analysisJunta testing

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: A natural problem in high-dimensional inference is to decide if a classifier $f:mathbb{R}^{n}ightarrow-1,1$ depends on a small number of linear directions of its input data. Call a function $g:mathbb{R}^{n}ightarrow-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:mathbb{R}^{n}ightarrow-1,1$ which is a linear $k$-junta with surface area $s$, 2. $f$ is $epsilon$-far from any linear $k$-junta with surface area $(1+epsilon)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 $c>0$, $epsilon>0$, distinguishes between 1. $f:mathbb{R}^{n}ightarrow-1,1$ has correlation at least $c$ with some linear $k$-junta with surface area $s$. 2. $f$ has correlation at most $c-epsilon$ with any linear $k$-junta with surface area at most $s$. The query complexity of our tester is $k^{mathsfpoly(s/epsilon)}$. Using our techniques, we also obtain a fully noise tolerant tester with the same query complexity for any class $mathcalC$ of linear $k$-juntas with surface area bounded by $s$. As a consequence, we obtain a fully noise tolerant tester with query complexity $k^{O(mathsfpoly(logk/epsilon))}$ 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.

Cited in

(4)

• Using pillow functions to efficiently compute crude range tests
• Low-degree test with polynomially small error
• scientific article; zbMATH DE number 19010 (Why is no real title available?)
• Survey on algorithms for multi-index models

This page was built for publication: Robust testing of low dimensional functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6087028)