Private Stochastic Convex Optimization: Optimal Rates in Linear Time

Introduction

Placing a differential privacy constraint usually comes at a cost in terms of utility. In this case, it is measured by the excess population loss of the solution, for a given number of samples $n$. Additionally, runtime efficiency of an optimization method is crucial for modern applications on large high-dimensional datasets, and this is the primary reason for the popularity of stochastic gradient descent-based methods. This motivates the problem of understanding the trade-offs between computational efficiency, and excess population loss in the presence of privacy constraints.

The first work to address the population loss for SCO with differential privacy (DP-SCO) is who give a bound of order $\max\{d^{1/4}\big/\sqrt{n},\varepsilon^{-1}\sqrt{d}\big/n\}$ [5, Sec. F]. For clarity, in the introduction we focus on the dependence on $d$, $n$ and $\varepsilon$ for $(\varepsilon,\delta)$-DP, suppressing the dependence on $\delta$ and on parameters of the loss function such as Lipschitz constant and the diameter of $\mathcal{K}$. For the most relevant case where $d=\Theta(n)$ and $\varepsilon=\Theta(1)$, this results in a bound of $\Omega(n^{-1/4})$ on excess population loss. More recent work of Bassily et al. demonstrates the existence of an efficient algorithm that achieves a bound of $O(1\big/\sqrt{n}+\varepsilon^{-1}\sqrt{d}\big/n)$, which is also shown to be tight. Notably, this bound is comparable to the non-private SCO bound of $O(1/\sqrt{n})$ as long as $d/\varepsilon^{2}=O(n)$. Their algorithm is based on solving the ERM via noisy stochastic gradient descent (SGD) but requires relatively large batch sizes for the privacy analysis. As a result, their algorithm uses $O(\min\{n^{3/2},n^{5/2}\big/d\})$ gradient computations. This is substantially less efficient than the optimal non-private algorithms for the problem which require only $n$ gradient evaluations. They also give a near-linear-time algorithm under an additional strong assumption that the Hessian of each loss function is rank-1 over the entire domain.

Along the other axis, several of the aforementioned works on private ERM are geared towards finding computationally efficient algorithms for the problem, often at the cost of worse utility bounds.

We describe two new techniques for deriving linear-time algorithms that achieve the (asymptotically) optimal bounds on the excess population loss. Thus our results show that for the problem of Stochastic Convex Optimization, under mild assumptions, a privacy constraint come for free. For $d\leq n$, there is no overhead in terms of either excess loss or the computational efficiency. When $d\geq n$, the excess loss provably increases, but the optimal bounds can still be achieved without any computational overhead. Unlike the earlier algorithm that solves the ERM and relies on uniform stability of the algorithm to ensure generalization, our algorithms directly optimize the population loss.

Formally, our algorithms satisfy the following bounds:

Our guarantees are stated in terms of Rényi differential privacy (RDP) for all orders $\alpha$ and can also be equivalently stated as 0-mean $(\rho^{2}/2)$-concentrated differential privacy (or $(\rho^{2}/2)$-zCDP) . Standard properties of RDP/zCDP imply that our algorithms satisfy $(2\rho\sqrt{\ln(1/\delta)},\delta)$-DP for all $\delta>0$ as long as $\rho\leq\sqrt{\ln(1/\delta)}$. Thus for $(\varepsilon,\delta)$-DP our bound is

matching the tight bound in . We now overview the key ideas and tools used in these techniques.

Our first algorithm relies on a one-pass noisy SGD with gradually growing batch sizes. Namely, at step $t$ out of $T$ the batch size is proportional to $1/\sqrt{T-t+1}$. We refer to SGD with such schedule of batch size as Snowball-SGD. The analysis of this algorithm relies on two tools. The first one is privacy amplification by iteration . This privacy amplification technique ensures that for the purposes of analyzing the privacy guarantees of a point $x_{i}$ used at step $t$ one can effectively treat all the noise added at subsequent steps as also added to the gradient of the loss at $x_{i}$. A direct application of this technique to noisy SGD results in different privacy guarantees for different points and, as a result, the points used in the last $o(n)$ steps will not have sufficient privacy guarantees. However, we show that by increasing the batch size in those steps we can achieve the optimal privacy guarantees for all the points.

A limitation of relying on this analysis technique is that the privacy guarantees apply only to the algorithm that outputs the last iterate of SGD. In contrast, the optimization guarantees usually apply to the average of all the iterates (see Section 6 for an example in which the privacy guarantees for the average iterate are much worse than those for the last iterate). Thus the second tool we rely on is the recent work of Jain et al. showing that, for an appropriate choice of step sizes in SGD, the last iterate has the (asymptotically) optimal excess population loss. (Without the special step sizes the last iterate has excess loss larger by a $\log n$ factor .) See Section 3 for additional details of this approach.

It is natural to ask if the last iterate analysis is really needed or if the average iterate itself be proven to have good privacy properties. In Section 6, we address this question and show that in general the average iterate can be very non-private even when the noise is sufficient to give strong privacy guarantees for the last iterate.

