When Does Differentially Private Learning
Not Suffer in High Dimensions?

Before stating the theoretical problem of interest, we recall the basic concepts of Lipschitz continuity, convexity, and approximate differential privacy.

In this work, we study both differentially private empirical risk minimization (DP-ERM) for convex objectives and differentially private stochastic convex optimization (DP-SCO).

In DP-ERM for convex objectives, we are given a dataset $\mathcal{D}=\{s_{j}\}_{j\in[n]}\in\mathcal{S}^{n}$ of $n$ examples. Each per-example loss $f(\cdot;s_{j})$ is convex over the convex body $\mathcal{K}\subseteq\mathbb{R}^{d}$ and $G$-Lipschitz. We aim to design an $(\varepsilon,\delta)$-DP algorithm that returns a solution $x^{\text{priv}}$ which approximately minimizes the empirical risk $F(x;\mathcal{D}):=\frac{1}{n}\sum_{s_{j}\in\mathcal{D}}f(x;s_{j})$. The term $\mathbb{E}_{x^{\text{priv}}}\left[F(x^{\text{priv}};\mathcal{D})-\min_{x\in\mathcal{K}}F(x;\mathcal{D})\right]$ is referred to as the excess empirical risk.

In DP-SCO, we assume the per-example loss $f(\cdot;s)$ is convex and $G$-Lipschitz for all $s\in\mathcal{S}$, and we are given $n$ examples drawn i.i.d. from some (unknown) distribution $\mathcal{P}$. The goal is to design an $(\varepsilon,\delta)$-DP algorithm which approximately minimizes the population risk $F(x;\mathcal{P}):=\operatorname*{\mathbb{E}}_{s\sim\mathcal{P}}[f(x;s)]$. The term $\mathbb{E}_{x^{\text{priv}}}\left[F(x^{\text{priv}};\mathcal{P})-\min_{x\in\mathcal{K}}F(x;\mathcal{P})\right]$ is referred to as the excess population risk.

Differentially Private Stochastic Gradient Descent (DP-SGD) [ACG⁺16, SCS13] is a popular algorithm for DP convex optimization. For the theoretical analysis, we study DP-SGD for unconstrained optimization. To facilitate analysis, we work with the $\ell_{2}$ regularized objective expressed as

To optimize this objective, DP-SGD independently samples an example in each iteration and updates the solution by combining the gradient with an isotropic Gaussian whose scale is proportional to $G$, the Lipschitz constant of $f$. Algorithm 1 presents the pseudocode.

It is straightforward to show that Algorithm 1 satisfies differential privacy. The following lemma quantifies the overall privacy spending and builds on a long line of work on accounting the privacy loss of compositions [ACG⁺16, BBG18].

Early works on bounding the excess empirical and population risks for privately optimizing convex objectives focused on a constrained optimization setup where algorithms typically project iterates back onto a fixed bounded domain after each noisy gradient update. Results in this setting suggested that risks are inevitably dimension-dependent in the worst case. For instance, it was shown that the excess empirical risk bound $\Theta(G\left\lVert\mathcal{K}\right\rVert_{2}\sqrt{d\log(1/\delta)}n^{-1}\varepsilon^{-1})$ and excess population risk bound $\Theta(G\left\lVert\mathcal{K}\right\rVert_{2}(n^{-1/2}+\sqrt{d\log(1/\delta)}n^{-1}\varepsilon^{-1}))$ are tight when privately optimizing convex $G$-Lipschitz objectives in a convex domain of diameter $\left\lVert\mathcal{K}\right\rVert_{2}$ [BST14]. Moreover, the lower bound instances in these works imply that such dimension-dependent lower bounds also apply when one considers the class of loss functions whose gradients are low-rank.

The body of work on unconstrained convex optimization is arguably less abundant, with the notable result that differentially private gradient descent need not suffer from a dimension-dependent penalty when learning generalized linear models with low-rank data (equivalently stated, when gradients are low-rank) [SSTT21]. Our main theoretical results (Theorems 3.3 and 3.5) extend this line of work and show that dimension-independence is achievable under weaker conditions.

We present the main theoretical result on DP-ERM for convex objectives. The result consists of two components: Equation (1) is a general bound that is applicable to any sequence of restricted Lipschitz coefficients; Equation (2) specializes the previous bound when the sequence of coefficients decays rapidly and demonstrates dimension-independent error scaling.

We include a sketch of the proof techniques in Subsection 3.3 and defer the full proof to Subsection 3.4.

The restricted Lipschitz continuity condition can be viewed as a generalized notion of rank. The result captured in (2) suggests that the empirical loss achieved by DP-SGD does not depend on the problem dimension if the sequence of restricted Lipschitz coefficients decays rapidly. We leverage these insights to build intuition for understanding privately fine-tuning language models in Section 4.

