Introduction

The goal of this work is to provide tools for sharing sensitive data in situations when the data curator does not know in advance what questions the (untrusted) analyst might want to ask about the data. Instead of putting the analyst through background checks and monitoring their access to data, we would like to provide an automated way for the analyst to interact with the data. We allow the analyst to specify a program, modeled as a black-box function , that they want the curator to run on the dataset. Black-box specification allows analysts to construct arbitrarily complicated programs; it also enables them to obfuscate their programs and thus hide the analysis they intend to perform from their competitors.

We study differentially private algorithms that, given a sensitive dataset and black-box access to a real-valued function , output an accurate approximation to ( ). Each entry in the dataset comes from some large (finite or countably infinite) universe U and represents data of one individual. Let U * denote the set of finite subsets of U. The dataset is modeled as a member of U * . Two datasets in U * are neighbors if they differ by the insertion or removal of one element. (Our constructions also apply to a more general setting that covers multisets and node-level privacy in graphs; we expand on this in the full version [33] .) The algorithm run by the data curator calls on the dataset and on some subsets of and returns either an approximation to ( ) or a nonresponse symbol §. Following Kohli and Laskowski [31], we call such an algorithm a privacy wrapper if it is differentially private for all functions . A privacy wrapper may also use additional information (that is, parameters) provided by the analyst, but differential privacy is required for all values of these parameters. Correct setting of these parameters will ensure better accuracy of the privacy wrapper. The bottleneck in the running time of our privacy wrappers is the number of calls to , which we refer to as queries. Our goal is to design privacy wrappers with high accuracy and small query complexity.

We introduce a novel setting, called the automated sensitivity detection setting, where the analyst supplies only the black-box function and the intended (finite) range of . In contrast, in the previously considered setting [27,31,32], which we refer to as the claimed sensitivity bound setting, the analyst also supplies additional parameters that describe the sensitivity of . We design the first privacy wrappers in the automated sensitivity detection setting and new privacy wrappers in the claimed sensitivity bound setting. We show that our wrappers are nearly optimal in terms of accuracy and locality (i.e., the depth of the local neighborhood of the dataset they explore, which is a proxy for query complexity). In the claimed sensitivity bound setting, we provide the first accuracy guarantees that have no dependence on the size of the universe U. We also re-interpret and analyze previous constructions in our framework, tailoring the analysis to our setting, and show that our wrappers improve on all previous constructions. Finally, we prove tight lower bounds for both settings.

In addition to addressing the black-box privacy problem, our private mechanisms provide feasibility results for differentially private release of general classes of functions. Most work on differential privacy considers the easier "white box" setting, when a complete description of the input function is available. Our results have applications in this setting. We discuss this perspective on our results in Section 1.1.4.

Our Contributions

Releasing ( ) privately in the black-box setting is especially challenging when the universe of potential data records is large, since it is not even feasible to query on all the datasets that differ from by the addition of one data record. Instead, we consider privacy wrappers that query the function only on large subsets of , and whose accuracy guarantees depend only on the behavior of the function on such sets. Specifically, let ∈ N be the locality parameter. Our algorithms query only on subsets of the input dataset , obtained from by removing data of at most individuals. Let N ³ ( ), called the -down neighborhood of , denote the collection of all subsets of of size at least | | -:

Algorithms that query only on N ³ ( ) are called -down local.

One of our goals in designing wrappers is to provide small locality . Observe that the query complexity of a -down local algorithm is (| | ). We focus on down-local algorithms for two reasons: first, such algorithms handle large or even infinite universe of potential data records. Second, it allows us to design privacy wrappers that are accurate for functions that are "well behaved" on the input dataset and its subsets, but potentially sensitive to the insertion of new data points (such as outliers).

Our accuracy guarantees (for both settings) are formulated in terms of the behavior of in the region N ³ ( ). Given an accuracy parameter > 0 and failure probability ∈ (0, 1), an algorithm A is ( , )-accurate for function on input if |A ( ) -( )| f with probability at least 1-. Let ( ) denote the set { ( ) : ∈ }. The diameter of a set is the difference between its maximum and minimum. We achieve small when the diameter of (N ³ ( )) is small and when function is "smooth" (i.e., has a small Lipschtiz constant) on the domain N ³ ( ).