Our second approach is based on an (implicit) reduction to an easier problem of localizing an approximate minimizer of the population loss. Specifically, the reduction is to a differentially private algorithm that given a point $w_{0}$ that is within distance $R$ from the minimizer of the loss, finds a point $\hat{w}$ that is within distance $R/2$ from a point that approximately minimizes the loss. By iteratively using such a localizing algorithm with appropriately chosen parameters, a sufficiently good solution will be found after a logarithmic number of applications of the algorithm. Each application operates on its own subset of the dataset and thus this reduction preserves the privacy guarantees of the localizing algorithm.

A simple way to implement a localization algorithm is to start with non-private SCO algorithm whose output has optimal $L_{2}$ sensitivity. Namely, solutions produced by the algorithm on any two datasets that differ in one point are at distance on the order of $R/\sqrt{n}$ (this property is also referred to as uniform stability in the parameter space). Given such an algorithm one can simply add Gaussian noise to the output. This is a standard approach to differentially private optimization referred to as output perturbation . However, for the purposes of localization, we only need to be within $R/2$ of the solution output by the algorithm and so we can add much more noise than in the standard applications, thereby getting substantially better privacy guarantees.

We note that in order to ensure that the addition of Gaussian noise localizes the solution with probability at least $1-\alpha$ we would need to increase the noise variance by an additional $\ln(1/\alpha)$ factor making the resulting rate suboptimal by a logarithmic factor. Thus, instead we rely on the fact that for algorithms based on SGD the bound on excess loss can be stated in terms of the second moment of the distance to the optimum.

We can now plug in existing uniformly stable algorithms for SCO. Specifically, it is known that under mild smoothness assumptions, one-pass SGD finds a solution that both achieves optimal bounds on the excess population loss and stability . This leads to the second algorithm satisfying the guarantees in Theorem 1.1. See Section 4 for additional details of this approach.

Both of our algorithms require essentially the same and relatively mild smoothness assumption: namely that the smoothness parameter is at most $\sqrt{n}$ (ignoring the scaling with $D,L$ and for simplicity focusing on the case when $d=O(n)$ and $\varepsilon=1$). Bassily et al. show that optimal rates are still achievable even without this smoothness assumption. Their algorithm for the problem relies on using the prox operator instead of gradient steps which is known to be equivalent to gradient steps on the loss function smoothed via the Moreau-Yosida envelope. Unfortunately, computing the prox step with sufficient accuracy requires many gradient computations and very high accuracy is needed due to potential error accumulation. As a result, implementing the algorithm in requires $O(n^{4.5})$ gradient computations.

Our reduction based technique gives an alternative and simpler way to deal with the non-smooth case. One can simply plug in a uniformly stable algorithms for SCO in the non-smooth case from . This algorithm relies on solving ERM with an added strongly convex $\lambda\|w\|_{2}^{2}$ term. In this case the analysis of the accuracy to which the ERM needs to be solved is straightforward. However achieving such accuracy with high probability requires $O(n^{2})$ gradient computations thus giving an $O(n^{2})$ algorithm for the non-smooth version of our problem. Improving this running time is a natural avenue for future work. We remark that finding a faster uniformly stable (non-private) SCO for the non-smooth case is an interesting problem in itself.

When the loss functions are strongly convex, the optimal (non-private) excess population loss is of the order of $O(1/n)$ rather than $O(1/\sqrt{n})$. The excess loss due to privacy is known to be $\Omega(d/\varepsilon^{2}n^{2})$. The best known upper bounds for this problem due to are $O(\sqrt{d}/\varepsilon n)$. We show a nearly linear time algorithm that has excess loss matching the known lower bounds. As in the convex case, when $d\leq n$, privacy has virtually no additional cost in terms of utility or efficiency. We describe several approaches that achieve these bounds (up to, possibly, a logarithmic overhead). The first approach is based on a folklore reduction to the convex case which can then be used with any of our algorithms for the (non-strongly-convex) convex case. We also give two direct algorithms that rely on a new analysis of SGD with fixed step-size in the strongly convex case. The first algorithm uses iterative localization approach and the second one relies on privacy amplification by iteration.

Preliminaries

In order to argue differential privacy we place certain assumptions on the loss function. To that end, we need the following two definitions of Lipschitz continuity and smoothness.

2 Probability Measures

Given two distributions $\mu$ and $\nu$ on a Banach space $(\mathcal{Z},\|\cdot\|)$, one can define several notions of distance between them. The primary notion of distance we consider is Rényi divergence:

Let $1<\alpha<\infty$ and $\mu,\nu$ be measures with $\mu\ll\nu$. The Rényi divergence of order $\alpha$ between $\mu$ and $\nu$ is defined as

Here we follow the convention that $\frac{0}{0}=0$. If $\mu\not\ll\nu$, we define the Rényi divergence to be $\infty$. Rényi divergence of orders $\alpha=1,\infty$ is defined by continuity.

3 (Rényi ) Differential Privacy

The notion of differential privacy is by now a de facto standard for statistical data privacy .

A randomized algorithm $\mathcal{A}$ is $(\varepsilon,\delta)$-differentially private ($(\varepsilon,\delta)$-DP) if, for all datasets $S$ and $S^{\prime}$ that differ in a single data element and for all events $\mathcal{O}$ in the output space of $\mathcal{A}$, we have

