Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: The author proposes an algorithm that improves DPSGD by using public data to identify a lower-dimensional space where the gradients lie in. They show that the algorithm can provide a better convergence guarantee, specifically, p reduced to log(p). They also conducted experiments to show the proposed algorithm outperforms the generic DPSGD especially at small epsilon with a small amount of public data.

The topic of the paper is interesting, and the presentation is clear. I hope the significance of the paper can be better justified. On the theory side, I think it needs more comparison with prior work and needs a better explanation of some of the key concepts. On the experiment side, to make the results more convincing, it might be better to conduct evaluations on harder datasets.

Comments:

- In related work, it is said that "Kairouz et al. (2020) .... In comparison, our work studies both convex and non-convex problems and our analysis applies for more general low-dimensional structures that can be characterized by small γ2 functions (Talagrand, 2014) (e.g., low-rank gradients and fast decay in the gradient coordinates)". I believe Kairouz et al was operating on private data only and that might be a major difference. And it might still be interesting to compare the results in more detail, e.g. how do the bounds compare on convex problems, how do the two measurements of dimensionality compare.

- Line 4 of Alg 1: better to say \tilde{z_i} \in S_h than enumerating i from 1 to m (m is undefined in the algorithm).

- It is mentioned that if M is evaluated on fresh public samples at each iteration, then the deviation of M from Σ can be analyzed easily. I wonder if it worth discussing what would happen if partition the public data (given that we have more than T samples) into T disjoint subsets for each iteration. Would the tradeoff be worse?

- Since γ(M, d) is the main component in the analysis and the bound, can you provide more intuition and explanation of it, like how large it can get, on what kind of dataset it might be small/large, would model architecture make a difference etc.?

- A question regarding the experiment setup: I didn't quite understand why a subset of 10000, instead of (60000 - 100), of the original data is picked for training. 10000 is definitely a legitimate setting, but I just wonder if there is a reason for picking that number and whether the number of examples has any influence on the results.

- In the experiments in Figure 5, as k=50 (or 70) outperforms DPSGD without projection, it might make more sense to further increase k to demonstrate the tradeoff between the two types of errors.

- A minor point: Sec 4 said "Papernot et al. (2020) shows the accuracy of DP-SGD is around 80% when ε ≈ 1", which I'm not sure is accurate. I didn't find Papernot et at (in Table 4) reporting the accuracy for epsilon around 1. If the statement is referring to the leftmost point in Fig 3 of Papernot et al., I believe it is not a fair comparison. The figure basically showed a training process in terms of epsilon instead of steps, so the result is not optimized for epsilon = 1 (but is rather for epsilon = 2.93). On the other hand, the [tensorflow privacy tutorial](https://github.com/tensorflow/privacy/tree/master/tutorials) achieves 95% at epsilon = 1.19.
review_title: Review

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper proposes a new private SGD method by projecting the noise gradient onto a subspace, which is estimated using some public datasets. The proposed method can improve the utility guarantee by reducing the dependence of the problem dimension p. The idea of the proposed method is interesting, but the assumptions in the current paper seem to be very strong, and the evaluations in the current paper are not convincing to show that the proposed method is beneficial. 
1. It is not always true in practice that we can have access to the public dataset.
2. In Theorem 4, the assumption about the principal component of the gradient looks very strong. 
3. How will the size of the public dataset affect the performance of the proposed method? It is important to have empirical evaluations on this.
4. Another issue of the proposed method seems to be the computational barrier. Why can the proposed method only deal with 10000 samples in MNIST dataset compared with DPSGD, which can deal with the whole training dataset?
5. I think the most valuable thing about the proposed method is to reduce the dependence of the problem dimension p. Therefore, it is very important for the authors to consider larger models such as resnet. If the proposed method can achieve better performance on larger models, I think the proposed method is very convincing. 

-----
After reading the author response and other reviews, most of my concerns have been addressed. I would like to increase my score to 6. It would also be interesting to compare the performance of DP-SGD and PDP-SGD when $\epsilon$ is relatively large as suggested by Figure 7.

review_title: New private SGD method to improve the utility

final_score: rating: 7: Good paper, accept
review_content: The paper considers the problem of solving differentially private empirical risk minimization. To reduce the dependence on dimensionality $p$, they propose Projected DP-SGD (PDP-SGD) that projects the noisy gradients to a low-dimensional subspace computed from a free public dataset at each iteration. They prove that PDP-SGD is differentially private and has only a logarithmic dependence on $p$.

Pros:
1. The paper is well written and easy to follow. 
2. It is very appreciated that authors analyze both convex and non-convex cases. All proof seems correct except for a minor mistake mentioned in the next part. What’s more, The method of uniformly bounding $\|M_t-\Sigma_t\|_2$ by generic chaining techniques may be an independent interest. 

Cons and some discussion: 
1. The establishment of (28) requires $u$ is larger than a constant (like 3), even though this would not affect the correctness of Theorem 2. The last inequality of (55) should be equality.

The main concern of mine is that the experiment part is not so good as the theoretical part. 

2. The authors propose to reduce dimensionality by projection. The projected space varies for each iteration and is computed from a public dataset. However, I think the author didn’t explain well the necessity of using an extra dataset. If reducing dimensionality is the most important, why not just use a random projection. [1] shows that a Johnson-Lindenstrauss transform preserves differential privacy, so it is natural to use random projection as a baseline (at least in experiments). However, the baseline considered in experiments excludes this easiest method. Besides, it is better to add non-private SGD as a baseline, which would help illustrate how the proposed method degrades accuracy.
3. The proposed method has a huge space complexity and computation complexity as it requires to formulate $M_t \in \mathbb{R}^{p \times p}$ and compute its top-$k$ eigenvectors at each iteration. It will require $O(p^2)$ space and $O(p^3)$ times. As a remedy, one may hope to reduce the frequency of eigenspace computation. It seems to make sense, since when $w_t$ starts to converge, the difference between consecutive $w_t$ is so small that the difference between consecutive $V(w_t)$ is also small, implying we can reuse the eigenspace estimated in the last iteration. It strikes me that it is better to explore such a heuristic method in experiments to further illustrate the usefulness of the proposed method.
4. I think more datasets should be considered. The author only considered two image datasets. Real datasets like CIFAR can be considered. 

[1] Blocki, Jeremiah, et al. "The johnson-lindenstrauss transform itself preserves differential privacy." 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science. IEEE, 2012.



------------------------------------------------------------------------------------------
I have read the authors’ rebuttal. The authors have addressed most of my concerns. The JL random projection baseline has been added and the heuristic method of reusing the eigenspace for some iterations has been explored, which I appreciate a lot. From the current experiments, the proposed method seems effective, though it will be more convincing if the method can be tested on larger models or harder datasets. 

I think the topic of the paper is quite interesting and the idea of bounding $M_t - \Sigma_t$ uniformly is also interesting. The theory indeed manifests the effectiveness of the proposed method. As a result, I increase my point to 7.
review_title: Good theorem but experiments limit

Meta-review: Based on the observation that the stochastic gradients for deep nets often stay in a low dimensional subspace, this paper proposes projected differential private SGD (DP-SGD) that performs noise reduction by projecting the noisy gradients to a low-dimensional subspace. Under certain assumptions, the authors provide a theoretical analysis and empirical evaluations to show that the proposed algorithm can substantially improve the accuracy of DP-SGD in the high privacy regime. There is unanimous support to accept this paper after the author’s response. Thus, I recommend accept.
Decision: Accept (Poster)