English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

A natural problem in high-dimensional inference is to decide if a classifier$f:\mathbb{R}^n \rightarrow \{-1,1\}$ depends on a small number of lineardirections of its input data. Call a function $g: \mathbb{R}^n \rightarrow\{-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 authorsshowed that linear $k$-juntas are testable. Thus there exists an algorithm todistinguish between: 1. $f: \mathbb{R}^n \rightarrow \{-1,1\}$ which is alinear $k$-junta with surface area $s$, 2. $f$ is $\epsilon$-far from anylinear $k$-junta with surface area $(1+\epsilon)s$, where the query complexityof the algorithm is independent of the ambient dimension $n$.  Following the surge of interest in noise-tolerant property testing, in thispaper we prove a noise-tolerant (or robust) version of this result. Namely, wegive an algorithm which given any $c>0$, $\epsilon>0$, distinguishes between 1.$f: \mathbb{R}^n \rightarrow \{-1,1\}$ has correlation at least $c$ with somelinear $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 querycomplexity of our tester is $k^{\mathsf{poly}(s/\epsilon)}$.  Using our techniques, we also obtain a fully noise tolerant tester with thesame query complexity for any class $\mathcal{C}$ of linear $k$-juntas withsurface area bounded by $s$. As a consequence, we obtain a fully noise toleranttester with query complexity $k^{O(\mathsf{poly}(\log k/\epsilon))}$ for theclass of intersection of $k$-halfspaces (for constant $k$) over the Gaussianspace. Our query complexity is independent of the ambient dimension $n$.Previously, no non-trivial noise tolerant testers were known even for a singlehalfspace.

Robust testing of low-dimensional functions