Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors argue that our ability to optimize a model trained with DP-SGD is governed by a quantity they call TAN (the total amount of noise), specifically $\Sigma^2 = 2 \sigma^2 N^2/(B^2 S)$, where $\Sigma$ is the TAN, $\sigma$ is the scale of the added Gaussian noise, $N$ is the dataset size, $B$ is the batch size and $S$ is the number of updates.

Additionally, they show empirically that when $\sigma \gtrsim 2$, the privacy parameter $\epsilon$ becomes a simple function of $\Sigma$ and $\delta$. Since it is standard to set $\delta \approx 1/N$, in practice this means that the privacy is determined solely by $\Sigma$, the TAN. Meanwhile, the privacy loss $\epsilon$ is very large when $\sigma \ll 2$.

The authors propose to exploit this observation by tuning hyper-parameters with small $\sigma$, small batch size $B$ and large privacy loss $\epsilon$, before extrapolating those hyper-parameters to $\sigma \gtrsim 2$ while increasing the batch size to ensure that the TAN $\Sigma$ is constant. This significantly reduces the privacy loss $\epsilon$ however it also significantly increases the compute cost of training. Extrapolating hyper-parameters from cheap non-private training runs to expensive runs with tight privacy guarantees reduces the total computation required to achieve strong performance with DP.
strength_and_weaknesses: Strengths:
1) Integrating the constraints of DP-SGD with optimization theory, in order to reliably predict good hyper-parameter choices, is one of the most important problems that needs to be solved in order to make differentially private deep learning practical. I'm pleased to see the authors tackle this difficult and important problem.
2) The metric proposed by the authors is intuitive and it appears to provide some helpful intuition.
3) The authors achieve strong performance when training from scratch on ImageNet with DP-SGD.

Weaknesses:
1) If TAN were an accurate measure of optimizability, then we should expect the train accuracy to be roughly constant at fixed TAN. However in practice, the authors find in figure 1 that the test accuracy decays log-linearly at fixed TAN as the batch size rises. I feel that the current paper is quite confusing because this discrepancy is not explicitly stated anywhere. I'd encourage the authors to make this explicit, and to explore in more detail why this discrepancy arises (eg comparing test vs train performance). 

2) As discussed above, Figure 1 shows that TAN over-estimates the performance of large batch sizes. It would be nice to also see a figure at fixed batch size, sweeping the number of steps S, to see whether TAN under/over-estimates the performance of small/large step budgets.

3) As a minor point, note that on some truly sensitive data we cannot train non-private models (even internally). It would be good to acknowledge that the hyper-parameter transfer process described here cannot be used in these cases.

4) For many of the experiments, key hyper-parameters are lifted from prior work (eg step budget, target batch size). Is it not possible to directly infer good settings for these hyper-parameters using the TAN framework?

5) The paper essentially only considers ImageNet (with some very limited experiments on CIFAR-10). Since very few groups have run experiments at this scale it is not clear how challenging the baseline from De et al. is in practice.


clarity,_quality,_novelty_and_reproducibility: Clarity:
I found the paper difficult to follow. I think this is because the authors do not clearly acknowledge that, if TAN were an accurate measure of trainability, then test accuracy should not fall as batch size rises (at constant TAN) in figure 1. It is also not always clear which hyper-parameters are extrapolated using the TAN framework, and which are lifted from prior work or tuned in the large batch/low privacy loss regime.

Quality:
I think the underlying quality of the work is quite high (if the clarity can be improved).

Novelty:
This is the first paper I am aware of to provide an explicit toy model predicting the trainability of DP-SGD. Although TAN has some flaws, I think this is a novel and worthwhile research direction.

Reproducibility:
I'm not sure how easy it would be to reproduce the results
summary_of_the_review: On the positive side, the authors identify an important and difficult problem, and provide some useful insights. However on the downside TAN is not a reliable measure of performance in practice, and the authors only achieve strong results on one dataset so it is not clear how reliable the methodology is.

I have scored the paper weak accept, however I would encourage the authors to improve the clarity of the writing and to empirically explore in more detail how test accuracy depends on (batch size, step budget, added noise) under the constraint of constant TAN.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors proposed to use the total amount of noise (TAN) to determine the privacy budget in Renyi DP. They observe scaling laws with TAN for DP-SGD which can be used to reduce the computational cost for hyper-parameter tuning. By the hyper-parameter tuning, the authors greatly improve the state-of-the-art on neural network training under privacy guarantees.
strength_and_weaknesses: Major strengths:
1. The observation of the scaling law is new. 
2. The results of hyperparameter tuning improve the state-of-the-art greatly.

