Correlated Noise Provably Beats Independent Noise for Differentially Private Learning

We thank the reviewer for the review. The “technical flaw” pointed out by the reviewer is an incorrect assessment, our original argument is correct (details below). We urge the reviewer to thoroughly re-read and review the paper again for a fair and unbiased assessment of the merits of this paper.

[Technical flaw] “... for a finite privacy budget and an infinite (large) number of iterations, an infinite (large) amount of noise should be added in every step to the gradient”

This assessment is incorrect. We prove bounds in the streaming setting, where each data point is processed only once. Thus, the number $n$ of data points and the number of iterations $T$ are equal. To see why a finite amount of noise is sufficient even as $T \to \infty$, consider the uncorrelated noise case (DP-SGD): the privacy guarantee for all iterations can be obtained from parallel composition, so the noise multiplier is independent of $T$. Prior work has also studied this setting, e.g. Chourasia et al. NeurIPS 2021 and Altschuler & Talwar, NeurIPS 2022.

For the more general correlated noise setting, Theorem 1.1 gives a rigorous privacy guarantee that holds any $T$, including in the limit $T \to \infty$. Note that the only dependence of the noise multiplier on $T$ is via the sensitivity $\gamma_T(\boldsymbol{B})$.

"While Eq (1) defines f(\theta, z) as objective function, Eq (6) seems to treat f as the derivative of the objective function."

The notation is correct — the objective for mean estimation is $f(\theta; z) = z^2 / 2 - z\theta$:

"The proof of theorem 2.1 cites Fourier analysis, but doesn't make explicit what is the derivation the authors have in mind."

The main paper only gives a short proof sketch (which provides an idea of why the statement is true), while the full proof and all its technical details are given in Appendix B.

The technical details are based on standard results in Fourier analysis that we recall in Appendix F (specifically, Theorem F.2). The key idea of the proof is conveyed in that it is based on Fourier analysis, but we strongly feel that technical details regarding the Fourier transform would be a distraction in a short proof sketch.

"There is even no proof that the asymptotic optimality defined by Eq (4) exists (i.e., the limit converges), which is non-trivial as the more iterations are performed, the higher the amount of noise per iteration needs to be."

The reviewer is mistaken as we pointed out above. The limit exists in all cases we consider in the theoretical statements. The argument goes as follows:

• For a finite noise variance, the quantity in Eq. (4) is well-defined. This requires the limiting sensitivity $\gamma_\infty(B)$ (defined in Eq. (5)) and the clip norm $G$ to both be finite; indeed, by Theorem 1.1, the required noise variance is $\gamma_\infty(B)^2 G^2 / (2 \rho)$.
• The sensitivity $\gamma_\infty(B)^2 = log(1/\nu)$ is finite for $\nu$-DP-FTRL (see Table 2).
• For mean estimation in Theorem 2.1, we take $G=1$ and for general strongly convex functions in Theorem 3.1, we take $G$ to be the Lipschitz constant of the loss function, which is assumed finite. Thus, the noise variance of DP-FTRL is finite and the limit in Eq. (4) is well-defined.
• For quadratic functions, we analyze the asymptotic suboptimality of noisy-FTRL (i.e. DP-FTRL without gradient clipping) in Theorem 2.2; this asymptotic quantity is always well-defined. To get a DP bound in this case, (a) we argue for privacy that the gradient norm after $T$ iterations is bounded with high probability, and (b) the suboptimality after $T$ iterations is upper bounded by the asymptotic suboptimality at the same noise variance. The full privacy-utility bound of this case is given in Theorem D.13 in Appendix D.4.

We thank the reviewer for the clarifications. We urge the reviewer to please re-read and review the paper again for a fair assessment (including the significance and novelty) of the key contributions, which are the following:

• Theoretical: We establish that DP-FTRL is provably better than DP-SGD as a function of problem parameters such as the effective dimension and condition number. This is the first clear theoretical separation between DP-SGD and DP-FTRL.
• Empirical/Practical: We show empirically that the proposed $\nu$-DP-FTRL is substantially better than other efficient DP-FTRL variants for private deep image classification and language modeling. Further, it can nearly match the SoTA “multi-epoch” variant (which has a $O(T^3)$ cost; denoted “ME”).

