DOPPLER: Differentially Private Optimizers with Low-pass Filter for Privacy Noise Reduction

Summary

The paper looks at the sequence of DP-SGD noisy gradients through a signal processing perspective, and argues that the exact gradients are likely a low-frequency signal, while the noise has higher frequencies. As a result, the paper proposes filtering the high-frequencies with a low-pass filter to improve the signal-to-noise ratio. The filter is a post-processing of the noisy gradients, so there is not extra privacy cost. The paper then studies the convergence rate of DP-SGD with the filter under standard assumptions, and finds that the filter can improve the constants of the convergence rate if the hyperparameters of the filter are chosen well. The paper also contains experiments comparing several DP first-order optimiser with and without the filter on several datasets and models. The filtered variant consistently outperforms the unfiltered one.

Strengths

Investigating the behaviour of DP-SGD in the frequency domain is interesting, and to my knowledge novel. The proposed low-pass filter is justified theoretically and consistently improves performance across several models, datasets and optimisers. Since the filter is just a post-processing of the noisy gradients, the privacy analysis does not change, and the filter should be easy to implement with different variants of DP-SGD.

Weaknesses

Many of the signal processing concepts are introduced too briefly, considering the audience, which makes fully understanding the theory difficult. Adding a section to the appendix explaining them clearly would make the theory much easier to understand for people not familiar with signal processing. The method used to compute the privacy bounds and the subsampling method in the experiments are not mentioned clearly in the paper. "Uniformly draw minibatch" or "randomly draw minibatch" from the algorithm listings is ambiguous, and could mean any of Poisson, with replacement or without replacement subsampling. Minor points: - Line 43: 250K steps for LLAMA training sounds like a typo. - It would be good to mention that there are multiple ways to interpret "neighbourhood" (substitute or add/remove), and that the paper's results do not depend on the precise definition. - As far as I know, the Gaussian mechanism bound in Definition 2 has only been proven for $\epsilon \leq 1$. - It is not clear how Algorithm 3 should be read for DPAdam or LP-DPAdam. The update on line 17 uses $\mathbf{d}_t$, but the Adam lines only compute $\tilde{\mathbf{d}}_t$.

Questions

- Do the adaptively selected filter coefficients from Section 5.3 have the same convergence guarantee? - Did you experiment with adaptively selected filter coefficients from Section 5.3? - Why does the performance of LP-DPSGD drop with larger epsilons when fine-tuning on CIFAR-10 in Figure 10?

Rating

7

Confidence

3

Soundness

4

Presentation

3

Contribution

4

Limitations

The paper clearly mentions the most important limitations of the work.

Summary

This paper augments DP-SGD with a low-pass filter-based postprocessing on the iterates of DP-SGD. This design is based on the intuition that the noise contributes more to the high frequencies, while the gradients (assuming sufficient smoothness of the objective) contribute more to the lower frequencies. The paper gives a theoretical convergence analysis, showing an improvement corresponding to a signal-to-noise ratio factor depending on the gradient auto-correlation. Importantly, precise knowledge of the gradient autocorrelation is not needed to run the algorithm, but it helps design better filters. The paper also shows broad empirical improvements from the proposed techniques in the vision setting.

Strengths

- A strength of the proposed method is its simplicity: it gives a simple add-on to the iterates of DP-SGD. It includes momentum as a special case but allows for more sophisticated running averages of the gradients. - The paper is well-written: the main idea comes across easily (although clarity can be improved; suggestions to follow). - The theoretical analysis looks sound. - I think the presented results are significant: The experiments demonstrate a clear win from the proposed approach. They also nicely corroborate the intuition behind the auto-correlation of the gradients vs. noise. - The first-order filters that work quite well empirically only need a modest additional storage cost (two extra buffers) over DP-SGD.

Weaknesses