Starting with Concentrated Differential Privacy , definitions that allow more fine-grained control of the privacy loss random variable have proven useful. The notions of zCDP , Moments Accountant , and Rényi differential privacy (RDP) capture versions of this definition. This approach improves on traditional $(\varepsilon,\delta)$-DP accounting in numerous settings, often leading to significantly tighter privacy bounds as well as being applicable when the traditional approach fails .

For $1\leq\alpha\leq\infty$ and $\varepsilon\geq 0$, a randomized algorithm $\mathcal{A}$ is $(\alpha,\varepsilon)$-Rényi differentially private, or $(\alpha,\varepsilon)$-RDP if for all neighboring data sets $S$ and $S^{\prime}$ we have

The following two lemmas allow translating Rényi differential privacy to $(\varepsilon,\delta)$-differential privacy, and give a composition rule for RDP.

If $\mathcal{A}$ satisfies $(\alpha,\varepsilon)$-Rényi differential privacy, then for all $\delta\in(0,1)$ it also satisfies $\big(\varepsilon+\frac{\ln(1/\delta)}{\alpha-1},\delta\big)$-DP. In particular, if $\mathcal{A}$ satisfies $(\alpha,\alpha\rho^{2}/2)$-RDP for every $\alpha\geq 1$ then for all $\delta\in(0,1)$ it also satisfies $(\rho^{2}/2+\rho\sqrt{2\ln(1/\delta)},\delta)$-DP.

The standard composition rule for Rényi differential privacy, when the outputs of all algorithms are revealed, takes the following form.

If $\mathcal{A}_{1},\dots,\mathcal{A}_{k}$ are randomized algorithms satisfying, respectively, $(\alpha,\varepsilon_{1})$-RDP,…,$(\alpha,\varepsilon_{k})$-RDP, then their composition defined as $(\mathcal{A}_{1}(S),\dots,\mathcal{A}_{k}(S))$ is $(\alpha,\varepsilon_{1}+\dots+\varepsilon_{k})$-RDP. Moreover, the $i$’th algorithm can be chosen on the basis of the outputs of $\mathcal{A}_{1},\dots,\mathcal{A}_{i-1}$.

4 Contractive Noisy Iteration

We start by recalling the definition of a contraction.

For a Banach space $(\mathcal{Z},\|\cdot\|)$, a function $\psi\colon\mathcal{Z}\to\mathcal{Z}$ is said to be contractive if it is 1-Lipschitz. Namely, for all $x,y\in\mathcal{Z}$,

A canonical example of a contraction is projection onto a convex set in the Euclidean space.

The map $\Pi_{\mathcal{K}}$ is a contraction.

Another example of a contraction, which will be important in our work, is a gradient descent step for a smooth convex function. The following is a standard result in convex optimization .

is contractive as long as $\eta\leq 2/\beta$.

We will be interested in a class of iterative stochastic processes where we alternate between adding noise and applying some contractive map.

Given an initial random state $X_{0}\in\mathcal{Z}$, a sequence of contractive functions $\psi_{t}\colon\mathcal{Z}\to\mathcal{Z}$, and a sequence of noise distributions $\{\mathcal{D}_{t}\}$, we define the Contractive Noisy Iteration (CNI) by the following update rule:

where $Z_{t+1}$ is drawn independently from $\mathcal{D}_{t+1}$. For brevity, we will denote the random variable output by this process after $T$ steps as $\mbox{CNI}_{T}(X_{0},\{\psi_{t}\},\{\mathcal{D}_{t}\})$.

As usual, we denote by $\mu\ast\nu$ the convolution of $\mu$ and $\nu$, that is the distribution of the sum $X+Y$ where we draw $X\sim\mu$ and $Y\sim\nu$ independently.

For a noise distribution $\mathcal{D}$ over a Banach space $(\mathcal{Z},\|\cdot\|)$ we measure the magnitude of noise by considering the function that for $a>0$, measures the largest Rényi divergence of order $\alpha$ between $\mathcal{D}$ and the same distribution $\mathcal{D}$ shifted by a vector of length at most $a$:

5 Privacy Amplification by Iteration

Let $X_{T}$ and $X^{\prime}_{T}$ denote the output of $\mbox{CNI}_{T}(X_{0},\{\psi_{t}\},\{\mathcal{D}_{t}\})$ and $\mbox{CNI}_{T}(X_{0},\{\psi^{\prime}_{t}\},\allowbreak\{\mathcal{D}_{t}\})$. Let $s_{t}\doteq\sup_{x}\|\psi_{t}(x)-\psi^{\prime}_{t}(x)\|$. Let $a_{1},\ldots,a_{T}$ be a sequence of reals and let $z_{t}\doteq\sum_{i\leq t}s_{i}-\sum_{i\leq t}a_{i}$. If $z_{t}\geq 0$ for all $t$, then

We now give a simple corollary of this general theorem for the case when the iterative processes differ in a single index and, in addition, the noise distribution with parameter $\sigma$ ensures that Rényi divergence for a shift of $a$ scales as $a^{2}/\sigma^{2}$. As discussed above, this is exactly the case for Gaussian distribution.

