Timezone: »
A Joint Exponential Mechanism for Differentially Private Top-k Set
Andres Munoz Medina · Matthew Joseph · Jennifer Gillenwater · Monica Ribero Diaz
Event URL: https://openreview.net/forum?id=BjBeRB3NqG »
We present a novel differentially private algorithm for releasing the set of k elements with the highest counts from a data domain of d elements. We define a ``joint'' instance of the exponential mechanism (EM) whose output space consists of all O(d^k) size-k subsets; yet, we are able to show how to sample from this EM in only time O(dk^3). Experiments suggest that this joint approach can yield utility improvements over the existing state of the art for small problem sizes.
Author Information
Andres Munoz Medina (Google)
Matthew Joseph (Google)
Jennifer Gillenwater (Google Research NYC)
Monica Ribero Diaz (University of Texas at Austin)
More from the Same Authors
-
2021 : Combining Public and Private Data »
Cecilia Ferrando · Jennifer Gillenwater · Alex Kulesza -
2021 : Population Level Privacy Leakage in Binary Classification wtih Label Noise »
Róbert Busa-Fekete · Andres Munoz Medina · Umar Syed · Sergei Vassilvitskii -
2021 : On the Pitfalls of Label Differential Privacy »
Andres Munoz Medina · Róbert Busa-Fekete · Umar Syed · Sergei Vassilvitskii -
2022 Poster: Private and Communication-Efficient Algorithms for Entropy Estimation »
Gecia Bravo-Hermsdorff · Róbert Busa-Fekete · Mohammad Ghavamzadeh · Andres Munoz Medina · Umar Syed -
2022 Affinity Workshop: LatinX in AI »
Maria Luisa Santiago · Juan Banda · CJ Barberan · MIGUEL GONZALEZ-MENDOZA · Caio Davi · Sara Garcia · Jorge Diaz · Fanny Nina Paravecino · Carlos Miranda · Gissella Bejarano Nicho · Fabian Latorre · Andres Munoz Medina · Abraham Ramos · Laura Montoya · Isabel Metzger · Andres Marquez · Miguel Felipe Arevalo-Castiblanco · Jorge Mendez · Karla Caballero · Atnafu Lambebo Tonja · Germán Olivo · Karla Caballero Barajas · Francisco Zabala -
2021 : Population Level Privacy Leakage in Binary Classification wtih Label Noise »
Róbert Busa-Fekete · Andres Munoz Medina · Umar Syed · Sergei Vassilvitskii -
2021 Social: Latinx in AI Social »
Andres Munoz Medina · Maria Luisa Santiago -
2021 : Closing Remarks »
Andres Munoz Medina -
2021 : Q&A Oral presentations »
Matias Valdenegro-Toro · Andres Munoz Medina · Johan Obando Ceron · Anil Batra -
2021 : On the Pitfalls of Label Differential Privacy »
Andres Munoz Medina · Róbert Busa-Fekete · Umar Syed · Sergei Vassilvitskii -
2021 Affinity Workshop: LatinX in AI (LXAI) Research @ NeurIPS 2021 »
Maria Luisa Santiago · Andres Munoz Medina · Laura Montoya · Karla Caballero Barajas · Isabel Metzger · Jose Gallego-Posada · Juan Banda · Gabriela Vega · Amanda Duarte · Patrick Feeney · Lourdes Ramírez Cerna · Walter M Mayor · Omar U. Florez · Rosina Weber · Rocio Zorrilla -
2019 : Pan-Private Uniformity Testing »
Kareem Amin · Matthew Joseph -
2019 : Poster Session »
Clement Canonne · Kwang-Sung Jun · Seth Neel · Di Wang · Giuseppe Vietri · Liwei Song · Jonathan Lebensold · Huanyu Zhang · Lovedeep Gondara · Ang Li · FatemehSadat Mireshghallah · Jinshuo Dong · Anand D Sarwate · Antti Koskela · Joonas Jälkö · Matt Kusner · Dingfan Chen · Mi Jung Park · Ashwin Machanavajjhala · Jayashree Kalpathy-Cramer · · Vitaly Feldman · Andrew Tomkins · Hai Phan · Hossein Esfandiari · Mimansa Jaiswal · Mrinank Sharma · Jeff Druce · Casey Meehan · Zhengli Zhao · Hsiang Hsu · Davis Railsback · Abraham Flaxman · · Julius Adebayo · Aleksandra Korolova · Jiaming Xu · Naoise Holohan · Samyadeep Basu · Matthew Joseph · My Thai · Xiaoqian Yang · Ellen Vitercik · Michael Hutchinson · Chenghong Wang · Gregory Yauney · Yuchao Tao · Chao Jin · Si Kai Lee · Audra McMillan · Rauf Izmailov · Jiayi Guo · Siddharth Swaroop · Tribhuvanesh Orekondy · Hadi Esmaeilzadeh · Kevin Procopio · Alkis Polyzotis · Jafar Mohammadi · Nitin Agrawal -
2019 Poster: Differentially Private Covariance Estimation »
Kareem Amin · Travis Dick · Alex Kulesza · Andres Munoz Medina · Sergei Vassilvitskii -
2019 Poster: Locally Private Gaussian Estimation »
Matthew Joseph · Janardhan Kulkarni · Jieming Mao · Steven Wu -
2018 Poster: Maximizing Induced Cardinality Under a Determinantal Point Process »
Jennifer Gillenwater · Alex Kulesza · Sergei Vassilvitskii · Zelda Mariet -
2018 Poster: Local Differential Privacy for Evolving Data »
Matthew Joseph · Aaron Roth · Jonathan Ullman · Bo Waggoner -
2018 Spotlight: Local Differential Privacy for Evolving Data »
Matthew Joseph · Aaron Roth · Jonathan Ullman · Bo Waggoner -
2017 Poster: Revenue Optimization with Approximate Bid Predictions »
Andres Munoz Medina · Sergei Vassilvitskii -
2016 Poster: Fairness in Learning: Classic and Contextual Bandits »
Matthew Joseph · Michael Kearns · Jamie Morgenstern · Aaron Roth