Memory-Sample Lower Bounds for Learning Parity with Noise

DOI10.4230/LIPICS.APPROX/RANDOM.2021.60arXiv2107.02320OpenAlexW3202425833MaRDI QIDQ6090918FDOQ6090918

Authors: Sumegha Garg, Pravesh Kothari, Pengda Liu, Ran Raz 

Publication date: 20 November 2023

Abstract: In this work, we show, for the well-studied problem of learning parity under noise, where a learner tries to learn $x=(x_1,ldots,x_n)in{0,1}^n$ from a stream of random linear equations over $mathrm{F}_2$ that are correct with probability $frac12+varepsilon$ and flipped with probability $frac12-varepsilon$, that any learning algorithm requires either a memory of size $Omega(n^2/varepsilon)$ or an exponential number of samples. In fact, we study memory-sample lower bounds for a large class of learning problems, as characterized by [GRT'18], when the samples are noisy. A matrix $M:AimesXightarrow-1,1$ corresponds to the following learning problem with error parameter $varepsilon$: an unknown element $xinX$ is chosen uniformly at random. A learner tries to learn $x$ from a stream of samples, $(a_1,b_1),(a_2,b_2)ldots$, where for every $i$, $a_{i}inA$ is chosen 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<frac12$). Assume that $k,ell,r$ are such that any submatrix 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 learning algorithm for the learning problem corresponding to $M$, with error, requires either a memory of size at least $Omegaleft(frackcdotellvarepsilonight)$, or at least $2^{Omega(r)}$ samples. In particular, this shows that for a large class of learning problems, same as those in [GRT'18], any learning algorithm requires either a memory of size at least $Omegaleft(frac(log|X|)cdot(log|A|)varepsilonight)$ or an exponential number of noisy samples. Our proof is based on adapting the arguments in [Raz'17,GRT'18] to the noisy case.

Full work available at URL: https://arxiv.org/abs/2107.02320

zbMATH Keywords

branching programspace lower boundmemory-sample tradeoffslearning parity under noise

Mathematics Subject Classification ID

Randomized algorithms (68W20) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cited In (2)

• A lower bound on the competitivity of memoryless algorithms for a generalization of the CNN problem
• On the robustness of learning parity with noise

This page was built for publication: Memory-Sample Lower Bounds for Learning Parity with Noise

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