File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Optimal Differentially Private Algorithms for k-Means Clustering

TitleOptimal Differentially Private Algorithms for k-Means Clustering
Authors
KeywordsDifferential privacy
K-means clustering
Well separation
Issue Date2018
PublisherACM Press.
Citation
Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (SIGMOD/PODS '18), Houston, TX, USA, 10-15 June 2018, p. 395-408 How to Cite?
AbstractWe consider privacy-preserving k-means clustering. For the objective of minimizing the Wasserstein distance between the output and the optimal solution, we show that there is a polynomial-time (ε,δ)-differentially private algorithm which, for any sufficiently large Φ2 well-separated datasets, outputs k centers that are within Wasserstein distance Ø(Φ2) from the optimal. This result improves the previous bounds by removing the dependence on ε, number of centers k, and dimension d. Further, we prove a matching lower bound that no (ε, δ)-differentially private algorithm can guarantee Wasserstein distance less than Ømega (Φ2) and, thus, our positive result is optimal up to a constant factor. For minimizing the k-means objective when the dimension d is bounded, we propose a polynomial-time private local search algorithm that outputs an αn-additive approximation when the size of the dataset is at least ~Ø (k3/2 · d · ε-1 · poly(α-1)).
Persistent Identifierhttp://hdl.handle.net/10722/260346
ISBN
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorHuang, Z-
dc.contributor.authorLiu, J-
dc.date.accessioned2018-09-14T08:40:10Z-
dc.date.available2018-09-14T08:40:10Z-
dc.date.issued2018-
dc.identifier.citationProceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (SIGMOD/PODS '18), Houston, TX, USA, 10-15 June 2018, p. 395-408-
dc.identifier.isbn9781450347068-
dc.identifier.urihttp://hdl.handle.net/10722/260346-
dc.description.abstractWe consider privacy-preserving k-means clustering. For the objective of minimizing the Wasserstein distance between the output and the optimal solution, we show that there is a polynomial-time (ε,δ)-differentially private algorithm which, for any sufficiently large Φ2 well-separated datasets, outputs k centers that are within Wasserstein distance Ø(Φ2) from the optimal. This result improves the previous bounds by removing the dependence on ε, number of centers k, and dimension d. Further, we prove a matching lower bound that no (ε, δ)-differentially private algorithm can guarantee Wasserstein distance less than Ømega (Φ2) and, thus, our positive result is optimal up to a constant factor. For minimizing the k-means objective when the dimension d is bounded, we propose a polynomial-time private local search algorithm that outputs an αn-additive approximation when the size of the dataset is at least ~Ø (k3/2 · d · ε-1 · poly(α-1)).-
dc.languageeng-
dc.publisherACM Press.-
dc.relation.ispartofProceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems-
dc.subjectDifferential privacy-
dc.subjectK-means clustering-
dc.subjectWell separation-
dc.titleOptimal Differentially Private Algorithms for k-Means Clustering-
dc.typeConference_Paper-
dc.identifier.emailHuang, Z: zhiyi@cs.hku.hk-
dc.identifier.authorityHuang, Z=rp01804-
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1145/3196959.3196977-
dc.identifier.scopuseid_2-s2.0-85047982941-
dc.identifier.hkuros290749-
dc.identifier.spage395-
dc.identifier.epage408-
dc.identifier.isiWOS:000455483100030-
dc.publisher.placeNew York, NY-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats