Timezone: »
Spotlight
Permute-and-Flip: A new mechanism for differentially private selection
Ryan McKenna · Daniel Sheldon
Tue Dec 08 07:20 AM -- 07:30 AM (PST) @ Orals & Spotlights: Social/Privacy
We consider the problem of differentially private selection. Given a finite set of candidate items, and a quality score for each item, our goal is to design a differentially private mechanism that returns an item with a score that is as high as possible. The most commonly used mechanism for this task is the exponential mechanism. In this work, we propose a new mechanism for this task based on a careful analysis of the privacy constraints. The expected score of our mechanism is always at least as large as the exponential mechanism, and can offer improvements up to a factor of two. Our mechanism is simple to implement and runs in linear time.
Author Information
Ryan McKenna (University of Massachusetts, Amherst)
Daniel Sheldon (University of Massachusetts Amherst)
Related Events (a corresponding poster, oral, or spotlight)
-
2020 Poster: Permute-and-Flip: A new mechanism for differentially private selection »
Tue. Dec 8th 05:00 -- 07:00 PM Room Poster Session 1 #534
More from the Same Authors
-
2023 Poster: (Amplified) Banded Matrix Factorization: A unified approach to private training »
Christopher Choquette-Choo · Arun Ganesh · Ryan McKenna · H. Brendan McMahan · John Rush · Abhradeep Guha Thakurta · Zheng Xu -
2023 Poster: Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacy »
Anastasiia Koloskova · Ryan McKenna · Zachary Charles · John Rush · H. Brendan McMahan -
2022 Spotlight: Kernel Interpolation with Sparse Grids »
Mohit Yadav · Daniel Sheldon · Cameron Musco -
2022 Poster: Kernel Interpolation with Sparse Grids »
Mohit Yadav · Daniel Sheldon · Cameron Musco -
2021 Poster: Relaxed Marginal Consistency for Differentially Private Query Answering »
Ryan McKenna · Siddhant Pradhan · Daniel Sheldon · Gerome Miklau -
2020 Poster: Advances in Black-Box VI: Normalizing Flows, Importance Weighting, and Optimization »
Abhinav Agrawal · Daniel Sheldon · Justin Domke -
2019 Poster: Divide and Couple: Using Monte Carlo Variational Objectives for Posterior Approximation »
Justin Domke · Daniel Sheldon -
2019 Spotlight: Divide and Couple: Using Monte Carlo Variational Objectives for Posterior Approximation »
Justin Domke · Daniel Sheldon -
2019 Poster: Differentially Private Bayesian Linear Regression »
Garrett Bernstein · Daniel Sheldon -
2018 Poster: Differentially Private Bayesian Inference for Exponential Families »
Garrett Bernstein · Daniel Sheldon -
2018 Poster: Importance Weighting and Variational Inference »
Justin Domke · Daniel Sheldon -
2018 Poster: Inferring Latent Velocities from Weather Radar Data using Gaussian Processes »
Rico Angell · Daniel Sheldon -
2016 Poster: Probabilistic Inference with Generating Functions for Poisson Latent Variable Models »
Kevin Winner · Daniel Sheldon -
2014 Poster: Stochastic Network Design in Bidirected Trees »
Xiaojian Wu · Daniel Sheldon · Shlomo Zilberstein -
2013 Workshop: Machine Learning for Sustainability »
Edwin Bonilla · Thomas Dietterich · Theodoros Damoulas · Andreas Krause · Daniel Sheldon · Iadine Chades · J. Zico Kolter · Bistra Dilkina · Carla Gomes · Hugo P Simao -
2011 Poster: Collective Graphical Models »
Daniel Sheldon · Thomas Dietterich -
2007 Spotlight: Collective Inference on Markov Models for Modeling Bird Migration »
Daniel Sheldon · M.A. Saleh Elmohamed · Dexter Kozen -
2007 Poster: Collective Inference on Markov Models for Modeling Bird Migration »
Daniel Sheldon · M.A. Saleh Elmohamed · Dexter Kozen