Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The authors propose to replace the standard clipping function in DP-SGD, $Clip_R(g) = min(R/|g|, 1)$ with the alternative clipping function $Clip_{\gamma}(g) = 1/(|g| + \gamma)$. They argue that this alternative clipping scheme is easier to tune, and matches or exceeds the performance of the standard scheme on a range of datasets.
strength_and_weaknesses: Strengths:

1) The proposed scheme is a natural alternative clipping scheme. 
2) The authors provide extensive experiments to confirm that it achieves similar performance to standard clipping

Weaknesses:

1) The core claim of the paper is that the clipping parameter R is difficult to tune, however a number of prior works have shown that this arises only because the choice of clipping norm changes the scale of the update. One can easily fix this by redefining $Clip_R(g) = min(1/|g|, 1/R)$. As De et al. show, after this transformation a wide range of small but finite values of R perform similarly well, and it is standard practice in recent works to simply set R=1.

2) After this transformation, it is clear that the two clipping schemes are almost identical. Essentially the authors propose a smoothed version of the standard clipping function.


clarity,_quality,_novelty_and_reproducibility: Clarity: the paper is relatively clear

Quality: the quality of the work is ok, including detailed experiments.

Novelty: the novelty is limited, since the two clipping functions are very similar, and prior work has established that the standard clipping function is also very easy to tune.

Reproducibility: the work is reproducible
summary_of_the_review: The paper relies on the claim that the clipping threshold in DP-SGD is difficult to tune, however recent works have shown that this is easy in practice if one simply re-scales the clipped gradient by the clipping threshold. Unfortunately I therefore feel the contribution here is simply too small for a top-tier conference.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper considers the problem of choosing the clipping threshold in DP-SGD routines and proposes two related modifications to the original fixed clipping technique of Abadi et al. They then show that the DP-SGD method with the proposed clipping has desirable theoretical properties in terms of convergence to stationary points. Importantly, they conduct extensive experiments to show that their method compares favourably to other schemes in practice.
strength_and_weaknesses: Strengths
1. Clipping of gradients is an integral constituent to the practice of modern differentially private machine learning. Moreover, as the authors have pointed out, the downstream performance is usually very sensitive to the choice of the clipping threshold. This has resulted in many works on how to *automatically* set the clipping threshold without tuning it explicitly. The authors of this paper contribute to this practically important area of research. 

2. Extensive experiments:
The main goal of the paper is to obtain empirical improvement over prior works.
The authors propose two variants of their clipping technique, AUTO-V and AUTO-S, and perform extensive experiments on various benchmark tasks. The experimental results are promising and demonstrate better performance than compared techniques.

Weaknesses

The key idea of the paper is very simple but in my view, its presentation feels rather obfuscated.
Basically, the trick is normalize all gradients  (AUTO-V) or normalize it with an additive scalar in the denominator (which is standard in implementations of adaptive gradient methods like ADAM). This normalization explicitly controls the sensitivity, and so privacy follows. If the per-sample gradients have different norms, then this method scales all of them to have the same norm, so intuitively it seems that we would lose some information, however the authors show that it still works well in practice.


**Theoretical results**:
The presentation of the theoretical results is convoluted for some reason -- I would have expected that the right hand side in Thm 4 and 5 are stated as an explicit function of problem parameters; instead they are written as a function F which is not defined in the main text. The authors say that has the same rate as SGD (which is true with respect to its dependence on $T$), but I am not sure if the dependence on other terms is same as SGD. This should be clarified.
Also, I am not sure about the remarks following Thm5.
Aren't all these observations could be made from any existing convergence result of this form (say DP-SGD)? So, why are they interesting in the context of the methods proposed? What am I missing here?

**Connections to optimisation methods with normalized updates**: (Variants of) Normalized updates have been used in optimization; for instance, in parameter-free methods [CM20], and variance-reduced methods [FJLZ18] as well as in empirical works (see references in [CM20]).
However, I did not find any discussion on this in the paper; I hope the authors add some to give context to the proposed approach.
Also, is the theoretical result and analysis significantly different from prior works? 

**Empirical Comparison with other adaptive clipping methods**: 
The authors do not do any empirical comparison with prior adaptive clipping methods such as Andrew et al, Pichapati et al. The authors rightfully pointed out these introduce new (but arguably robust) hyper-parameters. However, they often come with default settings of these hyperparameters (such as the quanitile). So, why not compare using these default values of hyperparameters of all the methods while keeping the other hyperpameters (like learning rate) fixed?

