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: This paper extends the last-iterate analysis to DP-SGD on strongly convex and smooth loss functions. The main contribution, compared the similar analysis GD, is to take two kinds of amplification into account: 1) post-processing by adding Gaussian noise; (2) sub-sampling. The empirical results show that the proposed methods outperforms composition-based algorithms.
strengths_and_weaknesses: This paper makes a solid step towards last-iterate analysis for DP-SGD. Although there is some space for improvement, I believe the paper surely passes the bar for acceptance.

Strength:
1. Last-iterate analysis is a very important direction to further improve privacy-utility trade-off for DP-SGD. The authors manage to augment the previous analysis for GD with amplification by post-processing and sub-sampling, which is a solid contribution.

Weakness:
1. The paper is not well written enough. There is huge space for improvement on the organization of the sections, the section names and the way to present the contributions. For example, even with some background knowledge, the titles for section 4 and 5 are somewhat confusing at the first glance for me. I suggest merging 4 and 5 into one section because they are actually two steps in one proof. There are also some sentences that do not read well (e.g. Line 109). Uppercase and lowercase letters are not used in a universal way in section titles. Some citations are outdated. For example, Tramer and Boneh 2022 are accepted to ICLR 2022 but the cited one is still the arXiv version.
2. Table 2 does not report what kind of clipping is used? Also the number of iterations used in the experiments are not reported.
3. Although hyperparameter tuning is typically not taken into consideration when counting privacy budget, the authors should still expose the details of their hyper-parameter tuning process.

questions: 1. Seems the only reason to assume strong convexity is for the Lipchitzness and utility result? Can we just assume Lipchitzness for the privacy guarantee? Please correct me if I miss anything.
2. How does the results in the paper compare to a parallel work "Langevin Diffusion: An Almost Universal Algorithm for Private Euclidean (Convex) Optimization"?
limitations: 1. The writing is not good enough.
2. Many details of the evaluation is missing.
review_title: null

final_score: 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.
review_content: summary: The paper focuses on improving the privacy analysis of DP-SGD. The paper studies the privacy guarantees when only the last iterate is released. The paper's main contribution in this particular setting is to provide tighter privacy bound for strongly convex loss functions. Finally, the paper provides an example of a classification task where a tighter privacy analysis leads to improved accuracy compared to when composition-based privacy analysis is used.

Overall, I think this is an extremely important result and strongly recommend the paper be accepted.
strengths_and_weaknesses: 1) The main result has significant practical implications on differentially private machine learning training.
2) There are many similarities with [14]. Perhaps a minor weakness of the paper is that it isn't entirely clear what are the technical challenges the authors had to overcome to complete the analysis, which were not already addressed in [14].
questions: 1) Could authors comment on the privacy-utility tradeoff when the average of iterates is used instead of the final iterate as the output of the SGD algorithm?

limitations: Yes.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This work improves the analysis of the last-iterate privacy bound which assumes the internal state of the algorithm is not revealed. The new analysis derives a privacy loss that grows slower than the one derived from the composition theorem if the network converges slowly or is trained for multiple epochs.
strengths_and_weaknesses: I have a basic understanding of the theoretical part of this work but didn't go deeper into the proofs, for me the strength and weakness of this work are:

Strength:

So far DP learning still suffers from dramatic performance loss compared with non-private learning, tailored and tight privacy bound can help reduce the required noise under certain privacy budgets and improve the performance.

Weaknesses:

1. This work extends the study of last-iterate privacy bound by considering mini-batch gradient and privacy amplification by subsampling, etc.. To apply the new analysis in practice, many assumptions have been made, which may not be satisfied when training a real network, so I expect the resulting network obviously outperforms others, so far it's not, perhaps a tighter bound is needed.

2. I am a little confused about the evaluation of the proposed privacy analysis. I see the baseline performance given in this work is lower than in its original work. For example in the experiment on CIFAR10, ScatterNet can actually obtain an accuracy of 69.3\%, ResNeXt-29 can achieve 80.0\%, SIMCLR can achieve 92.7\%, all are on par with using the method proposed in this work.
questions: Q1: Although the idea of sparing privacy by hiding internal states looks interesting, many assumptions have been made for the analysis, which could be broken in practice and thus breach privacy, on the other hand, the evaluation does not show the proposed method obviously outperforms the composition theorem (as described in Weakness), thus one may lack the motivation for using the proposed method and taking a risk.

