Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper investigates whether aggregating intermediate checkpoints of DP-SGD algorithms enable better privacy-accuracy trade-off and uncertainty estimate (when compared to those of last-iterate model). They provide empirical evidence that a variety of check point aggregation methods enables improved test accuracy for centralized and federated learning tasks. They also show that for strongly convex smooth loss function, check-point aggregation enables accurate variance estimate for bounded statistics of last-iterate model. This estimation error decays exponentially with the burn-in time and the minimum interval between any two sampled checkpoints. 
strength_and_weaknesses: Strengths:
- Averaging intermediate models is a promising direction for improving privacy-accuracy trade-off for differentially private learning.
- Utilizing checkpoints for uncertainty estimates is an attractive methodology that may enjoy lower computation cost.

Weaknesses:
- In terms of empirical result, it's not really clear what averaging method one should use and why. In the paper, the various aggregation methods (including one method from existing work De et al.) perform similarly for most tasks. For a few tasks where the differences between methods are more significant, the winning method is also not consistent. The authors may want to clarify why their methods are better than prior works for certain tasks but not others. How does this depend on the data distribution or learning tasks?
- In terms of theoretical results, to my understanding, the paper's main contribution is Theorem 3.1. which shows improved uncertainty (variance) estimate as the burning time and intervals between checkpoints increase. However, I do not see the effect of the number of checkpoint models in this theorem. It's not clear whether we should use more checkpoints for variance estimation and why. 
- In terms of the motivation of using checkpoints for uncertainty estimate, the authors emphasize computation efficiency of re-using checkpoints when compared to training multiple independent last-iterate models. However, the total number of training epochs increase in order to produce good quality checkpoints (with reasonable interval between them). These computations are not parallelizable. I think the authors need to support this motivation with more evidence, e.g., how much is the additional computation cost for longer training? Is it negligible when compared to multiple independent runs of the training algorithm (which could be done in parallel)?
clarity,_quality,_novelty_and_reproducibility: Some authors' statements need more support . After Theorem 3.1, the authors claims that 
> Per Harvey et al. (2019), in general this log(n) factor cannot be removed by a better analysis of the last iterate of DP-SGD as instantiated in Theorem 2.1.

However, Theorem 2.1. does not provide any technical lower bound that about why the log(n) factor "cannot" be removed. The reference Harvey et al. (2019) also does not provide any privacy analysis. Therefore it is difficult to understand how this statement is supported. The authors may want to add more detailed explanations. Finally, it is not clear what "in general" means. The authors may want to clarify the conditions for this claim, and add more reference for other settings where the log(n) factor could be removed, such as [a] [b] and [c]. Otherwise, the current claim is too strong and potentially misleading.

[a] Jain, P., Nagaraj, D., & Netrapalli, P. (2019, June). Making the last iterate of sgd information theoretically optimal. In Conference on Learning Theory (pp. 1752-1755). PMLR.
[b] Feldman, V., Koren, T., & Talwar, K. (2020, June). Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (pp. 439-449).
[b] Chourasia, R., Ye, J., & Shokri, R. (2021). Differential privacy dynamics of langevin diffusion and noisy gradient descent. Advances in Neural Information Processing Systems, 34, 14771-14781.
summary_of_the_review: The paper shows interesting potential of using intermediate model aggregation to improve privacy-accuracy trade-off and uncertainty estimate of differentially private learning. However, at current state, the paper does not offer clear investigation of which aggregation method works best in different setting and why. And the paper's Theorem 3.1, motivation for aggregating checkpoints, and some of the claims need more support and explanations. Therefore, my assessment is borderline.


======
Post authors' response

My main concern is still that the paper still needs better (more consistent) explanations for the gain in privacy-utility trade-off or uncertainty estimate by utilising intermediate checkpoints.

=====
Response to author's followup comments:
> The increase in training process length is unavoidable for a worst-case analysis; even for a simple loss such as a one-dimensional quadratic loss, obtaining k near-independent samples from a distribution close to the distribution of DP-SGD’s outputs using o(k) times the number of gradient accesses as a run of DP-SGD (i.e., o(k) times the privacy budget) would violate privacy lower bounds.

I appreciate the authors' lower bound argument. But at the current form, it needs more explanation, perhaps a formal statement and some references, to be interpretable and convincing. 

Secondly, "obtaining k near-independent samples from a distribution" is not a necessary condition for good uncertainty estimate. There are many uncertainty estimation methods, such as MC-dropout, that rely on correlated samples. The idea of using intermediate checkpoints intrinsically may involve analyzing how to use correlated samples and their benefits. Reducing the analysis to nearly-independent runs of MCMC (via large checkpoint interval) lack the perspective for explaining the advantage of performing checkpoint aggregation compared to independent runs of the training (fine-tuning) process. 

> We disagree with this performance analysis of UPA (i.e., uniform tail average). First note from Tables 1 to 3 and Figures 1 and 2 that UPA always performs better than the last checkpoint by large margins. Furthermore, note from Tables 1 and 2 that for the Stackoverflow dataset, UPA always performs better than all other aggregation methods.

In Table 1 and Figure 1 for the performance of UPA: For CIFAR10, under epsilon = 8, the performance improvement of UPA is 2.21%, which is only 0.33% larger than the standard deviation of the baseline (1.46%) plus the standard deviation of UPA (0.52%). Therefore, this test accuracy improvement almost falls in the range of standard deviation, which is marginal. For stackoverflow, in Table 1, the test accuracy improvement of UPA is below 0.5%, which is marginal. 

