Extractor-based time-space lower bounds for learning

DOI10.1145/3188745.3188962MaRDI QIDQ5230356zbMATH OpenOpenAlexFDO

Authors Sumegha Garg, Ran Raz, Avishay Tal

Publication date 22 August 2019

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

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

zbMATH Keywords

branching programsextractorslearning from samplestime-space tradeoff

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: A matrix $M:AimesXightarrow-1,1$ corresponds to the following learning problem: 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)$. 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$ requires either a memory of size at least $Omegaleft(kcdotellight)$, or at least $2^{Omega(r)}$ samples. The result holds even if the learner has an exponentially small success probability (of $2^{-Omega(r)}$). In particular, this shows that for a large class of learning problems, any learning algorithm requires either a memory of size at least $Omegaleft((log|X|)cdot(log|A|)ight)$ or an exponential number of samples, achieving a tight $Omegaleft((log|X|)cdot(log|A|)ight)$ lower bound on the size of the memory, rather than a bound of $Omegaleft(minleft(log|X|{)}^2,(log|A|{)}^{2}ightight)$ obtained in previous works [R17,MM17b]. Moreover, our result implies all previous memory-samples lower bounds, as well as a number of new applications. Our proof builds on [R17] that gave a general technique for proving memory-samples lower bounds.

Recommendations

• Fast learning requires good memory: a time-space lower bound for parity learning
• Entropy samplers and strong generic lower bounds for space bounded learning
• Time-space hardness of learning sparse parities
• A general lower bound on the number of examples needed for learning
• Memory-sample tradeoffs for linear regression with small error

Cited in

(18)

• Time and space efficient net extractor
• Provable time-memory trade-offs: symmetric cryptography against memory-bounded adversaries
• Authentication in the bounded storage model
• Fast learning requires good memory: a time-space lower bound for parity learning
• Entropy samplers and strong generic lower bounds for space bounded learning
• Two Party Distribution Testing: Communication and Security
• Time-space lower bounds for two-pass learning
• On the bias of Reed-Muller codes over odd prime fields
• scientific article; zbMATH DE number 7758323 (Why is no real title available?)
• Extractor Lower Bounds, Revisited
• Speak much, remember little: cryptography in the bounded storage model, revisited
• Statistical-computational trade-offs in tensor PCA and related problems via communication complexity
• Memory-sample lower bounds for learning with classical-quantum hybrid memory
• Memory-sample lower bounds for LWE
• On bounded storage key agreement and one-way functions
• Efficient convex optimization requires superlinear memory
• Learning what to remember
• Quantum logspace algorithm for powering matrices with bounded norm

This page was built for publication: Extractor-based time-space lower bounds for learning

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