Differentially Private Generalized Linear Models Revisited

{theorem}

[RS15] Let $K>0$ and $S\in\cZ^{n}$. Let $q_{1},...,q_{K}$ be functions s.t. for any adjacent datasets $S,S^{\prime}$ it holds that $|q_{j}(S)-q_{j}(S^{\prime})|\leq\gamma_{j}:\forall j\in[K]$. There exists an Algorithm, $\gem$, such that when given sensitivity-score pairs $(\gamma_{1},q_{1}(S)),...,(\gamma_{N},q_{N}(S))$, privacy parameter $\epsilon>0$ and confidence parameter $\beta>0$, outputs $j\in[N]$ such that with probability at least $1-\beta$ satisfies $q_{j}(S)\leq\min\limits_{j\in[N]}\bc{q_{j}(S)+\frac{4\gamma_{j}\log{N/\beta}}{\epsilon}}$.

Note that by assumptions on $\cA$, the process of generating $w_{1},...,w_{K}$ is $(\epsilon/2,\delta/2)-DP$. Furthermore, by Assumption 1 with probability at least $\delta/2$ the sensitivity values passed to $\gem$ bound sensitivity. Thus by the privacy guarantees of $\gem$ and composition we have that the entire algorithm is $(\epsilon,\delta)$-DP.

We now prove accuracy. In order to do so, we first prove that with high probability every $\tilde{L}_{j}$ is an upper bound on the true population loss of $w_{j}$. Specifically, define $\tau_{j}=\frac{\Delta(B_{j})\log{4K/\beta}}{n}+\sqrt{\frac{4\ybound^{2}\log{4K/\beta}}{n}}$ (i.e. the term added to each $L(w_{j};S_{2})$ in Algorithm 1). Note it suffices to prove

$$\mathbb{P}\left[\exists j\in[K]:|L(w_{j};S_{2})-L(w_{j};\cD)|\geq\tau_{j}\right]\leq\frac{\beta}{2}.$$

(1)

Fix some $j\in[K]$. Note that the non-negativity of the loss implies that $\ell(w_{B}^{*};(x,y)^{2})\geq 0$. The excess risk assumption then implies that $\ex{(x,y)\sim\cD}{\ell(w_{j};(x,y))^{2}}\leq 4\ybound^{2}$, which in turn bounds the variance. Further, with probability at least $1-\frac{\beta}{4K}$ it holds that for all $(x,y)\in S_{2}$ that $\ell(w,(x,y))\leq\Delta_{0}+\Delta(B)$. Thus by Bernstein’s inequality we have

$$\mathbb{P}\left[|L(w;S_{2})-L(w;\cD)|\geq t\right]\leq\exp{-\frac{t^{2}n^{2}}{\Delta(B_{j})tn+4n\ybound^{2}}}+\frac{\beta}{4K}$$

Thus it suffices to set $t=\frac{\Delta(B_{j})\log{4K/\beta}}{n}+\sqrt{\frac{4\ybound^{2}\log{4K/\beta}}{n}}$ to ensure $\mathbb{P}\left[|L(w;S_{2})-L(w;\cD)|\geq t\right]\leq\frac{\beta}{2K}$. Taking a union bound over all $j\in K$ establishes \eqrefeq:ploss-est-bound. We now condition on this event for the rest of the proof.

Now consider the case where $j^{*}\neq 0$ and $\mnorm\leq 2^{K}$. Note that the unconstrained minimizer $w^{*}$ is the constrained minimizer with respect to any $\ball{r}$ for $r\geq\norm{w^{*}}$. With this in mind, let $j^{\prime}=\min\limits_{j\in[K]}\bc{j:w^{*}\in\ball{2^{j}}}$ (i.e. the index of the smallest ball containing $w^{*}$). In the following we condition on the event that $\forall j\in[K],j\geq j^{\prime}$, the parameter vector $w_{j}$ satisfies excess population risk at most $\err(2^{j})$. We note by Assumption 1 that this (in addition to the event given in \eqrefeq:ploss-est-bound) happens with probability at least $1-\frac{3\beta}{4}$. By the guarantees of $\gem$, with probability at least $1-\beta$ we (additionally) have {align*} L(w_j^*;\cD) ≤L(w_j^*;S_2) + τ_j^* &≤min_j∈[K]\bcL(w_j;S_2) + τ_j + 4Δ(Bj)log4K/βnϵ
≤L(w_j’;S_2) + τ_j’ + 4Δ(Bj’)log4K/βnϵ
≤L(w_j’;\cD) + 2τ_j’ + 4Δ(Bj’)log4K/βnϵ.

Since $2^{j^{\prime}}\leq\max\bc{2\mnorm,1}$ we have {align*} L(w_j^*;\cD) - L(w^*;\cD) &≤L(w_j’;\cD)- L(w^*;\cD) + 2τ_j’ + 4Δ(Bj’)log4K/βnϵ
≤\err(2max\bc\mnorm,1) + 2τ_j’ + 4Δ(max\bc2\mnorm,1)log4K/βnϵ
≤\err(2max\bc\mnorm,1) + 4\ybound2log4K/βn + 5Δ(max\bc2\mnorm,1)log4K/βnϵ where the second inequality comes from the fact the assumption that $\mnorm\leq\ybound^{2}$. Now note that by the assumption that $\err(2^{K})\geq\ybound^{2}$, whenever $\mnorm\geq 2^{K}$ it holds that $\ybound^{2}\leq\err(\mnorm)$. However since the sensitivity-score pair $(0,\ybound^{2})$ is passed to $\gem$, the excess risk of the output is bounded by at most $\ybound^{2}$ by the guarantees of $\gem$).

