Timezone: »

 
Poster
Differentially Private Hierarchical Clustering with Provable Approximation Guarantees
Jacob Imola · Alessandro Epasto · Mohammad Mahdian · Vincent Cohen-Addad · Vahab Mirrokni

Wed Jul 26 05:00 PM -- 06:30 PM (PDT) @ Exhibit Hall 1 #331
in Poster Session 4 »
Hierarchical Clustering is a popular unsupervised machine learning method with decades of history and numerous applications. We initiate the study of *differentially-private* approximation algorithms for hierarchical clustering under the rigorous framework introduced by Dasgupta (2016). We show strong lower bounds for the problem: that any $\epsilon$-DP algorithm must exhibit $O(|V|^2/ \epsilon)$-additive error for an input dataset $V$. Then, we exhibit a polynomial-time approximation algorithm with $O(|V|^{2.5}/ \epsilon)$-additive error, and an exponential-time algorithm that meets the lower bound. To overcome the lower bound, we focus on the stochastic block model, a popular model of graphs, and, with a separation assumption on the blocks, propose a private $1+o(1)$ approximation algorithm which also recovers the blocks exactly. Finally, we perform an empirical study of our algorithms and validate their performance.
[ Poster] 

Author Information

Jacob Imola (UC San Diego)
Alessandro Epasto (Google)
Mohammad Mahdian (Google)
Vincent Cohen-Addad (Google, Switzerland)
Vahab Mirrokni (Google Research)

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

More from the Same Authors