Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper analyzes achieve trade-offs of privacy and utility for DP-ERM and DP-SCO via Langevin diffusion. Tight DP-SCO bounds for both convex and strongly convex are provided through the lens of algorithmic stability. For non-convex case, a lower bound is provided to show the impossibility of improvement from $\epsilon$-DP to $(\epsilon, \delta)$-DP.
strength_and_weaknesses: Strengths:
1. The main contribution of the paper is providing a framework based on Langevin diffusion to analyze privacy/utility trade-offs for DP-ERM and DP-SCO. 
2. Algorithmic stability is employed to provide the tight DP-SCO bounds.
3. The paper is well-written and solid in theoretical analysis.

Weaknesses: 
1. The comparison of tight bounds for DP-ERM and DP-SCO with related work is lacking(a table may can demonstrate the comparison better).
2. The theorems are fairly restrictive. (i.e. For Theorem 1.2, if $p \ll n$, the improvement from $p^2 \log(n)$ to $p\log(n) + p^2$ is limited; if $p \gg n$, the bound seems to be less meaningful. The assumptions for stability bound are required strongly convex and smooth, which are also strict. The choice of learning rate should satisfy empirical case and population case simultaneously.)
3. The experiment part is missing.
clarity,_quality,_novelty_and_reproducibility: This paper provides a framework for DP-ERM/DP-SCO with solid theoretical analysis, which may be applicable to other problems.
summary_of_the_review: Overall, I think the contribution of this paper is to employ Langevin diffusion to provide a framework to analyze the privacy/utility trade-offs, but it does not show a significant improvement compared with previous work. Additionally, the assumptions for uniform stability seem strict. However, it indeed provides a new thinking of analysis.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the differentially privacy guarantee, empirical risk bound and population risk bound of continuous time Langevin dynamics with tunable temperature and tuning time. For convex loss, the ε-DP result is cited from (Bassily et al., 2014). The ε-DP result for strongly convex function is derived for some iterated exponential mechanism similar to (Bassily et al., 2014). To derive the ε,δ-DP guarantee this paper uses Renyi differentially privacy as a sufficient condition. The Renyi divergence of two Langevin diffusions is derived using standard combinations of post processing theorem and composition theorem. 
The population risk for stochastic convex optimization is derived with uniform stability bound similar to (Hardt et al., 2016).
Combining these techniques, authors show various optimal bound under privacy guarantee in a unified model ,i.e. Langevin diffusion.
strength_and_weaknesses: Strength:

Although most techniques used in this paper exist in prior work, they are adapted to the specific problem considered here.
Combining these techniques, authors not only recover best known bounds, but also derive new results.
The collection of optimal bounds under various setting manifest that Langevin diffusion is indeed capable to serve as a unified framework to analysis empirical risk and population risk with privacy constraints.

Weakness:
The main weakness is that algorithms 2,3 in this paper are not actually algorithm, because sampling exactly from an Gibbs measure is generally not possible within finite number of operations.
Any implementation necessarily introduce a sampling bias which decrease with computation budget. For example, DP-SGD in (Bassily et al., 2014) uses a fixed step size.
It is still unclear how such bias interfere with bounds provided in this paper.

Another consequence of continuous model is that the effect of stochastic gradient error is totally ignored. For example, DP-SGD in (Bassily et al., 2014) uses a mini-batch for each iteration. However, in continuous time LD, all information of the whole dataset is used at every time point.

Given these mismatch between continuous time LD and real world algorithms, it is not clear how significant results in this paper is to the development of practical differentially private algorithms.

More specifically, it seems all improvement over existing results happens for ε-DP with $T=\infty$ (please correct me if I am wrong), thus it is hard to see whether the improvement is due to better algorithm design or a bonus of infinite computation power.

typos:

