KNG: The K-Norm Gradient Mechanism

Introduction

The last decade has seen a tremendous increase in research activity related to data privacy (Aggarwal and Philip, 2008; Lane et al., 2014; Machanavajjhala and Kifer, 2015; Dwork et al., 2017). This drive has been fueled by an increasing societal concern over the large amounts of data being collected by companies, governments, and scientists. These data often contain vast amounts of personal information, for example DNA sequences, images, voice recordings, electronic health records, and internet usage patterns. Such data allows for great scientific progress by researchers and governments, as well as increasingly curated business strategies by companies. However, the such data also comes with increased risk for privacy breaches, placing greater pressure on institutions to prevent disclosures.

Currently, Differential Privacy (DP) (Dwork et al., 2006) is the leading framework for formally quantifying privacy risk. One of the most popular methods for achieving DP is the Exponential Mechanism, introduced by McSherry and Talwar (2007), and used in (Friedman and Schuster, 2010; Wasserman and Zhou, 2010; Blum et al., 2013; Dwork and Roth, 2014). A major attribute of the exponential mechanism that contributes to its popularity is its flexibility; it can be readily adapted and incorporated into most statistical analyses. In particular, its structure makes it amenable to a wide array of statistical and machine learning problems that are based on minimizing an objective function, so called “$m$-estimators” (van der Vaart, 2000, Chapter 5). Some examples where the exponential mechanism has been used include PCA (Chaudhuri et al., 2013; Awan et al., 2019), hypothesis testing (Canonne et al., 2019), maximum likelihood estimation (related to posterior sampling) (Wang et al., 2015; Minami et al., 2016), and density estimation (Wasserman and Zhou, 2010).

However, examples have arisen (Wang et al., 2015; Awan et al., 2019) where the magnitude of the noise added by the exponential mechanism is substantially higher than other mechanisms. Recently, Awan et al. (2019), demonstrated that, in a very broad sense, the exponential mechanism adds noise that is not asymptotically negligible relative to the statistical estimation error, which other mechanism are able to achieve in different problems (e.g. Smith, 2011). In this paper we provide a new mechanism called the K-Norm Gradient Mechanism, or KNG, that retains the flexibility of the exponential mechanism, but with substantially improved utility guarantees. KNG provides a principled approach to developing efficient mechanisms that also perform well in practice. Indeed the Laplace, $K$-norm, and PrivateQuantile mechanisms can all be viewed as instantiations of KNG. Here we also use KNG to provide the first mechanism for private quantile regression that we are aware of, which we empirically show is efficient.

The remainder of this paper is organized as follows. In Section 2 we recall the necessary background on differential privacy and the exponential mechanism. In Section 3 we formally define KNG and show that it achieves $\epsilon$-DP with nearly the same flexibility as the exponential mechanism. We also provide a general utility result that shows that the noise introduced by KNG is of order $O_{p}(n^{-1})$, which is negligible compared to the statistical estimation error, which is typically $O_{p}(n^{-1/2})$. We also show that the noise introduced by KNG is asymptotically from a $K$-norm mechanism. In section 4 we provide several examples of KNG applied to statistical problems, including mean estimation, linear regression, median/quantile estimation, and quantile regression. We also illustrate the empirical advantages of KNG in the settings of linear and quantile regression through simulations. We conclude in Section 5 by discussing challenges and potential extensions of KNG.

Differential Privacy Background

Differential privacy (DP), introduced by Dwork et al. (2006) has taken hold as the primary framework for formally quantifying privacy risk. Several versions of DP have been proposed, such as approximate DP (Dwork and Roth, 2014), concentrated DP (Dwork and Rothblum, 2016; Bun and Steinke, 2016), and local DP (Duchi et al., 2013), all of which fit into the axiomatic treatment of formal privacy given by Kifer and Lin (2012). In this paper, we work with pure $\epsilon$-DP, stated in Definition 2.1.

Let $f:\mathcal{D}^{n}\to\Theta$ represent a summary of $\mathcal{D}^{n}$, and $\mathcal{F}$ a $\sigma$-algebra on $\Theta$, such that $(\Theta,\mathcal{F})$ is a measurable space. A privacy mechanism is a family of probability measures $\{\mu_{D}:D\in\mathcal{D}^{n}\}$ over $\Theta$.

A privacy mechanism $\{\mu_{D}:D\in\mathcal{D}^{n}\}$ satisfies $\epsilon$-Differential Privacy ($\epsilon$-DP) if for all $B\in\mathcal{F}$ and adjacent $D,D^{\prime}\in\mathcal{D}^{n}$,

The exponential mechanism, introduced by McSherry and Talwar (2007) is a central tool in the design of DP mechanisms (Dwork and Roth, 2014). In fact every mechanism can be viewed as an instance of the exponential mechanism, by setting the objective function as the log-density of the mechanism. In practice, it is most common to set the objective as a natural loss function, such as an empirical risk.

The K-Norm Gradient Mechanism

Since KNG utilizes the gradient, it links in nicely to optimization methods such as gradient descent. However, it could also suffer from some of the same challenges as gradient descent. Namely, if the objective function has multiple local minima, then KNG will promote output near each these points. For this reason, a great deal of care should be taken with KNG when applying to non-convex objective functions, such as fitting neural networks (Gori and Tesi, 1992).

While flexibility of a mechanism is an important concern, ultimately the utility of the output is of primary importance. Awan et al. (2019) showed that for a large class of objective functions, the exponential mechanism introduces noise of magnitude $O_{p}(n^{-1/2})$, where $n$ is the sample size. For many statistical problems the non-private error rate is also $O_{p}(n^{-1/2})$ (van der Vaart, 2000, Chapter 5), meaning that the exponential mechanism introduces noise that is not asymptotically negligible.

Under similar assumptions, we show in Theorem 3.2 that KNG has aymptotic error $O_{p}(n^{-1})$, which is asymptotically negligible compared to the statistical error. In fact, Theorem 3.2 shows that the noise introduced is asymptotically from a $K$-norm mechanism (Hardt and Talwar, 2010; Awan and Slavković, 2018), which generalizes the Laplace mechanism.

$\Delta(\theta)$ is continous in $\theta$, constant in $n$, and there exists $\Delta>0$ such that $\Delta\leq\Delta(\theta).$

The proof of the CLT for the exponential mechanism in Awan et al. (2019), as well as the proof of Theorem 3.2, both rely on a Taylor expansion of the objective function. In both cases, it is assumed that the Hessian converges, when scaled by $n$, to a positive definite matrix. However, using the original objective function requires two derivatives before the Hessian appears in the Taylor expansion, whereas the use of the gradient only requires one derivative. The consequence of this is that the traditional exponential mechanism results in a quadratic numerator inside the exponent, whereas KNG has a (normed) linear numerator. Asymptotically, this gives an $O_{p}(n^{-1/2})$ Gaussian noise for the exponential mechanism and an $O_{p}(n^{-1})$ $K$-norm noise for KNG. Geometrically, it seems that the use of an objective function which behaves linearly (in absolute value) near the optimum, rather than quadratic, results in better asymptotic utility. By using the normed-gradient, we construct an objective function with this property.

The assumptions in Theorem 3.2 are very similar to the assumptions for the CLT in Awan et al. (2019). So, whenever these properties hold, we know that KNG results in an $O_{p}(n^{-1})$ privacy noise whereas the exponential mechanism is $O_{p}(n^{-1/2})$. To further emphasize the importance of this result, we note that the magnitude of the noise introduced for privacy can have a substantial impact on the sample complexity. Asymptotically, KNG requires exactly the same sample size as the non-private estimator, whereas the exponential mechanism requires a constant $>1$ multiple of the non-private sample size to achieve the same accuracy.

As we see in Section 4, in the problem of quantile regression the assumptions of Theorem 3.2 do not hold, meaning that while we guarantee privacy in that setting, we can’t guarantee the utility of the estimator. However, we see in Figure 2 that KNG still introduces asymptotically negligible noise, suggesting that the assumptions of Theorem 3.2 can likely be weakened to accomodate a larger class of objective functions.

