Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper
1. shows the first RDP bound of Propose-Test-Release (PTR) algorithm in differential privacy.
2. shows another RDP bound of subsampled PTR
3. demonstrates that it is tighter in composition and applies it to robust SGD
strengths_and_weaknesses: Picking up a classic work is great! I really appreciate the paragraph "Direct DP Analysis of Propose-Test-Release". The analysis is intuitive and clear. However, starting from section 4.2, the paper seems less readable to me compared to the early sections. For example, I didn't understand the $f_\alpha(\epsilon_1)$ and $f_\alpha(\epsilon_2)$ notations. It might be helpful to state the content of lines 221-223 as a lemma. Not surprisingly, I also don't understand the theorem for subsampled PTR.
questions: Does Figure show that your RDP bound can be worse than direct analysis? I don't quite understand why this could happen. 
limitations: The main, and very personal concern is that the privacy of PTR is still not nailed. It's easily seen to have room to improve, for example, the algorithm doesn't actually output $\hat{\Delta}$ but the analysis assumes so. I don't have very involved experience with such analyses, but it looks to me that what needs to be considered is simply the divergences of two Gaussian mixtures, each with two components. Can't we obtain privacy parameters that truly respect the truth, so that no one has to worry about improving the analysis anymore?

I don't want to be too negative and discourage the authors, but I think less trotting and more big leaps could be more beneficial to the field.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper derives an RDP bound for a generalized version of the Propose-Test-Release (PTR) framework, which is typically used to privately release robust statistics such as the median. The RDP analysis enables PTR to apply more readily to differentially private machine learning. The authors derive an RDP bound for Poisson-subsampled PTR, and use these tools to demonstrate how the PTR framework can improve the performance of robust SGD algorithms. Empirical results show that the PTR-based robust SGD offers an improvement over the baseline and is robust against corrupted data.

strengths_and_weaknesses: The RDP analysis of PTR is novel and useful; it makes good progress in extending the PTR framework to machine learning applications. The paper is also nicely balanced with the empirical evaluation supporting the theoretical claims.

As for weaknesses, I do wonder about how widely applicable the PTR framework could be even with an RDP analysis. It seems like needing the privately released function to have small local sensitivity might be difficult to satisfy across all the variants of DP-SGD (especially the non-robust variants).
questions: 1. Apart from trimmed mean-based SGD, are there other applications for PTR that would be effective for differentially private machine learning? And would any of these be outside the realm of robust statistics?

2. It seems like the experimental evaluation only compares trimmed mean-based robust SGD with and without PTR. How does trimmed mean-based robust SGD compare to its non-robust counterpart?

limitations: The authors adequately address the limitations of their work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper applies Renyi DP to the propose-test-release (PTR) framework. The algorithmic difference between this work and the literature is that it changes "release nothing" by "releasing the result with a large noise". Then, armed with the RDP-based PTR, the authors improved the SGD in terms of differential privacy and robustness.
strengths_and_weaknesses: Strengths:
1. The framework is very interesting, and it considers two "big issues", robustness and privacy, at the same time
2. The PTR framework indeed provides an improvement in accuracy.

Weakness:
1. The definition of robustness is very unclear. I am not sure about which setting the authors studies. Adversarial attacks? Data poisoning? Or any other settings?
2. I didn't see any experimental results for the robustness.
3. In Table 1, CR is not defined. I think it means corruption rate.
questions: 1. Can the authors clarify the setting of robustness here?
2. Any results or intuition for the robustness of the proposed method?
limitations: I haven't found any negative social impact in this paper
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: 
Propose-test-release (PTR) is a general recipe for data-dependent DP analysis. PTR first proposes a local sensitivity bound and then tests the distance to the dataset such that the local sensitivity of which is larger than the predefined local sensitivity bound. The original PTR framework returns nothing when the test fails, while this work extends the PTR by

1.   modifying the PTR algorithm allows ``privacy for free'' when the safety margin is small. 
2.  deriving the RDP bound for PTR approach as well as its subsampled variant. 
3. applying PTR to the private SGD with robust estimates.

I have checked the appendix except the part of convergence analysis. 
strengths_and_weaknesses:  
The textbook PTR does not support the RDP-based analysis as they do not specify the global sensitivity of the target function. Once the global sensitivity is specified, the RDP version's extension is straightforward. However, the tighter RDP analysis of subsampled PTR is non-trivial as the proposed PTR does not satisfy the ``exact upper/lower RDP bound condition'' from the known literature. Moreover, the application to the private SGD with trimmed mean is novel.
questions: 1. In the proof of Theorem 4.3, Case 1 considers both the local sensitivity of $S$ and $S'$ are greater than $\tau$. Why requiring both of them instead of at least one of the local sensitivity being greater than $\tau$?  In my understanding, the private test shall be done for the dataset $S$ and $S'$ separately.

2. The authors claim that  the trimmed mean parameter $F$ could be adjusted dynamically during the model training. This part needs more clarification. If $F$ is a privacy parameter, then adaptively selecting $F$ requires the ``fully adaptive composition'' [1], rather than the general adaptive composition offered by the RDP accountant.

Small comments:
1. I was confused about the algorithm design on introducing two functions (target function f1 and the robust function f2) with the same global sensitivity. Usually, the PTR algorithm only deals with the robust function. However, the proposed PTR does not always release the output of f2. The extra output of releasing f1(S) might be unnecessary. If the authors replace f1 with f2, the privacy guarantee will still hold with a more precise logic.
2. The choice on $\sigma_1$ and $\sigma_2$ in two figures. The benefit of all data-dependent analysis is the assumption that ``the local sensitivity will be orders smaller than its global sensitivity counterpart''. However, the choices of $\sigma_1$ and $\sigma_2$ in the figures (and also the experiments) imply that the local sensitivity they consider is 0.5 while the global sensitivity is 1. I suggest the authors to try various choice of $\tau$ in the next version.


[1] Ryan M Rogers, Aaron Roth, Jonathan Ullman, and Salil Vadhan. Privacy odometers and filters:
pay-as-you-go composition
limitations: Not applicable.
review_title: null

Meta-review: metareview: Paper studies RDP bound of Propose-Test-Release (PTR) algorithm in differential privacy.  In particular, it shows RDP bound of subsampled PTR and demonstrates how it is useful for composition of robust SGD. Given the textbook importance of PTR, we recommend accepting. However, we encourage authors to incorporate the comments from the authors, make sure that all the details of the proofs are made available in the final version, and clarify any comments reviewers raised.
confidence: Less certain
Decision: Accept