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

arXiv: https://arxiv.org/abs/1705.10829 · HTML: https://mlsanity.com/paper/1705.10829/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 May 2017.

## Built on by (most cited first, 20 of 20)

- [Bounding Training Data Reconstruction in DP-SGD](https://mlsanity.com/paper/2302.07225/) (2023)
- [Fully Adaptive Composition in Differential Privacy](https://mlsanity.com/paper/2203.05481/) (2022)
- [Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent](https://mlsanity.com/paper/2206.02617/) (2022)
- [Practical Privacy Filters and Odometers with R'enyi Differential Privacy and Applications to Differentially Private Deep Learning](https://mlsanity.com/paper/2103.01379/) (2021)
- [Privately Publishable Per-instance Privacy](https://mlsanity.com/paper/2111.02281/) (2021)
- [InvisibleInk: High-Utility and Low-Cost Text Generation with Differential Privacy](https://mlsanity.com/paper/2507.02974/) (2025)
- [Generalization in the Face of Adaptivity: A Bayesian Perspective](https://mlsanity.com/paper/2106.10761/) (2021)
- [Certification for Differentially Private Prediction in Gradient-Based Training](https://mlsanity.com/paper/2406.13433/) (2024)
- [Unbounded Differentially Private Quantile and Maximum Estimation](https://mlsanity.com/paper/2305.01177/) (2023)
- [Clustering and Median Aggregation Improve Differentially Private Inference](https://mlsanity.com/paper/2506.04566/) (2025)
- [Brownian Noise Reduction: Maximizing Privacy Subject to Accuracy Constraints](https://mlsanity.com/paper/2206.07234/) (2022)
- [Striking a Balance: An Optimal Mechanism Design for Heterogenous Differentially Private Data Acquisition for Logistic Regression](https://mlsanity.com/paper/2309.10340/) (2023)
- [On the Privacy of Selection Mechanisms with Gaussian Noise](https://mlsanity.com/paper/2402.06137/) (2024)
- [Privacy-preserving Non-negative Matrix Factorization with Outliers](https://mlsanity.com/paper/2211.01451/) (2022)
- [Answering Private Linear Queries Adaptively using the Common Mechanism](https://mlsanity.com/paper/2212.00135/) (2022)
- [Adaptive Privacy Composition for Accuracy-first Mechanisms](https://mlsanity.com/paper/2306.13824/) (2023)
- [N-grams Bayesian Differential Privacy](https://mlsanity.com/paper/2101.12736/) (2021)
- [Towards Practical Differential Privacy in Data Analysis: Understanding the Effect of Epsilon on Utility in Private ERM](https://mlsanity.com/paper/2206.03488/) (2022)
- [Agents That Know Too Much: A Data-Centric Survey of Privacy in LLM Agents](https://mlsanity.com/paper/2606.26627/) (2026)
- [Performative Privacy: When Differential Privacy Maximizes Utility](https://mlsanity.com/paper/2608.28198/) (2026)

## Abstract (arXiv)

Traditional approaches to differential privacy assume a fixed privacy requirement ε 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, 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 objectives, 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.