Brownian Noise Reduction: Maximizing Privacy Subject to Accuracy Constraints
There is a disconnect between how researchers and practitioners handle
privacy-utility tradeoffs. Researchers primarily operate from a privacy first
perspective, setting strict privacy requirements and minimizing risk subject to
these constraints. Practitioners often desire an accuracy first perspective,
possibly satisfied with the greatest privacy they can get subject to obtaining
sufficiently small error. Ligett et al. have introduced a "noise reduction"
algorithm to address the latter perspective. The authors show that by adding
correlated Laplace noise and progressively reducing it on demand, it is
possible to produce a sequence of increasingly accurate estimates of a private
parameter while only paying a privacy cost for the least noisy iterate
released. In this work, we generalize noise reduction to the setting of
Gaussian noise, introducing the Brownian mechanism. The Brownian mechanism
works by first adding Gaussian noise of high variance corresponding to the
final point of a simulated Brownian motion. Then, at the practitioner's
discretion, noise is gradually decreased by tracing back along the Brownian
path to an earlier time. Our mechanism is more naturally applicable to the
common setting of bounded $\ell_2$-sensitivity, empirically outperforms
existing work on common statistical tasks, and provides customizable control of
privacy loss over the entire interaction with the practitioner. We complement
our Brownian mechanism with ReducedAboveThreshold, a generalization of the
classical AboveThreshold algorithm that provides adaptive privacy guarantees.
Overall, our results demonstrate that one can meet utility constraints while
still maintaining strong levels of privacy.