Timezone: »
Talk
Differentially Private Clustering in High-Dimensional Euclidean Spaces
Nina Balcan · Travis Dick · Yingyu Liang · Wenlong Mou · Hongyang Zhang
We study the problem of clustering sensitive data while preserving the privacy of individuals represented in the dataset, which has broad applications in practical machine learning and data analysis tasks. Although the problem has been widely studied in the context of low-dimensional, discrete spaces, much remains unknown concerning private clustering in high-dimensional Euclidean spaces $\R^d$. In this work, we give differentially private and efficient algorithms achieving strong guarantees for $k$-means and $k$-median clustering when $d=\Omega(\polylog(n))$. Our algorithm achieves clustering loss at most $\log^3(n)\OPT+\poly(\log n,d,k)$, advancing the state-of-the-art result of $\sqrt{d}\OPT+\poly(\log n,d^d,k^d)$. We also study the case where the data points are $s$-sparse and show that the clustering loss can scale logarithmically with $d$, i.e., $\log^3(n)\OPT+\poly(\log n,\log d,k,s)$. Experiments on both synthetic and real datasets verify the effectiveness of the proposed method.
Summary/NotesAuthor Information
Nina Balcan (Carnegie Mellon University)
Maria-Florina Balcan is an Associate Professor in the School of Computer Science at Carnegie Mellon University. Her main research interests are machine learning and theoretical computer science. Her honors include the CMU SCS Distinguished Dissertation Award, an NSF CAREER Award, a Microsoft Faculty Research Fellowship, a Sloan Research Fellowship, and several paper awards. She has served as a Program Committee Co-chair for COLT 2014, a Program Committee Co-chair for ICML 2016, and a board member of the International Machine Learning Society.
Travis Dick (CMU)
Yingyu Liang (Princeton University)
Wenlong Mou (Peking University)
Hongyang Zhang (Carnegie Mellon University)
Related Events (a corresponding poster, oral, or spotlight)
-
2017 Poster: Differentially Private Clustering in High-Dimensional Euclidean Spaces »
Wed. Aug 9th 08:30 AM -- 12:00 PM Room Gallery #86
More from the Same Authors
-
2022 : Meta-Learning Adversarial Bandits »
Nina Balcan · Keegan Harris · Mikhail Khodak · Steven Wu -
2020 Poster: Refined bounds for algorithm configuration: The knife-edge of dual class approximability »
Nina Balcan · Tuomas Sandholm · Ellen Vitercik -
2019 Poster: Provable Guarantees for Gradient-Based Meta-Learning »
Nina Balcan · Mikhail Khodak · Ameet Talwalkar -
2019 Poster: Theoretically Principled Trade-off between Robustness and Accuracy »
Hongyang Zhang · Yaodong Yu · Jiantao Jiao · Eric Xing · Laurent El Ghaoui · Michael Jordan -
2019 Oral: Provable Guarantees for Gradient-Based Meta-Learning »
Nina Balcan · Mikhail Khodak · Ameet Talwalkar -
2019 Oral: Theoretically Principled Trade-off between Robustness and Accuracy »
Hongyang Zhang · Yaodong Yu · Jiantao Jiao · Eric Xing · Laurent El Ghaoui · Michael Jordan -
2018 Poster: Learning to Branch »
Nina Balcan · Travis Dick · Tuomas Sandholm · Ellen Vitercik -
2018 Oral: Learning to Branch »
Nina Balcan · Travis Dick · Tuomas Sandholm · Ellen Vitercik -
2018 Tutorial: Machine Learning in Automated Mechanism Design for Pricing and Auctions »
Nina Balcan · Tuomas Sandholm · Ellen Vitercik -
2017 : Label Efficient Learning by Exploiting Multi-class Output Codes. »
Travis Dick -
2017 Poster: Collect at Once, Use Effectively: Making Non-interactive Locally Private Learning Possible »
Kai Zheng · Wenlong Mou · Liwei Wang -
2017 Talk: Collect at Once, Use Effectively: Making Non-interactive Locally Private Learning Possible »
Kai Zheng · Wenlong Mou · Liwei Wang -
2017 Poster: Provable Alternating Gradient Descent for Non-negative Matrix Factorization with Strong Correlations »
Yuanzhi Li · Yingyu Liang -
2017 Poster: Generalization and Equilibrium in Generative Adversarial Nets (GANs) »
Sanjeev Arora · Rong Ge · Yingyu Liang · Tengyu Ma · Yi Zhang -
2017 Poster: Risk Bounds for Transferring Representations With and Without Fine-Tuning »
Daniel McNamara · Nina Balcan -
2017 Talk: Risk Bounds for Transferring Representations With and Without Fine-Tuning »
Daniel McNamara · Nina Balcan -
2017 Talk: Provable Alternating Gradient Descent for Non-negative Matrix Factorization with Strong Correlations »
Yuanzhi Li · Yingyu Liang -
2017 Talk: Generalization and Equilibrium in Generative Adversarial Nets (GANs) »
Sanjeev Arora · Rong Ge · Yingyu Liang · Tengyu Ma · Yi Zhang