Let $X_{T}$ and $X^{\prime}_{T}$ denote the output of $\mbox{CNI}_{T}(X_{0},\{\psi_{t}\},\{\mathcal{D}_{t}\})$ and $\mbox{CNI}_{T}(X_{0},\{\psi^{\prime}_{t}\},\allowbreak\{\mathcal{D}_{t}\})$. Let $s_{i}\doteq\sup_{x}\|\psi_{i}(x)-\psi^{\prime}_{i}(x)\|$. Assume that there exists $t\in[T]$ such that for all $i\neq t$, $s_{i}=0$. For $\alpha\geq 1$ assume that there exists $\gamma$ such that for every $\zeta>0$ and $a\geq 0$, and $i\in[T]$, $R_{\alpha}(\mathcal{D}_{i},a)\leq\gamma\frac{a^{2}}{\sigma_{i}^{2}}$ for some $\sigma_{i}$. Then

We use Theorem 2.13 with $a_{i}=0$ for $i<t$ and $a_{i}=\frac{s_{t}\sigma_{i}^{2}}{\sum_{v=t}^{T}\sigma_{v}^{2}}$. The resulting bound we get

DP SCO via Privacy Amplification by Iteration

More formally, for this algorithm we prove the following privacy guarantees.

By our assumption, $f(w,x)$ is $L$-Lipschitz for every $x\in\mathcal{X}$ and $w\in\mathcal{K}$ and therefore

We can now apply Corollary 2.14 with $\gamma=\alpha/2$. Note that $s_{t}\leq\frac{2\eta_{t}L}{B_{t}}$ and thus we obtain that

Maximizing this expression over all indices $i\in[n]$ gives the claim. ∎

The important property of this analysis is that it allows for batch size to be used to improve the privacy guarantees. The specific batch size choice depends on the step sizes and noise rates. Next we describe the setting of these parameters that ensures convergence at the optimal rate.

2 Utility Guarantees for the Last Iterate of SGD

where $F^{*}\doteq\min_{w\in\mathcal{K}}F(w)$ and the expectation is taken over the randomness of $G$.

Further, Jain et al. show that the $\ln T$ factor can be eliminated by using faster decaying rates. Their step-size schedule is defined as follows.

where $F^{*}\doteq\min_{w\in\mathcal{K}}F(w)$ and the expectation is taken over the randomness of $G$.

3 Snowball-SGD

Finally we derive the privacy and utility guarantees for noisy SGD by calculating the batch sizes needed to ensure the privacy guarantees for the settings in Theorems 3.2 and 3.4. The sum of batch sizes in turn gives us the number of samples $n$ necessary to implement $T$ steps of these algorithms. The resulting batch sizes will be proportional to $\sqrt{d/(T-t+1)}$ and we refer to such batch size schedule as Snowball-SGD.

We first establish the privacy guarantees. By Theorem 3.1, all we need is to verify that for our choice of $\{B_{t}\},\sigma$ and $\eta$ we have for every $t\in[T]$,

where we used the fact that $\sum_{t\in[T]}\frac{1}{\sqrt{t}}\leq 2(\sqrt{T+1}-1)+1\leq 2\sqrt{T}$.

To establish the utility guarantees, we first note that for all $t\in[T]$,

This implies that for our choice of parameters PNSGD$(S,w_{0},\{B_{t}\},\{\eta\},\{\sigma\})$ can be seen as an execution PSGD$(G,w_{0},\{D/(L_{G}\sqrt{T})\})$ with stochastic gradient oracles with variance upper-bounded by $L_{G}^{2}=2L^{2}$. Plugging this value in Theorem 3.2 gives our bound on the utility of the algorithm. To obtain the bound in terms of $n$ we note that $n\leq T+\frac{4\sqrt{dT}}{\rho}$, implies that $T\geq\frac{n^{2}}{16d/\rho^{2}+4n}$ and thus

Next, we give a differentially private version of the step-size schedule from .

The utility guarantees for this algorithm follow from the same argument as in the proof of Theorem 3.5 together with Theorem 3.4. As before, by Theorem 3.1, all we need to establish the privacy guarantees is to verify that for our choice of $\{B_{t}\},\sigma$ and $\{\eta_{t}\}$ we have for every $t\in[T]$,

We first observe that for $t=T$ we have that

For $t\in[T-1]$, let $i$ be such that $T_{i}<t\leq T_{i+1}$. Then we note that for $c=D/(\sqrt{2}L)$

Plugging this and eq. (2) into eq.(1) we obtain that the privacy condition holds.

As in the proof of Theorem 3.6, we obtain that

and thus $T\geq\frac{n^{2}}{192d/\rho^{2}+4n}$. This means that

implying the claimed bound on utility in terms of $n$. ∎

As a corollary we get the proof of our main claim.

Localization-Based Algorithms

In this section, we describe the Iterative Localization framework, and give two instantiations of it. Our localization algorithm will be based on adding Gaussian noise to an algorithm whose output has low $L_{2}$-sensitivity (also referred to as uniform stability of the parameter). We first briefly recall the relevant definitions and the resulting privacy guarantees.

The well-known property of the Gaussian mechanism is that it can convert any algorithm with bounded $L_{2}$-sensitivity to a differentially private one.