We would like to reiterate that all theorem statements in the main paper and appendix are fully self-contained (we are happy to fix any that are not). All relevant background and technical details are provided in the appendices. The appendices also include several navigational aids, such as a table of contents and outlines at the beginning of each section, to help a reader easily find the information they need.

We would be more than happy to answer further questions or discuss any technical issues.

"The FTRL algorithms are suboptimal in this context"

You are right about potentially better algorithms for these problems. We are fully transparent about this fact at the start of Section 2:

We do not aim to achieve the best possible rates in these stylized models. Rather, our goal is to understand the noise dynamics of DP-FTRL and show a separation with DP-SGD.

We also mention on page 1 that DP-FTRL is a practical algorithm that is deployed in industrial settings but a theoretical understanding is lacking. Our analysis is a major step in building a theoretical understanding of this algorithm.

Minor clarifications:

Thank you for the suggestions. We have made some changes (see uploaded revision) and clarified confusions as detailed below.

• Streaming setting: Besides clearly mentioning that we consider a streaming setting, there are other clues in the setup. The dataset $\mathcal{D}$ has $T$ data points, and we run the algorithm for $T$ iterations (e.g. return $\theta_T$, the noise correlation matrix $\boldsymbol{B}$ is of size $T \times T$, etc.). We believe it is clear from the context that the size of the dataset grows with the number of iterations.
• max_{t<T}: We do consider the last column. The matrices are 0-indexed — this can be inferred from Eq. (2), for instance. We have added a clarifying note in the revision.
• correlation matrix $\boldsymbol{B}$: The term correlation matrix comes from the cited line of work on DP-FTRL [1, 2, 3]. We believe that it is unambiguously clear from Eq (2) that $\boldsymbol{B}$ is not the covariance matrix of the noise $\boldsymbol{w}_t$.
• Eq (6): The terms defined in Eq. (6) map back to the terms introduced in Eq. (1): they are the objective, loss, and regularizer respectively. Again, we believe that there is no ambiguity in the notation here.
• Pointer to the proof of Theorem 2.1: We have added a pointer to the right appendix, following the reviewer's suggestion. All other theoretical statements already contain the right appendix pointers.
• statement of Thm 2.1 uses the symbol $\boldsymbol{\beta}_{\text{dpsgd}}$ without defining it: Note that $\boldsymbol\beta_{\text{dpsgd}} = (1, 0, \ldots)$ are the noise weights that retrieve DP-SGD as a special case of DP-FTRL. The text says "... the asymptotic sub-optimality … of DP-SGD is $F_\infty(\boldsymbol{\beta}_{\text{dpsgd}}) = \cdots$", so we believe that it is clear from the context.
• doesn't mention [$\boldsymbol{\beta}$] should be square-summable: Note that $\boldsymbol{\beta}$ being square-summable is not a part of the definition --- $F_\infty(\boldsymbol{\beta})$ is simply infinite if $\boldsymbol{\beta}$ is not square-summable. Furthermore, all theorem statements in both the main paper and appendix give appropriate qualifications on the summability of $\boldsymbol{\beta}$. Technical details about the convergence of various stochastic processes can also be found in the appendix.
• zero-out neighboring: We have added a note in the revision pointing out the exact notion of neighborhood. We note that the results present an apples-to-apples comparison of DP-SGD vs. DP-FTRL under the same notion of neighborhood. We believe that the exact details of the neighborhood are technical detail that is not central to understanding the key results regarding the theoretical separation of DP-SGD and DP-FTRL.

Now we get to applying Theorem F.2 in the proof of Theorem 2.1. We should think of the following:

• $G$ in Thm 2.1 is not related to $\mathbf{G}(\omega)$ is Theorem F.2
• I guess $x_t$ in Thm F.2 corresponds to $\delta_t$ or $\beta_t$ or $w_t$ in Thm 2.1. Unfortunately, for $x_t$ in Thm F.2, $t$ ranges from $-\infty$ to $+\infty$ while both $\delta_t$, $\beta_t$ and $w_t$ in Thm 2.1 are sequences for which $t$ ranges from $t=0$ to $t=\infty$. Maybe, let us guess that $x_t$, $y_t$ and $H$ in Thm F.2 correspond to $w_t$, $\beta_t$ and $\delta_t$ in Thm 2.1.
• The text doesn't explain why the transformation from $\theta_t$ into $\delta_t$ was useful, Eq (11) looked much more as a linear transformation, but apparently it was a preparation for applying Thm F.2, and hence could provide a clue, even though only some of the symbols in the $\delta_t$ equation occur in the resulting bound. For example, the newly introduced $w_{sgd}$ doesn't occur in the resulting $F_\infty(B)$ equation. Maybe the term $\eta\sigma_{sgd} w_{sgd}$ is not important and we should only look at the term involving $w_t$, but in that term $\sigma_{sgd}$ does not occur, while this variable does occur in the $F_\infty(B)$ equation.
• Applying Thm F.2 requires the LTI is asymptotically stable, but the text doesn't argue why this condition is fulfilled. I guess this is a consequence of the assumption that the objective function is convex.

Nevertheless, it is plausible that with adding half a dozen of additional intermediate steps and explanations this step can be shown to be correct.

Next, the text says "Thus $F_\infty$ is a product of ...". In fact, $F_\infty$ is a function, and $F_\infty(B)$ is an integral, which we can interpret as a sum, but not immediately as a product. For every specific $\omega$, indeed we have as integrand $|B(\omega)|^2 \gamma_\infty(B)^2$ multiplied with other factors, where $\gamma_infty$ is an integral (a sum) with $|B(\omega)|^{-2}$ as one of its terms. To write $F_\infty(B)$ as a product, an alternative strategy (not mentioned in the text) would be to first observe that $\sigma_{sgd}^2$ is a constant, and then to minimize the part remaining after removing $\sigma_{sgd}^2$, in that case one could write $F_\infty(B)$ as a product by getting $\gamma_\infty(B)$ out of the integral.

Eq (14) then suggests that of the other factors in the product, including $G^2$ and $\sigma_{dp}^2$, only the denominator should be included when determining $B(\omega)$ to minimize $F_\infty(B)$, but the text doesn't give a reason.

"elliptic integrals coming from the $\sigma_{dp}$ term" -> I guess you mean "factor" rather than "term" here.

The text says the proof of the error bound now follows by applying a list of results it refers to. However, the bound stated in Theorem 2.1 contains the variable $\rho$, but neither Lemma F.15 nor Corollary C.5 seem to introduce a $\rho$ into the equation we have so far.

We thank the reviewer for appreciating our theoretical innovations and the potential applicability of the proof technique. We addressed the concern about gradient clipping, as well as your other questions below. Please do not hesitate to reach out in case of further clarifications/questions. Thank you!

"$\nu$-DP-FTRL doesn't need any gradient clipping … sensitivity might be prohibitively high"

Great question! The key is that the statement "most of the time, the stochastic gradients won’t exceed the clipping norm" is made for the unclipped gradients. However, we still use the clipped gradients in the algorithm, and so the formal DP guarantee always holds but the utility guarantee is conditional on the unclipped and clipped gradients being the same (i.e. the event $\mathcal{E}$). This is because DP-FTRL always includes gradient clipping as shown in Algorithm 1.

Please see Theorem D.13 in Appendix D for the detailed theorem statement.

"role of $\nu$ in $\hat \beta_t^\nu$"

It turns out that ${½ \choose t} \approx t^{-3/2}$ (this can be seen from Stirling’s approximation). However, this is not enough for theory or practice, as we explain below.

Firstly, a correction to the reviewer’s comment. The damping term $(1-\nu)^t \le \exp(-\nu t)$ is an exponential decay, which is asymptotically faster (not slower as the reviewer notes) than the polynomial $t^{-3/2}$ (although the latter is faster for $t$ small).

Theory: We need both these terms to get the right rate in theory. Note that $\nu=0$ corresponds to the weights of Fichtenberger et al. (2023). As shown in Table 2, its sensitivity grows as $\log(T)$ — this is unbounded as $T \to \infty$. Thus, its asymptotic suboptimality is unbounded too. The exponential damping term is sufficient to achieve near-optimality for linear regression.