Unlike our accuracy guarantees, the privacy guarantees of privacy wrappers are unconditional. As formalized in Definition 2.5, an ( , )-privacy wrapper is ( , )-DP for all black-box functions and for all settings of parameters. See Definition 2.1 for the definition of ( , )-differential privacy (DP). We use both pure DP (when = 0) and approximate DP (when > 0).

1.1.1 Automated Sensitivity Detection. We consider a novel setting when a bound on sensitivity has to be automatically inferred instead of being provided by the analyst. In contrast, previous work on the black-box privacy problem (discussed in Section 1.3) required the analyst to provide a parameter that bounds the sensitivity of the black-box function. We circumvent the need for information about the sensitivity from the analyst by phrasing the accuracy guarantee of the privacy wrapper in terms of the down sensitivity (called deletion sensitivity in some works) of the function at , defined next. Definition 1.1 (Down sensitivity at specified depth). Let ∈ N. The down sensitivity at depth of a function :

The down sensitivity differs by at most a factor of 2 from the diameter of the set (N ³ ( )).

As a simple example, consider the average function avg( )

, where ∈ R. The value of avg( ) can change arbitrarily with the insertion of a single additional value to . However, the down sensitivity at depth of avg at is finite: for every , it is at most ( ) • | | -. We discuss more sophisticated examples in Section 1.1.4.

We provide the first privacy wrapper in the automated sensitivity detection setting. The guarantees of the wrapper, which we dub Sens-o-Matic, are stated in Theorem 3.1. Sens-o-Matic works for all functions : U * → Y, where the range Y ¦ R is finite. 1 For privacy parameters , and failure probability , the accuracy of our wrapper is = ( ), where locality is

pure DP and 1 log 1 log * |Y| for approximate DP. In fact, Senso-Matic returns a value between the minimum and the maximum of ( ) for in the -down neighborhood of dataset . The locality of our privacy wrapper does not depend on the size of the universe U. The starting point for the design of Sens-o-Matic is the Shifted Inverse Sensitivity Mechanism (ShI) of Fang, Dong, and Yi [20]. This is a privacy mechanism for releasing a value of a monotone function evaluated on dataset . A function : U * → R is monotone if ( ) f ( ) for all , ∈ U * such that ¢ . The ShI mechanism is ( , 0)-DP for all monotone functions and has locality that depends logarithmically on the size of the range. We generalize their construction and present an approximate-DP variantfoot_1 of the ShI mechanism that has only 2 log * dependence on the size of the range (Lemma 3.2). Both versions of ShI release the value of a monotone function at the data set privately, with error bounded by ( ). However, they are not privacy wrappers, because they can violate differential privacy for general, black-box functions-the privacy proof relies crucially on the promise that is monotone.

The wrapper we design, Sens-o-Matic, is private for all functions : U * → Y with finite range Y and extends the accuracy guarantees of (both versions of) ShI from monotone functions to all functions. It works by running ShI (or our modification thereof) on a carefully selected "monotonization" of function -see Section 1.2 for more detail.

To complete the picture for automated sensitivity detection setting, we provide a lower bound on the locality of any privacy wrapper that achieves accuracy equal to down sensitivity at depth . Our lower bound matches the first term (corresponding to the pure DP) in the guarantee for Sens-o-Matic and nearly matches the second term (corresponding to approximate DP). We also provide a query complexity lower bound, Theorem 6.1 (and Remark 6.2), showing that the query complexity we achieve cannot be significantly improved, even if the locality requirement is relaxed. Proofs of our lower bounds appear in the full version [33]. Our guarantees for Sens-o-Matic are compared to guarantees for both variants of ShI and the locality lower bound in Table 1.

1.1.2 Privacy Wrappers with Claimed Sensitivity Bound. We also investigate the claimed sensitivity bound setting, which has been addressed in previous work, where the analyst provides a sensitivity bound along with a black-box function .

Sensitivity and the related notion of Lipschitz functions play a fundamental role in private data analysis. Intuitively, sensitivity measures how small modifications of the dataset affect the value of the function. Given a constant > 0 and a domain ¦ U * , a function :