While I really like this paper, my opinion is that it is currently lacking in some aspects. Given below are some suggestions to improve the paper along these dimensions. 1. Error bars: DP is a noisy process, so it would be good to see error bars across multiple repetitions of the experiments. This is especially important since the gaps appear to be small. Further, it would be good to see the final accuracies for the vision experiments in a table as it is hard to judge how much the gap between the proposed method and baseline is. 1. Autocorrelation assumption: The general form of Assumption A4 is quite natural given the intuition developed in the preceding sections. However, it is not clear why $c_\tau$ is unconstrained while $c_{-\tau}$ is required to be non-negative. This looks like a trick for the proof to go through but further justification and empirical evidence (potentially in toy problems) are necessary. 1. Clarity: There is much scope for improvement to make the paper more reader-friendly (especially for those unfamiliar with signal processing). Examples: - A review section in the appendix recapping the basic ideas of the signal processing tools used (in the appendix) - Example coefficients used in typical low pass filters on page 5, and the kinds of weighted averages (the $\kappa_\tau$ coefficients) they would lead to. Also, a few figures to visualize the types of filters that work well with different types of auto-correlations could be helpful. - Theorem 2 could be restructured to make it easier to parse. A lot of quantities are used before their definitions. - The partial fraction decomposition of eq (7) is not guaranteed to be real. It would be worth clarifying that complex coefficients are allowed. Also, how are the $\kappa_\tau$ coefficients are real? - What constraints are necessary on the filter coefficients so that the $\kappa_\tau$ coefficients define a proper weighted average (i.e. non-negative and sum to one)? 1. Parameter tuning: How are the filter coefficients tuned? It is only mentioned that the choices are ``empirical'' in Line 298. Ideally, for momentum SGD, we would tune the momentum and learning rate together; I would expect that tuning the filter coefficients and learning rate together would help. 1. Originality: the proposed approach is a straightforward application of classical ideas from signal processing to private optimization. While this can be viewed as a strength, I would have liked to see a more detailed investigation into the use of low-pass filters. For example: - An empirical investigation of the proposed adaptive filter. - A detailed empirical study on the choice of the filter coefficients. Only 3 different choices are explored (apart from DP-SGD and momentum), but it would be good to see the effect of changing filter coefficients for a first-order filter. - A plot of the performance vs. the order of the filter. - Some investigation on observed auto-correlation vs. choice of filter coefficients. 1. Minor comments and Potential typos: - what is $t$ in lines 263 and 265? - Top of page 13, in equation (c): should $\kappa_\tau \| \nabla F(x_{t-\tau})\|^2$ be $\kappa_\tau^2$ instead? - Top of page 13, eq 10: Extra $+$ sign between $\frac{L\eta^2}{2}$ and what follows.

Questions