For DP-SCO, we make use of the stability of DP-SGD to bound its generalization error [BE02], following previous works [BFTT19, BFGT20, SSTT21]. The bound on the excess population loss follows from combining the bounds on the excess empirical risk and the generalization error.

The privacy guarantees in Theorems 3.3 and 3.5 follow from Lemma 2.4. It suffices to prove the utility guarantees. We give an outline of the main proof techniques first and present full proofs afterwards. The following is a sketch of the core technique for deriving (2) in Theorem 3.3. For simplicity, we write $f_{j}(\cdot)$ for $f(\cdot;s_{j})$ and $F(\cdot)$ for $F(\cdot;\mathcal{D})$ when there is no ambiguity.

By convexity, the error term of SGD is upper bounded as follows

where $j\in[n]$ is the random index sampled at iteration $t$.

By definition of $G_{k}$, we know that there is a $k$ dimensional subspace $U$ such that the gradient component orthogonal to $U$ is small when $G_{k}$ is small. Naïvely, one decomposes the gradient $\nabla f_{j}(x^{(t)})=g_{1}+g_{2}$, where $g_{1}\in U$ and $g_{2}\in U^{\perp}$, and separately bounds the two terms $g_{1}^{\top}(x^{(t)}-x^{*})$ and $g_{2}^{\top}(x^{(t)}-x^{*})$. Since $g_{1}$ lies in a $k$ dimensional subspace, one can follow existing arguments on DP-SGD to bound $g_{1}^{\top}(x^{(t)}-x^{*})$. Unfortunately, this argument does not give a dimension-independent bound. Although $\|g_{2}\|_{2}\leq G_{k}$ (which can be small for large $k$), the term $\|x^{(t)}-x^{*}\|_{2}$ is as large as $\Omega(\sqrt{d})$ with high probability due to the isotropic Gaussian noise injected in DP-SGD.

Our key idea is to partition the whole space $\mathbb{R}^{d}$ into $\lfloor\log(d/k)\rfloor+2$ orthogonal subspaces, expressing the error term $\nabla f_{j}(x^{(t)})^{\top}(x^{(t)}-x^{*})$ as the sum of individual terms, each of which corresponds to a projection to a particular subspace. Fix a $k\in[d]$, and consider the following subspaces: Let $U_{0}=\text{range}(P_{k})$, $U_{s}$ be the subspace orthogonal to all previous subspaces such that $\bigoplus_{i=0}^{s}U_{i}=\text{range}(P_{2^{s}k})$ for $s=1,2,\cdots,\left\lfloor\log(d/k)\right\rfloor$, and $U_{S}$ be the subspace such that the orthogonal direct sum of all subspaces $\{U_{i}\}_{i=0}^{S}$ is $\mathbb{R}^{d}$, where $S=\left\lfloor\log(d/k)\right\rfloor+1$. Here, $P_{i}$ is the orthogonal projection matrix with rank $i$ promised by $G_{i}$ in Assumption 3.2. Let $Q_{s}$ be the orthogonal projection to the subspace $U_{s}$, and observe that $\operatorname{rank}(Q_{s})\leq 2^{s}k$ and $\|Q_{s}\nabla F(x)\|_{2}\leq G_{2^{s-1}k}\text{ for all }x\text{ and all }s\geq 1.$ Rewriting the right hand side of (3) with this decomposition yields

On the one hand, if $G_{k}$ decays quickly, $\|\mathbb{E}_{j}[Q_{s}\nabla f_{j}]\|_{2}$ can be small for large $s$. On the other hand, we expect $\|Q_{s}(x^{(t)}-x^{*})\|_{2}$ to be small for small $s$ where $Q_{s}$ is an orthogonal projection onto a small subspace. Thus, for each $s$, $\nabla f_{j}(x^{(t)})^{\top}Q_{s}(x^{(t)}-x^{*})$ is small either due to a small gradient (small $Q_{s}\nabla f_{j}$ in expectation over the random index) or small noise (small $Q_{s}(x^{(t)}-x^{*})$), since noise injected in DP-SGD is isotropic. More formally, in Lemma 3.9, we show that for any projection matrix $Q$ with rank $r$, $\|Q(x^{(t)}-x^{(0)})\|_{2}$ can be upper bounded by a term that depends only on $r$ (rather than $d$).

Before bounding the utility of DP-SGD, we first bound $x^{(t)}-x^{(0)}$ in expectation.

Now, we are ready to bound the utility. The proof builds upon the standard mirror descent proof.