Minor strengths:
1. This paper is easy to follow.
2. The visualization of the experimental results is good.
3. Figure 2 seems to deliver the same message as the linear part of Figure 3 (left) in (Li et al, 2021a), but the authors provide more explanations in Section 3.2.

Major weaknesses:
1. The privacy guarantee parameter $\varepsilon_{TAN}$ is an approximation of $\varepsilon_{RDP}$ and it is only a lower bound. For strict privacy guarantees, we need an upper bound.
2. There is no explanation for the reason for the scaling law. 

Minor weaknesses:
Some of the statements in this paper are inconsistent with each other. 
1. In the left figure of Figure 4, the legend shows that $\sigma_{ref}$ is constant for each line, but the caption says the $\eta_{step}$ is constant. I also wonder why the authors choose to fix different values in Figure 4 for CIFAR-10 and ImageNet. Is it because the results of CIFAR-10 do not look as linear as of ImageNet?
2. In Page 5, Choice of $\sigma$, the authors claimed that if $\sigma>4$, dividing it by 2 with halving q is likely to improve performance, but I cannot find experimental results supporting this.
3. In Page 7, the authors say that they decide not to use the gain from 'testing with augmentations' in Table 1 and Table 4. In Table 2, I guess the Total column is the sum of the other columns for B=128, ..., 1024. Therefore, the last row, B=16384, also has the AugTest (+0.8) in the Total result (6.7%). I guess in Table 4, the test ACC for B=16384, 36.9%, is derived by adding the total improvement 6.7% to the baseline 30.2%. Therefore, I am not sure if the authors forget to remove the improvement from AugTest.
4. In Page 9, in the last paragraph, the authors believe that the exponential increase in the privacy budget $\varepsilon$ as the noise level $\sigma$ decreases. I guess this is from Figure 2, but the x-axis for $\sigma$ is log-scale. Therefore, it is not easy to identify whether there is a linear or exponential relationship between $\varepsilon$ and $\sigma$.

By the way, there are duplicate references (Li et al, 2021a and 2021b).
clarity,_quality,_novelty_and_reproducibility: This paper is well-written. The statements in the paper are clear and concise. The novelty of this paper is good (see the strengths). The code is not provided, and the computation cost of the comparison experiments in this paper seems to be high; therefore the reproducibility is low.
summary_of_the_review: This paper demonstrates the scaling law between the batch size and the test accuracy in private deep learning. This law and the new concept, TAN, are very useful in improving private learning results by DP-SGD when the computation resources are limited. This law is found in the results of ImageNet and CIFAR-10 experiments, but the reason behind it is still unknown and it may be difficult to reproduce the results since the code is not provided.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: 

The paper studies how to transfer the hyperparameters of differentially private training based on low-cost search. It shows the privacy budget only depends on the total amount of noise (TAN) injected throughout training. They derives a scaling law for training models with DP-SGD with more than a 100 times reduction in computational budget.
strength_and_weaknesses: Strength: It studies an important problem of how to scale DP-SGD with hyper-parameter search. The paper provides a neat and simple relationship between the privacy budget and the other parameters, i.e., the noise multiplier, steps and the sampling rate. This relationship motivates a way of scaling the batchsize and the noise multiplier without affecting the privacy accountant.

Weakness: 
1. There is no application of using TAN relation in language task, either pretraining or fine-tuning.

2. The reference needs to cover more. Especially, Yu et al. 2021 starts the fine-tuning large language models with differential privacy and low-rank reparametrization. 
Yu et al. 2021 Large Scale Private Learning via Low-rank Reparametrization.
clarity,_quality,_novelty_and_reproducibility: The paper is well-written, and the finding is novel and useful for tuning DP-SGD.
summary_of_the_review: How to tune DP-SGD is both theoretically and practically important for private learning. The paper makes a clear contribution towards tuning DP-SGD in principle. The concluding solution is solid and well-supported. I recommend its acceptance.

