Linear-Time User-Level DP-SCO via Robust Statistics

As one of the central problems in privacy-preserving machine learning and statistical learning, DP stochastic convex optimization (DP-SCO) has garnered significant attention in recent years (e.g., [BST14, BFTT19, FKT20, BFGT20, BGN21, SHW22, GLL22, ALT24]). In DP-SCO, we are provided with a dataset $\{Z_{i}\}_{i\in[n]}$ of users, where each user $Z_{i}$ contributes samples drawn from an underlying distribution $\mathcal{P}$. The goal is to minimize the population objective function under the DP constraint:

where $f(x;z):\mathcal{X}\to\mathbb{R}$ is a convex function defined on the convex domain $\mathcal{X}$.

DP-SCO was initially studied in the item-level setting, where significant progress has been made with numerous exciting results. The study of user-level DP-SCO, to our knowledge, was first initiated by [LSA⁺21], where the problem was considered in Euclidean spaces, with the Lipschitz constant and the diameter of the convex domain defined under the $\ell_{2}$-norm. They achieved an error rate of $O\left(\frac{1}{\sqrt{mn}}+\frac{d}{n\varepsilon\sqrt{m}}\right)$ for smooth functions, along with a lower bound of $\Omega\left(\frac{1}{\sqrt{mn}}+\frac{\sqrt{d}}{n\varepsilon\sqrt{m}}\right)$.

Building on this, [BS23] introduced new algorithms based on DP-SGD, incorporating improved mean estimation procedures to achieve an asymptotically optimal rate of $\frac{1}{\sqrt{nm}}+\frac{\sqrt{d}}{n\sqrt{m}\varepsilon}$. However, their approach relies on the smoothness of the loss function and imposes parameter restrictions, including $n\geq\sqrt{d}/\varepsilon$ and $m\leq\max\{\sqrt{d},n\varepsilon^{2}/\sqrt{d}\}$. On the other hand, [GKK⁺23] observed that user-level DP-SCO has low local sensitivity to user deletions. Using the propose-test-release mechanism, they developed algorithms applicable even to non-smooth functions and requiring only $n\geq\log(d)/\varepsilon$ users. However, their approach is computationally inefficient, running in super-polynomial time and achieving a sub-optimal error rate of $O\left(\frac{1}{\sqrt{nm}}+\frac{\sqrt{d}}{n\sqrt{m}\varepsilon^{2.5}}\right)$. [AL24] proposed an algorithm that achieves optimal excess risk in polynomial time, requiring only $n\geq\log(md)/\varepsilon$ users and accommodating non-smooth losses. However, their algorithm is also computationally expensive: for $\beta$-smooth losses, it requires $\beta\cdot(nm)^{3/2}$ gradient evaluations, while for non-smooth losses, it requires $(nm)^{3}$ gradient evaluations. Motivated by these inefficiencies, [LLA24] focused on improving the computational cost of user-level DP-SCO while maintaining optimal excess risk. For $\beta$-smooth losses, they designed an algorithm requiring $\max\{\beta^{1/4}(nm)^{9/8},\beta^{1/2}n^{1/4}m^{5/4}\}$ gradient evaluations; for non-smooth losses, they achieved the same optimal excess risk using $n^{11/8}m^{5/4}$ evaluations.

Linear-time algorithms have also been explored in the user-level DP-SCO setting. [BS23] proposed a linear-time algorithm in the local DP model, achieving an error rate of $O\left(\sqrt{d}/\sqrt{nm}\varepsilon\right)$ under the constraints $m<d/\varepsilon^{2}$, $n>d/\varepsilon^{2}$, and $\beta\leq\sqrt{n^{3}/md^{3}}$. Similarly, [LLA24] achieved the same rate under slightly relaxed conditions, requiring $n\geq\log(ndm)/\varepsilon$ and $\beta\leq\sqrt{nmd}$.

In our work, we consider user-level DP-SCO under $\ell_{\infty}$-norm assumptions, in contrast to most of prior results, which were established under the $\ell_{2}$-norm. This distinction is significant, as the $\ell_{\infty}$-norm provides stronger per-coordinate guarantees and hence is more desirable. Furthermore, the $\ell_{\infty}$-norm enjoys properties that are crucial to our algorithmic design but do not hold in the $\ell_{2}$-norm setting. These properties influence both the development of our algorithm and the corresponding theoretical guarantees. The implications of this distinction and its role in our results will be discussed in detail in the subsequent sections.

For $X\in\mathbb{R}^{d}$, we use $X[i]$ to denote its $i$th coordinate. For a vector $X\in\mathbb{R}^{d}$ and a convex set $\mathcal{X}\subset\mathbb{R}^{d}$, we use $\Pi_{\mathcal{X}}(X):=\arg\min_{Y\in\mathcal{X}}\|Y-X\|_{2}$. For $X\in\mathbb{R}^{d}$ and $r\in\mathbb{R}_{\geq 0}$, we use $B_{\infty}(X,r)$ to denote the $\ell_{\infty}$-ball centered at $X$ of radius $r$.

