Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper provides a convergence analysis of DP-SGD and proposes a certain value-clipping method as an alternative to gradient clipping of DP-SGD. The convergence analysis leads to the same or better asymptotics than state-of-the-art results with slightly weaker assumptions, and the value-clipping leads to faster compute with similar experimental results however requires certain growth condition to be satisfied (for the loss function).

The convergence analysis relies on the assumption that the SGD noise of the gradients is 'light-tailed' meaning it is sub.Gaussian and also on the RDP analysis of the subsampled Gaussian mechanisms provided by Abadi et al. (2016) which connects the level of DP noise and epsilons. This way convergence bounds w.r.t. epsilons and deltas can be provided. 
strength_and_weaknesses: Pros:

- The paper is generally well written and easy to follow.
- The convergence analysis seems solid, it is impressive that same asymptotics are obtained as in (Bassily et al., 2014) for Lipschitz continuous loss functions.

Cons:

- The value clipping part is perhaps a bit weak part of the paper, e.g. the drop in test accuracy for MNIST is quite big (around 5%).
- Experiments could be improved: instead of showing all those training accuracy figures, would be more interesting to see how the value clipping behaves for different values of $\sigma$ and different values of $\varepsilon$.
- Some parts are a bit unclear, the presentation could be improved here and there. Let me elaborate:

How are actually the growth condition parameters $\beta_1$ and $\beta_2$ determined for the neural networks? I looked at Appendix E, and I only see bounds on the gradients, but there is nothing that explicitly says how to a priori bound $\beta_1$ and $\beta_2$. Could you elaborate on this and explicitly show how to determine them? How big is then the gap to the actual gradient norm, i.e. how loose are the bounds?

You write: "The value clipping step (line 4 of Algorithm 3) can be realized within one forward-backward propagation if the GC parameters are given in advance. Therefore DP-SGD-VC can be as fast as the vanilla SGD algorithm."

But are they given in advance in the experiments? Or do you compute them using the expressions of Appendix E at each iteration? As far as I see, to have rigorous DP guarantees, that is required.


clarity,_quality,_novelty_and_reproducibility: The paper is generally clearly written and all the math I checked is correct. 

Here few more points about the writing, I believe these can be easily fixed:

- You mention in Alg. 1 that "Uniform randomly sample a batch $B_t$ with size $B$..." However, the results of (Abadi et al., 2016) holds for the Poisson subsampling, which you do not mention in the paper. To keep things rigorous, I think this should be added/corrected.

- In the first paragraph of 'NUMERICAL STUDY' Section you mention: "In Appendix, we also present some experimental results on synthetic data with light-tailed noise." Does this mean that the SGD noise in the MNIST/CIFAR-10 experiments is not sub Gaussian? I.e., the theory does not hold here? If so, I think would be better to state it more directly.

- Why is the main algorithm called DP-SGD-GC, when DP-SGD is a widely used acronym for the very same algorithm?
summary_of_the_review: All in all, I feel this is a borderline case and I hope the authors can clarify some of my concerns.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper suggests convergence analysis of Differentially Private SGD with gradient clipping (DP-SGD-GC) in a smooth, unconstrained setting without bounded domain and Lipschitz continuity assumptions. Obtained results match the previously obtained bounds (for a more restrictive case) under an additional light-tail-noise assumption. In addition, the authors suggest a novel value-clipping technique and compare it to standard gradient clipping in a simple numerical study with neural networks on  MNIST and CIFAR-10 datasets.
strength_and_weaknesses: ## Strengths

- Removal of the restrictive bounded domain and Lipschitz continuity assumptions seems a novel and significant contribution.
- Proposed Value Clipping may be practically useful for certain settings. There is a potential for better scalability in comparison to standard gradient clipping.

## Weaknesses

- Numerical results are quite simple which is fine for me, as the main contributions are theoretical. Though they serve a well-illustrative purpose.

- Assumption 4.1 needs to be discussed in more detail. In my view, it is not enough to mention some not-very-recent references as the optimization field progressed quite a lot from that time. Namely, when does this assumption hold in practice? I see how it makes sense for a simple case of additive Gaussian noise for stochastic gradient estimates. But what are the assumptions on the distribution involved in the expectation? Does $i \sim \mathcal{U}[1, \dots, n]$ or other mini-batch samplings (better suitable from a differential privacy perspective) fit into this framework?

clarity,_quality,_novelty_and_reproducibility: 1. The paper’s main body is well-organized and easy to follow. The contributions are very clear and the proof sketch seems helpful and quite intuitive. Regarding the Appendix, I suggest giving more details for some of the proofs. E.g. in proof of Proposition 4.2, some steps are omitted. While they may be obvious for experts in the area, it would make it more accessible for a wider audience if some of the transitions were done more explicitly: like the first inequality for conditional expectation.