In eq 34, ε in denominator should not be square.
clarity,_quality,_novelty_and_reproducibility: The paper is in general clearly written.
There is no experiment.
summary_of_the_review: This paper present continuous Langevin dynamics as a unified approach to the problem of differential privacy. In particular, the bounds derived in this paper recover or exceed the best known bounds in the field. At the same time, the limitation of continuous dynamics and infinite computation budget raise questions on the practical significance.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper addresses differential privacy using the Langevin dynamic and claims to achieve the optimal utility-privacy trade-off for DP-ERM and DP-SCO. This paper provides bounds for excess risk on the \epsilon-DP-SCO. 
strength_and_weaknesses: Strength: 
- This is a very interesting problem to look at even though this is not the first time that DP is viewed through the Langevin dynamic. 
- Provides a comprehensive background on the topic. 
------------------------------------------------------------------------
Weakness: 
- This paper can be hard to follow. The main body of the paper is not self-sufficient and one should constantly go to the appendix to understand the paper. Perhaps it could have been a bit more organized. 
- This paper is way too long for a conference paper.  And it feels like the main contribution is lost in the notation and the amount of unnecessary information provided in the paper. 
- It feels like the main idea stems from one of the recent papers on the use of Langevin diffusion for DP (DP guarantees for SGLD by Ryffel), without having any sort of comparison for them. Notations, use of Renyi divergence and etc are borrowed from the same paper.
- Proofs seem to be correct as they follow the properties of LD and straightforward techniques in DP. 
- Due to the similarity of techniques (use of LD in this paper and the one by Ryffel), comparison/discussion on both these methods is required. Since some techniques are borrowed, how is this work different aside from being applied to ERM and SCO. Techniques seem to be very similar. 
- What can say about the sensitivity under the LD? 
- Are strong convexity a necessary condition? If this assumption was not made, how would the bound change?  
- I understand this paper is meant to be understood as theoretical but some practical implications of that could be helpful. 

clarity,_quality,_novelty_and_reproducibility: Paper is not clear at all and to be able to understand one should go back and forth and it feels like the contributions are lost. It somehow feels like it is written to confuse the reader. It is too long for a conference paper. This paper has some novel aspects even though some ideas are directly borrowed. The mathematical results can be reproduced. 
summary_of_the_review: This paper provides bounds on the DP-ERM and DP-SCO with the use of the Langevin dynamic. Seems like, with techniques borrowed from the literature, this paper provides bounds that claim to be "tight" specifically for \epsilon-DP.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies differentially private empirical risk minimization (DP-ERM) and differentially private stochastic (convex) optimization (DP-SCO). The authors consider the Langevin diffusion, which is a popular continuous-time algorithm, and show that Langevin diffusion has optimal privacy and utility trade-offs for both DP-ERM and DP-SCO under $\varepsilon$-DP and $(\varespilon,\delta)$-DP both for convex and strongly convex loss functions. They also obtain new uniform stability results for Langevin diffusion that are time and dimension independent. 
strength_and_weaknesses: The paper is a solid theory paper, and the authors have provided detailed and rigorous treatment in the relatively long appendix. The authors also seem to be quite familiar with the relevant literature. The topic is important and worth investigating. 

However, I have some concerns about the assumptions and especially how the paper is presented. 

(1) The assumptions are often confusing. For example, on page 2, when the authors introduce the problem description, one considers a constrained set $\mathcal{C}\subseteq\mathbb{R}^{d}$. However, it is not clear to me when $\mathcal{C}=\mathbb{R}^{d}$ and when it is a proper subset of $\mathbb{R}^{d}$. Moreover, if it is a proper subset of $\mathbb{R}^{d}$, what is the assumption on $\mathcal{C}$? For another example, the authors mentioned on page 3, that "Depending on the problem context, we make additional assumptions like $m$-strong convexity..." I am perfectly fine with this. However, it is not clear when you make such an assumption and when you do not. For example, in the statement of Lemma 1.1., you didn't mention the strong convexity assumption, so I suppose it is not used. But then, in Theorem 1.2., $m$ appears in the equation, does that mean you used this $m$-strongly convex assumption? If so, you should mention it. If not, you should mention what $m$ means in Theorem 1.2. 

