Timezone: »

 
Poster
On the Sample Complexity of Privately Learning Axis-Aligned Rectangles
Menachem Sadigurschi · Uri Stemmer

Thu Dec 09 08:30 AM -- 10:00 AM (PST) @
in Poster Session 6 »
We revisit the fundamental problem of learning Axis-Aligned-Rectangles over a finite grid $X^d\subseteq\mathbb{R}^d$ with differential privacy. Existing results show that the sample complexity of this problem is at most $\min\left\{ d{\cdot}\log|X| \;,\; d^{1.5}{\cdot}\left(\log^*|X| \right)^{1.5}\right\}$. That is, existing constructions either require sample complexity that grows linearly with $\log|X|$, or else it grows super linearly with the dimension $d$. We present a novel algorithm that reduces the sample complexity to only $\tilde{O}\left\{d{\cdot}\left(\log^*|X|\right)^{1.5}\right\}$, attaining a dimensionality optimal dependency without requiring the sample complexity to grow with $\log|X|$. The technique used in order to attain this improvement involves the deletion of "exposed" data-points on the go, in a fashion designed to avoid the cost of the adaptive composition theorems.The core of this technique may be of individual interest, introducing a new method for constructing statistically-efficient private algorithms.
Keywords: Theory · Privacy

Author Information

Menachem Sadigurschi (Ben-Gurion University of the Negev)

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. My Email: sadigurs@post.bgu.ac.il

Uri Stemmer (Ben-Gurion University and Google Research)

More from the Same Authors