Detecting Correlations with Little Memory and Communication

Speaker: Yuval Dagan , Technion

Date: Wednesday, March 21, 2018

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G575

Event Type: Seminar

Room Description:

Host: Akshay Degwekar, Pritish Kamath and Govind Ramnarayan, MIT CSAIL

Contact: Rebecca Yadegar,

Relevant URL:

Speaker URL:

Speaker Photo:

Reminders to:,

Reminder Subject: TALK: Yuval Dagan: Detecting Correlations with Little Memory and Communication

Abstract: We study the problem of identifying correlations in multivariate data, under information constraints: Either on the amount of memory that can be used by the algorithm, or the amount of communication when the data is distributed across several machines. We prove a tight trade-off between the memory/communication complexity and the sample complexity, implying (for example) that to detect pairwise correlations with optimal sample complexity, the number of required memory/communication bits is at least quadratic in the dimension. Our results substantially improve those of Shamir (2014), which studied a similar question in a much more restricted setting. To the best of our knowledge, these are the first provable sample/memory/communication trade-offs for a practical estimation problem, using standard distributions, and in the natural regime where the memory/communication budget is larger than the size of a single data point. To derive our theorems, we prove a new information-theoretic result, which may be relevant for studying other information-constrained learning problems.
Joint work with Ohad Shamir.

Research Areas:
Algorithms & Theory

Impact Areas:

See other events that are part of the Algorithms and Complexity Seminar Series 2017/2018.

Created by Rebecca Yadegar Email at Sunday, March 04, 2018 at 10:53 PM.