2. I would like to ask the authors to compare their conclusions to the results of the paper [1] as it seems that there is a contradiction to their theses based on large-scale numerical studies. Namely, it was observed that for huge models the best performance is achieved for low clipping bounds and clipping happens almost always (especially for language models).

3. The name growth condition used in Definition 3.1 seems confusing taking into account recent optimization literature on SGD. In the mentioned references GC usually refers to the following condition
$$
\mathrm{E} \||g(x)\||^2 \leq \alpha \||\nabla h(x)\||^2 + \beta,
$$
where $g(x)$ is an unbiased stochastic gradient estimator of $\nabla h(x)$. It would be better not to use this term or replace it.

4. I suggest providing an example of DP-SGD utility bound with a non-vanishing bias term for unconstrained smooth problems for a better illustration of the theoretical contribution.

5. Regarding the proposed Value Clipping technique I recommend adding a more explicit discussion of the limitations of this method for complex models when it can not be done analytically so easily. In addition, a commentary on possible hyper-parameter tuning overhead could be very valuable.

6. It would be interesting to understand the privacy-utility trade-off given the results of this work. Because as far as I see (given the same privacy budget) higher clipping threshold requires adding Gaussian noise with a larger variance which can be detrimental to training. I understand that privacy is not the main focus of this work, but adding a discussion on it could be very helpful.

___


[1] Bu, Zhiqi, et al. "Automatic clipping: Differentially private deep learning made easier and stronger." arXiv preprint arXiv:2206.07136 (2022).
summary_of_the_review: Overall this is a good submission with a strong theoretical contribution and a good practical potential worth accepting to a conference.

**Minor comments**

I would like to ask the authors to adjust some of the citations by using the `\citet` LaTeX command not to duplicate text. Especially in the Related Work section.

Small typos on page 18 (top): lower indexes for $z_t \to z_i, u_t \to u_i$ and $Z_{T-1} \to Z_{t-1}$
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the problem of DP optimization in the convex setting. This paper considers the problem in the setting that the loss function  is smooth but not Lipschitz and the domain is not bounded. Instead the author assumes a growth condition which basically relates the gradient of a point to the optimal gap of that point.

Then, under these conditions the authors show that noisy SGD can be used to achieve an optimization gap of sqrt(d)/sqr(n)eps. Also, assuming light tail noise for the gradients the optimization gap can be improved to sqrt(d)/n eps. 

Their analysis provide an approach to better clip the gradients, and using this result the authors propose a practical algorithm DP-SGD.
strength_and_weaknesses: The paper is well-written and the results are clear. In general the paper is good and provides some new insights.

Questions:

1)In the following paper the authors provide some lower bounds for DP optimization. In which they show that the boundedness of the diameter space is necessary. It should be discussed in the paper why the lower bound does not hold under the growth condition.
 
Bassily, Raef, Adam Smith, and Abhradeep Thakurta. "Private empirical risk minimization: Efficient algorithms and tight error bounds." 2014 IEEE 55th annual symposium on foundations of computer science. IEEE, 2014.

2) In Prop 4.2, the authors provide a "uniform" upper bound on the excess error of every iteration. This result and growth condition imply that we can choose a clipping norm such that with a high probability, we "never" clip the gradients. I think given that we are operating under this event, the standard convergence results for smooth convex function work. I want to understand how the analysis in the paper differs from this.
clarity,_quality,_novelty_and_reproducibility: The paper is well-written and very clear. The authors provide proof sketch in the paper which improves readability. 
summary_of_the_review: This paper considers the DP-Optimization problem. The main result is that under a natural growth condition, the lipschitzness and boundedness assumption can be removed and we can obtain a nearly optimal convergence rate.
I think this paper is interesting.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The main contribution of the paper is a new analysis of private SGD with clipping that removes restrictive assumptions for smooth convex functions, namely the bounded domain assumption and the assumption that the function is globally Lipschitz continuous. If the noise from the subsampled gradient are light-tailed (sub-Gaussian), the guarantees obtained are comparable to those established in prior work under the additional assumptions. The paper is primarily theoretical and focuses on improving the theoretical understanding of private SGD. On the practical side, the paper introduces a new clipping technique for functions that satisfy the weak growth condition, which is a relaxation of smoothness, that can be implemented efficiently.

The reviewers agree that the theoretical contribution of the paper is relevant and interesting, and it is strong enough to merit acceptance. The reviewers felt that the experiments could be improved and that the practical benefits of the new clipping techniques were limited.

justification_for_why_not_higher_score: The experiments could be improved and the practical benefits of the new clipping techniques seem limited.
justification_for_why_not_lower_score: The paper expands our understanding of private SGD by removing restrictive assumptions that do not hold in important scenarios.
Decision: Accept: poster