**Algorithms & Randomness Center (ARC)**

**Sumegha Garg (Princeton)**

**Monday, October 12, 2020**

**Virtual via Bluejeans - 11:00 am**

** **

**Title: **Extractor-based Approach to Proving Memory-Sample Lower Bounds for Learning

**Abstract: **A recent line of work has focused on the following question: Can one prove strong unconditional lower bounds on the number of samples needed for learning under memory constraints? We study an extractor-based approach to proving such bounds for a large class of learning problems as follows.

A matrix M: A x X -> {-1,1} corresponds to the following learning problem: An unknown function f in X is chosen uniformly at random. A learner tries to learn f from a stream of samples, (a_1, b_1), (a_2, b_2) ..., where for every i, a_i in A is chosen uniformly at random and b_i = M(a_i,f).

Assume that k, l, r are such that any submatrix of M, with at least 2^{-k}|A| rows and at least 2^{-l}|X| columns, has a bias of at most 2^{-r} (extractor property). We show that any learning algorithm for the learning problem corresponding to M requires either a memory of size at least Ω(k l), or at least 2^{Ω(r)} samples.

We also extend the lower bounds to a learner that is allowed two passes over the stream of samples. In particular, we show that any two-pass algorithm for learning parities of size n requires either a memory of size Ω(n^{3/2}) or at least 2^{Ω(n^{1/2})} samples.

Joint works with Ran Raz and Avishay Tal.

**----------------------------------**

*Videos of recent talks are available at: *http://arc.gatech.edu/node/121

*Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu *