Timezone: »

Adaptive Data Analysis with Correlated Observations
Aryeh Kontorovich · Menachem Sadigurschi · Uri Stemmer

Wed Jul 20 03:30 PM -- 05:30 PM (PDT) @ Hall E #1003

The vast majority of the work on adaptive data analysis focuses on the case where the samples in the dataset are independent. Several approaches and tools have been successfully applied in this context, such as {\em differential privacy}, {\em max-information}, {\em compression arguments}, and more. The situation is far less well-understood without the independence assumption. We embark on a systematic study of the possibilities of adaptive data analysis with correlated observations. First, we show that, in some cases, differential privacy guarantees generalization even when there are dependencies within the sample, which we quantify using a notion we call {\em Gibbs-dependence}. We complement this result with a tight negative example.%Second, we show that the connection between transcript-compression and adaptive data analysis can be extended to the non-iid setting.

Author Information

Aryeh Kontorovich
Menachem Sadigurschi (Ben Gurion University)
Menachem Sadigurschi

I’m a PhD student at the Computer Science department of the Ben-Gurion University. Focusing on the theory of machine learning, privacy and statistics. My main interests are: differential privacy, compression schemes and adaptive data analysis. Under the supervision of Prof. Aryeh Kontorovich and Dr. Uri Stemmer.

Uri Stemmer (Tel Aviv University and Google Research)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors