Private Convex Optimization via Exponential Mechanism

Introduction

Differential Privacy (DP), introduced in [DMNS06, DKM+06], is increasingly becoming the universally accepted standard in privacy protection. We see an increasing array of adoptions in industry [App17, EPK14, BEM+17, DKY17] and more recently the US census bureau [Abo16, KCK+18]. Differential privacy allows us to quantify the privacy loss of an algorithm and is defined as follows.

A randomized mechanism $\operatorname*{\mathcal{M}}$ is $(\varepsilon,\delta)$-differentially private if for any neighboring databases $\mathcal{D},\mathcal{D}^{\prime}$ and any subset $S$ of outputs, one has

In this paper, we say $\mathcal{D}$ and $\mathcal{D}^{\prime}$ are neighboring databases if they agree on all the user inputs except for a single user’s input.

where $x^{*}\in\mathcal{K}$ is the true minimizer of $F(x;\mathcal{D})$.

One of the first mechanisms invented in differential privacy, the exponential mechanism, was proposed by [MT07] precisely to solve this. It involves sampling $x^{priv}$ from the density

Here $k$ controls the privacy-vs-utility tradeoff, large $k$ ensures that we get a good solution but less privacy and small $k$ ensures that we get good privacy but we lose utility. Suppose $\Delta_{F}=\sup_{\mathcal{D}\sim\mathcal{D}^{\prime}}\sup_{x}|F(x;\mathcal{D})-F(x;\mathcal{D}^{\prime})|$ is the sensitivity of $F$, where the supremum is over all neighboring databases $\mathcal{D},\mathcal{D}^{\prime}$. Then choosing $k=\frac{\varepsilon}{2\Delta_{F}}$, the exponential mechanism satisfies $(\varepsilon,0)$-DP.

Exponential mechanism is widely used both in theory and in practice, such as in mechanism design [HK12], convex optimization [BST14, MV21], statistics [WZ10, WM10, AKRS19], machine learning and AI [ZP19]. Even for infinite and continuous domains, exponential mechanism can be implemented efficiently for many problems [HT10, CSS13, KT13, BV19, CKS20]. There are also several variants and generalizations of the exponential mechanism which can improve its utility based on different assumptions [TS13, BNS13, RS16, LT19]. See [LT19] for a survey of these results.

DP Empirical Risk Minimization (DP-ERM)

In many applications, the loss function is given by the average of the loss of each user:

where $\mathcal{D}=\{s_{1},s_{2},\cdots,s_{n}\}$ is the collection of users $s_{i}$ and $f(x;s_{i})$ is the loss function of user $s_{i}$.

In particular, [BST14] shows that exponential mechanism in (2) achieves the optimal excess empirical risk of $O\left(\frac{GDd}{n\varepsilon}\right)$ under $(\varepsilon,0)$-DP. On the other hand, [BST14, BFTT19, BFGT20] show that noisy gradient descent on $F(x;\mathcal{D})$ achieves an excess empirical risk of

under $(\varepsilon,\delta)$-DP, which is also shown to be optimal [BST14]. This is a significant $\sqrt{d}$ improvement over the exponential mechanism.

Exponential mechanism is a universally powerful tool in differential privacy. However, nearly all of the previous works on DP-ERM rely on noisy gradient descent or its variants to achieve the significant $\sqrt{d}$ improvement over exponential mechanism under $(\varepsilon,\delta)$-DP. One natural question is whether noisy gradient descent has some extra ability that exponential mechanism lacks or we didn’t use exponential mechanism optimally in this setting. This brings us to the first question.

Can we obtain the optimal empirical risk in (1) under $(\varepsilon,\delta)$-DP using exponential mechanism?

DP Stochastic Convex Optimization (DP-SCO)

Beyond the privacy guarantee and the empirical risk guarantee, another important guarantee is the generalization guarantee. Formally, we assume the users are sampled from an unknown distribution $\mathcal{P}$ over convex functions. We define the loss function as

We want to design a DP mechanism $\mathcal{M}$ which outputs $x^{priv}$ given users $\mathcal{D}=\{s_{1},s_{2},\dots,s_{n}\}$ independently sampled from $\mathcal{P}$ and minimize the excess population loss

where $x^{*}$ is the minimizer of $\widehat{F}(x)$. We call the problem of minimizing the excess population loss in (6) as DP Stochastic Convex Optimization (DP-SCO). By a suitable modification of noisy stochastic gradient descent, [BFTT19, FKT20] show that one can achieve the optimal population loss of

[BFTT19] bounds the generalization error by showing that running SGD on smooth functions is stable and [FKT20] proposes an iterative localization technique. Note that only the algorithm for smooth functions in [BFTT19] can achieve both optimal empirical risk and optimal population loss at the same time, with the price of taking more gradient queries and loss of efficiency. It is unclear to us how one can obtain both using current techniques for non-smooth functions. This brings us to the second question.

Can we achieve both the optimal empirical risk and the optimal population loss for non-smooth functions with the same algorithm?

Sampling

Without extra smoothness assumptions on $f$, currently, there is no optimally efficient algorithm for both problems. For example, with oracle access to gradients of $f$, the previous best algorithms for DP-SCO use:

$\widetilde{O}(nd)$ queries to $\nabla f(x;s)$ (by combining [FKT20], Moreau-Yosida regularization and cutting plane methods),

$\widetilde{O}(\min(n^{3/2},n^{2}/\sqrt{d}))$ queries to $\nabla f(x;s)$ [AFKT21],

$\widetilde{O}(\min(n^{5/4}d^{1/8},n^{3/2}/d^{1/8}))$ queries to $\nabla f(x;s)$ [KLL21].

Combining these results, this gives an algorithm for DP-SCO that uses

many queries to $\nabla f(x;s)$. Although the information lower bound for non-smooth functions with the gradient queries is open, it is unlikely that the answer involves four different cases.

In this paper, we focus on the function value query (zeroth order query) on $f(x;s)$. This query is weaker than gradient query as it obtains $d$ times less information. They are used in many practical applications such as clinical trials and ads placement when the gradient is not available and is also useful in bandit problems. This brings us to the third question.

Can we obtain an algorithm with optimal query complexity for DP-SCO for zeroth order query model?

1 Our Contributions

then, for a suitable choice of $\mu$ and $k$, we recover the optimal excess risk in (4) for DP-ERM and optimal population loss in (7) for DP-SCO. Finally, we give an algorithm to sample $x^{priv}$ from the density (8) with nearly optimal number of queries to $f(x;s)$ (See Figure 1). To the best of our knowledge, our algorithm is the first whose query complexity has polylogarithmic dependence in both dimension and accuracy (in TV distance).

Let $\mathcal{K}$ be a convex set with diameter $D$ and $\{f(\cdot;s)\}$ be a family of convex functions on $\mathcal{K}$ where $f(\cdot;s)-f(\cdot;s^{\prime})$ is $G$-Lipschitz for all $s,s^{\prime}$. Given a database $\mathcal{D}=\{s_{1},s_{2},\cdots,s_{n}\}$, for any $\varepsilon,\delta\in(0,\frac{1}{10})$, See Theorem 6.2 for general conclusions for all $\varepsilon>0$ the regularized exponential mechanism

is $(\varepsilon,\delta)$-DP with expected excess empirical loss

for some appropriate choices of $k$ and $\mu$. Furthermore, if $f(\cdot;s)$ is $G$-Lipschitz for all $s$, we can sample $x^{(priv)}$ using $O(\frac{\varepsilon^{2}n^{2}}{\log(1/\delta)}\log^{2}(\frac{nd}{\delta}))$ queries in expectation to the values of $f(x;s)$.

Let $\mathcal{K}$ be a convex set with diameter $D$ and $\{f(\cdot;s)\}$ be a family of convex functions on $\mathcal{K}$ where $f(\cdot;s)-f(\cdot;s^{\prime})$ is $G$-Lipschitz for all $s,s^{\prime}$. Given a database $\mathcal{D}=\{s_{1},s_{2},\cdots,s_{n}\}$ of samples from some unknown distribution $\mathcal{P}$. For any $\varepsilon,\delta\in(0,\frac{1}{10})$, See Theorem 6.9 for general conclusions for all $\varepsilon>0$. the regularized exponential mechanism

is $(\varepsilon,\delta)$-DP with expected excess population loss

for some appropriate choice of $k$ and $\mu$. Furthermore, if $f(\cdot;s)$ is $G$-Lipschitz for all $s$, we can sample $x^{(priv)}$ using $O(\min\{\frac{\varepsilon^{2}n^{2}}{\log(1/\delta)},nd\}\log^{2}(\frac{nd}{\delta}))$ queries in expectation to the values of $f(x;s)$ and the expected number of queries is optimal up to logarithmic terms.

For DP-SCO, we provide a nearly matching information-theoretic lower bound on the number of value queries (Section 7), proving the optimality of our sampling algorithm. Moreover, when $f$ is already strongly convex, our proof shows the exponential mechanism (without adding a regularizer) itself simultaneously achieves both the optimal excess empirical risk and optimal population loss.

In a concurrent and independent work, [GTU22] study the DP properties of Langevin Diffusion, and provide optimal/best known private empirical risk and population loss under both pure-DP ($\delta=0$) and approximate-DP ($\delta>0$) constraints. Utility/privacy trade-off of non-convex functions is also discussed.

Techniques

The main contribution of this paper is the discovery that adding regularization terms in exponential mechanism leads to optimal algorithms for DP-ERM and DP-SCO. For this, we develop some important tools that could be of independent interest. We now briefly discuss each of the main tools.

To analyze the privacy of the regularized exponential mechanism, we need to bound the privacy curve between a strongly log-concave distribution and its Lipschitz perturbation in the exponent. [MASN16] gave a nearly tight (up to constants) privacy guarantee of exponential mechanism if the distribution $\exp(-kF(x;\mathcal{D}))$ satisfies Logarithmic Sobolev inequality (LSI). Since strongly log-concave distributions satisfy LSI, their result immediately gives the $(\varepsilon,\delta)$-DP guarantee of our algorithm. However, this gives a sub-optimal privacy bound because it does not fully take advantage of the strongly log-concave property.

Instead, we show directly that the privacy curve between a strongly log-concave distribution and its Lipschitz perturbation in the exponent is upper bounded by the privacy curve of an appropriate Gaussian mechanism. This new proof uses the notion of tradeoff function introduced in [DRS19] and the isoperimetric inequality for strongly log-concave distribution.

This proves that the privacy curve for distinguishing between $P,Q$ is upper bounded the privacy curve of a Gaussian mechanism with sensitivity $G/\sqrt{\mu}$ and noise scale 1.

which is precisely the upper bound guaranteed by the theorem.

2 Generalization Error of Sampling

Many important and fundamental problems in machine learning, optimization and operations research are special cases of SCO, and ERM is a classic and widely-used approach to solve it, though their relationships are not well-understood. If one can solve the ERM problem optimally and get the exact optimal solution $x^{*}$ to minimizing $F(\cdot;\mathcal{D})$ (see Equation 3), then [SSSSS09] showed $x^{*}$ will also be a good solution to the SCO for strongly convex functions. But in most situations, solving ERM optimally costs too much or even impossible. Can we find a approximately good solution to ERM and hope that it is also a good solution for SCO? [Fel16] provides a negative answer and shows there is no good uniform convergence between $F(\cdot;\mathcal{D})$ and $\widehat{F}$, that is there always exists $x\in\mathcal{K}$ such that $|F(x;\mathcal{D})-\widehat{F}(x)|$ is large. This fact forces us to find approximate solution to ERM with very high accuracy, which makes the algorithms inefficient.

Prior works proposed a few interesting ways to overcome this difficulty, such as the uniform stability in [HRS16] and the iterative localization technique in [AFKT21]. Roughly speaking, uniform stability means that if running algorithms on neighboring datasets lead to similar output distributions, then the generalization error of the ERM algorithm is bounded. Thus a good solution to ERM obtained by a stable algorithm is also a good solution for SCO. [BFTT19] makes use of the stability of running SGD on smooth functions to get a tight bound on the population loss for DP-SCO.

Recall $F(x;\mathcal{D})$ and $\widehat{F}(x)$ are defined in Equation (3) and (5) respectively. Our result enriches the toolbox of bounding the generalization error and provides new insights for this problem.

Suppose $\{f_{i}\}$ is a family of $\mu$-strongly convex functions over $\mathcal{K}$ and $f_{i}-f_{i^{\prime}}$ is $G$-Lipschitz for any two functions $f_{i},f_{i^{\prime}}$ in the family. For any $k>0$ and suppose the $n$ samples in data set $\mathcal{D}$ are drawn i.i.d from the underlying distribution, then by sampling $x^{(sol)}$ from density $\propto e^{-kF(x^{(sol)};\mathcal{D})}$, the population loss satisfies

Considering two neighboring datasets $\mathcal{D}$ and $\mathcal{D}^{\prime}$, our result is based on bounding the Wasserstein distance between the distributions proportional to $e^{-kF(x;\mathcal{D})}$ and $e^{-kF(x;\mathcal{D}^{\prime})}$, which means the sampling scheme is stable and leads to the $\frac{G^{2}}{\mu n}$ term in generalization error. The other term $\frac{d}{k}$ is excess empirical loss of the sampling mechanism. One advantage of our result is that it works for both smooth and non-smooth functions. Moreover, we may choose the value $k$ carefully and get a solution with both optimal empirical loss and optimal population loss.

3 Non-smooth Sampling and DP Convex Optimization

Implementing the exponential mechanism involves sampling from a log-concave distribution. When the negative log-density function $F$ is smooth, i.e. the gradient of $F$ is Lipschitz, there are many efficient algorithms for this sampling tasks such as [Dal17, LSV18, MMW+21, CV19, DMM19, SL19, CDWY20, LST20]. For example, if $F=\frac{1}{n}\sum_{i=1}^{n}f_{i}$ and each $f_{i}$ is $1$-strongly convex with $\kappa$-Lipschitz gradient,For convenience, we used $f_{i}$ to denote the function $f(\cdot;s_{i})$ in this and Section 5. we can sample $x\sim\exp(-F(x))$ in $\widetilde{O}(n+\kappa\max(d,\sqrt{nd})\log(1/\delta))$ iterations with $\delta$ error in total variation distance and each iteration involves computing one $\nabla f_{i}(x)$ [LST21]. Note that this is nearly linear time when $n\gg\kappa^{2}d$ and the $\delta$ error in total variation distance can be translated to an extra $\delta$ error in the $(\varepsilon,\delta)$-DP guarantee.

Our result is based on the alternating sampler proposed in [LST21] and a new rejection sampling scheme.

Furthermore, each steps accesses only $O(1)$ many $f_{i}(x)$ and samples from $\exp(-\psi(x)-\frac{1}{2\eta}\|x-y\|^{2}_{2})$ for $O(1)$ many $y$ in expectation with $\eta=\Theta(G^{-2}/\log(T/\delta))$.

Preliminaries

A DP algorithm $\operatorname*{\mathcal{M}}$ usually satisfies a collection of $(\varepsilon,\delta)$-DP guarantees for each $\varepsilon$, i.e., for each $\varepsilon$ there exists some smallest $\delta$ for which $\operatorname*{\mathcal{M}}$ is $(\varepsilon,\delta)$-DP. By collecting all of them together, we can form the privacy curve or privacy profile which fully characterizes the privacy of a DP algorithm.

One can explicitly calculate the privacy curve of a Gaussian mechanism as

where $\Phi(\cdot)$ is the Gaussian cumulative distribution function (CDF) [BW18].

Given two (continuous) distributions $P,Q$, we define the trade-off functionTradeoff curves in [DRS19] are defined using type I and type II errors. The definition given here is equivalent to their definition for continuous distributions. $T(P\|Q):\to$ as

It is easy to compute explicitly the tradeoff function for Gaussian mechanism [DRS19],

$\delta(P\|Q)\leq\delta(P^{\prime}\|Q^{\prime})$ iff $T(P\|Q)\geq T(P^{\prime}\|Q^{\prime})$

2 Optimization

Here we collect some properties of functions which are useful for optimization and sampling.

3 Distribution Distance and Divergence

