Memory-Sample Lower Bounds for Learning Parity with Noise

2021/07/05 by Garg, Sumegha, Kothari, Pravesh K., Liu, Pengda +1 · 1 citation
#Computational Complexity (cs.CC) #F.2.3 #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2107.02320

Abstract

In this work, we show, for the well-studied problem of learning parity under noise, where a learner tries to learn x=(x₁,…,x_n) ∈ \0,1\ⁿ from a stream of random linear equations over F₂ that are correct with probability (1)/(2)+ε and flipped with probability (1)/(2)-ε, that any learning algorithm requires either a memory of size Ω(n²/ε) 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: A × X → \-1,1\ corresponds to the following learning problem with error parameter ε: an unknown element x ∈ X is chosen uniformly at random. A learner tries to learn x from a stream of samples, (a₁, b₁), (a₂, b₂) …, where for every i, a_i ∈ A is chosen uniformly at random and b_i = M(a_i,x) with probability 1/2+ε and b_i = -M(a_i,x) with probability 1/2-ε (0

Cited by

• Foundations of Artificial Intelligence Frameworks: Notion and Limits of AGI

Related

• Tight Time-Space Lower Bounds for Constant-Pass Learning
• Extractor-Based Time-Space Lower Bounds for Learning
• Approximating the Number of Relevant Variables in a Parity Implies Proper Learning
• Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning
• On learning k-parities with and without noise