Timezone: »
Poster
On the Sample Complexity of Privately Learning Axis-Aligned Rectangles
Menachem Sadigurschi · Uri Stemmer
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.
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
-
2021 Poster: Differentially Private Multi-Armed Bandits in the Shuffle Model »
Jay Tenenbaum · Haim Kaplan · Yishay Mansour · Uri Stemmer -
2020 Poster: Adversarially Robust Streaming Algorithms via Differential Privacy »
Avinatan Hassidim · Haim Kaplan · Yishay Mansour · Yossi Matias · Uri Stemmer -
2020 Poster: Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity »
Haim Kaplan · Yishay Mansour · Uri Stemmer · Eliad Tsfadia -
2020 Oral: Adversarially Robust Streaming Algorithms via Differential Privacy »
Avinatan Hassidim · Haim Kaplan · Yishay Mansour · Yossi Matias · Uri Stemmer -
2018 Poster: The Limits of Post-Selection Generalization »
Jonathan Ullman · Adam Smith · Kobbi Nissim · Uri Stemmer · Thomas Steinke -
2018 Poster: Differentially Private k-Means with Constant Multiplicative Error »
Uri Stemmer · Haim Kaplan -
2018 Spotlight: Differentially Private k-Means with Constant Multiplicative Error »
Uri Stemmer · Haim Kaplan