We present some distribution distances or divergences mentioned or used in this work.

[Rén61, Rényi Divergence] Suppose $1<\alpha<\infty$ and $\pi,\nu$ are measures with $\pi\ll\nu$. The Rényi divergence of order $\alpha$ between $\pi$ and $\nu$ is defined as

We follow the convention that $\frac{0}{0}=0$. Rényi Divergence of orders $\alpha=1,\infty$ are defined by continuity. For $\alpha=1$, the limit in Rényi Divergence equals to the Kullback-Leibler divergence of $\pi$ from $\nu$, which is defined as following:

The Kullback–Leibler divergence between probability measures $\pi$ and $\nu$ is defined by

where $\Gamma(\pi,\nu)$ is the set of all couplings of $\pi$ and $\nu$.

The total variation distance between two probability measures $\pi$ and $\nu$ on a sigma-algebra $\mathcal{F}$ of subsets of the sample space $\Omega$ is defined via

4 Isoperimetric Inequality for Strongly Log-concave Distributions

The cumulative distribution function (CDF) of one-dimensional standard Gaussian distribution will be denoted by $\Phi(x)=\Pr_{y\sim\mathcal{N}(0,1)}[y\leq x]$. The following Lemma relates the expanding property of log-concave measures with $\Phi$.

The property above implies the concentration of Lipschitz functions over log-concave measures.

Fix some $z\in$. Let $A=\{x\in\mathcal{K}:\alpha(x)\leq m(z)\}$, so $\pi(A)=z$. Let $A_{r}=\{x:d(x,A)\leq r\}.$ Since $\alpha$ is $G$-Lipschitz, $\alpha(x)\geq m(z)+r$ implies that $d(x,A)\geq r/G.$ Therefore $\left\{x:\alpha(x)\geq m(z)+r\right\}\subset\left\{x:d(x,A)\geq r/G\right\}=\overline{A_{r/G}}$ and so

We obtain the other inequality by applying the above inequality to $-\alpha(x).$ ∎

GDP of Regularized Exponential Mechanism

In this section, we prove our DP result (Theorem 2.1). The proof uses the isoperimetric inequality for strongly log-concave measures [Led99]. Intuitively, the privacy loss random variable will be $G$-Lipschitz under the hypothesis and isoperimetric inequality implies that any Lipschitz function will be as concentrated as a Gaussian with appropriate standard deviation. This allows us compare the privacy curve $\delta\left(P\;\middle\|\;Q\right)$ to that of a Gaussian mechanism. In our proof, it is actually more convenient to compare tradeoff curves ($T\left(P\;\middle\|\;Q\right)$) which are equivalent to privacy curves via convex duality (Proposition 3.3 and Theorem 2.1).

We finish by calculating the integrals that showed up in the proof.

As a corollary to Theorem 4.1, we can bound any divergence measure that decreases under post-processing such as Renyi divergence or KL divergence. In particular, this also implies Renyi Differential Privacy [Mir17] of our algorithm.

By Theorem 2.10 in [DRS19], if $T(P\|Q)\geq T(X\|Y)$, then there exists a randomized algorithm $M$ such that $M(X)=P$ and $M(Y)=Q$. Therefore for any divergence measure which decreases under post-processing we have,

Efficient Non-smooth Sampling

In this section, we will present an efficient sampling scheme for (non-smooth) functions to complement our main result first. Specifically, we study the following problem about sampling from a (non-smooth) log-concave distribution.

Our sampler is based on the alternating sampling algorithm in [LST21] (See algorithm 1). This algorithm reduces the problem of sampling from $\exp(-\widehat{F}(x))$ to sampling from $\exp(-\widehat{F}(x)-\frac{1}{2\eta}\|x-y\|^{2})$ for some fixed $\eta$ and for roughly $\frac{1}{\eta\mu}$ many different $y$. When the step size $\eta$ is very small, the later problem is easier because the distribution is almost like a Gaussian distribution. For our problem, we will pick the largest step size $\eta$ such that we can sample $\exp(-\widehat{F}(x)-\frac{1}{2\eta}\|x-y\|^{2})$ using only $\widetilde{O}(1)$ many steps.

Given a $\mu$-strongly convex function $F$ defined on $\mathcal{K}$ with an initial point $x_{0}$. Let the distance $D=\|x_{0}-x^{*}\|_{2}$ for any $x^{*}=\arg\min_{x\in\mathcal{K}}\widehat{F}(x)$. Suppose the step size $\eta\leq\frac{1}{\mu}$, the target accuracy $\delta>0$ and the number of step $T\geq\Theta(\frac{1}{\eta\mu}\log(\frac{d/\mu+D^{2}}{\eta\delta}))$. Then, Algorithm 1 returns a random point $x_{T}$ that has $\delta$ total variation distance to the distribution proportional to $\exp(-\widehat{F}(x))$.

Now, we show that Line 1 in Algorithm 1 can be implemented by a simple rejection sampling. The idea is to pick step size $\eta$ small enough such that $\widehat{F}(x)$ is essentially a constant function for a random $x\sim\mathcal{N}(y,\eta\cdot I_{d})$. The precise algorithm is given in Algorithm 2.

Let $\pi$ be the distribution proportional to $\exp(-\widehat{F}(x)-\frac{1}{2\eta}\|x-y\|_{2}^{2})$ and let $\mathcal{G}$ be the distribution proportional to $\exp(-\psi(x)-\frac{1}{2\eta}\|x-y\|^{2})$. Then, we have that

Let $\widetilde{\pi}$ be the distribution returns by Algorithm 2. Then, we have that