Suppose we have an algorithm $\mathcal{A}$ that given a point $w\in B(w^{\ast},D)$ and a sequence of samples from $F$, outputs a $w^{\prime}\in B(w^{\ast},D/4)$. We will want this $\mathcal{A}$ to have small sensitivity, and small suboptimality, both of which scale, say, linearly with $D$. Given such an $\mathcal{A}$, we can iteratively invoke it with geometrically decreasing $D$, adding noise at the end of each phase to ensure privacy. Crucially, once the diameter bound $D$ becomes small enough, the noise added is small enough that the suboptimality due the added noise is negligible. This would allow us to incur only a logarithmic overhead in terms of sample complexity, while ensuring privacy and good utility bounds.

We next describe two instantiations of this Iterative Localization framework. To get better bounds, we only bound the second moment of the distance \mathopen{{\mathchoice{\hbox{\displaystyle\left\lVert\vbox to0.0pt{}\right.}}{\hbox{\textstyle\left\lVert\vbox to0.0pt{}\right.}}{\hbox{\scriptstyle\left\lVert\vbox to0.0pt{}\right.}}{\hbox{\scriptscriptstyle\left\lVert\vbox to0.0pt{}\right.}}}}{w^{\prime}-w^{\ast}}\mathclose{{\mathchoice{\hbox{\displaystyle\left\rVert\vbox to0.0pt{}\right.}}{\hbox{\textstyle\left\rVert\vbox to0.0pt{}\right.}}{\hbox{\scriptstyle\left\rVert\vbox to0.0pt{}\right.}}{\hbox{\scriptscriptstyle\left\rVert\vbox to0.0pt{}\right.}}}}, instead of requiring that \mathopen{{\mathchoice{\hbox{\displaystyle\left\lVert\vbox to0.0pt{}\right.}}{\hbox{\textstyle\left\lVert\vbox to0.0pt{}\right.}}{\hbox{\scriptstyle\left\lVert\vbox to0.0pt{}\right.}}{\hbox{\scriptscriptstyle\left\lVert\vbox to0.0pt{}\right.}}}}{w^{\prime}-w^{\ast}}\mathclose{{\mathchoice{\hbox{\displaystyle\left\rVert\vbox to0.0pt{}\right.}}{\hbox{\textstyle\left\rVert\vbox to0.0pt{}\right.}}{\hbox{\scriptstyle\left\rVert\vbox to0.0pt{}\right.}}{\hbox{\scriptscriptstyle\left\rVert\vbox to0.0pt{}\right.}}}} is uniformly bounded. The first instantiation uses SGD as algorithm $\mathcal{A}$, and applies to convex functions. The sensitivity bound here comes from bounding the step sizes and holds under mild smoothness assumptions. The second instantiation will apply to arbitrary convex functions, and optimizes a regularized objective to ensure a sensitivity bound.

Our algorithm relies on the fact that SGD on sufficiently smooth loss functions has low $L_{2}$-sensitivity .

Each iterate of one-pass online projected gradient descent with fixed step size $\eta$ over a sequence of $\beta$-smooth $L$-Lipschitz convex functions has $L_{2}$-sensitivity of at most $2L\eta$ as long as $\eta\leq 2/\beta$. In particular, the same applies to the average of all the iterates.

Assume that \mathopen{{\mathchoice{\hbox{\displaystyle\left\lVert\vbox to0.0pt{}\right.}}{\hbox{\textstyle\left\lVert\vbox to0.0pt{}\right.}}{\hbox{\scriptstyle\left\lVert\vbox to0.0pt{}\right.}}{\hbox{\scriptscriptstyle\left\lVert\vbox to0.0pt{}\right.}}}}{w_{0}-w^{\ast}}\mathclose{{\mathchoice{\hbox{\displaystyle\left\rVert\vbox to0.0pt{}\right.}}{\hbox{\textstyle\left\rVert\vbox to0.0pt{}\right.}}{\hbox{\scriptstyle\left\rVert\vbox to0.0pt{}\right.}}{\hbox{\scriptscriptstyle\left\rVert\vbox to0.0pt{}\right.}}}}_{2}\leq D (this is the case, for example, when $\mathcal{K}$ has diameter at most $D$), and set

Then for the output of Algorithm 2, we have

To prove the theorem, we first provide utility and privacy guarantees for each individual phase of the algorithm.

Assume that $\eta_{i}\leq 2/\beta$. Then for any $\alpha\geq 1$, the output $w_{i}$ of phase $i$ in Algorithm 2 satisfies $(\alpha,\alpha\rho^{2}/2)$-RDP, and for any $w\in\mathcal{K}$,

The privacy guarantee follows from 4.2 together with the fact that PSGD (when viewed as a deterministic mapping from a data set to a final iterate) with step size $\eta_{i}\leq 2/\beta$ has $L_{2}$-sensitivity bounded by $2L\eta_{i}$ (this is a consequence of 4.3). The utility guarantee follows from standard convergence bounds for PSGD (e.g., Lemma 7 of ). ∎