The test accuracy gain of UPA in Table 2-3 and Figure 2 is indeed more significant. However, the experiments for Table 2 and 3 and Figure 2 are under periodic distribution shift or data-dependent checkpoints aggregations, which the current Theorem 2.1 does not apply to. To explain the benefits in Table 2 and 3 and Figure 2, the authors would need new analysis.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies re-using the intermediate checkpoints during DP training for two purposes: 1. improve the accuracy; 2. construct reasonable uncertainty quantification. The contribution is on the methodology and empirical results.
strength_and_weaknesses: Strength: This paper is clearly presented. The contribution is solid and the experiments are convincing and well-designed. The new method has no cost in terms of privacy guarantee, improves the accuracy, does no incur additional computation, and particularly the UPA trick is better than EMA in that no additional hyperparameter $\beta_t$ needs extra privacy budget to tune honestly.

Weaknesses: I have some concerns on the novelty (see details in next comment) and not comparing carefully to existing work. For example, although the work claims above Section 2.3.3 "we improve the SOTA baseline of De et al. (2022) from 70.6% to 75.51% at ε = 1 and from 77.6% to 80.8% at ε = 8". De et al. is not SOTA: CIFAR100 has achieved 83.0% at ε = 1 and 88.4% at ε = 8 without using any checkpointing like EMA, by "Scalable and Efficient Training of Large Convolutional Neural Networks with Differential Privacy". Testing on this setting is important.

clarity,_quality,_novelty_and_reproducibility: The quality of this paper is solid and the clarity is good. My concern on the novelty of uncertainty quantification with DP, which has been studied in [1] (see Section 5). Therefore the argument in Section 3 "(Naive) uncertainty quantification, and its hurdles" are already known results. [1] studies DP-SGLD which includes DP-LD in this work's Section 3 as a sub-case. Though this work provides some theoretical analysis, using DP Bayesian approach to do uncertainty quantification is not new.

Also, using checkpoints is already explored as in EMA and DP-SGLD in [1][2] (e.g. Algorithm 2 in [1], the output line), whose computational advantage over multiple runs is clear so some novelty is comprised too.



[1] Bu et al. "Differentially Private Bayesian Neural Networks on Accuracy, Privacy and Reliability" (https://arxiv.org/pdf/2107.08461.pdf). 
[2] Li et al. "On Connecting Stochastic Gradient MCMC and Differential Privacy" (https://arxiv.org/pdf/1712.09097.pdf)
summary_of_the_review: Overall I think this is a borderline paper and needs non-trivial revision on the related work discussion and experiments.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper studies the problem of differential private machine learning (DP ML) and propose to aggreagate the checkpoint (intermediate parameters during training) for test time inference. On the experimental sides, the paper conduct experiments over standard dataset like CIFAR10 and stackoverflow and their methods improve the accuracy around 1% to 3%. It also provides some theory on convex optimization and demonstrate the advantage of averaging instead of using only the last iteration.

Method. The paper proposes to aggregate the checkpoint in a few ways: (1) average parameter (exponential averaging or uniform averaging) and (2) aggregate the output (majority vote or averaging). The DP guarantee follows directly as they are post-processing

Experiments. The paper conduct experiments over CIFAR10 and stackoverflow, in both centralized setting and federated setting. I am not a specialist in experiments but the improvement seems solid/consistent, but marginal at the same time.

Theory. The paper shows averaging is better than the last-iteration in the constrained convex optimization setting. It provides good insight. However, technically, their method just plug-in and play the bounds of [Shamir and Zhang'13], and they also fail to show a lower bound (this means it is not really a separation between averaging and plug-in and play, in contrast with [Shamir and Zhang'13]). Moreover, in the convex optimization setting, there are many DP gradient descent type algorithm that uses averaging, so it is not novel.


strength_and_weaknesses: Strength. Overall, I think this is a solid paper with consistent and extensive experiments. It also provides some theory explaining the insight of their method.

Weakness. (1) The aggregation of checkpoint seems to be fairly straightforward idea of post-processing. (2) The experiment improvement seems marginal. (3) The theory only explains the insight at the convex optimization domain, as I mentioned, there are a tons of related literature and I believe they have better rate in convex optimization setting.
clarity,_quality,_novelty_and_reproducibility: The paper is well-written, the idea seems to be new.
summary_of_the_review: This a solid paper, but the idea/improvement seems to be marginal for a ICLR paper.

--------------------------------------------------------------------------------

Post rebuttal

I have read the rebuttal and my evaluation remains.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies several methods that aggregate intermediate checkpoints (during training) to improve the utility of DP training. The authors propose two  classes of aggregation methods based on aggregating the parameters of checkpoints, or their outputs. Moreover, the authors consider the problem of quantifying the uncertainty that DP noise adds to DP ML training, and show that the sample variance from last few checkpoints provides a good approximation of the variance of the final model of a DP run. The proposed methods are supported by theoretical statements and empirical evaluations. 

All the authors found the ideas of the paper to be interesting. They also thought hat the paper was well written. I have discussed this papers with the reviewers, and some of their major concerns still remain. In particular (please see the updated reviews for full details), they were not convinced by (i) the statements/explanations provided in the paper on the gain in privacy-utility trade-off or uncertainty estimate by utilizing intermediate checkpoints; (ii) the experimental results need clear revisions/improvements. There were also some other concerns about the theoretical results, etc. 

All in all, I this the paper introduces a novel idea of using intermediate model aggregation to improve privacy-accuracy trade-off. Once the reviewers' concerns are properly addressed, the paper will become an interesting contribution to the literature of private learning. 
justification_for_why_not_higher_score: Two of the reviewers (which are expert reviewers) have recommended rejecting the paper. 
justification_for_why_not_lower_score: -
Decision: Reject