Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: Differentially private stochastic gradient descent requires clipping the gradient computed on each example before aggregation. That is, we compute the 2-norm of the gradient vector and, if it is too large, we scale it down. Surprisingly, this step entails a significant computational overhead relative to non-private stochastic gradient descent.
The reasons for this slowdown are not entirely clear to me. It seems to be a software issue deep in the bowels of TensorFlow and PyTorch -- somewhere between the Python and the Hardware this operation is poorly optimized.

This paper proposes to alleviate the problem by performing approximate, rather than exact clipping. Specifically, a Johnson-Lindenstrauss sketch is used to approximate the 2-norm of the vector instead of exactly computing it. This JL approximation can be computed more efficiently than the exact norm. However, there is a tradeoff between speed and approximation quality as we can alter the dimension of the JL sketch.

Technically, the most involved aspect of this work is the privacy analysis. Since the gradients are only approximately bounded, we cannot apply the usual analysis. This algorithm does not satisfy Renyi differential privacy as there is heavy-tailed privacy loss due to the possibility of drastically underestimating the norm. Instead an entirely new analysis is required based on the recent Fourier accounting approach.

Experimental results demonstrate that there is a significant improvement in runtime. However, the privacy parameters also degrade significantly.

main_review: This paper presents a novel approach to accelerating differentially private deep learning. This is accompanied by a thorough theoretical privacy analysis and an experimental evaluation. 

Computation is a significant bottleneck in practical implementations of differentially private deep learning. Thus the faster approach in this paper is valuable. However, it comes at the expense of a blowup in the privacy parameters. This tradeoff may be acceptable in some circumstances, but unacceptable in others. In any case, it is a good addition to our toolbox.

One thing to note is that the problem being solved is, as far as I know, a software issue, rather than a fundamental limitation. Thus the value of the proposed solution may disappear with a future version of the software.


A low level comment: Differentially private stochastic gradient descent predates the work of Abadi et al. I believe it was first introduced by Bassily, Smith, & Thakurta in 2014. Abadi et al. however were the first to do it in a practical setting.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 3: Clear rejection
review_content: summary: This paper presents a new algorithm to approximate per-sample gradient norms in DP-SGD using Johnson-Lindenstrauss (JL) projection. Experimental results were conducted on IMDb and MNIST datasets showing that the proposed approach is faster with the same memory footprint as the vanilla DP-SGD. 


main_review: Approximating the per-sample gradient norm is new and interesting. The paper presentation is clear and easy to understand. However, there is room for improvement.
Figure 3 shows that the proposed approach consumes an excessive privacy budget epsilon compared with the vanilla DP-SGD. In the low-value regime of privacy budget (tight privacy protection), it is unclear how the proposed approach can advance the vanilla DP-SGD. This is quite critical in practice since the trade-off between model utility and privacy loss in the low-value regime of the privacy budget is more significant. From that angle, the contribution of the paper is marginal.
An extensive study is needed to show the advantages of the proposed approach clearly. Larger datasets are needed since it is hard to draw a convincing conclusion only using the MNIST dataset.
Question: Whether all the algorithms in Figure 4 consume the same privacy budget given the same number of epochs? It appears that they do not consume the same privacy budget given the analysis in Figure 3. As a result, the comparison in Figure 4 is unconvincing.
limitations_and_societal_impact: The paper did not discuss limitations and societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers the computation and memory cost problem introduced by per-sample clipping in private gradient descent algorithms. To accelerate per-sample clipping, this paper proposed a new framework using JL projections to estimate the per-sample gradient norms. The authors provide rigorous differential privacy analysis of the proposed framework. They also give empirical evaluations of the proposed algorithms in terms of privacy, utility, and computation time.
main_review: Strengths:
 
- This idea of using JL projections to estimate the gradient norms and using Jacobian-vector product to accelerate computation is new. The framework is potentially useful for training large-scale neural networks. 
- This paper is technically sound. The authors discussed that each iteration of the proposed algorithm is not a Gaussian mechanism due to the estimated clipping norm. Thus, they provided rigorous privacy analysis for the new framework. 
- This paper is well written and clearly presented.

Weaknesses and some discussion: 
- The main concern is that the privacy bound provided in this paper of this framework is larger than that of the standard differentially private SGD algorithms as shown in Figure 1. I am wondering if the privacy bound or the numeric method to compute privacy can be improved?

- In Figure 3, If we further increase the projection dimension r to match the privacy level of DP-Adam, how does the computation time compare with that of DP-Adam/DP-SGD? Will DP-Adam-JL still require less computation time than DP-Adam?
 

Overall, I think this paper is above borderline. The significance can be improved by improving the privacy bound of the proposed framework, so I recommend borderline acceptance. 
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: To accelerate DP-SGD, this paper uses JL projection to approximate the $\ell_2$ norm of the per-sample gradients, which can be calculated during the forward pass efficiently. Moreover, the privacy analysis requires new techniques (convolving the privacy loss distributions using FFT) since the standard moment accountant cannot be used in this case.
main_review: - The proposed method does not explicitly compute nor store the per-sample gradients, unlike DP-SGD.
- The novelty and technical depth of this paper is limited.
- The experiments show that the accuracy of the proposed method may be worse than DP-SGD (see Figure 3). although much faster.
limitations_and_societal_impact: See above.
review_title: null

Meta-review: This submission makes significant time and memory efficiency improvements for differentially private SGD using random projections, at the cost of a worse privacy/utility tradeoff when compared with vanilla DPSGD as emphasized by one reviewer. The authors gave a compelling rebuttal however that despite this worse tradeoff, DPSGDJL still has value for fast hyperparameter tuning for private training. The contribution of this submission thus seems strong.
Decision: Accept (Poster)