for all neighbors , ∈ . The smallest constant for which function is -Lipschitz on U * is called the Lipschitz constant or the (global) sensitivity of . A basic result is that the Laplace mechanism, which releases ( ) with Laplace noise scaled to , is ( , 0)-differentially private [17]. Most work on differential privacy considers the "white box" case, where a complete description of is available, and one analyzes sensitivity analytically.

The problem of privately evaluating black-box functions was first considered by Jha and Raskhodnikova [27]. In their setting, in addition to the black-box function , the analyst providesfoot_2 a sensitivity parameter . The data curator must guarantee differential privacy whether or not the provided bound is correct, but the mechanism's accuracy depends on the bound being correct and as tight as possible. Jha and Raskhodnikova [27] and follow-up work [3,32] handle the case where the data universe U is finite, and they investigate the function's behavior in a ball around the input that includes both insertions and deletions. This means the data universe has to be small to achieve reasonable query complexity, and also that the function must be robust to both insertions and deletions of data points.

We consider instead the setting introduced by Kohli and Laskowski [31], where the curator is limited to evaluating the black-box at subsets of the actual input . The privacy wrapper for this setting in [31], called TAHOE, has locality independent of the data set size | |. In [31], the accuracy of TAHOE is analyzed for some special cases, under distributional assumptions, and empirically. We aim to get a privacy wrapper in this setting that is private for all and , and satisfies the following type of accuracy: For every and such that is -Lipschitz on N ³ ( ) (where varies by mechanism), the wrapper outputs ( ) + where is drawn from a Laplace distribution. Our goal is to simultaneously minimize and the scale of . We provide a novel privacy wrapper, Subset-Extension, for this setting with accuracy and locality guarantees that are each optimal up to constant factors. Table 2 summarizes our results and compares them to the guarantees of existing privacy mechanisms that query only on the subsets of dataset , which we summarize briefly here. In particular, we provide a self-contained accuracy analysis of TAHOE in the full version [33]. It adds Laplace noise that is larger by a factor of log(1/ )/ than the scale / that can be used in the white-box setting when the function is promised to be -Lipschitz on its entire domain. (This latter scale is known to be optimal, even for the special case where is a simple counting query [23].)

We observe that the literature on Lipschitz extensions-generally thought of as "white box" objects-also provides a different, incomparable privacy wrapper for this black-box setting. Specifically, given and , Cummings and Durfee [13] construct a function that is -Lipschitz (everywhere), and for which ( ) is computable based only on the values of on the subsets of . Furthermore, ( ) equals ( ) whenever is -Lipschitz on the entire power set P ( ) of , that is, on the neighborhood N ³ | | ( ). This construction implies a privacy wrapper: given , and , compute ( ) and release it with noise scale / . The resulting wrapper has optimal error but very high locality | | and query complexity 2 | | .

Our Subset-Extension privacy wrapper, achieves the best of both worlds: the accuracy of Cummings-Durfee and the locality of TAHOE. We describe its construction, which departs significantly from the existing approaches, in Section 1.2.

Both the error scale and locality of our privacy wrappers are essentially optimal. The optimality of error follows the work of Ghosh et al. [23], mentioned above. To prove optimality of locality, we give two lower bounds: one which bounds locality directly , and the other which bounds query complexity , and thus locality by implication. The proofs of our lower bounds appear in the full version [33].

1.1.3 Privacy Wrappers with Claimed Sensitivity Bound for Bounded-Range Functions. In the full version, we show that one can achieve improved guarantees in the claimed sensitivity bound setting for functions with small intended range. We present our results for this setting in Table 3.

The Double Monotonization mechanism extends the guarantees of Subset-Extension to the setting of bounded range, replacing the log(1/ ) factor in the locality with log . At a technical level, it builds on Sens-o-Matic, modifying it to take advantage of the (claimed) Lipschitz constant provided by the analyst.

In contrast, the Small Diameter Subset Extension mechanism is based on a novel approach to local Lipschitz filters. This approach follows the spirit of [27], who initiated an approach based on sublineartime algorithms that was later studied in [3,32]. As a corollary of our techniques, we construct a local Lipschitz filter that improves on [32]. The resulting privacy wrapper achieves the best of both the algorithms of [32], and [13].