Q2: I don't know how the hyperparameters are tuned, but since the privacy loss of the last-iterate analysis becomes flat after multiple epochs of training, perhaps longer training will make the results of the proposed method better.
limitations: N/A
review_title: null

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: In this paper, authors extend recent work in convergent privacy cost of convex optimization to subsampled gradient descent (GD) setting. Authors show, that for strongly convex Lipschitz loss functions, the privacy cost of releasing last iterate of DP-SGD does not grow to infinity as the number of epochs grows, but that there is a finite upper bound for this loss. Authors present a novel privacy analysis that builds on top of recent work by Chourasia et al. 2021, and is able to capture the privacy amplification by subsampling. Finally, authors demonstrate empirically how the reduced privacy cost improves the prediction accuracy of logistic regression model learned under DP.
strengths_and_weaknesses: In many applications, the intermediate steps of DP-SGD are not needed, but are released which causes the privacy cost of these types of release schemes to grow as the number of iterations grows. In this paper, authors continue the research in direction of releasing only the last iterate and quantifying the privacy amplification due to keeping the internal states secret. More specifically, this paper extends the work by Chourasia et al. 2021, who proposed a bound for the privacy cost for DP gradient descent algorithm. As the GD algorithm is often computationally expensive, authors take the natural next step and quantify the privacy cost of stochastic GD. Authors show several novel theoretical results (mainly Thms 4.2, 4.3, 5.2 and 5.3), that are based on novel privacy analysis, capturing the privacy amplifying effect of subsampling. The new privacy bound is significantly tighter than the privacy bound of Chourasia et al. that does not capture the subsampling amplification.

I also think that the paper is generally well written, and after couple of reads the story and the contributions become very clear. There are some parts that I think could be further clarified, and I will add those to the questions section. 

The most significant limitation of this work must be the assumptions on the loss function. The strong convexity and the Lipschitzity rule out quite a few applications of DP-SGD. However, I still believe that the paper makes significant contributions that will be beneficial in the future works on convergent bounds of DP-SGD.
questions: Typos:
- Lines 108-109: sentence inside parenthesis seems bit odd. Also, missing capital letter after period as in ". then"
- Thm 5.2: I guess K>=1 being mentioned twice is a typo.

Some questions:

- When you say "fixed sequence of minibatches", does this mean that the minibatches are the same across the epochs? As in $B^j_k = B^j_l \, \forall k,l \in [K]$? I just want to make sure that I understand the difference in the contributions of Sections 4 and 5. So Sec. 4 builds the theoretical background under the assumption that the sequence is fixed and Sec. 5 then extends this to actual subsampling scheme?

- In beginning of Sec. 4, it sounds like you say that you focus on the case where the adjacent index is not accessed by Alg. 1. This seems weird given the theoretical contributions of this Section, e.g. Thms 4.2 and 4.3. Maybe it is a typo? Or did I just misunderstand your point.

- Out of curiosity, could you use some learning rate adaptation like Adam under the last iterate release scheme? I wonder would it cause some side-channel privacy leak through the gradient history it uses to update the learning rate.

- Maybe I missed something, but after Thm 5.2 you mention that the bound is tighter than composition based after $4 \cdot \frac{1}{\lambda  \eta} + 4 \cdot \frac{n}{b}$ epochs. You justify this by saying, that the parts leading to this bound are smaller than the composition based one after $4 \cdot \frac{1}{\lambda  \eta}$ epochs and $4 \cdot \frac{n}{b}$ epochs. Now, I wonder, why cannot you just pick the max of these and say that the both parts are majored with the composition based after these many epochs. Of course the sum of the terms also works, but I was just curious if there is a reason not to use $\max(4 \cdot \frac{1}{\lambda  \eta}, 4 \cdot \frac{n}{b}) \leq 4 \cdot \frac{1}{\lambda  \eta} + 4 \cdot \frac{n}{b}$?
limitations: I think the limited use cases due to assumptions on the loss function could be further discussed. Negative societal impact is not discussed in the paper, but I believe the paper is purely theoretical and does not have direct negative impacts.
review_title: null

Meta-review: metareview: This work shows that for strongly convex and smooth loss functions, running DPSGD has a privacy cost that stops growing at some point. The answers a question that has been open and is of significant theoretical and practical interest. They show empirically that this new result can allows one to get better privacy-accuracy trade-offs in some cases.
This work is a big step ahead in analysis of DPSGD and I recommend acceptance.
confidence: Certain
Decision: Accept