Based on the discussion in Section 1, a result similar to 3.2 may hold for objective perturbation as well. The main issue is dealing with the change of variables factor $|\det\bf H_{n}(\theta)|$, which may or may not contribute to the asymptotic form. We suspect that when both KNG and objective perturbation are applicable (e.g. linear regression, see subsection 4.3), they will have similar performance. However, as KNG does not require a second derivative (or convexity), it is applicable in more settings than objective perturbation (e.g. quantile regression, see subsection 4.5).

Examples

Mean estimation is one of the simplest statistical tasks, and one of the first to be solved in DP. Assuming bounds on the data, the mean can be estimated by adding Laplace noise (Dwork et al., 2006). Recently there has been some work developing statistical tools for the mean under differential privacy, such as confidence intervals in the normal model (Karwa and Vadhan, 2017) and hypothesis tests for Bernouilli data (Awan and Slavković, 2018). We show that KNG recovers the $K$-norm mechanism when estimating the mean, a generalization of the Laplace mechanism.

Because the KNG results in a location family in this case, the integrating constant does not depend on the data. So, we do not need to divide $\epsilon$ by 2 in the density, and may instead draw from $f_{n}(\theta)\propto\exp\left\{\frac{n\epsilon}{2r}\left\|\bar{x}-\theta\right\|_{K}\right\}$, which is how the $K$-norm mechanism is normally stated.

2 Linear Regression

with respect to the uniform measure on $\Theta=\{\theta\mid\lVert\theta\rVert_{1}\leq B\}$.

Alternative sensitivity bounds can be obtained by choosing other bounds on $x$ and $y$. The bound on $\theta^{*}$ can be removed entirely, allowing $\Delta$ to depend on $\theta$. In that case, a nontrivial base measure will be required as the resulting density is not integrable with respect to Lebesgue measure. We prefer to use the given sensitivity bound as it allows a fairer comparison against the exponential mechanism and objective perturbation in subsection 4.3.

3 Linear Regression Simulation

In this section, we examine the finite sample performance of the KNG mechanism on linear regression compared to the exponential mechanism and objective perturbation mechanism. KNG samples from the density (1), the exponential mechanism samples from

At the end, we compute the average distance over the 100 replicates for each mechanism and for each sample size $n$. The results are plotted in Figure 1, taking the base 10 log of both axes. At each $n$ value and for each mechanism, the Monte Carlo standard errors are between $0.01380$ and $0.02729$, in terms of the log-scale used in the plot. The benefit of plotting in this fashion is that it makes it easier to understand the asymptotic behavior of each estimator.

4 Median Estimation

Again, the error introduced is $O_{p}(n^{-1})$, which is negligible compared to the statistical error.

5 Quantile Regression

We bound the sensitivity as $\Delta=2(1-\tau)C_{X}$, where $\sup_{x_{1}}\lVert x_{1}\rVert\leq C_{X}$. Then KNG samples from

Finally note that if we are only interested in estimating the $\tau^{th}$ quantile of a set of real numbers $Y_{1},\ldots,Y_{n}$, we could set $X_{i}=1$ for all $i=1,\ldots,n$, in which case KNG samples from

In fact, this is the Private Quantile algorithm proposed by Smith (2011), who also establish strong utility guarantees for the algorithm; this exercise demonstrates that KNG could provide, or at least contribute to, a more unified framework for developing efficient privacy mechanisms.

In this section, we examine the empirical performance of the KNG mechanism on quantile regression compared to the exponential mechanism. KNG samples from the density (2) using the $\lVert\cdot\rVert_{\infty}$ norm and setting $C_{X}=1$, and the exponential mechanism samples from

We assume, as in subsection 4.3 that $B=1$. Details on the exponential mechanism can be found in the Supplementary Materials. Note that objective perturbation cannot be used in this setting, as discussed in subsection 4.5.

We see in figure 2 that the non-private estimate appears as a straight line with slope $-1/2$, reflecting the fact that its estimation error is $O_{p}(n^{-1/2})$. We also see that the exponential mechanism approaches a line with slope $-1/2$, but with a higher intercept, reflecting that it has increased asymptotic variance. Last, we see that the error of KNG approaches the error line of the non-private estimator, suggesting that KNG has the same asymptotic rate as the non-private estimator.