1. It would be nice to have a more detailed comparison to correlated noise approaches for DP optimization e.g. [KMST+](https://arxiv.org/abs/2103.00039) or [DMRST](https://arxiv.org/abs/2202.08312). For instance, can those approaches be interpreted as some filtering of the noise? Also [CDPG+ (Fig. 1 right)](https://arxiv.org/abs/2310.06771) appear to use a high-pass filter on the noise for DP optimization. This seems to be similar in spirit to the proposed low-pass filter approach and a detailed comparison would be nice. 1. There is no batch size factor in the privacy-utility tradeoff of Theorem 3. How? 1. How does the low-pass filter work on the iterates of DP-SGD instead of the gradients? For instance, it is common to obtain a sequence $x_1, x_2, ...$ from SGD but use the average $\frac{x_1 + \cdots + x_t}{t}$ for inference. I wonder if a sophisticated average from the low-pass filter can help for inference alone (without using it for training).

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes, but a more detailed empirical investigation would be good, as detailed above.

Summary

This paper suggests the effects of a low-pass filter for private training with DP-SGD. After investigating the noise and true gradients during training, the authors propose using previous gradients and momentum to distinguish effective gradients from random noise. They empirically prove their idea across various settings, including different optimizers and datasets.

Strengths

• The paper presents a very simple and effective theory based on the optimization of DP-SGD and the similarities between gradients $\nabla F(x_t)$. • The authors investigate the optimization dynamics in terms of the frequency domain rather than the time domain. • The paper conducts experiments on various datasets and existing well-known optimizers, demonstrating the effectiveness of the frequency-aware optimization. • The authors establish an interesting relationship between SNR and frequency domain approaches.

Weaknesses

Please refer to the Questions section.

Questions

I will happily increase the score if the authors can address the following questions: • The authors use assumptions of bounded variance and gradient norm. However, these assumptions might not be true in real DP-SGD situations. The strong underlying assumption of the authors is that the whole-batch gradient directions are similar between timestamps $\nabla F(x_t)$ and $\nabla F(x_{t-\tau})$. This is widely known in GD settings, but it may not be obvious in SGD (and DP-SGD) settings. Can the authors provide evidence with mini-batch gradients $\nabla f(x_{t})$? [1,2,3] • Using a low-frequency signal typically requires the use of FFT and iFFT to distinguish patterns in the frequency domain. While I understand that the authors try to investigate the auto-correlation and PSD of gradients (as shown in Figure 1), I cannot agree that this approach is orthogonal to conventional approaches depending on timestamps. As the authors mentioned momentum, this approach seems somewhat similar to the learning dynamics of DP-SGD, rather than the frequency domain. The authors should clarify this issue. • There are some existing papers that investigated the use of previous gradients in DP-SGD that are missing from the discussion. [1] investigated the use of previous gradients and their momentum approaches for sharpness-aware training. They explored the correlation between previous private gradients and the current gradient during optimization. • For the momentum approaches, why don’t you use $\alpha$ and $1-\alpha$ for the popular setup in EMA? In the appendix, I saw that tuning both $\alpha$ and $\beta$ requires quite a large search space. I wonder if the effectiveness of your methods comes from the enlarged search space. Could you provide an ablation study for this search space? • The authors try to make a theoretical analysis (line 233), however, it may not be true in the real application. The learning rate of private training is much larger than standard training, where it cannot be lower than $O(\sqrt{1/\tau})$ as far as I know. [1] Explicit loss asymptotics in the gradient descent training of neural networks, NeurIPS 21 [2] Measurements of Three-Level Hierarchical Structure in the Outliers in the Spectrum of Deepnet Hessians, ICML 18 [3] Implicit Jacobian regularization weighted with impurity of probability output, ICML 23 [4] Differentially Private Sharpness-Aware Training, ICML 23

Rating

5

Confidence

4

Soundness

2

Presentation

4

Contribution

3

Limitations

The authors clarify the limitations.

Summary

This paper proposes DOPPLER mechanism to post-process DP gradients and reduce noise in them, before updating the model. The work makes an observation that, in frequency domain, there is a clear distinction between distribution of SGD gradients and DP noise; the earlier lies in a small window of lower frequencies while the latter is distributed uniformly over all frequencies. Based on this observation, the DOPPLER mechanism uses a low-pass frequency filters that filters all high frequency signals, and hence, most noise is filtered while only some of the useful gradient is filtered thereby increasing overall SNR. Paper presents theoretical connection between SGD gradients and DP noise in the time and frequency domains, privacy analysis and empirical evaluation on standard benchmarks to showcase efficacy of DOPPLER.

Strengths

- Interesting signal processing perspective for DP optimization problem and observation about gradients and noise in frequency domain - DOPPLER is a post-processing method, hence can be used with SOTA DP methods - Experimental results show that in training-from-scratch settings DOPPLER is useful

Weaknesses

- Connection between time/frequency domains is difficult to understand; adding some background might be useful - Motivation of the paper is to enable DP training for large, foundation models, but experiments are performed on relatively small models - DOPPLER can be combined with any SOTA DP training, but results with such SOTA methods are missing

Questions

Section 3: - Can you provide some intuition about what does it mean to convert a series of gradients from time to frequency domain? It might be useful to have this somewhere (even if it’s in appendix) to help readers understand the approach better. - Line 167-168: In Figure 1a, auto-correlation coefficient first increases and then decreases with time, but description seems to state something else. Can you clarify? - Line 168-169: How do you compute PSD? How do you go from the first equation in Section 3 to drawing Figure 1b, 1c? - Line 187-188: Why can a linear low pass filter be written as in the first equation of section 3.1? Section 6: - What are the sizes of the models used? - Why do you not compare with SOTA methods, e.g., De et al. 2022 or Shejwalkar et al. 2022? Shejwalkar et al., Recycling Scraps: Improving Private Learning by Leveraging Intermediate Checkpoints, arXiv 2022

Rating

5

Confidence

3

Soundness

3

Presentation

2

Contribution

2

Limitations

- Proposed method, although motivated from enabling DP for large models, cannot be used for large models due to computation inefficiency. - Current set of results lacks depth and should be improved. - Paper writing/clarity can be improved (see questions/weaknesses). - Equations are not properly numbered.

Additional comment to Reviewer vvxz

> Detailed comparison to correlated noise approaches for DP optimization We would like to provide a detailed discussion between our method and the correlated noise method (KMST+, DMRST, and CDPG+) in this comment. As discussed in the above response, the update of correlated noise method can be written as $B(CG_{0:t}+W_{0:t}) = AG_{0:t}+BW_{0:t},$ where $B$ is a high-pass filter and our method is $AM(G_{0:t}+W_{0:t})$, where $M$ is a low-pass filter. **Connection:** The correlated noise methods and our proposed method can all be viewed as processing the signal in the frequency domain to "separate" the noise and the gradient. **Differences:** The existing correlated noise methods 1) pre-process the gradient/noise to separate the gradient and the DP noise in the frequency domain, and therefore require careful design of the matrices $B, C$ for each problem and optimizer, 2) require extra memory ($O(d\log(t))$ to $O(dt)$), which is unrealistic for large scale training, and 3) only work for SGD update, since Adam cannot be written as such a prefix sum of privatized gradient. In contrast, our method 1) post-processes the noisy signal to extract the gradient from the noise from the frequency domain, 2) only requires $O(d)$ extra memory, which is *independent* of $t$, and 3) is compatible with any first-order optimizer since it just post-processes the gradient.

Thanks for the response

I carefully read the rebuttal of the authors, including the general response and answers to my questions and those of the other reviewers. Although I thought some of the mathematical support was still limited, I understand the authors' novelty points and the experimental results of the proposed method. Personally, the authors effectively addressed the questions, including mine and those of the other reviewers. Thus, I have raised the score.