1.1.4 Applications of Privacy Wrappers to White-Box Se ing. Formal statements and proofs from this section appear in the full version [33]. We, give several applications of our privacy wrappers in the white-box privacy setting, both recovering known results, and obtaining immediate improvements to existing results. Our privacy wrappers offer a unified derivation of a range of results that, a priori, seem to require different techniques.

Private mean estimation: As a simple illustration of our results, we show how they recover known bounds [16,36] on private mean estimation in one dimension. If the dataset ∈ R is contained in an unknown interval of radius , then applying each of our wrappers to the average function leads to privately releasing with error roughly .

Empirical risk minimization:

We improve upon the user-level (also known as person-level) private empirical risk minimization algorithm of [21] for the setting of one dimensional parameter spaces. Full version of our work [33] In particular, we show that in empirical risk minimization for a one-dimensional parameter space Y, the dependence on privacy parameters and can be reduced from 1 5/2 log 2 1 to the minimum of the terms 1 3/2 log 1 and 1 log 1 exp( log * |Y|). The first term in the minimum follows immediately by substituting the Subset-Extension mechanism for the relevant subroutine in the private empirical risk minimization algorithm of [21]. The second term leverages the Sens-o-Matic mechanism, as well as a straightforward extension of one of the key tools used in [21] to bound the Lipschitz constant on N ³ ( ) for g | |/2.

Estimating graph parameters: Our results give simpler derivations of the rate at which one can estimate the parameter of an Erdős-Rényi graph model ( , ) subject to node privacy guarantees. There is a node-private algorithm [6] that, for all , given a graph drawn from ( , ), generates an estimate ˆ with additive error 1 + √

for bounded away from 0 and 1 (efficient algorithms achieving a similar bound were later given by [10,39]). This bound was surprising since the non-private estimator is a simple sum whose local sensitivity, which is Θ( 1 ) on typical graphs from ( , ), is too large to obtain the optimal rate by simply applying the Laplace mechanism. Such a strategy would lead to error 1 , instead of

We can rederive this bound using the observation that, for graphs generated from ( , ), the non-private estimator-which reports the density of edges in the input -has down sensitivity ≈ √

at depth , with high probability. Applying our results for automated sensitivity detection directly implies a similar feasibility result to that of [6]. See the full version [33] for details.

Techniques

Monotonization and the Shifted Inverse Mechanism. Our wrappers with automatic sensitivity detection use the Shifted Inverse mechanism of [20] as a starting point. That mechanism relies on the promise, for both privacy and accuracy, that its input function is monotone. We show how to transform an arbitrary function into a monotone function with two additional locality properties:

where "-∞" is a lower bound on the analyst-specified range of .

We combine this both with the original shifted inverse mechanism of [20] as well as a new, ( , )-private variant, described in Section 3.1, that achieves better dependency on the range size. This latter improvement comes from abstracting the original version as a reduction to the generalized interior point problem [7,12]. Monotonization and the resulting wrapper are described in Section 3.2. Subset Extension. Our starting point for the claimed sensitivity bound setting is the TAHOE algorithm of [31]. We first briefly describe (in a way that fits well with our adaptation). As with monotonization, we first (privately) compute and release a lower bound ℓ on the size of , which lies in the range

(with high probability). This gives a "floor" below which we do not need to read and bounds the locality by 3 . The next step is to attempt to find a subset of N ³ 2 ( ) on which is Lipschitz. Specifically, we say a subset of is ℓ-stable if is Lipschitz when restricted to the subsets of of size at least ℓ. Kohli and Laskowksi show several structural properties of these sets. Let Σ ℓ,ℎ 0 ( ) denote the collection of ℓ-stable subsets of of size at least ℎ

Then is Lipschitz on the domain Σ ℓ,ℎ 0 ( ). Furthermore, for every ℎ g ℎ 0 , if ′ is a neighboring dataset of that is larger (by one insertion), then