Experiments: We compare to $\nu=0$ experimentally under the name “Optimal CC” (see Table 3 for details). Our experiments show that despite tuning a restart parameter for Optimal CC, it is around 3pp worse than $\nu$-DP-FTRL for all levels of privacy for CIFAR-10. Together, both these results show that the $(1-\nu)^t$ damping term is essential both in theory and practice.

Hope we answered all your concerns. We would be happy to address further questions. Thank you for your time!

We thank the reviewer for appreciating the significance of the results. We have addressed the questions about Noisy-FTLR vs. DP-FTRL, and the practical applicability of the theory below. Please do not hesitate to reach out in case of further clarifications/questions. Thank you!

"Most of the results are for Noisy-SGD and Noisy-FTRL, which are not DP as written in the paper."

Theorem 2.1 for mean estimation and Theorem 3.1 for general strongly convex functions both hold for DP-FTRL and satisfy full DP guarantees.

We give the main results for linear regression for noisy-FTRL for simplicity. The corresponding finite-time privacy-utility guarantees for DP-FTRL are given in Theorem D.13 of Appendix D, where DP-FTRL has a similar advantage over DP-SGD as Noisy-FTRL over Noisy-SGD (effective dimension dependence instead of dimension, etc.). Further, all our deep learning results compare our $\nu$-DP-FTRL to DP-SGD and prior works in a non-convex setting where all methods satisfy the stated privacy guarantees.

"This paper uses lots of assumptions, and it seems difficult to adopt the results in practice."

We respectfully disagree with this assessment. Our theoretical guarantees have two strengths:

• This is the first rigorous evidence that DP-FTRL is provably better than DP-SGD. This explains empirical observations in prior works that lacked the theoretical backing.
• Next, our theory is a guiding principle for further algorithmic developments. $\nu$-DP-FTRL, which we derived from our theoretical analysis, is readily applicable in practice for private deep learning.

We empirically demonstrate that $\nu$-DP-FTRL outperforms all previous efficient DP-FTRL instantiations (Table 1) and DP-SGD for private image classification and federated language modeling. Furthermore, the simple structure of our correlated noise, which avoids the need to solve an SDP, actually makes it even easier to deploy in practice than the DP-FTRL instantiations proposed by Denisov et al. (NeurIPS 2022) and Choquette-Choo et al. (ICML 2023).

Thus, our theoretical analysis seamlessly leads to practical improvements.

"...add more experimental results..."

In Section 4, we compare our method on the benchmark tasks established in the prior literature (Kairouz et al. ICML 2021), (Choquette-Choo et al. ICML 2023), (Choquette-Choo et al. NeurIPS 2023, Koloskova et al. NeurIPS 2023): example-level DP for image-classification on CIFAR-10 and user-level DP for language modeling (next word prediction) on Stack Overflow. Since the submission, we have updated our results on Stack Overflow to include all mechanisms and find that $\nu$-DP-FTRL outperforms all efficient baselines (listed in Table 3) and even matches the multi-epoch upper bound.

If the reviewer has specific experiments they would like to see, we would be happy to add them.

"Is it possible to extend the analysis to general correlation matrices instead of Toeplitz?"

Analysis of DP-FTRL with non-Toeplitz matrices is likely to be very technically involved. It is an exciting direction for future work.

From a theoretical perspective, the assumption that $\boldsymbol{B}$ is Toeplitz makes DP-FTRL a time-homogeneous stochastic process (i.e. $P(\theta_{t+1} | \theta_t, z_t=z) = P(\theta_t | \theta_{t-1}, z_{t-1} = z)$). This ensures the existence of a stationary distribution, whose properties we analyze. This is analogous to the classical topic of Markov chains, where most studies of stationarity assume that the system is time-homogeneous.

In the absence of the Toeplitz assumption, $\mathbb{E}[F(\theta_T) - F(\theta_\star)]$ might not even have a limit as $T \to \infty$. We have to find and make appropriate assumptions so that this limit is well-defined. Investigating tree aggregation (Kairouz et al. ICML 2021) can be a good starting point but the analysis will likely require much stronger technical tools.

From a practical perspective, Toeplitz matrices are more computationally efficient than general correlation matrices. They have been proposed in the previous literature e.g. Choquette-Choo et al. ICML 2023 for this reason.