We have not lifted any functions out of this paper's repositories yet, so there is nothing we have run. The repositories linked to it are listed below.
Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.
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 $ε$-DP algorithm must exhibit $O(|V|^2/ ε)$-additive error for an input dataset $V$. Then, we exhibit a polynomial-time approximation algorithm with $O(|V|^{2.5}/ ε)$-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.
The same record, over MCP at https://syntology.ai/mcp:
get_harvested_code_for_paper("2302.00037")
get_code_for_paper("2302.00037")
have("2302.00037")
The run record, dated, one paper per request, free:
curl https://syntology.ai/api/ran/2302.00037.json
A badge for a README (the split and the date, never a ratio):
[](https://syntology.ai/paper/2302.00037)
Connect an agent — have() is free.