Venue: NeurIPS 2022 Conference

Reviews:

final_score: 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.
review_content: summary: The paper proposes a new privacy-preserving algorithm and proves convergence guarantees on the existing differentially private normalized SGD algorithm and the variant proposed in the paper. The new variant of sensitivity reduced normalized sgd achieves better convergence guarantees on smooth non-convex problems than previous algorithms. The improvement comes from using tree-aggregation technique that reduces the amount of noise needed to make partial sums differentially private.
strengths_and_weaknesses: Strengths:
1. The paper uses the tree-aggregation technique to propose a new technique that achieves better error guarantee on smooth, non-convex objectives than prior works (although the dependence on the dimension $d$ and $\epsilon$ is worse).
2. The paper presents a new analysis of differentially private normalized sgd which achieves same error rates as previous papers, without needing any privacy amplification techniches or needing full batch gradient descent which were needed in previous papers.


Weaknesses:
1. Although the error dependence of algorithm 2 on N is better, the dependence on d and $\epsilon$ is worse for the new algorithm.
2. The paper admits that runtime is worse for the new algorithm is proportional to $N^{11/3}/d^{2/3}$. Even in the regime when $N$ is proportional to $d$, this is $N^3$. Also, number of steps needed by algorithm 1 is proportional to $N^2$. Both of these numbers are large, but the $N^3$ runtime of the new algorithm is particularly problematic.
3. The paper admits that it is not obvious that privacy amplification by shuffling can be directly applied to their tree-aggregation based method.
4. The paper does not have any experiments showing the convergence properties of the new algorithm. I understand that this is a theoretical paper, but some small scale experiments would be nice to better gauge the algorithm.
questions: Lines 103-111: Since the noise is being added to each gradient to make each of them differentially private, and the gradients in an epoch come from different samples, even after summing the gradients in an epoch, I think the differential privacy for each sample will remain  $(\epsilon/\sqrt{t}, \delta/t)$. I think the composition rule applies when the gradients are from the same sample, but here since a sample will not be seen until the next epoch, the differential privacy guarantee does not reduce. Is the paragraph explaining the case when gradients are coming from the same sample (that is, GD instead of SGD)? Can the authors clarify this?


Typo in Algorithm 1: step size is missing in the statement $w_{t+1} ← w_t − m_t/\|m_t\|$
limitations: .
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposed a few new algorithms for private ERM. The key idea of the new algorithms is using tree aggregation in momentum normalized SGD from Cutkosky and Mehta, 2020. The proposed algorithms can achieve better convergence rate than the existing method.
strengths_and_weaknesses: Strengths:

1. The idea of using tree aggregation for momentum seems to be quite novel in the field. 
2. The proposed algorithms can achieve better convergence rate.

Weaknesses:
1. The proposed algorithm seems to require a larger memory to store some tree aggregation nodes.

questions: The results looks quite solid to me. One question I have is why to use normalized SGD as the base algorithm, could the authors elaborate more on it?
limitations: Limitations are well-discussed.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposes the use of momentum techniques in conjunction with the tree aggregation framework in differential privacy to obtain better rates for differentially private stationary points for the empirical loss. This problem has got recent attention in the literature, and all existing rates are slow ($O(d^{1/4}/\sqrt{N\epsilon})$) and require high running time. This paper focuses on both aspects, first providing algorithm with the above rate but with better running time, which is primarily based on noisy SGD with momentum (which crucially makes use of tree aggregation). And second, providing a sharper rate of $O((d/[N\epsilon]^2)^{1/3})$ for this problem (gradient complexity of the method is $O(N^{7/3}\epsilon^{4/3}/d^{2/3})$, but running time is actually at least cubic in the sample size). This is achieved by the use of a recursive gradient estimator, for which its terms have low sensitivity due to the small displacement of iterates, together with smoothness of the loss. 
strengths_and_weaknesses: Strengths:

1. This is a definite improvement upon the state of the art.
2. The problem is of key relevance in differential privacy and  machine learning.
3. At the technical level, the algorithms do not require privacy amplification techniques, although they use multiple random shuffles of the data, which is somewhat baffling. Regarding this last point, I wonder whether the shuffling is necessary at all: I suspect this can be circumvented using analyses of incremental SGD, such as Nedic, Bertsekas (Incremental subgradient methods for nondifferentiable optimization, SIOPT 2001).

Weaknesses:

