A Caltech Library Service

Accuracy First: Selecting a Differential Privacy Level for Accuracy-Constrained ERM

Ligett, Katrina and Neel, Seth and Roth, Aaron and Waggoner, Bo and Wu, Zhiwei Steven (2017) Accuracy First: Selecting a Differential Privacy Level for Accuracy-Constrained ERM. In: 31st Conference on Neural Information Processing Systems (NIPS). Advances in Neural Information Processing Systems. No.30. , pp. 1-11.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Traditional approaches to differential privacy assume a fixed privacy requirement epsilon for a computation, and attempt to maximize the accuracy of the computation subject to the privacy constraint. As differential privacy is increasingly deployed in practical settings, it may often be that there is instead a fixed accuracy requirement for a given computation and the data analyst would like to maximize the privacy of the computation subject to the accuracy constraint. This raises the question of how to find and run a maximally private empirical risk minimizer subject to a given accuracy requirement. We propose a general "noise reduction" framework that can apply to a variety of private empirical risk minimization (ERM) algorithms, using them to "search" the space of privacy levels to find the empirically strongest one that meets the accuracy constraint, and incurring only logarithmic overhead in the number of privacy levels searched. The privacy analysis of our algorithm leads naturally to a version of differential privacy where the privacy parameters are dependent on the data, which we term ex-post privacy, and which is related to the recently introduced notion of privacy odometers. We also give an ex-post privacy analysis of the classical AboveThreshold privacy tool, modifying it to allow for queries chosen depending on the database. Finally, we apply our approach to two common objective functions, regularized linear and logistic regression, and empirically compare our noise reduction methods to (i) inverting the theoretical utility guarantees of standard private ERM algorithms and (ii) a stronger, empirical baseline based on binary search.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Ligett, Katrina0000-0003-2780-6656
Additional Information:© 2017 Neural Information Processing Systems Foundation, Inc.
Series Name:Advances in Neural Information Processing Systems
Issue or Number:30
Record Number:CaltechAUTHORS:20190107-104411349
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:92112
Deposited By: Tony Diaz
Deposited On:07 Jan 2019 19:31
Last Modified:03 Oct 2019 20:41

Repository Staff Only: item control page