The contractivity of gradient descent plays a crucial role in the sensitivity analysis, for which we need the Hessians to be diagonally dominant (Assumption 2.5).

[] [Contractivity] Suppose $f:\mathcal{X}\to\mathbb{R}$ is a convex and $\beta$-smooth function satisfying Assumption 2.5, then for any two points $x,y\in\mathcal{X}$, with step size $\eta\leq 2/\beta$, we have

Now, we discuss Algorithm 1. Given the dataset $\mathcal{D}$, we proceed in $T=|\mathcal{D}|/B$ steps. At the $t$th step, we draw $B$ users $\{Z_{i,t}\}_{i\in[B]}$ and compute the average gradient of each user. We then apply our gradient estimation algorithm (Algorithm 2) and perform normal gradient descent for $T$ steps.

In the second phase of Algorithm 1, we perform the concentration test (Algorithm 3) on the $B$ gradients at each step based on $\mathsf{AboveThreshold}$ (Algorithm 4). If the concentration test passes for all steps (i.e., $a_{t}=\top$ for all $t\in[T]$), we output the average iterate. Otherwise, the algorithm fails and returns the initial point. As mentioned in the Introduction, the crucial novelty of Algorithm 1 and Algorithm 2 lies in bounding the sensitivity of each solution $x_{t}$ by incorporating the (coordinate-wise) robust statistics into SGD.

We utilize robust statistics in the gradient estimation sub-procedure. We make the following assumptions regarding the robust statistics used:

In Algorithm 2, we output means if they are close to the robust statistics to control the bias, and project the means onto the sphere around the robust statistics in a coordinate-wise manner when they are far apart. However, we still need to ensure that the sensitivity remains bounded when the projection is operated. The following technical lemma plays a crucial role in establishing iteration sensitivity to deal with the sensitivity with potential projection operations.

[] Consider four real numbers $a,b,c,d$, such that $|a-b|\leq 1$, and $|c-d|\leq 1$. Let $c^{\prime}=\Pi_{B(a,r)}(c)$ and $d^{\prime}=\Pi_{B(b,r)}(d)$ for any $r\geq 0$. Then, we have $|c^{\prime}-d^{\prime}|\leq 1.$

Unfortunately, we are unaware of any robust statistic satisfying Assumption 3.2 in high dimensions under the $\ell_{2}$-norm, and Lemma 3.3 does not hold in high dimensions either. These limitations restrict the applicability of our techniques in high-dimensional Euclidean spaces; see Section 5.

Let $\{x_{t}\}_{t\in[T]}$ and $\{y_{t}\}_{t\in[T]}$ be two trajectories corresponding to neighboring datasets that differ by one user. The crucial technical novelty is that, for any $t\in[T]$, we can control $\|x_{t}-y_{t}\|_{\infty}$ as long as the number of “bad” users in each phase ($B$ in total) does not exceed the “break point”, say $2B/3$. Without loss of generality, assume that $Z_{1,1}\neq Z_{1,1}^{\prime}$ is the differing user in the neighboring dataset pairs $(\mathcal{D},\mathcal{D}^{\prime})$ considered in the following proof.

The first property of Assumption 3.2 ensures that when the number of “bad” users in each phase does not exceed the “break point” $2B/3$, the robust statistic remains close to most of the gradients, allowing us to control $\|x_{1}-y_{1}\|_{\infty}$. To formalize this, we say that the neighboring dataset pair $(\mathcal{D},\mathcal{D}^{\prime})$ is $\rho$-aligned if there exist points $X^{\prime}$ and $Y^{\prime}$ such that $|X_{\mathrm{good}}|\geq 2B/3$ and $|Y_{\mathrm{good}}|\geq 2B/3$, where

This definition essentially states that the number of “bad” users does not exceed the “break point” in either $\mathcal{D}$ or $\mathcal{D}^{\prime}$, ensuring that most gradients remain well-aligned within a bounded region.

[] For some (unknown) parameter $\rho>0$, suppose $(\mathcal{D},\mathcal{D}^{\prime})$ is $\rho$-aligned. Then, by running Algorithm 2 with threshold parameter $\varsigma\geq 0$, we have $\|x_{1}-y_{1}\|_{\infty}\leq\eta(4\rho+2\varsigma)$.

The sequential sensitivity can be bounded using induction, with the base case $\|x_{1}-y_{1}\|_{\infty}$ already established. The formal statement is provided in Lemma 3.

[Iteration Sensitivity] If we use a robust statistic satisfying Assumption 3.2 in Algorithm 2, then for all $t\in[T]$, we have $\|x_{t}-y_{t}\|_{\infty}\leq\|x_{1}-y_{1}\|_{\infty}$.

