The bernstein mechanism: Function release under differential privacy

Abstract

© Copyright 2017, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. We address the problem of general function release under differential privacy, by developing a functional mechanism that applies under the weak assumptions of oracle access to target function evaluation and sensitivity. These conditions permit treatment of functions described explicitly or implicitly as algorithmic black boxes. We achieve this result by leveraging the iterated Bernstein operator for polynomial approximation of the target function, and polynomial coefficient perturbation. Under weak regularity conditions, we establish fast rates on utility measured by high-probabi..