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, 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.

本文提出了一种名为噪声约简框架的通用方法，能够应用于各种私有经验风险最小化 (ERM) 算法，使用它们来 “搜索” 隐私级别的空间，以找到在满足准确性约束下最强的隐私级别，并仅产生对搜索的隐私级别数量的对数开销。

优先考虑准确度：选择不泄露隐私的差分隐私阈值以满足准确度约束的 ERM

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

We consider the problem of Bayesian learning on sensitive datasets and
present two simple but somewhat surprising results that connect Bayesian
learning to "differential privacy:, a cryptographic approach to protect
individual-level privacy while permiting database-level utility. Specifically,
we show that that under standard assumptions, getting one single sample from a
posterior distribution is differentially private "for free". We will see that
estimator is statistically consistent, near optimal and computationally
tractable whenever the Bayesian model of interest is consistent, optimal and
tractable. Similarly but separately, we show that a recent line of works that
use stochastic gradient for Hybrid Monte Carlo (HMC) sampling also preserve
differentially privacy with minor or no modifications of the algorithmic
procedure at all, these observations lead to an "anytime" algorithm for
Bayesian learning under privacy constraint. We demonstrate that it performs
much better than the state-of-the-art differential private methods on synthetic
and real datasets.

本文提出了一种使用差分隐私技术保证贝叶斯学习个体隐私安全的算法，采样自后验分布得出的估计符合要求，同时随机梯度下降方法也可以达到类似效果，是较好的解决贝叶斯学习隐私问题的方法。