For the distribution $\widetilde{\pi}$ by the algorithm, we sample $x\sim\mathcal{G}$, then accept the sample if $u\leq\frac{1}{2}\rho$. Hence, we have

Since $u$ is uniform between and $1$, we have the result.

Finally, for the expectation of $\rho$, we note that

and that the probability that the loop pass step $\alpha$ is exactly $\frac{1}{\alpha!}$. Hence, we have

Taking expectation over $z$ gives the result. ∎

Now, we are already to prove our main result. This shows that if $\eta\ll G^{-2}$, then the algorithm indeed implements Line 1 correctly up to small error.

Let $\pi$ be the distribution given by $c\cdot\exp(-\widehat{F}(x)-\frac{1}{2\eta}\|x-y\|_{2}^{2})$ and $\widetilde{\pi}$ is the distribution outputted by the algorithm. By Lemma 5.3, we have

We split the $\rho$ into two terms $\rho_{\leq L}$ and $\rho_{>L}$. The first term $\rho_{\leq L}$ is the sum of all terms added to $\rho$ when $\alpha\leq L$ (including the initial term $1$). The second term $\rho_{>L}$ is the sum when $\alpha>L$. Hence, we have $\rho=\rho_{>L}+\rho_{\leq L}$ and hence

For the term $\rho_{>L}$, by a calculation similar to Lemma 5.3, we have

Denote a function $h_{x,z}(t):=\Pr_{i\in I}[|f_{i}(z)-f_{i}(x)|\geq t]$. Since each $f_{i}$ is $G$-Lipschitz, Lemma 5.4 shows that

By Markov inequality, for any $k>0$, we know

As $|f_{i}(z)-f_{i}(x)|\leq G\|x-z\|_{2}$, if $h_{x,z}(t)=\Pr_{i\in I}[|f_{i}(z)-f_{i}(x)|\geq t]\leq e^{-t^{2}/(16\eta G^{2})}$, we know

Hence, we have $\Pr(\Delta\geq k)\leq 6\exp(-k^{2}/(64G^{2}\eta))$ and

As for the term $\rho_{\leq L}$, we know that

Note that the term $\rho_{\leq L}$ involves only less than $\frac{L^{2}}{2}$ many $f_{i}(x)$ and $f_{i}(z)$. Lemma 5.4 shows that for any $i$, we have

Under the event $|f_{i}(x)-f_{i}(z)|\leq\frac{1}{3}2^{k}$ for all $i$ appears in $\rho_{\leq L}$, we have

Therefore, we have $\Pr(|\rho_{\leq L}|>2^{kL})\leq L^{2}\exp(-\frac{4^{k}}{32\eta G^{2}})$ and

Picking $\eta\leq 2^{-8}G^{-2}L^{-1}$, we have that

It remains to bound the term $\Pr[\rho\notin]\cdot 2^{L}$. We know the probability the algorithm enters the $(L+1)$-th phase is at most $\frac{1}{L!}\leq\frac{2}{2^{L}}$. Hence we know $\Pr[\rho\notin]\leq\frac{2}{2^{L}}+\Pr[\rho_{\leq L}\notin]$. Similarly, by Gaussian Concentration and union bound, we have

Under the event that $|f_{i}(x)-f_{i}(z)|\leq 1/2$ for all $i$ appears in $\rho_{\leq L}$, we have

Combining Theorem 5.2 and Lemma 5.5, we have the following result:

Furthermore, each steps accesses only $O(1)$ many $f_{i}(x)$ in expectation and samples from $\exp(-\psi(x)-\frac{1}{2\eta}\|x-y\|^{2}_{2})$ for $O(1)$ many $y$ with $\eta=\Theta(G^{-2}/\log(T/\delta))$.

DP Convex Optimization

In this section we present our results about DP-ERM and DP-SCO.

In this subsection, we state our result for the DP-ERM problem (3). Briefly speaking, our main result (Theorem 2.1) shows that sampling from $\exp(-kF(x;\mathcal{D}))$ for some appropriately chosen $k$ is $(\varepsilon,\delta)$-DP and achieves the optimal empirical risk in (4). Our sampling scheme in Section 5 provides an efficient implementation. We start with the following lemma which shows the utility guarantee for the sampling mechanism.

This is first shown by [KV06] for any linear function $F$, and [BST14] extends it to any convex function $F$ with a slightly worse constant.

The excess empirical risk is bounded by $\frac{d}{k}+\frac{\mu D^{2}}{2}$. Moreover, if $\{f(\cdot,s)\}_{s\in\mathcal{D}}$ are already $\mu$-strongly convex, then sampling $x^{(priv)}$ with probability proportional to $\exp(-kF(x;\mathcal{D}))$ is $(\varepsilon,\delta(\varepsilon))$-differentially private where

The excess empirical risk is bounded by $\frac{d}{k}$.

The privacy guarantee follows directly from our main result Theorem 2.1, and the bound on excess empirical loss can be proved by Lemma 6.1. ∎

Before we state the implementation results on DP-ERM, we need the following technical lemma:

For any constants $1/2>\delta>0$ and $\varepsilon>0$, if $|s|\leq\sqrt{2\log(1/(2\delta))+2\varepsilon}-\sqrt{2\log(1/(2\delta))}$, one has