(2) It seems that the paper is hard to read unless you go back and forth between the main body and the appendix. For example, in Theorem 1.2., it uses Algorithm 3, but you cannot find Algorithm 3 in the main paper at all. 

(3) Some of the assumptions might be too strong. For example, the authors assumed that the loss function is $L$-Lipschitz. That assumption is quite strong when $\mathcal{C}=\mathbb{R}^{d}$, because for the Langevin literature that I am familiar with, people usually just assume (strong) convexity plus smoothness, but not the Lipschitz assumption. If your $\mathcal{C}$ is compact, you need to make an assumption and make it clear in the main body of the paper. For instance, when I look at the statement of Theorem 1.3., it seems to me that $\mathcal{C}$ needs to be bounded. But when I'm looking at Lemma 1.1., I don't know whether you need assumption on $\mathcal{C}$ or not. 

(4) I am a bit confused with equation (2), about "Projected" Langevin diffusion on page 3. I understand that for Langevin algorithm on a constrained domain, you can project it back to the constrained set if the algorithm exits the domain. However, in equation (2), you are considering a continuous-time dynamics. In Bubeck et al., they showed that (discrete-time) projected Langevin algorithm, in the continuous-time limit, corresponds to a Langevin diffusion that is reflected when it touches on the boundary. You are considering a continuous-time SDE in equation (2), that makes me wonder why it is not a reflected SDE, but rather involves a projection map?

(5) The fact that the authors are considering a "continuous-time" algorithm, instead of a discrete time algorithm, makes the contributions of the paper a bit weak. 

(6) Langevin algorithm is used in the optimization literature usually when the objective is non-convex, so that the injected Gaussian noise can help the algorithm escape local minima; see e.g. Raginsky et al. (2017). It is not clear to me when for convex optimization, one needs to use a Langevin algorithm. 
clarity,_quality,_novelty_and_reproducibility: The paper is not written in a very clear way as I explained in the weaknesses previously. It is not clear to me when certain assumptions are made and when they are not. The quality of the presentation should be improved. 
summary_of_the_review: The paper studies an important and interesting topic. It is a solid theory paper. However, it has quite a few weaknesses as I mentioned previously.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper concerns a new unified viewpoint for DP-ERM and DP-SCO via the Langevin diffusion algorithm. Namely, the authors prove that this (natural) algorithm in a certain precise sense provides the optimal utility/privacy trade-off. The results are proven by combining techniques from Bassily et al, as well as stability-based generalization bounds (e.g., Hardt et al). After some discussion with the authors, the conclusion was that while the paper has some interesting conceptual contribution, it has several shortcomings: 
(1) The technical analysis is largely present in prior work (e.g., Bassily et al, Hardt et al, standard analyses of Renyi divergence of diffusion processes). This would on its own not an issue, if it conveyed a conceptually new point --- which is here unclear. 
(2) While Langevin diffusion is an appealingly clean algorithm to have the optimal trade-off, it is crucially not a runnable algorithm. It needs to be discretized to be turned into an algorithm one can run, and the authors do not analyze discretization effects (nor consequences to computational complexity). 
 
justification_for_why_not_higher_score: While the paper has some interesting conceptual contribution, it has several shortcomings: 
(1) The technical analysis is largely present in prior work (e.g., Bassily et al, Hardt et al, standard analyses of Renyi divergence of diffusion processes). This would on its own not an issue, if it conveyed a conceptually new point --- which is here unclear. 
(2) While Langevin diffusion is an appealingly clean algorithm to have the optimal trade-off, it is crucially not a runnable algorithm. It needs to be discretized to be turned into an algorithm one can run, and the authors do not analyze discretization effects (nor consequences to computational complexity).
Decision: Reject