Let $\out$ denote the output of the regularized output perturbation method with boosting and noise and privacy parameters $\epsilon^{\prime}=\frac{\epsilon}{K}$ and $\delta^{\prime}=\frac{\delta}{K}$. We have by Theorem LABEL:thm:boosted-smooth-output-perturbation that with probability at least $1-\frac{\beta}{4K}$ that {align*} L(\out;\cD) - L(w^*;\cD) &= ~O(HB\norm\cX\norm\cY + \norm\cY2n +\br\brHB\norm\cX4/3\norm\cY2/3+ \brHB\norm\cX2(nϵ)2/3
+ \br\ybound2+ HB2\xbound2nϵ + \br\ybound+HB\xboundn ). Note that this is no smaller than $\ybound^{2}$ when $B=\Omega\br{\max\bc{\frac{\ybound\sqrt{n\epsilon}}{\xbound\sqrt{H}},\frac{\ybound^{2}(n\epsilon)^{2/3}}{\sqrt{H}\xbound^{2}}}}$, and thus it suffices to set $K=\Theta\br{\log{\max\bc{\frac{\ybound\sqrt{n}}{\xbound\sqrt{H}},\frac{\ybound^{2}(n\epsilon)^{2/3}}{\sqrt{H}\xbound^{2}}}}}$ to satisfy the condition of the Theorem statement.

Let $\sigma_{j}$ denote the level noise used for when the guess for $\mnorm$ is $B_{j}$. To establish Assumption 1, by Lemma D.4 we have that this assumption is satisfies with $\Delta(B)=\ybound^{2}+H\xbound^{2}\sigma_{j}^{2}\log{K/\min\bc{\beta,\delta}})+HB^{2}\xbound^{2}$. In particular, we note for the setting of $\sigma_{j}$ implied by Theorem LABEL:thm:boosted-smooth-output-perturbation and the setting of $K$ we have for all $j\in[K]$ that $H\xbound^{2}\sigma_{j}^{2}=\tilde{O}(\ybound^{2})$. Thus $\Delta(B)=\tilde{O}\br{\ybound^{2}+HB^{2}\xbound^{2}}$. The result then follows from Theorem 1.

{lemma}

Algorithm LABEL:alg:noisySGD run with constraint set $\ball{B}$ satisfies Assumption 1 with $\Delta(B)=\ybound^{2}+HB^{2}\xbound^{2}$. The proof is straightforward using Lemma LABEL:lem:smooth_loss_bound (provided in the Appendix). For the output perturbation method, we can obtain similar guarantees. Here however, we must account for the fact that the output may not lie in the constraint set. We also remark that the JL-based method (Algorithm LABEL:alg:jl-constrained-dp-erm) can also enjoy this same bound. However, in this case one must apply the norm adaptation method to the intermediate vector $\tilde{w}$, as $\Phi^{\top}\tilde{w}$ may have large norm. {lemma} Algorithm LABEL:alg:constrained-reg-erm-output-perturbation run with parameter $B$ and $\sigma$ satisfies Assumption 1 with $\Delta(B)=\ybound^{2}+H\xbound^{2}\sigma^{2}\log{K/\delta})+HB^{2}\xbound^{2}$ {proof} Note that since $S$ and $S^{\prime}$ differ in only one point, it suffices to show that for any $(x,y),(x^{\prime},y^{\prime})$ that $\ell(\out;(x,y))\leq\ybound^{2}+HB^{2}\xbound^{2}+H\xbound^{2}\sigma^{2}\log{K/\delta}$ and similarly for $\ell(\out,(x^{\prime},y^{\prime}))$. Let $w\in\ball{B}$ and let $\out=w+b$ where $b\sim\cN(0,\mathbb{I}_{d}\sigma^{2})$. We have by previous analysis $\ell(\out;(x,y))\leq\ybound^{2}+HB^{2}\xbound^{2}+H\ip{b}{x}^{2}$. Since $\ip{b}{x}$ is distributed as a zero mean Gaussian with variance at most $\xbound^{2}\sigma^{2}$, we have $\mathbb{P}[|\ip{b}{x}|\geq t]\leq\exp{\frac{-t^{2}}{\xbound^{2}\sigma^{2}}}.$ Setting $t=\xbound\sigma\log{K/\delta}$ we obtain $\mathbb{P}[|\ip{b}{x}|^{2}\geq\xbound^{2}\sigma^{2}\log{K/\delta}]\leq\delta/K$. Thus with probability at least $1-\delta/K$ it holds that $\ell(\out;(x,y))\leq\ybound^{2}+HB^{2}\xbound^{2}+H\xbound^{2}\sigma^{2}\log{K/\delta}$.