Timezone: »

Smoothly Bounding User Contributions in Differential Privacy
Alessandro Epasto · Mohammad Mahdian · Jieming Mao · Vahab Mirrokni · Lijie Ren

Tue Dec 08 09:00 AM -- 11:00 AM (PST) @ Poster Session 1 #257

A differentially private algorithm guarantees that the input of a single user won’t significantly change the output distribution of the algorithm. When a user contributes more data points, more information can be collected to improve the algorithm’s performance. But at the same time, more noise might need to be added to the algorithm in order to keep the algorithm differentially private and this might hurt the algorithm’s performance. Amin et al. (2019) initiates the study on bounding user contributions and proposes a very natural algorithm which limits the number of samples each user can contribute by a threshold.

For a better trade-off between utility and privacy guarantee, we propose a method which smoothly bounds user contributions by setting appropriate weights on data points and apply it to estimating the mean/quantiles, linear regression, and empirical risk minimization. We show that our algorithm provably outperforms the sample limiting algorithm. We conclude with experimental evaluations which validate our theoretical results.

Author Information

Alessandro Epasto (Google)

I am a senior research scientist at Google, New York working in the Google Research Algorithms and Optimization team lead by Vahab Mirrokni. I received a Ph.D in computer science from Sapienza University of Rome, where I was advised by Professor Alessandro Panconesi and supported by the Google Europe Ph.D. Fellowship in Algorithms, 2011. I was also a post-doc at the department of computer science of Brown University in Providence (RI), USA where I was advised by Professor Eli Upfal. My research interests include algorithmic problems in machine learning and data mining, in particular in the areas of clustering, and large scale graphs analysis.

Mohammad Mahdian (Google Research)
Jieming Mao (Google Research)
Vahab Mirrokni (Google Research NYC)
Lijie Ren (Google)

More from the Same Authors