Lemmas 3.3 and 3 together establish the iteration sensitivity of Algorithm 1.

We have established iteration sensitivity for any aligned neighboring dataset pair $(\mathcal{D},\mathcal{D}^{\prime})$. Next, we analyze the influence of the concentration test, which we use to check if the number of “bad” users exceed the “break point”.

To apply the privacy guarantee of $\mathsf{AboveThreshold}$ (Lemma A.3), it suffices to bound the sensitivity of each query in the concentration test. Recall that we assume $Z_{1,1}\neq Z_{1,1}^{\prime}$ in the neighboring datasets. Thus, by the definition (Equation (3)), it is straightforward to observe that

Next, we consider the sensitivity of $s^{\mathsf{conc}}_{t}$ for $t\geq 2$. The sensitivity is proportional to $\|x_{t}-y_{t}\|_{\infty}$, which we have already bounded by $\|x_{1}-y_{1}\|_{\infty}$. Note that we can bound the iteration sensitivity if the neighboring datasets are aligned, meaning the number of “bad” users does not exceed the “break point”. We first show that if the number of “bad” users exceeds the “break point”, the algorithm is likely to halt after the first step by failing the first test.

[] Suppose $B\geq\frac{100\log(T/\delta)}{\varepsilon},\varepsilon\leq O(1)$ and we set $\upsilon=0.9B+\frac{2\log(T/\delta)}{\varepsilon}$. Suppose for any point $Y$, we get $|X_{\mathrm{good}}|<B/3$ where $X_{\mathrm{good}}=\{q_{1}(Z_{i,1}):q_{1}(Z_{i,1})\in B_{\infty}(Y,1/\tau),i\in[B]\}$. Then with probability at least $1-\delta/T\exp(\varepsilon)$, the $\mathsf{AboveThreshold}$ returns $a_{1}=\bot$.

We now analyze the query sensitivity between the aligned neighboring datasets.

[Query Sensitivity] Suppose $6\beta\eta B\leq 1$. Suppose $(\mathcal{D},\mathcal{D}^{\prime})$ is $(1/\tau)$-aligned and set threshold parameter $\varsigma=1/\tau$ in Algorithm 4, the sensitivity of the query is bounded by at most $2$. That is,

Equation (4) shows that the sensitivity is always bounded for $s^{\mathsf{conc}}_{1}$. Lemma 3 shows that if the number of “bad” users exceeds the “break point”, we obtain $a_{1}=\bot$, and the query sensitivities of the subsequent queries do not need to be considered. Lemma 3 establishes the query sensitivity in the concentration test when the neighboring datasets are aligned, and the number of "bad" users is below the threshold.

The final privacy guarantee–stated formally below–now easily follows from the previous lemmas. The full proof is deferred to Appendix B.7.

[Privacy Guarantee] Under Assumption 2.4 and Assumption 2.5, suppose $\varepsilon\leq O(1),B\geq\frac{100\log(T/\delta)}{\varepsilon}$, then Algorithm 5 is $(\varepsilon,\delta)$-user-level-DP.

We apply the localization framework in private optimization to finish the utility argument. We analyze the utility guarantee of Algorithm 1 based on the classic convergence rate of SGD on smooth convex functions (Lemma A.6) as follows:

[] Let $x\in\mathcal{X}$ be any point in the domain. Suppose the data set $\mathcal{D}$ of the users, whose size $|\mathcal{D}|$ is larger than $\frac{100\log(T/\delta)}{\varepsilon}$, is drawn i.i.d. from the distribution $\mathcal{P}$. Setting $\tau=G\log(nmd/\omega)/\sqrt{m}$ then the final output $\overline{x}$ of Algorithm 1 satisfies that

Now we apply the localization framework. We set $\omega=1/(nmd)^{3}$ to make the term depending on it negligible. The proof of the following lemma mostly follows from [FKT20].

[Localization] Under Assumption 2.4 and Assumption 2.5, suppose $\beta\leq\frac{G}{D}(\frac{\sqrt{n}\varepsilon}{\sqrt{m}\log(nmd/\delta})$, $n\geq\log^{2}(nd/\delta)/\varepsilon,\varepsilon\leq O(1)$ and $m\leq n^{O(\log\log n)}$. Set $\eta\leq\frac{D}{G}\cdot\min\{\frac{B\sqrt{m}}{\sqrt{n}},\frac{\sqrt{m}\varepsilon}{\sqrt{d\log(1/\delta)\log(nmd)}}\}$, $B=100\log(mnd/\delta)/\varepsilon$, $\tau=O(G\log(nmd)/\sqrt{m})$ and $\upsilon=0.9B+\frac{2\log(T/\delta)}{\varepsilon}$. If the dataset is drawn i.i.d. from the distribution $\mathcal{P}$, the final output $x_{S}$ for Algorithm 5 satisfies