Without loss of generality, we assume $s\geq 0$ and want to find an appropriate value of $s$ such that $\Phi\left(-\frac{\varepsilon}{s}+\frac{s}{2}\right)\leq\delta$. Denote $t\stackrel{{\scriptstyle{\text{def}}}}{{=}}\Phi^{-1}(1-\delta)$ and since $1-\Phi(t)\leq\frac{1}{2}\exp(-t^{2}/2)$ for $t>0$, we know that $t\leq\sqrt{2\log(1/(2\delta))}$. It is equivalent to solve the equation $\frac{\varepsilon}{s}-\frac{s}{2}\geq t$, which is equivalent to $0\leq s\leq\sqrt{t^{2}+2\varepsilon}-t$. Note that $\sqrt{t^{2}+2\varepsilon}-t$ decreases as $t$ increases, which implies that we can set $s\leq\sqrt{2\log(1/(2\delta))+2\varepsilon}-\sqrt{2\log(1/(2\delta))}$. ∎

Combining the sampling scheme (Theorem 5.6) and our analysis on DP-ERM, we can get the efficient implementation results on DP-ERM directly.

With same assumptions in Theorem 6.2, and assume $f(\cdot;s)$ is $G$-Lipschitz over $\mathcal{K}$ for all $s$. For any constants $1/10>\delta>0$ and $\varepsilon>0$, there is an efficient sampler to solve DP-ERM which has the following guarantees:

The scheme is $(\varepsilon,\delta)$-differentially private;

The expected excess empirical loss is bounded by $\frac{GD\sqrt{d}}{n(\sqrt{\log(1/\delta)+\varepsilon}-\sqrt{\log(1/\delta)})}$. In particular, if $\varepsilon<1/10$, the expected excess empirical loss is bounded by $\frac{2GD\sqrt{d\log(1/\delta)}}{\varepsilon n}.$ If $\varepsilon\geq\log(1/\delta)$, the expected excess empirical loss is bounded by $O(\frac{GD\sqrt{d}}{n\sqrt{\varepsilon}})$.

queries to the values on $f(x;s)$ in expectation and takes the same number of samples from some Gaussian restricted to the convex set $\mathcal{K}$.

By Lemma 6.3, we can set $s=\sqrt{2\log(3/(4\delta))+2\varepsilon}-\sqrt{2\log(3/(4\delta))}$ to make $\delta\left(\mathcal{N}(0,1)\;\middle\|\;\mathcal{N}(s,1)\right)\leq 2\delta/3$. For our setting, Theorem 6.2 shows that we have $s=\frac{G\sqrt{k}}{n\sqrt{\mu}}$ and hence we can take

Putting it into the excess empirical loss bound of $\frac{d}{k}+\frac{\mu D^{2}}{2}$ and setting $\mu=\frac{G\sqrt{d}}{nD\left(\sqrt{\log(3/(4\delta))+\varepsilon}-\sqrt{\log(3/(4\delta))}\right)}$, we get the result on the empirical loss.

Particularly, consider the case when $\varepsilon<1/10$. We know the excess empirical loss is bounded by $\frac{GD\sqrt{d}}{n(\sqrt{\log(3/(4\delta))+\varepsilon}-\sqrt{\log(3/(4\delta))})}$. Note that $1+\frac{x}{2}-\frac{x^{2}}{8}\leq\sqrt{1+x}\leq 1+\frac{x}{2}$ for $x\geq 0$. Under the assumption that $\delta,\varepsilon\in(0,\frac{1}{10})$, we know $\frac{GD\sqrt{d}}{n(\sqrt{\log(3/(4\delta))+\varepsilon}-\sqrt{\log(3/(4\delta))})}\leq\frac{2GD\sqrt{d\log(4/(5\delta))}}{n\varepsilon}$. The case when $\varepsilon\geq\log(1/\delta)$ also follows similarly.

To make it algorithmic, we apply Theorem 5.6 with the accuracy on the total variation distance to be $\min\{\delta/3,\frac{1}{cn^{c}\varepsilon}\}$ for some large enough constant $c$. This leads to $(\varepsilon,\delta)$-DP and an extra empirical loss and hence we use $\log(1/\delta)$ rather than $\log(3/(4\delta))$ or $\log(4/(5\delta))$ in the final loss term.

The running time follows from Theorem 5.6. ∎

2 DP-SCO and Generalization Error

As mentioned before, one can reduce the DP-SCO (5) to DP-ERM (3) by the iterative localization technique proposed by [FKT20]. But this method forces us to design different algorithms for DP-ERM and DP-SCO, and may lead to a large constant in the final loss. In this section, we show that the exponential mechanism can achieve both the optimal empirical risk for DP-ERM and the optimal population loss for DP-SCO by simply changing the parameters. The bound on the generalization error works beyond differential privacy and can be useful for other (non-private) optimization settings.

The proof will make use of one famous inequality: Talagrand transportation inequality. Recall for two probability distributions $\nu_{1},\nu_{2}$, the Wasserstein distance is equivalently defined as

where the infimum is over all couplings $\Gamma$ of $\nu_{1},\nu_{2}.$

To prove our main result on bounding the generalization error of sampling mechanism, we need the following lemma.

For any learning algorithm $\mathcal{A}$ and dataset $\mathcal{D}=\{s_{1},\cdots,s_{n}\}$ drawn i.i.d from the underlying distribution $\mathcal{P}$, let $\mathcal{D}^{\prime}$ be a neighboring dataset formed by replacing a random element of $\mathcal{D}$ with a freshly sampled $s^{\prime}\sim\mathcal{P}$. If $\mathcal{A}(\mathcal{D})$ is the output of $\mathcal{A}$ with $\mathcal{D}$, then

