Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacy
We study gradient descent under linearly correlated noise. Our work is motivated by recent practical methods for optimization with differential privacy (DP), such as DP-FTRL, which achieve strong performance in settings where privacy amplification techniques are infeasible (such as in federated learning). These methods inject privacy noise through a matrix factorization mechanism, making the noise linearly correlated over iterations. We propose a simplified setting that distills key facets of these methods and isolates the impact of linearly correlated noise. We analyze the behavior of gradient descent in this setting, for both convex and non-convex functions. Our analysis is demonstrably tighter than prior work and recovers multiple important special cases exactly (including anticorrelated perturbed gradient descent). We use our results to develop new, effective matrix factorizations for differentially private optimization, and highlight the benefits of these factorizations theoretically and empirically.
Paper
Similar papers
Peer review
Summary
The authors propose a new analysis method that unifies the analysis of noisy gradient descent-based algorithms, where the noise is added to the matrix factorization, which provides a tight analysis of both the algorithms simultaneously, and hence would give the analysis for convergences for a general class of such matrix-factorization based gradient descent algorithms. Based on this new analysis, the authors also propose a new matrix factorization objective to further tighten the upper bound and empirically show it.
Strengths
- The method of analysis is based on a very simple yet essential idea and it opens the possibilities of a unified method of analysis for a good class of algorithms which are based on gradient descent algorithms based on matrix factorization. - The transition from proposing a tighter bound to a new matrix factorization objective shows powerful empirical applications of this class of algorithms to private optimization. - The paper is theoretically very sound. - Evaluation done on the paper is simple and easy to understand and evaluation has been done not only with respect to utility but also to visualize the trend that the gradients follow across training.
Weaknesses
- The novelty and the reach of this problem are limited to a very specific class of algorithms on a practical scale. - Although the authors have already addressed this in their future work, it is still important to note that the average case analysis for differentially private algorithms might not be a correct metric to judge the performance of the model since the final iterate of the algorithm is returned.
Questions
- Can the authors elaborate on what they exactly want to denote using Figure 1 and maybe provide a more clear diagram for it so that the process can be understood better?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
4 excellent
Presentation
4 excellent
Contribution
3 good
Limitations
Authors have mentioned most of the limitations in their future work and additional points have been discussed above in the weakness section (novely and final iterate analysis).
Summary
This paper conducted a theoretical study of gradient descent with linearly correlated noise, with strong motivation from the theory and applications of differential privacy (in particular, the popular DP-SGD algorithm). The main contribution is a new convergence analysis based on the idea of "restart iterations". The paper argues that it unifies two previous "incompatible" analyses for two different noisy gradient descent algorithms, namely perturbed gradient descent (PGD) and anti-PGD. Inspired by the new analysis, this paper proposes a new matrix factorization method for noisy SGD. The matrix factorization coordinates noises across different iterations of gradient descent. The new factorization refines a previous method. Experiments show that it compares favorably to prior works.
Strengths
* The paper is very well-written and looks both educational and professional. * It tackles an important and popular question of optimization and private learning. The "restart iteration" analysis looks nice. However, I don't work on this area myself, it is hard for me to evaluate the novelty of the new analysis.
Weaknesses
* I am slightly dissatisfied with the hyper-parameter "\tau" required in your new algorithm and analysis (more on this in the question section).
Questions
* If possible, it would be nice to discuss why the two analyses for PGD and anti-PGD are incompatible. Also, I am curious if the two different proofs directly inspire your analysis. * Your paper shows that the "restart" in analysis and algorithm design does help. However, could you provide some intuition on why "restart" is beneficial in both theory and applications? Do you have evidence that this method yields tight analysis? * Are there good heuristics to find an appropriate "tau" in practice? Is there a way to come up with an algorithm that is equally good, but does not require the knowledge of the hyperparameter?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
The limitations and future directions are discussed in the paper.
Summary
This paper studies (stochastic) gradient descent with linearly correlated noise. The paper builds upon recent results on (MF-)DP-FTRL. It highlights the limitations of this methods, proposes a restarting trick to improve it, and derive the corresponding analysis. Interestingly, the proposed analysis gives a unified analysis of PGD and Anti-PGD, that are difficult to analyze together otherwise. Theoretical results are confirmed by numerical experiments.
Strengths
Overall, I think this paper is a nice paper, that perfectly fits the conference. 1. The proposed method identifies the limitations of an (important) existing method and proposes a clever trick to overcome them. 2. Corresponding theory is derived in multiple settings (convex and non-convex), and is confirmed by numerical experiments. 3. Overall, the paper is very pleasant to read (even the appendix), with a clear introduction and clear motivations, and the math seems to be correct.
Weaknesses
In my opinion, this paper does not have major weaknesses. I only have a few minor remarks. 1. The method is claimed to work for DP-SGD, but the theory is only derived with full-batch gradients. This is a bit unfortunate since DP-FTRL-like methods aim at providing stochastic DP algorithms that do not rely on amplification. 2. The proposed method seems a bit "handmade": it seems there is something deeper behind it. 3. Example 3.3 is a bit crude and could benefit from a little more details (on the choice of the pseudo-inverse and the fact that B and C are not square).
Questions
1. The restarting trick essentially states that not all iterates should have correlated noise. Do you think this is a fundamental property of the method or simply a caveat of the analysis? 2. How does the restarting trick affect numerical performances in terms of time of execution? It seems that solving $OPT_F(\Lambda_\tau A)$ could be easier due to the structure of $\Lambda_\tau$: is it the case?
Rating
8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
Confidence
5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.
Soundness
4 excellent
Presentation
4 excellent
Contribution
4 excellent
Limitations
Yes, authors pointed that their analysis does not encompass clipping, and only works for averaged iterate. Some other research directions/limitations have also been mentioned in the conclusion.
Summary
This paper develops many techniques to analyze gradient descent convergence with linearly correlated noise, a setting motivated by many DP algorithms. The work derives tighter bounds, and use the resulting insights to motivate DP-MF and DP-MF+.
Strengths
- The paper is structured well, and is very notationally precise for the most part. - The theoretical results are very involved, and I particularly appreciate the authors including several noteworthy special cases.
Weaknesses
Clarity: - This work is not very self contained, and it seems like the authors expect the reader to be very familiar with Denisov et al. and Choquette-Choo et al. This makes the work a bit difficult to follow at times. I would advise the authors to include more details about these works in the supplementary or even the main paper if possible. - Related to the previous point, details about Example 3.3 in Section 3 are not provided at all. - This is a minor suggestion, but using $x$ to denote the weights is unconventional in the machine learning community as it typically is used to denote the dataset. This may be a source of confusion to some readers. Practicality: - The problem setting seems impractical, as factorizing $\mathbf{A} \in \mathbb{R}^{T x T}$ is intractable in realistic settings. In the experimental settings considered in this work, T is reasonable. However, in practice $T$ can be on the order of millions and even a one-time matrix factorization is not tractable. - Is Assumption 4.2 a realistic assumption for deep learning? The loss landscapes for neural networks are typically extremely sharp, rendering some of the convergence rate results vacuous. I understand that this is a common assumption in the optimization community.
Questions
1. How can this method be scaled to large $T$?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
Limitations are adequately discussed.
Summary
This paper studies variants of noisy gradient descent, focusing on when the noise added at different time steps may be dependent. The motivation of this is differentially private optimization: while the standard DP-(S)GD adds independent noise at each time step, the recent DP-FTRL mechanism [1] adds carefully correlated noise. Even more recent work [2,3] extends this approach via the matrix mechanism. This paper builds heavily on the latter two works. It begins by identifying how the prior analysis is pessimistic and settings where one might hope to improve upon it. We then analyze in detail "perturbed gradient descent," PGD, ie gradient descent with independent Gaussian noise, and "anti-PGD," which after each gradient step we add a new noise term and *subtract* the noise term from the previous time step. This latter method is closely related to randomized smoothing. The authors establish the main theorems (for general "noisy SGD-type" algorithms without clipping) via a novel analysis, analyzing virtual iterates that periodically revert to the actual sequence. The authors perform experiments, first on synthetic data without gradient clipping (to validate their theorems) and then with clipping on benchmark data sets. They show that, in some settings, their approach matches or exceed DP-SGD. [1] Kairouz, P., McMahan, B., Song, S., Thakkar, O., Thakurta, A., & Xu, Z. (2021, July). Practical and private (deep) learning without sampling or shuffling. In International Conference on Machine Learning (pp. 5213-5225). PMLR. [2] Denisov, S., McMahan, H. B., Rush, J., Smith, A., & Guha Thakurta, A. (2022). Improved differential privacy for sgd via optimal private linear operators on adaptive streams. Advances in Neural Information Processing Systems, 35, 5910-5924. [3] Choquette-Choo, C. A., McMahan, H. B., Rush, K., & Thakurta, A. (2022). Multi-epoch matrix factorization mechanisms for private machine learning. arXiv preprint arXiv:2211.06530.
Strengths
The paper investigates a topic of clear theoretical and practical importance; there is substantial food for thought. In particular, the authors convince me that there is more to be done in this direction. They analyze simplified cases but lay out many directions for further analysis. I agree that the paper "highlights the wealth of stochastic optimization questions arising from recent advances in differentially private model training." In addition, the paper makes clear progress beyond prior work, bringing a new set of tools to bear. I thought the analysis for the main theorems was very cool. It seems plausible that this type of analysis might be extended or applied elsewhere. I feel the authors do a good job placing their work within the broader literature.
Weaknesses
The paper has limited scope and there were fewer conclusions after the main theorems than I had hoped. For instance, in line 253 we read "Intuitively, since $\lVert \Lambda_{\tau} \mathbf{B}\rVert_{F}^{2}$ is a better proxy for learning performance than $\lVert \mathbf{B}\rVert_{F}^2$, minimizing this quantity... should lead to... better privacy-utility tradeoffs." The "intuition" just repeats the paper's setup, that of finding better factorization. I would like a discussion of *why* this proxy is better, beyond the theorem statement. I feel that future work may supercede this approach without building on it. It is not clear how much this paper would contribute beyond pointing out that there is more work to be done. Indeed, perhaps algorithms from from Choquette-Choo et al. already outperform this approach? While the contribution is clear, I feel there is a ceiling on its impact. I feel the paper spends too little time on background. This is on purpose, since the setup is similar to that of Denisov et al. and Choquette-Choo et al. However, I would like to see a more self-contained discussion. Two examples in particular stand out to me: first, the expression sens(C) is never defined. Second, as far as I can tell there is no detail on how DP-SGD was run as an experimental baseline. Although the motivation and experiments deal with privacy, the main theoretical results are for nonprivate algorithms. I was confused by this at first, especially in the transition from Section 2 to 3: the paper says "we derive a tighter bound... to design better factorization mechanisms for differentially private optimization," and then almost immediately says "we omit gradient clipping from our analysis."
Questions
What is the DP-SGD you're comparing against? How were the hyperparameters selected? Can you elaborate on what kinds of factorizations your approach favors? Do you have an intuition for how they differ from those of Denisov et al.? The main theorems specify a value of $\tau$, but the experimental performance seems to improve monotonically with $\tau$. Maybe I missed it, but do you have an idea for why that is?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
4 excellent
Presentation
3 good
Contribution
3 good
Limitations
I feel the authors are clear about the limitations of their work. As I see it, the main limitations are (i) the narrow scope and (ii) the experiments, which I feel are more "illustrative" rather than comparing to the state of the art.
Thanks for the detailed comments. My only comment (to which you need not reply) is that I feel your response to the first weakness misunderstands my concern. From the submission, I understood that $\lVert \Lambda_{\tau} B\rVert_F^2$ yields stronger theoretical guarantees that are tight in special cases. I was looking for more intuition, such as an informal description of what your proxy captures that $\lVert B \rVert_F^2$ does not.
We would like to thank the reviewer for their prompt response ! Intuitively, our convergence rate accounts only for correlations in noise that are close in terms of round numbers (within the $\tau$ closest iterations) and does not consider noise correlations for round numbers that are far apart. We will clarify this in the main text.
Response to Authors
Thanks to the Authors for addressing the questions. I do not have further questions.
Thank you for your answer and for the additional precisions. I don't have further comments.
Thank you
Thanks to the authors for answering my questions!
Only the smooth case?
From a quick look it appears that the main difference from the previous analysis is that it is based on adapting existing analyses for smooth convex optimization as opposed to the general convex case (as in Denisov et al) and then optimizing the resulting matrix decomposition. If that's the case then the main claim that the achieved bounds are tighter than the previous work seems misleading as the new bound requires stronger assumptions (and thus is incomparable to prior work). Could you please clarify this point?
Dear AC, We would like to thank you for your question. Indeed, our assumptions are different from assumptions used in the analysis of (Denisov et al): we analyze smooth convex and non-convex functions, while (Denisov et al) analyze Lipschitz strongly convex functions. However, even under assumptions of (Denisov et al), the convergence rate based on $||B||_F$ is not tight. Please note that our discussion in lines 130-134 refers to the rate from [39] that is derived under the same assumptions as in (Denisov et al). This rate from [39] for a special case of PGD noise correlation (when B = A) is tighter than the one derived in (Denisov et al). Moreover, our analysis is **not** simply based on adapting existing proof techniques of smooth optimization, as we detailed in Section 4.1. In this section, we reviewed two main existing techniques of smooth optimization: real-iterate analysis and perturbed iterate analysis, and showed that it is non trivial to obtain a tight rate using either of these two techniques. See our discussion in lines 218-220, as well as appendix F. Our analysis is novel, and is based on the *non-trivial* combination of the two existing proof techniques through utilizing virtual sequence with restarts (see Section 4.2). In particular, lines 533-541 in the non-convex proof, as well as lines 558-572 in the convex proof *are non trivial and novel* steps in the proofs. We chose to impose smoothness as (i) common in optimization literature, and (ii) because it allows us to theoretically study an important class of non-convex functions, thus being closer to the deep learning setting. In experiments we illustrate that our approach can lead to practical improvements for both: differentially private convex learning (MNIST, logistic regression) as well as deep learning training (CIFAR10, CNN). We will clarify this in the main text. To sum up, all the reviewers positively assessed our paper, with each of them commenting on the novelty and soundness of our analysis: - Reviewer dQeP: *“the paper makes clear progress beyond prior work, bringing a new set of tools to bear. I thought the analysis for the main theorems was very cool. It seems plausible that this type of analysis might be extended or applied elsewhere.”* - Reviewer ptMd: *”theoretical results are very involved”* - Reviewer WD4o: *“Interestingly, the proposed analysis gives a unified analysis of PGD and Anti-PGD, that are difficult to analyze together otherwise.”* - Reviewer 2HBd: *”The main contribution is a new convergence analysis based on the idea of "restart iterations" ”* - Reviewer xFGx: *” the paper is theoretically very sound ”* We would be happy to provide additional clarifications whether you have any remaining questions or concerns regarding our paper ! [39] S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan. Stochastic convex optimization. In 447 Annual Conference Computational Learning Theory, 2009.
I do not see how the discussion in lines 130-134 addresses my point. Indeed prior bounds may be loose but your bounds require additional assumption to improve on them. Not particularly important but I do not see a strong convexity assumption in your restatement of Denisov et al. To clarify I agree that smoothness is a common assumption and deriving better bounds for it is important. But my point is that convergence is often faster under the assumptions of smoothness. So the issue is that the high-level claims of direct improvement over prior work look misleading to me (and might have mislead reviewers as well).
Dear AC, We would like to thank you for your follow-up. We are sorry for the confusion caused regarding the assumptions that we make, and we thank you for pointing to that. We will make our discussions clearer in the next version of the paper. We agree that it is incorrect to directly compare the rates from (Denisov et al) and our derived convergence rates in Theorems 4.6 and 4.7. In fact, our paper never directly compares these two rates. We want to highlight that in the contributions section in lines 40-50, as well as below our main Theorems 4.6 and 4.7 we never mention that our rates are tighter than that of (Denisov et al). Instead, in section 4, we establish the two baseline approaches using existing tools of smooth optimization and identify that these two baselines are not tight (see Appendix F). Our improved convergence rate is based on novel proof techniques and clearly improves upon established baselines in section 4.1. This is what we refer to in the abstract as being “demonstrably tighter than prior work”. We will further clarify this in the paper. It is worth noting that the analysis in (Denisov et al) is based on perturbed iterate analysis, but applied to the non-smooth optimization setting. In the smooth setting, perturbed iterate analysis gives the rate based on $||B||_F$, similarly to the non-smooth in (Denisov et al). In section 4.1. we established (for the smooth setting) that this rate based on $||B||_F$ is tight for Anti-PGD but not for PGD, and also showed a lower bound that perturbed iterate analysis *cannot be tight* for smooth optimization (see Appendix F). In conclusion, we first thank the AC for pointing out the inaccuracy in our discussions, we will make our discussion clearer in the next version. Despite using different assumptions from (Denisov et al), we carefully set the baselines for the assumptions that we used. We therefore believe that our paper makes a non-trivial contribution to the smooth optimization literature bringing a new set of analytic tools. We hope that our answer could resolve your concern and we are happy to discuss this further.
I thank the AC for identifying this issue. I had not understood that the assumptions differed between this work and Denisov et al., and was under the impression that the two operated in the same setting. For instance, the authors' rebuttal to me says "making our rates in Theorem 4.7. strictly tighter than that in (5)", where (5) is the equation with Denisov et al.'s rates. Of course, I should have read more closely. Looking over the submission and the discussion here, I think part of the issue is the word "tighter," which is used in several places where it might be more appropriate to say "faster." I feel that (i) I was at least slightly misled by the high-level claims of direct improvement over prior work, and (ii) analyzing the smooth setting is still important.
Decision
Accept (poster)