Denote $\overline{w}_{0}=w^{\ast}$ and $\xi_{0}=w_{0}-w^{\ast}$; by assumption, \mathopen{{\mathchoice{\hbox{\displaystyle\left\lVert\vbox to0.0pt{}\right.}}{\hbox{\textstyle\left\lVert\vbox to0.0pt{}\right.}}{\hbox{\scriptstyle\left\lVert\vbox to0.0pt{}\right.}}{\hbox{\scriptscriptstyle\left\lVert\vbox to0.0pt{}\right.}}}}{\xi_{0}}\mathclose{{\mathchoice{\hbox{\displaystyle\left\rVert\vbox to0.0pt{}\right.}}{\hbox{\textstyle\left\rVert\vbox to0.0pt{}\right.}}{\hbox{\scriptstyle\left\rVert\vbox to0.0pt{}\right.}}{\hbox{\scriptscriptstyle\left\rVert\vbox to0.0pt{}\right.}}}}_{2}\leq D. Using 4.5, the total error of the algorithm can be bounded by

Recall that by definition $\eta\leq(D/L)\cdot(\rho/\sqrt{d})$, so that for all $i\geq 0$,

2 Non-Smooth DP-SCO: Phased ERM

In this section, we demonstrate that the general approach based on localization can also be applied to the non-smooth case. We only require $f(\cdot,x)$ to be convex and $L$-Lipschitz for any $x\in\mathcal{X}$. Our algorithm is similar to the one in the previous section, except that we replace the PSGD subroutine in step 3 of the algorithm with a regularized ERM computation. The $L_{2}$ regularization in this case is the standard technique for ensuring low sensitivity that we require. In addition, low-sensitivity ensures uniform stability and thus generalization of the solution to the population. To get a more efficient algorithm, we use an approximate optimizer instead of an exact one. The suboptimality of this optimization should be small enough that the sensitivity of the resulting algorithm can still be controlled. To solve the regularized problem, we employ SGD that ensures the suboptimality bound, and hence the sensitivity bound, with high probability. To allow for a small failure probability of this approach, we will only give $(\varepsilon,\delta)$-DP guarantees for the algorithm. We will use the following standard variant of 4.2:

We first prove the relevant properties of the regularized ERM algorithm.

The output $w_{i}$ of phase $i$ of Algorithm 3 satisfies $(\varepsilon,2\delta)$-DP, and for any $w\in\mathcal{K}$,

The objective $F_{i}$ minimized in phase $i$ is $L$-Lipschitz and $\lambda_{i}$-strongly convex for $\lambda_{i}=2/(\eta_{i}n_{i})$; denote by $\overline{w}_{i}\in\mathcal{K}$ its minimizer. From the results in we know that the minimizer $\overline{w}_{i}$ has $L_{2}$ sensitivity bounded by $4L/(\lambda_{i}n_{i})=2L\eta_{i}$, and furthermore,

The proof of the following result is identical to that 4.4, with 4.7 replacing 4.5.

Assume that \mathopen{{\mathchoice{\hbox{\displaystyle\left\lVert\vbox to0.0pt{}\right.}}{\hbox{\textstyle\left\lVert\vbox to0.0pt{}\right.}}{\hbox{\scriptstyle\left\lVert\vbox to0.0pt{}\right.}}{\hbox{\scriptscriptstyle\left\lVert\vbox to0.0pt{}\right.}}}}{w_{0}-w^{\ast}}\mathclose{{\mathchoice{\hbox{\displaystyle\left\rVert\vbox to0.0pt{}\right.}}{\hbox{\textstyle\left\rVert\vbox to0.0pt{}\right.}}{\hbox{\scriptstyle\left\rVert\vbox to0.0pt{}\right.}}{\hbox{\scriptscriptstyle\left\rVert\vbox to0.0pt{}\right.}}}}_{2}\leq D, and set

Then for the output of Algorithm 2, we have

Further, a version of this algorithm can be implemented with $O(n^{2}\sqrt{\ln(1/\delta)})$ stochastic gradient computations.

The Strongly Convex Case

Suppose that the population loss of interest $F$ is $\lambda$-strongly convex and $L$-Lipschitz over the domain $\mathcal{K}$. In this case, the optimal statistical rate is $O(L^{2}\big/\lambda n)$ , and the private ERM can be optimized with an error of $\smash{\widetilde{O}}(dL^{2}\big/\varepsilon^{2}\lambda n^{2})$. The best known bound for Private Stochastic Convex Optimization for this case is due to who give an upper bound of $\smash{\widetilde{O}}(L^{2}\sqrt{d}\big/\lambda\varepsilon n)$. As in the convex case, we show that the optimal rate is in fact the larger of the two lower bounds, and is attained by a linear-time algorithm.

We first show that an asymtotically-optimal algorithm and linear-time for this case can be obtained via a folklore reduction to the convex case (see, e.g., for a similar instantiation of this reduction). We then give two new algorithms for the strongly convex case: one based on the iterative localization and the other based on privacy amplification by iteration. The algorithms are simpler and require weaker assumption on the condition number than the reduction-based approach. Both of the new algorithms rely on a new analysis of SGD with fixed step-size in the strongly convex case.

Assume a private stochastic (non-strongly) convex optimization algorithm $\mathcal{A}$ with the following utility guarantee when initialized at $w_{0}\in\mathcal{K}$:

