ARC Colloquium: Sumegha Garg (Princeton)

Event Details
  • Date/Time:
    • Monday October 12, 2020
      11:00 am - 12:00 pm
  • Location: Virtual via Bluejeans
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
No contact information submitted.

Summary Sentence: Extractor-based Approach to Proving Memory-Sample Lower Bounds for Learning: Virtual via Bluejeans at 11:00am

Full Summary: No summary paragraph submitted.

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.


Speaker's Webpage

Videos of recent talks are available at:

Click here to subscribe to the seminar email list:

Additional Information

In Campus Calendar


Invited Audience
Faculty/Staff, Postdoc, Graduate students, Undergraduate students
No keywords were submitted.
  • Created By: Francella Tonge
  • Workflow Status: Published
  • Created On: Sep 3, 2020 - 10:56am
  • Last Updated: Sep 29, 2020 - 12:23pm