TAHOE can then be described as follows: first, select a publiclyreleased ℓ and unreleased ℎ, both noisy (according to Laplace like distributions) and likely to satisfy

) is empty, and release this bit. Finally, if Σ ℓ,ℎ ( ) is not empty, then pick an arbitrary largest set in Σ ℓ,ℎ ( ) and release ( ) + ( / ). We can think of ( ) as an approximation to ( ) which is exact when is Lipschitz on all of N ³ 3 ( ) (since then = ). Privacy goes through because the bit indicating the emptiness of Σ ℓ,ℎ ( ) is randomized (by the randomness of ℎ) and differentially private; and the diameter of Σ ℓ,ℎ 0 ( ′ ) is ( ), so the sensitivity of ( ) is ( ) no matter how is chosen.

We develop two different improvements over TAHOE, each of which modifies the structure above so that, roughly, the approximation to ( ) has sensitivity ( ) even when is not Lipschitz.

Our first major departure from the TAHOE approach is to transform to get a new function ˆ :

that is monotone and Lipschitz whenever is Lipschitz. Unlike the monotonization described in the previous section, this transformation comes with no guarantees for arbitrary . However, it allows us to choose a nearly-canonical representative in the set Σ ℓ,ℎ ( ), which is a point that maximizes ˆ ( ) over Σ ℓ,ℎ ( ). When ˆ is monotone, maximizing the function value and maximizing the size of coincide.

Our second major departure is to average over the choices of ℎ rather than choosing ℎ randomly. In Subset-Extension, we set ℓ using the truncated Laplace mechanism and average over the choice of ℎ in a range determined by ℓ. For neighboring datasets and ′ , we show a coupling between the function estimates computed using different (ℓ, ℎ) pairs such that coupled (ℓ, ℎ) values lead to similar estimates of ( ) and ( ′ ) with high probability. Averaging over ℎ turns this high-probability Wasserstein distance bound into an

(1) upper bound on the difference between estimates (when all checks for existence of stable sets pass), allowing us to release the estimate with little noise.

This description hides a number of challenges that arise in the analysis. See the full version [33] for details.

Lower Bound Techniques. Proofs of our lower bounds appear in the full version. We provide two lower bounds: one on the locality of accurate privacy wrappers-via reduction from well-studied problem in the privacy literature-and another on the actual query complexity, via a new argument closer to the techniques in the property testing literature.

In order to prove the lower bound on locality, we reduce from the "point distribution problem" . In the point distribution problem, an algorithm is given a multiset of elements from some universe Y as input. For all ∈ Y, the algorithm must output whenever consists only of identical copies of . Standard packing arguments suffice to show a lower bound on the size of the multiset for any differentially private algorithm that solves the point distribution problem. Our reduction then proceeds by arguing that a privacy wrapper that is -down local can be used to solve the point distribution problem with mutlisets of size + 1.

Our second lower bound, states that every ( , )-privacy wrapper that is ( , )-accurate on Lipschitz functions with range size must have query complexity | |

. Thus, the query complexity of our privacy wrappers is optimal. Additionally, while all of our privacy wrappers are down-local, the query complexity lower bound applies even to privacy wrappers that do no satisfy this guarantee (i.e., privacy wrappers that query on arbitrary datasets ). To prove our query complexity lower bound, we take advantage of the fact that if two points , ∈ U * are "close", but ( ) and ( ) are "far", then every privacy wrapper must be inaccurate on or . Leveraging this property, we construct distributions N and P over pairs ( , ) where is a dataset and is a function from [ ] * to R with the following properties: First, every algorithm that gets query access to and input must make many queries to to distinguish whether ( , ) ∈ supp(N ) or ( , ) ∈ supp(P). And second, every privacy wrapper that is accurate for Lipschitz functions is inaccurate when ( , ) ∈ supp(N ) and accurate when ( , ) ∈ supp(P). Combining these two observation, we show that a query-efficient privacy wrapper that is accurate for all Lipschitz functions can be used as a subroutine to construct a low query algorithm for distinguishing N and P. It follows that privacy wrapper that is accurate for all Lipschitz functions must make many queries to .

Related Work