Now we begin to state and prove our main result on the generalization error.

Suppose $\{f(\cdot,s)\}$ is a family $\mu$-strongly convex functions over $\mathcal{K}$ such that $f(x;s)-f(x;s^{\prime})$ is $G$-Lipschitz for all $s,s^{\prime}$. For any $k>0$ and dataset $\mathcal{D}=\{s_{1},s_{2},\cdots,s_{n}\}$ drawn i.i.d from the underlying distribution $\mathcal{P}$, let $\mathcal{D}^{\prime}$ be a neighboring dataset formed by replacing a random element of $\mathcal{D}$ with a freshly sampled $s^{\prime}\sim\mathcal{P}$,

If we sample our solution from density $\pi_{\mathcal{D}}(x)\propto e^{-kF(x;\mathcal{D})}$, we can bound the excess population loss as:

We form a neighboring data set $\mathcal{D}^{\prime}$ by replacing a random element of $\mathcal{D}$ by a freshly sampled $s^{\prime}\sim\mathcal{P}.$ Let $\pi_{\mathcal{D}}\propto e^{-kF(x;\mathcal{D})}$ and $\pi_{\mathcal{D}^{\prime}}\propto e^{-kF(x;\mathcal{D}^{\prime})}$. By Corollary 4.3, we have

By the assumptions, we know both $F(x;\mathcal{D})$ and $F(x;\mathcal{D}^{\prime})$ are $\mu$-strongly convex and by Theorem 6.5, we have

By Lemma 6.6 and properties of Wasserstein distance, we have

where the last inequality follows from Lemma 6.1. ∎

With the bounds on generalization error, we can get our first result on DP-SCO.

If users in the data-set $\mathcal{D}$ are drawn i.i.d. from the underlying distribution $\mathcal{P}$, the excess population loss is bounded by $\frac{G}{n\mu}+\frac{d}{k}+\frac{\mu D^{2}}{2}$. Moreover, if $\{f(\cdot;s)\}_{s\in\mathcal{D}}$ are already $\mu$-strongly convex, then sampling $x^{(priv)}$ with probability proportional to $\exp(-kF(x;\mathcal{D}))$ is $(\varepsilon,\delta(\varepsilon))$-differentially private where

The excess population loss is bounded by $\frac{G}{n\mu}+\frac{d}{k}$.

The first part about privacy is a restatement of our result on DP-ERM (Theorem 6.4). The excess population loss (See Equation (6)) follows from the bound on generalization error (Theorem 6.7) and utility guarantee (Lemma 6.1). ∎

We give an implementation result of our DP-SCO result.

With same assumptions in Theorem 6.8, and assume $f(\cdot;s)$ is $G$-Lipschitz over $\mathcal{K}$ for all $s$. For $0<\delta<\frac{1}{10}$ and $0<\varepsilon<\frac{1}{10}$, there is an efficient algorithm to solve DP-SCO which has the following guarantees:

The algorithm is $(\varepsilon,\delta)$-differentially private;

The expected population loss is bounded by

where $c>0$ is an arbitrary constant to be chosen.

queries of the values of $f(\cdot,s_{i})$ in expectation and takes the same number of samples from some Gaussian restricted to the convex set $\mathcal{K}$.

As for the non-typical case when $\varepsilon\geq 1/10$, one can use the bound in Theorem 6.4 and the bound on generalization error (Theorem 6.7) . Particularly, one can achieve expected population loss $O\left(GD\left(\frac{\sqrt{d}/n}{\sqrt{\log(1/\delta)+\varepsilon}-\sqrt{\log(1/\delta)}}+\frac{1}{\sqrt{n}}\right)\right)$.

By Theorem 6.8, sampling from $\exp(-k(F(x;\mathcal{D})+\mu\|x\|_{2}^{2}/2))$ when $k\leq\frac{\varepsilon^{2}n^{2}\mu}{2G^{2}\log(3/(4\delta))}$ is $(\varepsilon,2\delta/3)$-DP. Besides, we can set $k=\frac{\mu}{G^{2}}\min\{\frac{\varepsilon^{2}n^{2}}{2\log(3/(4\delta))},2nd\}$ for arbitrarily large constant $c>0$ to make the mechanism $(\varepsilon,2\delta/3)$-differentially private, achieving tight population loss and decrease the running time. Then the population loss is upper bounded by

By setting $\mu=\frac{G}{D}\sqrt{2(\frac{2\log(3/(4\delta))d}{\varepsilon^{2}n^{2}}+\frac{1}{2n})}$, the population loss is upper bounded by

To make it algorithmic, we also apply Theorem 5.6 with the accuracy on the total variation distance to be $\min\{\delta/3,\frac{1}{cn^{c}}\}$ for some large enough constant $c$. This leads to an extra empirical loss and hence we use $\log(1/\delta)$ rather than $\log(3/(4\delta))$ in the final loss term. The runtime follows from Theorem 5.6. ∎

Information-theoretic Lower Bound for DP-SCO

In this section, we prove an information-theoretic lower bound for the query complexity required for DP-SCO (with value queries), which matches (up to some logarithmic terms) the query complexity achieved by our algorithm (in Theorem 6.9). Our proof is similar to the previous works like [ACCD12, DJWW15] with some modifications.

Therefore $G=\sqrt{d(\delta^{2}+\sigma^{2})}.$

where $\widehat{v}$ denotes the output of any algorithm mapping from the observation $(Y^{1},\cdots,Y^{k})$ to $\{-1,1\}^{d}$, and the probability is taken over the distribution of the underlying $v$, the observation $(Y^{1},\cdots,Y^{k})$ and any additional randomness in the algorithm.