[CM2020]Momentum Improves Normalized SGD
[FJLZ18]:SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
clarity,_quality,_novelty_and_reproducibility: I found the presentation of ideas in the paper more convouted than it perhaps needs to be. The theorem statements about equivalence with fixed $R$ and different step sizes (Thm1 and Thm2) are simple observations, but their presentation seems to hint that there is some deep going on. I hope that the authors can try to simplify the presentation.
The key idea of using normalized updates is simple and novel only in the specific context of DP optimization. The quality hinges o empirical improvements over prior works; however, comparison with other adaptive clipping methods is missing and so it is not clear if these results are enough to ascertain if this method would work (significantly) better than existing counter-parts in general.
summary_of_the_review: The paper tackles a practically important problem and present promising empirical results. It is also interesting that it is not a heurisitc but comes with some theoretical guarantees. However, the key ideas behind it are rather simple and a comparison with competing methods is currently missing.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper suggests two new methods for doing clipping in DP optimization automatically, with the goal of avoiding the need to tune the clipping norm while minimally reducing (or perhaps even improving) model accuracy. The authors propose two methods. AUTO-V and AUTO-S. AUTO-V effectively rescales every gradient norm to 1, but runs into a lazy-region issue where the mean clipped gradient can be very close to even if the mean unclipped gradient are not. AUTO-S remedies this by instead multiplying each gradient g by 1/(||g|| + gamma), where gamma is a small positive constant, which gives large gradients slightly more magnitude than smaller gradients and avoids the lazy region issue. The authors give a survey of clipping thresholds in past work which motivates these clipping methods: Most past work does well when the clipping threshold is sufficiently small such that most gradients are clipped. If all gradients were clipped, then the gradient update using standard clipping can combine the learning rate and clipping norm hyperparameters, and reduces to what AUTO-V does anyway.

The authors show a theoretical convergence result for AUTO-S that applies to non-convex smooth functions. This analysis also shows the necessity of using AUTO-S over AUTO-V. Noticeably, the convergence proof has the same asymptotic dependence on T as that of non-private SGD.

The authors also run experiments using AUTO-S clipping to train image classification models, sentence classification models, and text generation models with DP. For image classification models, using the same setups as past work but replacing standard clipping with AUTO-S, the mean accuracy increases across a multitude of tasks. For sentence classification, AUTO-S improves upon the previous work of Li et al. for almost all settings, using the same hyperparameters and setup. For text generation, AUTO-S has the highest performance compared to past methods. 
strength_and_weaknesses: I think the main strength of the paper is that it suggests a simple method for hyperparameter reduction backed by theoretical and empirical exploration that also has both impressive theoretical and empirical performance. The authors do a good job using the explorations in the first few pages of the paper to motivate the eventual automatic clipping method they arrive at in the paper. The results in the paper feel very complete and comprehensive; there are theoretical converge results, a wide range of empirical evaluations on benchmarks, and discussions on ease of implementation into existing codebases including code snippets, as well as lengthy discussions on each. Despite the main goal of the paper being to reduce the number of hyperparameters, the authors are also able to achieve empirical increases in accuracy using their method.

I think the main weakness of the paper is that it is unclear from reading the paper just how much of an improvement in terms of hyperparameter reduction this paper gives over past approaches; in particular, I felt that Figure 14 is one of the most important parts of the paper (giving examples that quantify the effect on performance of varying gamma), and should have been discussed in more detail especially in the body of the paper. In particular, the authors state that "deep learning optimizers are insensitive to the choice of gamma", but in Figure 14, the effect of gamma on accuracy and the effect of clipping norm on accuracy seem to be within a small constant factor of each other (e.g., the maximum difference b/t two clipping norms that differ by 10 seems to be < 1% absolute accuracy, and for some settings two gammas that differ by 10 can differ in accuracy by half a percent). It seems then arguable in terms of hyperparameter reduction if AUTO-S with gamma = 0.01 is substantially improving over e.g., just fixing the clip norm to be 0.01 in DP-SGD. One could reasonably argue that this constant factor is substantial in practice, but this topic is somewhat swept over by the quoted statement which to me implies the difference is much more drastic.

That being said, I think since (i) as mentioned above, gamma has less of an effect than the clipping norm and one can argue the decrease of this effect is substantial (ii) the authors also include comparisons to AUTO-V (which truly has strictly fewer hyperparameters to tune) and still see comparable performance from AUTO-V, this is a minor weakness. Furthermore, I think it's easily fixable by just adding a few sentences to the main body of the paper.

Nitpick: In various places references probably should go in parentheses, i.e. (X et al. 2022) instead of X et al. (2022) for readability, please fix.
clarity,_quality,_novelty_and_reproducibility: The paper is well-written and generally easy/enjoyable to read. The authors do a good job spending time explaining more nuanced concepts as well. The results in the paper are high quality. The precise method in this paper I believe is original, though as the authors do mention, other non-standard clipping methods have been considered in the past.
summary_of_the_review: I recommend accepting the paper. Hyperparameter reduction is an important problem in practice, and the authors have done a very good job motivating the method they use to address this problem and making their results as well-studied and suitable for use in practice as existing methods. So I believe the paper can have high impact in practice. The empirical results in the paper are also fairly impressive, improving over the SOTA in performance despite that not being the main focus of the work necessarily. The aforementioned weakness in the paper I believe is easily fixed before the camera-ready version as well.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This work largely focuses on removing the clipping norm hyperparameter, but replacing it with another hyperparameter which the authors show that the optimizer is relatively insensitive to. The modification is fairly similar to a previous reparameterization made by De et al. Some reviewers were also critical of the writing. One back-and-forth between a reviewer and the authors also seemed to indicate that it would get comparable performance to simply fix the clipping norm, which obviates the need for the modification in this paper. No reviewer was willing to champion this paper.
justification_for_why_not_higher_score: Limited advantage and novelty versus prior methods.
Decision: Reject