\#### After rebuttal and discussion with other reviewers \#####
As discussed with other reviewers, the relation of TAN with privacy accounting has been derived in literature e.g., Lemma 2 and Proposition 3 of Bun et al. 2020. The paper is not fully aware of the literature, which undermines the novelty of the contribution. I change the score to 6.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Recent work shows that large batch size can give better privacy-utility trade-off in differentia private ML training. However, training with large batch sizes is computationally expensive. The paper observes (empirically) that the privacy budget of differential private ML training depends mostly on the total amount of noise added during training when the noise multiplier \sigma>=2. At the same time, the accuracy of the final results can be predicted by the results on a corresponding hyper-parameter setting in which the batch size is small. Following these observations, the paper proposes to do hyper-parameter tuning for small batch sizes (which is computationally efficient) and then transform the hyper-parameters to the target large batch size. Experiments demonstrate that this approach works well in practice.
strength_and_weaknesses: 
Strength:

* The observations (batch scaling law, privacy budget computation) in the paper are new and interesting.

* The proposed hyper-parameter tuning process can be very useful in practice, as it saves the computation requirement and therefore speeds up the development process.

Weaknesses:

* Overall, the writing is clear, but there are still some issues that need to be addressed:
    - Equation 2: many of the notations here are not defined, e.g., clip_C, l, theta, C.
    - Figure 4: B_ref, S_ref, \sigma_ref are not defined. I can guess their meaning from the context, but all notations should be defined explicitly in the text.
    - Page 5: it says "Simultaneously doubling the batch size and \sigma has a negligible or small impact on accuracy (Figure 4)". However, in Figure 4(b), the impact on the accuracy is not small. Indeed, this is claimed in the next sentence "Reciprocally, if \sigma > 4, dividing it by 2 simultaneously with halving q is likely to improve performance." These two sentences contradict each other.
    - Table 1: I guess "8,8." should be "8,"?


clarity,_quality,_novelty_and_reproducibility: 
Clarity: The paper is overall well-written and clear.

Quality: The observation and the proposed approach are interesting and useful, and the claims are supported by experiments. Overall the quality is good.

Reproducibility: the code of the experiments is not provided.

Novelty: The observation is new and the proposed approach is novel.

summary_of_the_review: 
Overall, the paper is well-written and the observations and the proposed approach can potentially be very useful for the community. It would be even better if the authors can demonstrate/verify the observation on more network architectures, datasets, and models (e.g., generative models).
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies the hyperparameter choices of DP-SGD, arguably the most popular method for deep learning with differential privacy.  The main finding of the paper is the claimed discovery of the so-called "Total Amount of Noise"  (abbrv TAN), denoted by $q^2S / (2 \sigma^2)$ where $q$ is the sampling probability for the minibatch,  $S$ is the number of iterations and $\sigma$ is the "noise multiplier" (the ratio between the standard deviation of the noise and the clipping threshold).

The paper states that when \sigma > 2, TAN provides a good approximation of the RDP parameter in the useful ranges for obtaining (eps,delta)-DP.   The paper then used TAN to inform on the hyperparameter choices for DP-SGD. It recommended a particular configuration of the hyperparameters (fix S, choose $\sigma \in [2,4]$, and decide on q according to a given privacy budget).  Experiments show that the better hyperparameter choices (smaller batch size, smaller amount of noise while keeping TAN the same), provide stronger results in training ImageNet from scratch using DP-SGD.

The strengths of the paper include:  
- new SOTA for imagenet with DP
- an intuitive explanation of TAN  (and an informal discussion on how it is related to "effective noise" from Li et al. 2021)
- interesting experimental results that demonstrate that test accuracy reduces linearly w.r.t. the log of BatchSize.

The weakness of the paper include (some of these come up in the AC-reviewer discussion):
- TAN, and the observed relationship between TAN and privacy loss in the regime of interest is not new, and in fact well-known.  
- TAN does not explain the interesting linear scaling between the  "test accuracy and the log of BatchSize"; and the explanation that appeals to better "generalization" is ad hoc and is unlikely to be the reason.
- The paper seems to have missed well-known convergence results in DP-SGD. The claimed new insight on hyperaparameter choices appears to be directly implied by theory. 

More details of the above are provided in the summary of AC-reviewer meeting below.






justification_for_why_not_higher_score: See the discussion above.
Decision: Reject