Now we continue our proof of the lower bound. We will make use of the property of the Bayes risk.

Suppose that $v$ is uniformly sampled from $\mathcal{V}=\{-1,1\}^{d}$, then any estimate $\widehat{v}$ obeys

where the first inequality follows from the definition of Bayes risk $B_{j}$, the second inequality follows by Lemma 7.3 and the last inequality follows by the Cauchy-Schwartz inequality.

To complete the proof, it suffices to show that

Assuming Equation (18) first, which will be established later. Then we know that

We will complete the proof of Lemma 7.4 by showing the following bounded total variation distance.

The convexity of the KL divergence suggests that

As we are considering linear functions, without loss of generality we can assume $\langle Q_{i}^{j},Q_{i}^{j^{\prime}}\rangle=0$ for each $i$ and any $j\neq j^{\prime}$, and $\|Q_{i}^{t}\|_{2}\in\{0,1\}$ for any $i$ and $t$. We name this assumption Orthogonal Query. Roughly speaking, for any algorithm, we can modify it to satisfy the Orthogonal Query. Whenever the algorithm wants to query some point, we can use Gram–Schmidt process to query another point and satisfy Orthogonal Query, and recover the function value at the original point queried by the algorithm.

By the chain-rule of KL-divergence, if we define $P_{-1,j,v^{\prime}}(Y^{t}\mid Y^{[t-1]})$ to be the distribution of $t$th observation $Y^{t}$ conditional on $v^{\prime}$, $v_{j}=-1$ and $Y^{[t-1]}$, then we have

Fix $Y^{[t-1]}$ such that $Y^{[t-1]}=y$. Since the algorithm is deterministic and $(X^{t},S^{t})$ is fixed given $Y^{[t-1]}$. Let $S^{t}=s_{i}$ so $X^{t}=Q_{i}^{t}$.

where $Q_{i}^{t}(j)$ is the $j$-th coordinate of $Q_{i}^{t}$. Summing over the terms, one has

where the last line follows from the fact that for each $t$,$\sum_{i=1}^{n}\|Q_{i}^{t}\|_{2}^{2}=\sum_{i=1}^{n}\sum_{j=1}^{d}(Q_{i}^{t}(j))^{2}=1$ as we only query one user for $t$-th step.

Having Lemma 7.4, we can complete the proof of Theorem 7.1.

of Theorem 7.1. As discussed before, we know

where the last line follows from Lemma 7.4. We now set $\delta=\frac{\sigma\sqrt{d}}{2\sqrt{k}}$ and $\sigma=\frac{G}{\sqrt{d+d^{2}/4k}}$, so that $d(\sigma^{2}+\delta^{2})=G^{2}$. Hence one has

Note that Theorem 7.1 almost gives us what we want, except that the Lipschitz constant of the functions in the hard distribution is bounded only on average by $G$. To get distributions over $G$-Lipschitz functions, we just condition on the bad event not happening.

In particularly, for some constant $c$, we know

By the concentration of spherical Gaussians, we know if $s\sim\mathcal{N}(\delta v,\sigma^{2}I_{d})$, then

We can choose the constant $c$ large enough, such that $\Pr[\max_{s_{i}\in\mathcal{D}}\|s_{i}\|_{2}\leq cG\sqrt{1+\log(nd)/d}]\geq 1-1/\operatorname{poly}(nd)$, which implies

If we use the distributions conditioned on $\max_{s_{i}\in\mathcal{D}}\|s_{i}\|_{2}\leq cG\sqrt{1+\log(nd)/d}$ rather than the Gaussians, and scale the constant to satisfy the assumption on Lipschitz continuity, we can prove the statement. Particularly, let $G^{\prime}=cG(\sqrt{1+\log(nd)/d})$. If the algorithm can only make $k=O\left(\min\{\frac{\varepsilon^{2}n^{2}}{\log(1/\delta)},nd\}\right)$ observations, we know

which proves the lower bound claimed in the Corollary statement. ∎

where $\widehat{F}_{v}^{*}=\min_{x\in\mathcal{K}}\widehat{F}_{v}(x)$ and $\widehat{x}_{k}\in\mathcal{K}$ is the output of $\mathcal{A}$.

Suppose we have a sampling algorithm that takes $k$ queries. We use it to sample from $x^{(sol)}$ proportional to $p(x):=\exp(-\widehat{F}_{v}(x)-\frac{\mu}{2}\|x\|^{2})$ on $\mathcal{K}$ with total variation distance $\eta\leq\min(1/2,\sqrt{d\mu/G^{2}})$.

where the last term involving $\eta$ is due to the total variation distance between $x^{(sol)}$ and $p$. Setting $D=\sqrt{d/\mu}$ and using the diameter of $\mathcal{K}$ is $D$ and $\eta\leq\min(1/2,\sqrt{d\mu/G^{2}})$, we have

Note that we set $D=\sqrt{d/\mu}$. Comparing with (19), we have

and hence $k=\Omega(G^{2}/\mu)$. If $G^{2}/\mu\geq\exp(d)$, we have

and hence $k=\Omega(\frac{G^{2}d/\mu}{\log(G^{2}/\mu)})$. If $G^{2}/\mu\leq d$, we can construct our function only on the first $O(G^{2}/\mu)$ dimensions to get a lower bound $k=\Omega(G^{2}/\mu).$ Combining all cases gives the result. ∎

References