  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-probability
uniform approximation. We provide a lower bound on the utility achievable for
any functional mechanism that is $\varepsilon$-differentially private. The
generality of our mechanism is demonstrated by the analysis of a number of
example learners, including naive Bayes, non-parametric estimators and
regularized empirical risk minimization. Competitive rates are demonstrated for
kernel density estimation; and $\varepsilon$-differential privacy is achieved
for a broader class of support vector machines than known previously.
