Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: Strong Points:

1. The problem studied is interesting and important for the privacy community - private gradient descent is an important mechanism for private convex optimization, and one of the only mechanisms for non-convex optimization.  
2. The authors do a good job engaging with prior work, identifying gaps in related work (i.e., theoretical justification for dynamic noise schedules) and putting their contributions in that context.  
3. The analysis seems technically correct and pretty strong, although I did not check this closely.  

Weak Points:
1. Excess risk upper bound is probably quite loose, so improving that may not necessarily improve actual excess risk.
2. log(N) improvement may be an artifact of the analysis, and not an inherent advantage of dynamic schedules.  Needs more clarification (see below). 

Other Notes:

It’s not clear to me where the log(N) term in the excess risk upper bound comes from for the uniform noise schedule.  In other works on this topic, it is not there (e.g., https://arxiv.org/pdf/2005.04763.pdf) .  Since we are dealing with upper bounds, I wonder if it is just an artifact of the analysis of Wang et al., rather than an improvement offered by dynamic scheduling.  Are there other ways to remove this dependence other than dynamic noise?

review_title: This paper analyzes private gradient descent when using dynamic noise schedules.  They propose a dynamic schedule that minimizes the excess risk upper bound, and that the resulting bound on excess risk improves over the standard uniform schedule.  

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary: The paper investigates the idea that a dynamic privacy schedule of decreasing noise can help private gradient descent. The main contribution is a theoretical analysis of a dynamic privacy schedule which helps reduce the utility upper bound of private gradient descent (with or without momentum).

Strengths:
1)	Private gradient descent is an important optimization technique in differentially private ML, therefore, understanding its behavior is broadly interesting.
2)	The paper investigates both the vanilla private gradient descent as well as a version with momentum.

Concerns:
1)	While there is some improvement with the dynamic schedule vs. fixed schedule, the improvement does not seem to significant (ref. Table 1). 
2)	Results hold only under PL condition (which is a more general condition than strong convexity) and smoothness.

The results look correct. My current scores are because I see limited value/interest in these results. 

Questions:
- Maybe relaxing the assumptions might be a way to strengthen the paper.  Is that possible?
- What is the advantage of using the momentum method in terms of the utility upper bound (ref. Table 1). It looks like (within constant factors) vanilla GD with dynamic schedule works as well as using the momentum.
- Do these results hold with a stochastic gradient?

Minor comment: hat{T} not defined in Table 1
review_title: Review for "On Dynamic Noise Influence in Differential Private Learning"

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper studies private gradient descent when the noise added to each of the iteration is dynamically scheduled. Prior to this work, the work of Zhou et al. tries to achieve the same for DP-SGD and they analyze their algorithm for many variants of adaptive gradient descent based method. The difference with Zhou et al. is that they do not gradient norm and the generalization property of DP. As a result, the authors claim that Zhou et al. achieves suboptimal utility guarantee. 

I will keep my reviews limited to the current submission. My first objection to the paper is that gradient descent requires computation of gradients over the entire dataset. As such, every iteration is very costly and not practical at all, given the training data set can be very large. 

The paper considers Polyak-Lojasiewicz's condition, a more general form than strongly convex loss function. However, I find some of the comparison misleading. For example, Feldman et al. (STOC 2020) and Zhou et al. show an excess "population loss" of order $O(1/n)$. On the other hand, if I understand the paper correctly, the current submission only give excess empirical risk. Further, Feldman et al's two algorithms achieve optimal excess loss while running in nearly "linear" time, which is not the case in the current submission. 

There might be some interesting idea in this paper, especially, looking at the dynamic schedule for PPML. However, I fail to see the strength of the result in the view of prior work as the comparison done in the paper is between apples and oranges.   

I did not verify the proof very carefully. There are some typos that I found. For example, line following equation (1), $v_t$ should be $\nu_t$. 

$\alpha$ depends on $f(\theta_t)- f(\theta^*)$ and $T, \sigma_t$ depends on $\alpha$. How are we going to set these parameters when we do not know the minimum value of the objective function?
review_title: Paper studies use of momentum based method to improve utility of private-SGD

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary 


Gradient Descent and related variants are the defacto standard algorithms for optimizing empirical risk functions. Since published models have been shown in the literature to leak private information, the problem of performing gradient descent under privacy constraints is an important one. Given a fixed privacy budget R, private gradient descent adds noise to the gradients at each round, ensuring overall privacy budget R by composition. However, this still leaves the question of what privacy schedule is best open, since any schedule whose privacy budgets sum up to R achieves the privacy objective. In this paper they compute the optimal privacy schedule from an accuracy perspective via a novel analysis of the convergence of private gradient descent on loss functions that satisfy the PL condition, which turns out to be exponentially decaying noise (increasing privacy budget for each round). These results extend to a privatized variant of the momentum-based gradient descent algorithm, although the dynamic privacy schedule has less improvement there. Experimental results show that dynamic privacy schedules lead to enhanced accuracy even absent convexity. 

Pros
- improves over previous soa analysis of private gradient descent (wang 2017) by $log N^2$ factor
- Novel analysis for an important practical problem that also yields intuition via the notion of noise influence / propagation

Cons 
- Grammatical Errors throughout: e.g. sentence fragment page 6 “because our bound saved a factor of log N and is thus tighter, as compared to Wang”
- Overall the clarity of the writing and explanations, both in terms of prefacing the technical content, and readability could be improved. 
- Experimental section needs more detailed fleshing out: 1) how does the middle pane show the trend of variance of influence? 2) how are we modeling influence for DNN and how are we then computing the optimal dynamic schedule 3) does plot #1 perform a sensitivity analysis on the ERR via retraining to estimate $q_t$ empirically? Explain this. 


Comments
- why does the utility bound for non-private GD in table 1 have a factor of $R$ (privacy budget) in the denominator?
- What is the difference between $v_t$ and $g_t$? $v_t = g_t$ it says on the bottom of page 3
- $v_t$ and $\nu_t$ look very similar, choose more distinct notation 
- write out the definition of the ERUB in the main text on page 4
- 4.11 uses the improved analysis to sharpen the utility analysis of a uniform schedule by choosing an optimal value of T. Please contrast the Wang bound more clearly with (5) and state the improvement factor. We can read this from the analysis but it should be stated more prominently.
- Discussion of robustness on page 6 is a little imprecisely worded. Is the takeaway that when the condition number is very high relative to the sample size, the dynamic schedule ERUB doesn’t blow up? Since we are calling this robustness, is it obvious that noise in the samples or labels leads to high loss curvature? 
review_title: Important Theoretical Contribution with Practical Relevance, Exposition Needs Work. 

Meta-review: This work proposes algorithms for solving ERM with continuous losses satisfying the PL condition. The first algorithm achieves that by using a chainging noise variance and thus the paper frames the contribution in terms of the advantages of non-constant noise rate.

The problem is a well-studied one and the result is a nice if relatively modest improvement over Wang et al. However, as pointed out in reviews, in the context of convex optimization the same rate has already been established (Feldman,Koren,Talwar STOC 2020). This work is cited and briefly discussed but the discussion only includes one of the algorithms in the paper (that does have an additional log N factor). The overall assumptions in this paper are not comparable (weaker in some ways and stronger since they only require PL instead of strong convexity) but still the overall the contribution appears to be incremental.
Decision: Reject