Private Evaluation of Black-box Functions. Privacy in the context of black-box functions was first explicitly considered by [27]. They connect the claimed sensitivity setting with the concept of local filter from the sublinear algorithms literature. This line of work [3,27,32] constructs privacy wrappers from local filters for Lipschitz functions. Their constructions query the function on inputs obtained by both insertions and deletions. Their query complexity depends on the universe size, and the analyst's sensitivity bound must allow for the insertion of arbitrary outliers in the dataset.

Local Sensitivity and Robustness. Soon after the introduction of differential privacy, the research community aimed to identify properties of a function that allow for accurate differentially private approximation. A key concept was the local sensitivity [36] of at , the maximum change in that can be incurred by inserting or removing one element (or a small number of elements) in .

Starting with [36] and [16], a rich line of work found different ways to enforce and take advantage of (variants of) low local sensitivity (e.g., [1,2,24], to mention only a few). Low local sensitivity within a neighborhood of insertions and deletions is equivalent to the notion of adversarial robustness from the robust statistics literature. Many natural estimators do not have that type of robustness: for example, sample means and ordinary least-squares regression estimates can be moved arbitrarily far by the insertion of a single outlier. They often require function-specific modifications (such as trimming, huerization, and so forth) to make them robust. Indeed, there is a large literature in the design of robust versions of popular estimators [25,35].

Look Down: Lipschitz Extensions and Down Sensitivity. Another rich line of work in the privacy literature develops techniques for settings where we expect a computation of interest to be much more sensitive to insertions than removals of entries from the input dataset. One branch, initially motivated by node-private algorithms for graphs [4-6, 11, 14, 26, 28, 30, 37-39], developed Lipschitz extensions, which extend a function from a subdomain of input datasets that has low sensitivity to the entire domain. The subdomains of interest were generally closed under removals but not insertions. The concept of down sensitivity (at depth 1) was introduced by Chen and Zhou [11] to help describe these subdomains; they also studied the Lipschitz constant of on the power set of . (For the supermodular functions studied in [11,30], these coincide.) These works generally focused on efficient constructions in the white-box setting, mostly for monotone functions. However, some extensions, such as that of [13], can be interpreted as a black-box construction (as in Table 2). Down Sensitivity at Bounded Depth. Two recent works on privacy study mechanisms that look only at the behavior of the function on large subsets of the input. Fang, Dong, and Yi [20] focus on white-box approaches to releasing monotone functions without an a-priori sensitivity bound, while Kohli and Laskowski [31] consider the black-box, claimed sensitivity setting. The KL mechanism was recently extended to general outputs in [21,22], though their improvements do not affect our setting.

Resiliency in Robust Statistics. The two notions of accuracy that we consider-expressed in terms of the diameter of (N ³ ( )) and the Lipschitz constant on N ³ ( )-correspond to two different notions of resiliency. The diameter-based notion corresponds (up to reparameterization) to the definition of resiliency [41], whereas the Lipschitz notion has not been considered explicitly before in the statistics and learning literature, to our knowledge. One can interpret the information-theoretic results of [41] as a generic transformation that takes a function and produces a version that is robust in the neighborhood of an input whenever is resilient with respect to the original function . However, we are not aware of a generic way to transform that into a differentially private mechanism using previous work, without still needing to explore the values of ( ) for all sets that differ from in insertions and deletions. We make the [41] transformation explicit and discuss its consequences in the full version [33].

Generic Statistical Results. Dwork and Lei [16] and Smith [40] give generic transformations that create differentially private versions of statistical estimators. These results are incomparable to ours, since they rely on specific properties of the estimators, such as asymptotic normality and low bias.

Preliminaries

In this section, we formally define privacy wrappers, our main object of study. Let U be an arbitrary countable universe of elements and U * be the set of finite subsets of U. First, we recall the definition of differential privacy. Definition 2.1 (Neighboring sets, differential privacy [17]). Two sets , ∈ U * are neighbors if either = ∪ { } or = ∪ { } for some ∈ U. A randomized algorithm M is ( , )-differentially private (DP) if for all neighboring , ∈ U * and all measurable subsets of the set of outputs of M,