While the utility guarantees of Theorem 3.2 do not apply in this setting, as the objective function is not strongly convex, the santized estimates still achieve $\epsilon$-DP and we see from Figure 2 that, empirically, KNG introduces $o_{p}(n^{-1/2})$ error in this setting as well. This suggests that the assumptions in Theorem 3.2 can likely be weakened, and KNG in fact produces efficient mechanisms for an even broader set of problems than Theorem 3.2 prescribes.

Conclusions

In this paper we presented a new privacy mechanism, KNG, that maintains much of the flexbility of the exponential mechanism, while having substantially better utility guarantees. These guarantees are similar to those provided by objective perturbation, but privacy can be achieved with far fewer structural assumptions. A major draw back of the mechanism is the same as for gradient descent, which can have trouble with local minima or saddle points. Two interesting open questions concern the finite sample efficiency of KNG vs objective perturbation and if KNG can be adapted or combined with other methods to better handle multiple minima.

We also believe that KNG has a great deal of potential for handling infinite dimensional and nonlinear problems. For example, parameter spaces consisting of Hilbert spaces or Riemannian manifolds have structures that allow for the computation of gradients, and which might be amenable to KNG. With Riemannian manifolds, the gradient is often viewed as a linear mapping over tangent spaces, while in Hilbert spaces, the gradient is often treated as a linear functional. A major advantage of KNG over other mechanisms is the direct incorporation of a general $K$-norm. Awan et al. (2019) showed that the exponential mechanism has major problems over function spaces, which are of interest in nonparametric statistics. These issues could potentially be alleviated by KNG with a careful choice of norm. Many interesting challenges remain in data privacy, especially if there is additional complicated structure in the parameters or data.

KNG has strong connections with prior DP mechanisms, especially the exponential mechanism and objective perturbation. Indeed, like nearly every privacy mechanism, KNG can be phrased as very particular type of exponential mechanism, however this doesn’t provide insight into why KNG achieves better statistical properties. In particular, a key point is to consider the objective function that motivated the original statistical summary, which, when used with KNG produces sanitized estimators with better statistical performance than the classic implementation of the exponential mechanism.

One downside of KNG is the issue of sampling, which is similar to the exponential mechanism in that sampling from these distributions is, in general, non-trivial. We show that for mean and quantile estimation, KNG results in distributions that are efficiently sampled. However, for linear and quantile regression, we used a one-at-a-time MCMC procedure (also used for exponential mechanism). Just like sampling from an posterior distribution, developing a convenient sampling scheme is case-by-case, but often a simple MCMC procedure works well in practice.

Acknowledgements

This research was supported in part by NSF DMS 1712826, NSF SES 1853209, and NSF SES-153443 to The Pennsylvania State University. The first author is also grateful for the hospitality of the Simons Institute for the Theory of Computing at UC Berkeley.

References

Proofs

For notational simplicity, we assume that the base measure, $\mu$, is Lebesgue. The density of the KNG mechanism can then be expressed as

Using a one term Taylor expansion, we have by Assumption (2) and (3) that

for some constant $C$. Since $\exp\{-\|z\|_{2}\}$ is integrable, we can apply the dominated convergence theorem to conclude that the constants converge to a nonzero and finite quantity. Since $\Delta(\theta)$ is continuous in $\theta$, we also have that $\Delta(\hat{\theta}+z/n)\rightarrow\Delta(\theta^{*})$. Putting everything together, we can conclude that

which is the density of the $K$-norm mechanism. Applying Scheffe’s Theorem, we thus have both convergence in distribution as well as convergence in total variation to a $K$-norm mechanism ∎

Linear Regression

with respect to the uniform measure on $\{\theta\mid\lVert\theta\rVert_{1}\leq B\}$.

2 Objective Perturbation

For objective perturbation, we use the version stated in Awan and Slavković , which allows us to use the same bound on the gradient as developed in subsection 4.2. Objective perturbation also requires a bound on the eigenvalues of the hessian for one datapoint:

Objective perturbation then draws a random vector $b$ from the density $f(b)\propto\exp\left(-\frac{\epsilon}{8(1+B)}\lVert b\rVert_{\infty}\right)$ (a simple sampling algorithm for $f(b)$ is stated in Awan and Slavković ), and then finds the optimum of the modified objective:

Quantile Regression

The exponential mechanism then samples from the density