Venue: NeurIPS 2022 Conference

Reviews:

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: This paper studies the privacy loss of noisy projected stochastic gradient descent. More specifically, the authors show that after some iterations, noisy projected stochastic gradient will not cause further privacy leakage if we only release the last iterate of the algorithm. This result looks very interesting and promising for private convex optimization.
strengths_and_weaknesses: Strengths:
1. The authors provide a new privacy analysis for noisy projected stochastic gradient descent when optimizing a convex, Lipschitz, and smooth objective with a bounded parameter space.
2. The new privacy loss upper bound shows that noisy projected stochastic gradient descent will not cause further privacy loss after a certain number of iterations.

Weaknesses:
1. It is unclear how this result can be used to study the utility guarantee of noisy SGD. According to Bassily et al, 2019, the original private analysis can achieve the optimal utility guarantee for noisy SGD, and thus it is unclear how we can make use of the new privacy analysis.
2. One drawback of the current analysis is that we can only release the last iterate.
questions: I think the result of the current paper is very interesting, and my main concerns are as follows:
1. How to make use of the new analysis to better understand the utility of noisy SGD.
2. The new analysis seems to be limited to noisy projected SGD. However, in practice, people often clip the stochastic gradient and then add noisy, and how can this analysis help us to understand the privacy loss of the widely used clipped based method? In other words, whether practitioners can benefit from your analysis in practice to apply noisy project SGD?
limitations: Yes
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: This work proposes an asymptotic privacy bound analysis when $T$ is large in Noisy SGD (SGLD) for convex functions. The results show when the number of iterations $T$ increases at the start, the privacy decreases at a linear rate. After a burn-in period, the privacy is bounded by a constant, and running SGD longer leaks no further privacy.  Some techniques based on PABI are also proposed in the analysis. The work also shows the tightness with a lower bound construction based on the trace analysis of random walk, which makes the proposed magnitude more convincing.
strengths_and_weaknesses: Pros:
1. The paper discusses the core problem in the Noisy-SGD analysis and provides a new asymptotic viewpoint for the privacy bound. Some new techniques are also proposed for the problem 
2. The paper is well-organized and some important points and proof sketches are shown in the main context with the detailed proof in the Supplement.
3. Good and detailed sketches for the existing Noisy-SGD analysis.

Cons:
1. The paper only discusses the function for convex cases, which simplifies the difficulties for analysis. More works might focus on the analysis in non-convex cases (like deep networks).
2. The paper lacks some numerical studies to give more insights and verify the performance of the proposed framework.
questions: Some questions:
1. Can the proposed framework be extended to the bounded non-convex function with a regularizer, like [Li et al, 2019] for SGLD (Also mentioned in [Chourasia et al. 2021]).
2. How can the proposed bounds be used/ help the cost minimization and privacy mechanism design?
3. How a $D$ determined for the real cases? Is $D$ related to the dimension and the convergence of the convex problem? Will the convergence influence the privacy level?


Some suggestions:
1. Some simple examples/numerical studies can be provided to show the effectiveness of the proposed framework more intuitively.

limitations: The assumptions have been discussed in detail, showing the limitations of the work.
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: In this paper, authors show that running DP-SGD for a convex function on a bounded domain converges to a bounded privacy cost opposed to the classical composition results that grow to infinity as the number of iterations grow. Similar to Chourasia et al. 2021, authors assume that the internal state (i.e. the intermediate parameter values) are kept private and only the final iterate is released. Authors build a novel analysis, where they split the the parameter trace in two halves and analyse the privacy cost of these halves separately. This involves finding a new improved privacy amplification by iteration (PABI) result. Authors also present a lower bound result for the privacy guarantee.
strengths_and_weaknesses: The main result of the paper (the upper bound) is a significant finding. Although, Chourasia et al. 2021 already showed this type of behaviour of the privacy cost for an iterative algorithm, this paper presents following significant updates to the result of Chourasia el al; extending the result for subsampled GD (preferable for computational reasons), and replacing the strong convexity assumption with just convexity. 

Authors have done significant amount of original work to solve the question at hand. The proof of main theorem (Thm. 3.1) comprises of many novel techniques and results, such as the new PABI result. I think the main limitation of the result is the assumption of limited search domain. However it is not a too strong of an assumption, and I think there are several real world problems that do have a priori known limited optimization domain.

To me, the most apparent weakness of the work is the presentation. The supplement included in the submission seemed like a (almost) perfectly good journal version (~19 pages) of the article, and was really pleasant to read. However, the cut down version is way too crowded currently. I do appreciate authors efforts to have the most crucial bits in the main paper, but I think the paper needs even more polishing and moving less important stuff to the appendix to make it to the NeurIPS format. And I'm afraid that it is going to be really difficult given the amount of material this paper contains.This lack of space also gives the paper a really abrupt ending with no discussion or conclusions. 
questions: I don't have much to ask, since I found the proofs quite easy to follow. Couple of very minor things that caught my eye:
- Lines 303-304: "Notice also that this bias term is only realized with probability 1 − b/n because the probability that i∗ is in a random size-b subset of [n] is b/n.", maybe I miss something, but I thought the noise is realized w.p. b/n
- The bound in beginning of page 14 of supplement: I do understand that if you set $R=\tilde{T}$, the summands inside the $\min$ get equivalent and with larger $R > \tilde{T}$ the latter term gets smaller and and former grows. However, I'm not quite sure, how do you form the last inequality. It almost seems like you only have the second term of the summand in the final expression, and the first has vanished somewhere.
- I'm curious, could one use some adaptive step-size schemes like Adam with this final iterate release analysis? Or would the Adam cause some sort of side-channel privacy leak through the last gradients it uses in adapting the step-size?
limitations: There is not much discussion of the limitations, probably due to lack of space. I guess the authors could further discuss the limitations that the assumptions make. For example the assumption of bounded domain.
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: The authors show that Noisy SGD achieves a privacy loss that does not grow indefinitely in the setting of convex optimization with smooth Lipchitz functions over a bounded set. The proof technique relies on privacy amplification by sampling and on amplification by iteration. Additionally, the authors also show a lower bound showing that the upper bound is tight up to a constant.
strengths_and_weaknesses: Strenghts: Paper is well written, easy to read, provides enough background on the problem and a good literature review. The result is also pretty cool since it shows that previous upper bounds for the privacy loss, where privacy scales indefinitely, exhibit the wrong qualitative behavior.
It looks like the only similar results (a bounded privacy loss) only hold in the case of smooth and strongly convex setting, so being able to relax strong convexity is significant. 
Weaknesses: I don’t have much to say here, I think it is a good paper.
questions: No questions
limitations: NA
review_title: null

Meta-review: metareview: The paper solves a longstanding open problem of showing bounded privacy loss for releasing the last iterate of noisy SGD for convex problems This improves upon previous work by going from GD to SGD and strongly convex to convex. All reviewers agree this is a strong paper and should be accepted.
confidence: Certain
Decision: Accept