When = 0, this guarantee is referred to as pure differential privacy; the guarantee with > 0 is called approximate differential privacy. Definition 2.2 (Diameter). The diameter of a bounded set ¢ R is sup ( )inf ( ). Moreover for all : U * → R and ¦ U * , we define ( ) as the set { ( ) : ∈ }.

Definition 2.3 (Lipschitz functions and global sensitivity).

Fix g 0. Given a domain ¦ U * , a function : U * → R is -Lipschitz over if | ( ) -( )| f for all neighbors , ∈ . For brevity, we use "Lipschitz" instead of "1-Lipschitz". When = U * , we just say " -Lipschitz", without specifying the domain. The smallest constant for which function is -Lipschitz is called the Lipschitz constant or the (global) sensitivity of . Definition 2.4 (Monotone functions). Given a domain ¦ U * , a function : U * → R is monotone on if ( ) f ( ) for all , ∈ such that ¢ .

Next, we define privacy wrappers. Informally, a privacy wrapper is a differentially private algorithm W that gets two types of inputs: public and sensitive. The public inputs consist of a function , to which the wrapper has query access, and a possibly empty list of parameters. The sensitive input is a data set ∈ U * . The algorithm run with query access to is denoted W , and its output on dataset is denoted W ( ). (We treat W ( ) as a random variable.) We omit explicit notation for the parameters. Definition 2.5 (Privacy wrapper [31]). Fix a universe U and privacy parameters > 0 and ∈ [0, 1). Consider a randomized algorithm W that gets as input a dataset ∈ U * , additional parameters, and query access to a function : U * → R. It then produces output in R ∪ { §}. Algorithm W is an ( , )-privacy wrapper if, for every function and every choice of the additional parameters, the algorithm W is ( , )-differentially private. Fact 2.1 (Laplace mechanism [17]). Fix > 0 and let : U * → R be a -Lipschitz function. Then, the algorithm that gets a query ∈ U * as input, samples ∼ Lap( ), and outputs ( ) = ( ) + , is ( , 0)-DP. Additionally, for all > 0, we have | ( ) -( )| f ln 1 with probability at least 1 -. Moreover, the same mechanism implemented with noise ∼ TruncLap( , ln 1 ) is ( , )-DP.

We repeatedly use the following tail bound for Laplace random variables.

Fact 2.2 (Laplace tails). For all > 0 and ∈ (0, 1), if ∼ Lap( ) then Pr | | g ln 1 = .

We use the following well known facts regarding the composition of differentially private mechanisms and postprocessing. (See [18]). following expression:

Sens-o-Matic: A Wrapper for General Functions

The two variants of the Shifted Inverse mechanism discussed in the previous section are not privacy wrappers because they are only private under the promise that the function is monotone. In this section, we generalize ShI to work for all functions.

Proof of Theorem 3.1. The main idea in the generalization of the ShI mechanism is to construct a monotone function from the original function and use in the ShI mechanism. The value of at point will be computed from the down neighborhood of . We parameterize by the lowest level (i.e., the set size) we include in the down neighborhood.

The following properties of monotonization follow directly from its definition. ² is set so that ShI run with the parameter 2:

² settings below uses depth parameter /2. The two failure events we consider are (1) the noise variable in Line 3 has large absolute value, | | > 2 ln 2 , and (2) ShI fails. Each of these events happens with probability at most /2, by Fact 2.2 and the setting of parameters given to ShI. By the union bound over these two events, the overall failure probability is at most . Now, we analyze accuracy of Sens-o-Matic. Suppose that neither failure event occurred. Then | | f 2 ln 2 f 4 . (We assume w.l.o.g. that is sufficiently large for this inequality to hold.) Consequently,

Let W denote Algorithm 1 and M denote the ShI mechanism. Recall that is set so that ShI in Line 4 is run with the depth parameter /2. By the accuracy guarantee of ShI, we get Thus, with probability at least 1 -, we get |W ( ) -( )| f ( ), as claimed. Finally, to evaluate M ℓ [ ], the wrapper only needs to query the subsets of the dataset of size at least ℓ. Recall that ℓ satisfies (8) with probability at least 1 -. When it does, all queries of W are within N ³ ( ), completing the proof of Theorem 3.1. □