Convergence of PrivateGD in Strongly Convex Problems

Note that when $\rho\leq\sqrt{\log(1/\delta)}$, zCDP implies $(\epsilon,\delta)$-DP with $\rho\geq\frac{\epsilon^{2}}{8\log(1/\delta)}$. This means that as $T$ goes to $\infty$ and $\frac{\sigma^{2}}{T}$ stays a constant, the first term vanishes and second term matches the information-theoretic limit of differentially private learning under $(\epsilon,\delta)$-DP in the convex case and in the strongly convex case respectively.

When additional regularization with parameter $\lambda$, the utility we consider should still be considered in terms of $\mathcal{L}(\hat{\theta})-\mathcal{L}(\theta^{*})$. Let $\theta^{*}$ be any comparator satisfying $B>\|\theta^{*}\|$

	$\displaystyle\mathcal{L}(\hat{\theta})-\mathcal{L}(\theta^{*})$	$\displaystyle=J(\hat{\theta})-J_{\lambda}(\theta^{*}_{\lambda})+J_{\lambda}(\theta^{*}_{\lambda})-J(\theta^{*})+\frac{\lambda}{2}\|\theta^{*}-\theta_{\text{ref}}\|^{2}-\frac{\lambda}{2}\|\hat{\theta}-\theta_{\text{ref}}\|^{2}$
		$\displaystyle\leq J(\hat{\theta})-J_{\lambda}(\theta^{*}_{\lambda})+\frac{\lambda}{2}\|\theta^{*}-\theta_{\text{ref}}\|^{2}.$

Take expectation on both sides and substitute the bound with an initialization at $o$

$\displaystyle\mathbb{E}[\mathcal{L}(\hat{\theta})]-\mathcal{L}(\theta^{*})\leq\frac{4(nL+\lambda B)^{2}}{\mu T}+\frac{dL^{2}}{\mu\rho}+\frac{\lambda}{2}\|\theta^{*}-\theta_{\text{ref}}\|^{2}.$

In the case when $\mathcal{L}$ is not strongly convex, $\mu=\lambda$ we get

$$\frac{4(nL+\lambda B)^{2}}{\lambda T}+\frac{dL^{2}}{\lambda\rho}+\frac{\lambda}{2}\|\theta^{*}\|^{2}$$

when we choose $\lambda=\sqrt{\frac{\rho}{2\|\theta^{*}-\theta_{\text{ref}}\|dL^{2}}}$ we get

$$\mathbb{E}[\mathcal{L}(\hat{\theta})]-\mathcal{L}(\theta^{*})\leq\frac{4(nL+\lambda B)^{2}}{\lambda T}+\frac{\sqrt{d}L\|\theta^{*}-\theta_{\text{ref}}\|}{\sqrt{2\rho}}.$$

Again, when $T\rightarrow+\infty$, the first term vanishes and the second term is the information-theoretic limit for general convex problems. when $\theta_{\text{ref}}=0$. However, if we choose $\theta_{\text{ref}}$ according to the public data, then if the public data gives either a good initialization or a good reference point for the strongly convex regularization, then it provably improves the utility under the same privacy parameter $\rho$.

Assume the public data with $m$ samples are drawn from the same distribution of the private data. Assume that the (population risk)

$$R(\theta)=\mathbb{E}_{(x,y)\sim\mathcal{D}}[\ell(\theta^{*},(x,y))]$$

is $c$-strongly convex at $\theta^{*}$ for some constant $c$. Note that this does not require strong convexity everywhere and it also does not require strong convexity to hold on the empirical risk objective function finite dataset.

Moreover, assume that the $\mathbb{E}_{(x,y)\sim\mathcal{D}}[\|\nabla\ell(\theta,(x,y))\|^{2}]\leq G^{2}$. Then running one-pass SGD which returns $\theta_{\text{ref}}$ to be the weighted average satisfies that

$$\mathbb{E}[\|\theta_{\text{ref}}-\theta^{*}\|^{2}]\leq\frac{4G^{2}}{c^{2}m}.$$

This result together with the bound above, implies that

$$\mathbb{E}[\mathbb{E}[\mathcal{L}(\hat{\theta})]-\mathcal{L}(\theta^{*})]\leq\frac{4\sqrt{d}LG^{2}}{c^{2}m\sqrt{2\rho}}$$

The outer expectation is taken over the distribution of the public data, which implies a learning bound of the form (by dividing both sides by $n$ and adjust for the difference between empirical risk and population risks)

$$\mathbb{E}[R(\hat{\theta})]-R^{*}\leq\frac{4\sqrt{d}LG^{2}}{c^{2}mn\sqrt{2\rho}}+\text{GeneralizationGap}(n).$$

where the GeneralizationGap(n) is difference between the empirical and population risk of $\hat{\theta}$, typically obtained via a uniform convergence argument. The generalization gap is required even for the non-private learning and is between $O(\sqrt{1/n})$ and $O(1/n)$ when we qualify for a condition for fast rate (e.g., strong convexity, low-noise, etc). Note that the above bound extra factor due to privacy is on the order of $O(\frac{\sqrt{d}}{mn\sqrt{\rho}})$ comparing to $O(\frac{\sqrt{d}}{n\sqrt{\rho}})$ when we have private data only.

For the generalized linear model case, all dimension $d$ above can be replaced with $\mathrm{rand}(X)$ where $X\in\mathbb{R}^{n\times d}$ is the data matrix and $\leq\min\{d,n\}$. The arguments follow from (song21evading) by leveraging that the gradients are all within the row-space of $X$ and it suffices to consider.

This observation is quite useful to us because the linearization of a deep model is often very high-dimensional and $d\geq n$. In this case, this is saying that we can chooses the learning rate as a function of $n$ instead.

It was established in (chen2020understanding) that the gradient clipping is known to have the effect of Huberization of the loss function in the GLM cases. The convergence to the optimal solution of a modified objective function is guaranteed if we fix the clipping parameter. Our approach on the adaptive clipping has the effect of selecting the hyperparameter adaptively in an homotopy style algorithm, which shows further empirical benefits.

The theory on the convergence of SGD is well-studied under various regimes. The exposition above is based on the analysis of (ghadimi2013stochastic) (for the convex cases) and (lacoste2012simpler) (for the strongly convex cases). song21evading provided the first analysis of this algorithm in the general convex case with dependence on the $\min{n,d}$, and first illustrated the interpretation of gradient clipping as a Huberization of the link function. chen2020understanding provided an alternative explanation of the gradient clipping in terms of how it effectively modify the data distribution. To the best of our knowledge, we are the first that states these results for GLM that depends on $\min{n,d}$ in the strongly convex case, as well as showing that the use of public data gives provably smaller sample complexity comparing to the standard private learning setting.