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

In this work, we show, for the well-studied problem of learning parity undernoise, where a learner tries to learn $x=(x_1,\ldots,x_n) \in \{0,1\}^n$ from astream of random linear equations over $\mathrm{F}_2$ that are correct withprobability $\frac{1}{2}+\varepsilon$ and flipped with probability$\frac{1}{2}-\varepsilon$, that any learning algorithm requires either a memoryof size $\Omega(n^2/\varepsilon)$ or an exponential number of samples.  In fact, we study memory-sample lower bounds for a large class of learningproblems, as characterized by [GRT'18], when the samples are noisy. A matrix$M: A \times X \rightarrow \{-1,1\}$ corresponds to the following learningproblem with error parameter $\varepsilon$: an unknown element $x \in X$ ischosen uniformly at random. A learner tries to learn $x$ from a stream ofsamples, $(a_1, b_1), (a_2, b_2) \ldots$, where for every $i$, $a_i \in A$ ischosen uniformly at random and $b_i = M(a_i,x)$ with probability$1/2+\varepsilon$ and $b_i = -M(a_i,x)$ with probability $1/2-\varepsilon$($0<\varepsilon< \frac{1}{2}$). Assume that $k,\ell, r$ are such that anysubmatrix of $M$ of at least $2^{-k} \cdot |A|$ rows and at least $2^{-\ell}\cdot |X|$ columns, has a bias of at most $2^{-r}$. We show that any learningalgorithm for the learning problem corresponding to $M$, with error, requireseither a memory of size at least $\Omega\left(\frac{k \cdot \ell}{\varepsilon}\right)$, or at least $2^{\Omega(r)}$ samples. In particular, this shows thatfor a large class of learning problems, same as those in [GRT'18], any learningalgorithm requires either a memory of size at least $\Omega\left(\frac{(\log|X|) \cdot (\log |A|)}{\varepsilon}\right)$ or an exponential number of noisysamples.  Our proof is based on adapting the arguments in [Raz'17,GRT'18] to the noisycase.

Memory-Sample Lower Bounds for Learning Parity with Noise