for some universal constant $c\geq 1$, where $D>0$ is such that \mathopen{{\mathchoice{\hbox{\displaystyle\left\lVert\vbox to0.0pt{}\right.}}{\hbox{\textstyle\left\lVert\vbox to0.0pt{}\right.}}{\hbox{\scriptstyle\left\lVert\vbox to0.0pt{}\right.}}{\hbox{\scriptscriptstyle\left\lVert\vbox to0.0pt{}\right.}}}}{w_{0}-w^{\ast}}\mathclose{{\mathchoice{\hbox{\displaystyle\left\rVert\vbox to0.0pt{}\right.}}{\hbox{\textstyle\left\rVert\vbox to0.0pt{}\right.}}{\hbox{\scriptstyle\left\rVert\vbox to0.0pt{}\right.}}{\hbox{\scriptscriptstyle\left\rVert\vbox to0.0pt{}\right.}}}}_{2}\leq D. (E.g., this can be one of Algorithms 1, 2 and 3 under their respective assumptions and settings of $\rho$.) Consider the following algorithm: starting from a given $w_{0}\in\mathcal{K}$, repeat the private optimization algorithm $\mathcal{A}$ for $k=\lceil\log\log{n}\rceil$ times, where run $i=1,\ldots,k$ is initialized at the output of the previous phase and is run for $n_{i}=2^{i-2}n/\log{n}$ iterations. We prove the following:

The algorithm described above is private (with the same privacy parameters as of $\mathcal{A}$), and using no more than $n$ samples outputs a solution whose expected population loss is at most

This is the optimal rate under strong convexity assumptions. Further, under $\beta$-smoothness assumptions and when the condition number is $\beta/\lambda=O(\max\{\sqrt{n/\log{n}},\sqrt{d}/\rho\})$, the inner stochastic convex optimization problems are sufficiently smooth so that we can use Algorithm 2 as the basic private optimization algorithm (with step sizes $\eta_{i}$ that satisfy $\beta\leq 1/\eta_{i}$, as $n_{i}=\Omega(n/\log{n})$ for all $i$ in the reduction) and get a linear time algorithm for stochastic strongly convex optimization. Without any smoothness assumptions, we can invoke the reduction with Algorithm 3 and get a quadratic-time algorithm with the optimal rate. In Section 5.2 we show how the constraint on the condition number can be relaxed all the way up to $\beta/\lambda=O(n/\log n)$ via a more careful argument that utilizes our iterative localization framework directly.

Let us denote by $E_{i}$ the expression $c^{2}(2L^{2}/\lambda)\mathopen{}\big(\frac{1}{\sqrt{n_{i}}}+\frac{\sqrt{d}}{\rho n_{i}}\big)^{2}$. Since $E_{i}/E_{i+1}\leq 4$ (as $n_{i+1}/n_{i}=2$ by construction), the above inequality can be rearranged as

This implies that for $k>\log\log(\Delta_{1}/E_{1})$, it holds that $\Delta_{k}\leq 2E_{k}$. Observing that $\Delta_{1}\leq 2L^{2}\lambda$ (due to strong convexity) and $E_{1}\geq 2L^{2}\lambda/n$, we see that after $k=\lceil\log\log{n}\rceil$ phases, we hold a solution with error

2 Direct Algorithms for the Strongly Convex Case

Now we show a linear time algorithm for the $\lambda$-strongly convex case, as long as the condition number $\kappa=\beta/\lambda$ is bounded by $O(n/\log n)$. Towards this goal, we first analyze a fixed step-size algorithm for stochastic strongly convex optimization. In typical variants of strongly convex (stochastic) gradient descent, one employs a decaying step-size schedule of the form $\eta_{t}=1/(\lambda t)$ for obtaining the optimal convergence rate. Here we show that the same rate (up to a logarithmic factor) can be attained by a fixed step-size algorithm, which is useful for our privacy analysis.

Consider PSGD iterations with a fixed step size $\eta$. Suppose that $\eta\leq\frac{1}{2\lambda}$ and define weights $\gamma_{t}=(1-\eta\lambda)^{-t}$ for $t=1,\ldots,T$. Then for any $w$,

In particular, setting $\eta=2\log(T)/\lambda T$ ensures that the average iterate $\overline{w}_{T}=(\sum_{t=1}^{T}\gamma_{t})^{-1}\sum_{t=1}^{T}\gamma_{t}w_{t}$ has, for $T>1$,

Observe that for ensuring $\eta\leq 1/\beta$, it is sufficient that $T=\Omega(\kappa\log{\kappa})$ for $\kappa=\beta/\lambda$.

Denote the gradient vector used on iteration $t$ by $g_{t}$. Following the standard SGD analysis, we can obtain

for all $t$, and taking expectations of the above yields

On the other hand, the $\lambda$-strong convexity of $F$ implies

Combining inequalities and summing over $t=1,\ldots,T$ with coefficients $\gamma_{1},\ldots,\gamma_{T}$, we obtain