1. The improvements seem to be marginal, compared to existing literature.
2. Regarding algorithmic performance it is arguably more interesting to understand the out of sample performance of the algorithm. 
3. The technique of recursive gradient estimation, used particularly in the second method, is already well known (see e.g., BGM'21 paper cited, and also Bassily, Guzman, Nandi 2021: "Non-Euclidean Differentially Private Stochastic Optimization"). The paper does not reflect this fact in its presentation. The main difference between the current submission and past work is that in the current paper this is analyzed for multiple passes on the data, which adds another layer of complexity into the analysis.
4. The paper contains typos and some small inconsistencies which make reading difficult.
questions: 1. Line 120:  The notation of the samples in the dataset from $x$  to $z$ is confusing, as $x$ already been used for data points. Maybe they should avoid summing intervals $[x,y]$ and prefer denoting intervals as $[y,z]$. This applies to other parts of the paper where this notation is used. 
2. Page 4, line 143: an extra 'in' after m_t. 
3. Page 4, equations after line 143. I find confusing that the sum in the second equality goes from $x+1$ to $y$. Does this mean that e.g., when $x=y$ we get an empty sum? BTW, it would be highly beneficial that, before unraveling the formula for $m_t$, the recursion $m_t=(1-\alpha)m_{t-1}+\alpha \nabla f(w)$ is introduced. Also there is a typo: w'_t should be w_{t'}. 
4. Algoritm 1, page 5. It is never said (only in the appendix) what $S_i[1]$ is. Besides, the '$b-(S_i[1])$' I think should be '$t-(S_i[1])$'. 
5. Algorithm 1, when generating the noise map $Z$, shouldn't it be $\chi_{[a2^b + 1 : (a+1)2^b]} and Z[a2^b + 1 : (a+1)2^b]$? 
6. Page 5, line 157. $f_{[x,y)}$ should be $f_{[x,y]}$?
7. Page 5, line 161: $q$ is used to indicate the data point that is different on the neighboring datasets, but $q$ is already been used to indicate the epochs in the algorithms. This is not a mistake, but please consider a different notation. Other repetitions of use in notation (e.g. for $R$) are present throughout, which make reading quite confusing.
8. Page 7, Algorithm 2. $q_i$ is defined in the third line, but when it is actually used, it should be q_t instead of q_i, and indeed I think one could simply use '$q$' since It is defined by $t = qN + r$. 
9. Page 7, Algorithm 2. I couldn't follow why there are two types of noises, depending on whether $t\leq 2N$ or larger. Is there a fundamental reason for this? I am also confused about the fact that the algorithm seems to rebuild all estimators from scratch every time they are needed, and then new noise is added to them. In this sense, it is not entirely clear to be that the privacy analysis here is accounting for all these repeated noise estimates. I would think it's easier and more natural to reuse the privatized terms from previous iterations, but possibly I am missing something here.
10. Page 7, line 196: should be an N instead of T in the rate? 
11. Page 8, equation (2). Correct $G_{[1:t]}$ and $\alpha_{[1:t]}$ by $G_{[1,t]}$ and $\alpha_{[1,t]}$.
12. Page 8, equation (3). What is $r$ here? There could be multiple choices for it. Also, the notation is confusing, because of the use of $r_{[a,b]}$. I think it would be easier to understand the decomposition if they explicitly say that they are considering $t = qN + r$. 
13. Equation (4) after line 551: Should Compose(t) be Compose[1,t] instead?
14. Line 472: $F_i$ should be $G_i$? 
15. Line 492 and Appendix C in general: sometimes the bold notation of the functions $f_i$ is dropped.  Even in algorithm 5 f_1 is not written in bold but the rest iterations are. 
16. Proof of lemma 11 (below line 564), in the first inequality there is a term $(1-\alpha)^t$ that should be $(1-\alpha)^{t-i}$. However, it is correct it in the next inequality. 





limitations: Yes. Limitations on running time and possible additional improvements are discussed. It is not discussed though how far from tight the obtained upper bound is, which I think it is an important consideration.
review_title: null

Meta-review: metareview: The authors obtain improved guarantees for differentially private smooth, non-convex empirical risk minimization. Following the discussion stage, there appears to be a consensus in favor of accepting this paper, due largely to the clear theoretical improvement and the fundamental nature of the problem. However, reviewer nfxU, who remains unenthusiastic about the paper, is still concerned about lack of clarity regarding a number of algorithm design choices: the necessity of making the entire optimization trajectory DP, whether or not the magnitude of noise changes between steps, and whether shuffling is the data is truly necessary. While these points do not cause direct concern over the correctness of the results, they are nevertheless important to clarify, and I urge the authors to do so thoroughly in the camera-ready revision. 
confidence: Less certain
Decision: Accept