By plugging in our choice of $\eta$ and applying Jensen’s inequality on the left-hand side, we establish the first bound. The second bound is obtained by plugging in $\eta=\log(T)/\lambda T$ and bounding \mathopen{{\mathchoice{\hbox{\displaystyle\left\lVert\vbox to0.0pt{}\right.}}{\hbox{\textstyle\left\lVert\vbox to0.0pt{}\right.}}{\hbox{\scriptstyle\left\lVert\vbox to0.0pt{}\right.}}{\hbox{\scriptscriptstyle\left\lVert\vbox to0.0pt{}\right.}}}}{w_{1}-w^{\ast}}\mathclose{{\mathchoice{\hbox{\displaystyle\left\rVert\vbox to0.0pt{}\right.}}{\hbox{\textstyle\left\rVert\vbox to0.0pt{}\right.}}{\hbox{\scriptstyle\left\rVert\vbox to0.0pt{}\right.}}{\hbox{\scriptscriptstyle\left\rVert\vbox to0.0pt{}\right.}}}}^{2}\leq 4L^{2}/\lambda^{2} (using strong convexity). ∎

2.2 Direct Algorithm via Iterative Localization

We can now analyze a variant of Algorithm 2 for the strongly convex case, with appropriately chosen parameters.

Assume that in Algorithm 2, we set $k=\ln\ln n$, $n_{i}=n/k$, $\eta_{i}=2^{-2^{i}}\eta$ and $\eta=\frac{4ck\ln n}{\lambda n}$. Then for the output of Algorithm 2, we have

provided that $\kappa\leq\frac{n}{k\ln n}$.

Denote $\overline{w}_{0}=w^{\ast}$ and $\xi_{0}=w_{0}-w^{\ast}$; by strong convexity, \mathopen{{\mathchoice{\hbox{\displaystyle\left\lVert\vbox to0.0pt{}\right.}}{\hbox{\textstyle\left\lVert\vbox to0.0pt{}\right.}}{\hbox{\scriptstyle\left\lVert\vbox to0.0pt{}\right.}}{\hbox{\scriptscriptstyle\left\lVert\vbox to0.0pt{}\right.}}}}{\xi_{0}}\mathclose{{\mathchoice{\hbox{\displaystyle\left\rVert\vbox to0.0pt{}\right.}}{\hbox{\textstyle\left\rVert\vbox to0.0pt{}\right.}}{\hbox{\scriptstyle\left\rVert\vbox to0.0pt{}\right.}}{\hbox{\scriptscriptstyle\left\rVert\vbox to0.0pt{}\right.}}}}_{2}\leq 2L^{2}/\lambda^{2}. Using 5.2, the total error of the algorithm can be bounded by

Here we have used the fact that $\exp(a)-1\geq\exp(a)/2$ for $a\geq 1$ and $\exp(a)-1\geq a$. Continuing from above,

For $c\geq 2$, it is easy to check that each of the terms is bounded by $\max\mathopen{}\big\{O(\frac{kL^{2}\ln n}{\lambda n}),O(\frac{dk^{2}L^{2}\ln n}{\lambda\rho^{2}n^{2}})\big\}$. The claim follows. ∎

2.3 Direct Algorithm via Privacy Amplification by Iteration

We next derive a variant of Snowball-SGD for the strongly convex case.

The privacy proof is identical to that of 3.5. For the utility analysis, we prove the following bound for the last iterate of our fixed step-size algorithm:

We next relate $S_{k-1}$ and $S_{k}$. Let $\Gamma_{k}=\sum_{t=T-k}^{T}\gamma_{t}$. Note that

Dividing by $\Gamma_{k-1}$ and using Eq. 6, we conclude

The claimed utility bound follows from the fact that, as in the proof of 3.5, the expected second moment of the gradient goes up from $L^{2}$ to $2L^{2}$. The final bound follows by noting that

No Privacy Amplification by Averaged Iteration

A common technique in convex optimization is to use iterate averaging. A plausible conjecture is that the average of the iterates enjoys privacy properties similar to the last iterate. Indeed, in a Contractive Noisy Iteration with uniform noise, the privacy for the last iterate and that for the average iterate are within constant factors of each other when the contractive map is the identity.

Here we show that this does not hold true in general. Consider the contractive noise process defined by contractive maps:

Here $k$ is a parameter we will set appropriately. Thus the contractive noise process is

The sum of $X_{t}$’s thus is easily seen to be distributed as:

Simplifying, the average iterate is distributed as:

For $\sigma=\frac{1}{\sqrt{T}}$, where the final iterate has $(\alpha,O(\alpha))$-RDP, this simplifies to

Whereas for $k=1$ and for $k=T$, this amount of noise gives $(\alpha,O(\alpha))$-RDP, for intermediate values of $k$, e.g., $k\in[T^{\frac{1}{3}},T^{\frac{2}{3}}]$, the effective amount of noise is not sufficient to mask $X_{0}$.

Here $k$ is a parameter to be set appropriately, and $b\in\{-1,1\}$. Suppose that step size is $\eta=\frac{1}{\sqrt{T}}$ and the noise scale at each step is $\frac{1}{\sqrt{T}}$. If the noise added to the gradient at step $t$ is $\xi_{t}$, then one can verify that the average iterate is

In other words, the average iterate is distributed as

This is the same behaviour as in the counterexample above. Thus the average is not $(\alpha,O(\alpha))-RDP$. This example can be easily modified to handle suffix averaging over a $\Omega(T)$-sized suffix.

References