Renyi Differential Privacy of Propose-Test-Release and Applications to Private and Robust Machine Learning
Authors: Tianhao Wang
Saeed Mahloujifar
Shouda Wang
Ruoxi Jia
Prateek Mittal
Venue: NeurIPS 2022 Accept (2022)
Keywords: Renyi Differential Privacy
Propose Test Release

Abstract: Propose-Test-Release (PTR) is a differential privacy framework that works with local sensitivity of functions, instead of their global sensitivity. This framework is typically used for releasing robust statistics such as median or trimmed mean in a differentially private manner. While PTR is a common framework introduced over a decade ago, using it in applications such as robust SGD where we need many adaptive robust queries is challenging. This is mainly due to the lack of \Renyi Differential Privacy (RDP) analysis, an essential ingredient underlying the moments accountant approach for differentially private deep learning. In this work, we generalize the standard PTR and derive the first RDP bound for it. We show that our RDP bound for PTR yields tighter DP guarantees than the directly analyzed $(\varepsilon, \delta)$-DP. We also derive the algorithm-specific privacy amplification bound of PTR under subsampling. We show that our bound is much tighter than the general upper bound and close to the lower bound. Our RDP bounds enable tighter privacy loss calculation for the composition of many adaptive runs of PTR. As an application of our analysis, we show that PTR and our theoretical results can be used to design differentially private variants for byzantine robust training algorithms that use robust statistics for gradients aggregation. We conduct experiments on the settings of label, feature, and gradient corruption across different datasets and architectures. We show that PTR-based private and robust training algorithm significantly improves the utility compared with the baseline. 

Rényi Differential Privacy of Propose-Test-Release and Applications to Private and Robust Machine Learning
Jiachen T. Wang
Saeed Mahloujifar Princeton University sfar@princeton, edu
Princeton University
tlanhaovaag@ppiicttoo..coo
Shouda Wang Princeton University sv1041@princetonn.
Ruoxi Jía
Prateek Mittal Princeton University pmittal@prrinetton.cc edu
Virginia Tech
Fuoxijia@vt.
Abstract
Propose-Test-Relent (PTR) is a differential privacy framework that works with local sensitivity of functions, instead of their global sensitivity. This framework is typically used for releasing robust statistics such median trimmed mean in a differentially private manner. While PTR is a common framework introduced over decade ago, using it in applications such robust SGD where need many adaptive robust queries is challenging. This is mainly due to the lack Rényi Differential Privacy (RDP) analysis, essential ingredient underlying the moments accountant approach for differentially private deep learning. this work, we generalize the standard PTR and derive the first RDP bound for it when the target function has bounded global sensitivity. We show that our RDP bound for PTR yields tighter DP guarantees than the directly analyzed (e, 0D-DP. We also derive the algorithm-specing privacy amplification bound of PTR under subsampling. We show that our bound is much tighter than the general upper bound and close to the lower bound. Our RDP bounds enable tighter privacy loss calculation for the composition of many adaptive runs of PTR. As an application of our analysis, we show that PTR and our theoretical results can be used to design differentially private variants for byzantine robust training algorithms that use robust statisties for gradients aggregation. We conduct experiments on the settings of label, feature, and gradient corruption across different datasets and architectures. show that PTR-based private and robust training algorithm significantly improves the utility compared with the baseline.
Introduction
Privacy is a major concern for deploying machine learning (ML). In response, differential privacy (DP) [DMNS06] has become the fe-facto measure of privacy. For differentially private mechanism, the probability distribution of the mechanism's outputs on a dataset should be close to the distribution of its outputs the same dataset with any single individual's 's data replaced. A general recipe for releasing the value of a function f on dataset S in a differentially private way is adding random noise to f(S) (output perturbation), where noise magnitude should scale with f's global sensitivity.
However, it might be over-conservative to add noise scaled with global sensitivity. There is line of research whether we can do better (e.g., INRS07 [L909 TSI3 KNRSE)) Hoopose-Test-ellee (PTR) [L.99 is a framework that improves the general recipe with the notion local sensitivity.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

The main idea of PTR is as follows: instead of adding noise with respect to global sensitivity, we propose an amount of noise that tolerable for many common queries. When we receive the actual query, we test (in differentially private way) whether answering the query with the proposed amount of noise enough for privacy. the proposed noise is too small for limiting the privacy loss from the actual query, we may refuse to answer the query or respond with a larger noise. PTR works especially well for releasing robust statistics such as median or trimmed mean, as the robust statistics usually have small local sensitivity most common inputs.
While PTR is a basic framework that ages back to the early days after the introduction of DP. it has not been used for differentially private optimization before. DP-SGD [ACG*16] is the general backbone for differentially private deep learning and optimization. One major challenge of augmenting SGD with PTR and training DP models is the calculation of privacy parameters after a large number of adaptive compositions. Rényi differential privacy (RDP) and Moment Accountant [Mi ACG 16) enable us to calculate tighter privacy parameters for training DP models. Without the RDP hound of PTR, we need to calculate the privacy parameters using the advanced composition theorems [D + 14 that can lead to significantly looser privacy bounds. Besides, we also need the bound of privacy amplification by subsampling for PTR, which is the other important support for training DP models. It allows us to exploit the stochasticity of SGD for the interest of stronger privacy guarantees.
Technical Overview. In this work, we derive the Rényi DP bound for PTR. as well as for its Poisson subsampled variant when the target function has bounded global sensitivity. Our bounds make it possible for us use PTR framework in augmenting private SGD. PTR could be characterized by three mechanisms. The first mechanism is Mi that determines which mechanism to run next. Depending on the outcome of M1 we then either run M2 or M2 It is often the case that the worst-case privacy loss of one of M2 or M2 is much larger than the other. Our bound exploits the fact that the worst-case will happen with small probability. Specifically, instead of considering the worst-case privacy loss between M2 and M2. and naively composing it with Mi, we show that for RDP we can tighten the bound by the average privacy loss of M2 and M' under the distribution imposed by MM. Direct (e, dD analysis does not enjoy this benefit; compared with directly analyzing the (e, -DP bound of PTR, we show that by first bounding the RDP of PTR and then convert it to (z, 6DD can lead to better privacy guarantee. Our proof could serve general recipe for analyzing DP/RDP guarantees for composed mechanisms where the privacy loss of each mechanism is adaptively determined. Additionally, we extend our analysis the RDP of subsampled PTR. Our algorithm-specific analysis (the "white-box bound") allows us to get tighter privacy amplification bounds, compared with the one obtained by general subsampled RDP bound that supports any mechanisms (the "black-box bound")) [7] The proof tackled several additional
difficulties compared with the analysis for simple Gaussian mechanism [TTZ By numerical verification, we show that our RDP bound for subsampled PTR is much tighter than the black-box
bound, and is close to the lower bound (Figure
Applications of PTR in ML. PTR is especially suitable for improving the utility of privatizing robust statistics such trimmed mean, as these functions usually have much smaller local sensitivity compared to their global sensitivity. A critical application of robust statistics for machine learning is defending against corrupted data. The learning algorithm should be robust in the presence of corrupted data (referred to as Byzantine failure (LSP82).. ). Since privacy and robustness are two major concerns for ML training, developing techniques that achieve both goals simultaneously is desirable. We demonstrate the application of PTR in incorporating differential privacy with robust SGD methods. A popular technique for robustifying SGD is replace the mean with some robust statistics (e.g.. trimmed mean) for gradient aggregation [YCKBI8 AHJ+ GLV2TJ. We use trimmed mean as an example of showing how to augment robust SGD with DP through PTR. We show that the augmented SGD still maintains the robustness guarantec. We conduct extensive experiments on defending against three kinds of attacks: label, feature, and gradient corruptions, and we show that PTR-based robust SGD achieves much better utility than naively privatizing the robust SGD with global sensitivity.
2 Related Work
Since the seminal work of [LL09) the mainly used in statistical inference [BM200] LKO2T.
has become a common DP framework To the best of our knowledge, this work the first application of PTR in machine learning.
2

---

Several prior works (e.g., [LQS12 BEGI8 WBK19 ZW19 focus the general subsampled DP/RDP bound that supports any mechanisms. [BK11 derives general RDP privacy amplification for "sampling without replacement" scheme, and ZW obtains similar result under Poisson subsampling (i.e., including each data point independently at random with certain probability). Only small body of recent works study algorith--specffec privacy amplification bound by subsampling. However, most of them focus on subsampled Gaussian mechanism |ACG* 16, BDRST8 MTZI9] This work derives the first subsampled RDP bound specific for flexible algorithms such as PTR.
Designing machine learning and optimization algorithms that achieve both privacy and Byzantine- robustness is certainly an important direction. Nevertheless, there are only few works on this line so far. |G) considered the problem of achieving privacy and byzantine resilience in distributed SGD with an untrusted server. The privacy level they considered is essentially local differential privacy, which is orthogonal to our focus. [HK]20] and [SGA20 aim for both robustness and secure multiparty computation instead of differential privacy. [MZH119 naively applies differential privacy to defend against data poisoning attack. However, they find that DP alone cannot defend adversaries that poison large fraction of training examples. Aside from the setting of training ML models, [LККO2I propose a polynomial time algorithm that achieves both goals for mean estimation via privatizing filter-based robust mean estimator [DKK 17). [EMN2I develop a robust and differentially private mean estimator based on exponential mechanism. However, both of their approaches become inefficient (even in polynomial time asymptotically) in high dimensional settings.
3 Background
In this section, we introduce some background on differential privacy, Rényi differential privacy, and arivacy-amplificatii by subsampling. We will also introduce notations as we proceed.
Differential Privacy. Differential privacy is a framework for protecting privacy when performing statistical releases dataset with sensitive information about individuals (see the surveys DR+114 VadIZ). Specifically, for a differentially private mechanism, the probability distribution of the mechanism's 's outputs of a dataset should be close the distribution of its outputs on the same dataset with any single individual's s data replaced. To formalize this, we call two datasets S, S', each multisets over data universe X, adjacent if one can be obtained from the other by adding or removing single element of X. Further, we use d(S, S') to denote the number of times of adding/removing of data points to transform S to S'. So S and S' are adjacent if and only if d(S, =1.
Definition 3.1 (Differential Privacy (DMS006). ). For e, 0, randomized algorithm M MultiSets ()) + y is (e, 8)-differentiaall private if for every dataset pair S' e MMultiSess()))
such that d(S, 1, we have:
VTCD Pr(M(S) E S
e Pr(M(S') ET
where the randomness is over the coin flips of M.
Rényi Differential Privacy (RDP). Rényi differential privacy (RDP) is a variant of the standard (E, dDDP that uses Rényi-divergence as distance metric between the output distributions of M(S) and M(S),, which is particularly useful in training differentially private machine learning models.
Definition 3.2 (Rényi Differential Privacy [Mri77]) We say that a mechanism A is (a, e) RDDP with order a E oo) if for every dataset pair S, E MulttSets((2') such that d') = 1, we have:
1 - log Bis =-
(MMISSO))
DR (M(S))LM(S')
(2)
where pm(()) denotes the density function of M's distribution. Further, we denote the moment
E. (S()) := EooM(s)) (
(M)rs((o) ( )
and function fa(s) = exx(((x-aaa>))) - 1)s).
As we can see, (ax,) RDD is essentially an upper bound for the moment E, (M(S))M (S") S (s) for all adjacent S, where e can be viewed as degree of the privacy loss incurred by running M. A different a typically leads to a different privacy bound e. Following the convention of literature IW11, we view E as function of and the notation (v)(a) means the algorithm M obeys
3

---

(a, (.Mm))))DDDD We note that RDP reduces to (s. 0)-DP when we take co. The current tightest (E, 6)-DP/DDP transformation we are aware by (1LC*21). A central property of DP/RDP its behavior under composition. If we run multiple distinct differentially private algorithms on the same dataset, the resulting composed algorithm is also differentially private, with some degradation in the privacy parameters (c,5). Specifically, if we run k sequentially chosen (e, 6)-DP algorithm on
dataset, the overall composed privacy parameter is (Ō(Vks), kō + 5') -DP by Advanced composition
theorem [DR 14]. However, the Advanced composition theorem for ().6)- is loose. On the contrary, the composition is trivial for RDP as &M, (.) E.M, (-) + E.M,()). (-). The Moment Accountant technique, which composes RDP and then transforms to DP, is a much simpler approach and often produces much more favorable privacy parameters than directly composing (e, 8)-DP. Therefore, RDP and Moment Accountant are widely used to calculate the privacy guarantee in training differentially private deep learning models.
Privacy amplification by subsampling. "Privacy amplification by subsampling" is the other booster besides RDP/ moments accountant that drives much of the recent progress in differentially private deep learning. Most of the existing works focus on Poisson subsampling [BEGIE] which samples each data point independently with a given sampling probability q. The tightest privacy amplification bound we are aware of for general mechanism under Poisson Subsampling is from [WT9]
4 Propose- Test- and Rényi Differential Privacy
In this section, we introduce a general version of the Pespose-Test-Reee framework, present our main results on its RDP bound, and its privacy amplification bound under Poisson subsampling.
In our presentation, use G of target function (in & distance), and denote the local sensitivity of function f on dataset S. Before present our main results, we would like to remind the readers about the definition of Laplace and Gaussian mechanisms, as well as their DP/RDP bound, which will be referred to later in the main results.
IIf(S) f(S")l to denote the global sensitivity
(S) sups.s'
[I f(S")]l to
Laplace Mechanism: If f's output is 1-dimensional, the Laplace mechanism Mlap,b(S) = (8) e²/², and obeys (a, Lap (ap(a))-DDD for
f(S) + Tap((,))) b) obeys (elap: 0)-DP for e(
R La- Lap (a) - log exp
( n-1 2 exp (-+)). where b = b/OSş (the "noise-
to io-sensitivity" ratio).
Gaussian Mechanism: If f's output is d-dimensional, the Gaussian mechanism MM..(() = ((S)+W(0, oheys (e (6), 5DD for (2) (6) = ã 2 (1.25/0), and obeys (a, 6 x())- RDP for R R-x(a)= 2 where ā o / (the "noise- soiss-to-sensstivvtt"" ratio).
(0)
(5)
4.1 Propose-Test-Releee
Naive use of Laplace/Gaussian mechanism may result in the poor utility of function output, as the global sensitivity of the target function may be intolerably large due to some extreme cases. Meanwhile, robust statistics such as median, mode, Inter-Quantile Range (IQR) are quite insensitive to single data addition/rremovll for datasets that are i.i.d. drawn from natural distributions. This means that robust statistics may have a small local sensitivity for most input datasets. The seminal work framework reduce the noise addition when the target function has an approximation that is robust statistic" Here, we introduce a more general and useful version of PTR instantiated by Laplace and Gaussian mechanism. Given target function f1 (e.g.. mean) and its robust variant /2 (e.g., median), the PTR framework proceeds as follows: (1) Propose: local sensitivity bound of the target function, т, is proposed; (2) Test: safety margin A(S), which is the minimum amount of data points that we need to replace for S to have local sensitivity larger than T, is computed. A private version (via Laplace mechanism) of the safety margin, A, is compared with threshold; (3) Release: the safety margin is large enough, then the algorithm releases (S) via Gaussian mechanism with a smaller noise 02 (usually scaled with 7). Otherwise, the algorithm
of [DL09] introduced Propose-Test
Sometimes the robust statistic itself the target function, i.e., fi f2 in Algorithm

---

release fi(S) with a larger noise di (usually scaled with G The pseudocode is outlined in Algorithm
We make several remarks on Algorithm | Remark 4.1. (1) The traditional version of PTR in the textbooks DD+14 V simply refuse to output anything when the noisy safety margin Á is small. Algorithm iis a more general version which output (i()) + +O00 La when the sensitivity test is failed. The textbook PTR can be thought of as special case of Algorithm | where we set 01 - oc. (2) The mechanism used in the Test and Release step be other mechanisms instead of Laplace and Gaussian. In this paper. we present our sults for the PTR instantiated by these two mechanisms since we intend to apply it for differentially private SGD later. Our proof can be easily extended to other mechanisms as well. (3) The threshold
Propose-Tese Laplace and Gaussian mechanism.
Algorithm 1:
with
input S dataset, f1 target function, f2 robust statistic, 7 proposed local sensitivity bound of fz. 01, d2, Gaussian/Laplace noise scales
(a) > o2), 6n failure probability.
1 min ($),, d (s. (
2 A + A + b).
3 A S log(1/ (266))) then
return (1(5) (1 of
s else
return f2(5) + NV(0,
in Line is chosen that Pr[Lap(O, > (og(1/(26)))) 6o- (4) The global sensitivity of (--) is 1 for any functions. This could be seen by noticing that, for any pair of adjacent S, S", we have d(S, S) S d(S", 1 for any dataset S.
We show the DP guarantee for the Propose- -est- Release framework. To prove privacy, we need to find the worst pair of adjacent datasets and S' that incurs the largest privacy loss. It is clear that the worst possible scenario of PTR is when [2(S) - (2(S) > т, while the algorithm still releases (2(S) with noise scaled with r. However, note that this worst possible scenario will only happen when both IL3(S) and T.S(S") are greater than т. In this case, however, A for both S and S" are 0 since there are no data points we need to change for them to have local sensitivity larger than and thus there is no privacy loss from A. Moreover, when A = O, the probability that PTR will release (2( + (O, o3 1a) is at most dg by construction, which could be simply added to the d term in (e. DD. If one of LS(S) and ILS(S") is smaller than t, then we know that /2(S)- [2(S") $ т, and the overall privacy parameters could be computed by Basic Composition Theorem [DR + 14]. We obtain the following differential privacy guarantee for PTR based on these observations. We defer more details of the proof to the Appendix
Direct DP Analysis of Coopose-Test-Rlleeee
Theorem 4.2 (Direct DP analysis for PTR). Suppose GS GE 1 and 01 02/T, then (a1)
Algorithm is ( + EN (6), 00 + 6)-DP, where ELap = e//b is the DP guarantee for Laplace
mechanism, and EN (d) 2 (1.55/0)
4.2 RDP of Propose- Teee-Teet--eResse
We then derive the RDP of Propose-Test Test-Release framework. The major differences between the proofs of (z, DD and RDP bound is that, for (s, oDD we can move the probability of running into the bad scenario to the ô term, while for RDP need to consider the "average-case" privacy loss. This is in fact an advantage of RDP, which we illustrate
the following simple example.
Comparison between (s, DDP and RDP Analysis: A motivating example i Suppose we have two mechanisms Mj and M2 who are (1 DDP and (E2.62)-1 dDP, respectively. Consider simple PTR-like mechanism M that randomly picks one of mechanisms Mi and M2 to execute, each with probability ōn and dg. respectivelyEi We can only claim that M (max(e1, 82): (1 50)6, + )DP, or if we know 82 > we can also move the "bad case" probability do to the 8 term and obtain (e1, 80 + dD)-DP. However, if we know the RDP guarantee of M, and M2 as I (51) and E. (M) < fa then E. (M())))M)(
E. (M))
Details of derivation can be found in Appendix A
FFor the actual PTR, the do is not fixed hut depends on the input dataset.
'Recall that (e( exp((a- 1)e) where if M (a, e) RDD then Es (M(S))M((S)) $ fa(e).
5

---

Direct Analysis
Converted from RDP
0
0,
4.
1,
le 5
0
16,
02
8, b
1,6
1e-5
0
8,
4,
0.5,
1e-5
1,50
1.24
1.23
1.48
2.48
1.22
1466
1.21
144
2.44
(a)
2
0p 1e-6 0
6
(b)
4
8
(c)
4
8
60
16-6
0p
1e-6
The E parameter of the (e, DD guarantee of PTR when å = 10 for different noise scales. We convert the RDP bound in Theorem 4.3 (e, o by the RDP-DP conversion formula from BBBG+20), and compare it with the & obtained from the direct analysis Theorem 4.2 For the bound converted from RDP, search for the optimal different 6n since when 6g is small, the RDP for PTR will take the second term in
Figure 1:
[1, 200). The bound is constant across
can be simply bounded by (1 - (o) no extra inequalities used in RDP analysis of M except for the RDP guarantee of Mi and M2. Thus, RDP more favorable in for PTR's privacy analysis, especially when &g is close the target 6.
(E2) Compared with (c, 5)-DP analysis, there
Theorem 4.3 (RDP analysis of PTR). Suppose GS,, GS₁z 1 and 01 02/T. Then for any > 1, Algorithm i is (o,ErTR((a))RDD) for
(01) (PTR(o) max [5a ((1 (11-5)) (01) (<k-v(a)) + dola (L(z) (x)= R-x((a) + (b)
R- (a)
The above result implies that, with appropriately chosen op. the privacy loss PTR the same as directly adding up the privacy loss from A and from releasing fi fi()) + ((0,oī1a) regardless of the value of Â. Compared with naively releasing (S) + of(0 PTR will only pay extra cost for privatizing A, independent from the privacy cost for the case of releasing fz(S) + (00 ozla)! Thus, the algorithm could potentially add much smaller noise while introducing just little extra privacy loss. In Figure we convert this RDP bound to (e, 6)P via the RDP-DP conversion formula by [BG 20). and compare with the (s, 6DD bound obtained through direct analysis in Theorem 4.2 Although due to the loss in RDP-DP conversion, the & parameter by RDP is worse than the by direct analysis when 6p far smaller than the target 6, it is tighter when dg close to 8. A larger ōn means PTR has a greater chance to release (2( + (0, o 1a), which leads to a better utility. Thus, the privacy parameter converted from the RDP bound more favorable.
We would like to stress that in the theorem, most the conditions on the parameters such as GS or 01, 22 be easily relaxed. The conditions in the theorems mainly used to make the presented bound more clean and interpretable.
4.3 RDP for Poisson Subsampled Beeposs-Test-RRlleee
We further derive the RDP for Poisson subsampled PTR. Here, "subsampled" means the input dataset will be subsampled first before feeding to PTR. Poisson subsampling means cach data point x will be included with probability independently. One way of obtaining the RDP for any subsampled mechanism is by simply plugging in the RDP bound of the original algorithm into the privacy amplification formula for general mechanisms (e.g., [WBK19] (W19). Here, we directly derive the RDP for Poisson subsampled PTR in white-box manner. Denote MM as the random variable for PTR's output on dataset S, and MI for PTR's output on dataset
S U {xr, and M (1 Mo + q.M. Compared with the analysis for subsampled Gaussian mechanism by MTZ19). there are two main difficulties for extending the arguments of quasi-convexity of Rényi divergence for PTR: (1) the distribution of PTR's 's output may not be centrally symmetric, thus need bound both (2(M)))Ma) and (MMp) MM). (2) the conditional distribution M cannot decomposed as (1 4)MM + &. A big part our novelty the proof is about addressing these two challenges. We defer details of the proof to Appendix A

---

Black-bok box Bound
White-bol box Bound
Lower Bound
0 8, 02 = 11
0 16, 0 = ==
= 0g
4, b 0.5
0.0100
0.004
q 4e
0.0075
9- 0.01
0.003
E(a)
0.002
9 0.01
0.005
0.0050
0. 0.005
q 2e
0.0001
0.001
0.0025
q= 0.003
q
0.0000
0.000
=
0.003
0.0000
50
(a)
(b)
(c)
0
Figure 2: The RDP parameter ((a) of the subsampled PTR function of order We compare the white-box bound from Theorem 4.4 and the black-box bound as well as the lower bound by plugging in the RDP of PTR in Theorem to the privacy amplification upper/lower bounds for general mechanisms from ZW119.
4
Theorem 4.4 (RDP analysis of sub-sampled PTR (the "wh bound")). Let q be the subsampling probability. Suppose GS GS 1 and 01 02/T. When q, 1,, 02 and satisfy certain conditions, we have
PoissoooionSaalll (a) S fa (max B1,
where By + a(a - 1)(21 + ) ). B, = R (0) + 2a(a - 1) 2(11 - Rg (a-1)
of
(1 - 1)
B2 R(a) + 20((a - (a(ag
2(1 9) g) + (1 - -)2 with R(aa.
Ex
1
m() Ho(s)
and R(aa) E Enap
[a](s] M(s)
for μi ~ Lap(O, b) and ~ (1 L1g)Laap(O.l
gLap(1. b).
Remark 4.5. Both R and R. can be computed easily since they either have closed form or can be accurately computed via numerical integration in bounded range.
This bound may not be very interpretable, which is typical feature for the privacy amplification bounds as they are meant to be implemented in practice. After all, constant matters for differential privacy practitioners! To show the tightness of our bound, we plug the RDP of original PTR
(Theorem 4.3) 3 to the current tightest privacy amplification formula for general mechanisms derived
[ZW19 (the "black-box bound"), and compare it with our white-box bound in Theorem 4.4 As
we see from Figure 2 Theorem
(orange curve) is much tighter than the black-box bound (blue curve). Moreover, it is very close to the lower bound of privacy amplification by [ZW19 (green line), which means that Theorem
is near optimal. In Figure S we illustrate the application of subsampled RDP bound in Moment Accountant. We can see that the privacy parameters for the composed mechanism obtained based on white-box bound (Theorem 4.4 is tighter than the one by black-box box bound, as well as the one by directly composing Theorem 4.2 with strong composition theorem [KOV15) We remark that Direct Analysis achieves lower privacy loss with very few iterations since we set 6 = 10-8 to allow more iterations for Strong Composition of Os which leads better for single iteration (see Figure M-
An exciting byproduct during our research on subsampled PTR is the privacy amplification bound for M that outputs Mi (S), scquentially and independently. This result is important since such a M is instantiated in many existing techniques in improving differentially private deep learning. We defer this result to the Appendix.
5 Differentially Private and Robust SGD with Propose--Tes-RRleeas
In this section, we demonstrate the application of the RDP for (subsampled) PTR algorithm in privatizing robust SGD algorithms.
Attack Model. Mini-batch SGD is common method for training deep neural networks. Despite its strong convergence properties in the standard settings, it is well known that even small fraction of corrupted gradients can lead SGD to an arbitrarily poor solution BTNO)) BECIT. An important attack model is called Byzantine contamination framework Byzantine failure SP82 Consider an
7

---

Black box Bound Moment Acct.
White box Bound
Moment Acct.
Direct Analysis
Comp.
8, 02 4, b 1, 0.001
16, 02 8, b 1, 0.001
0,
=
8, 02 4, b 0.5, 0.001
0.200
0.225
0.175
0.2
0.200
0.150
w
0.175
0.150
0.125
0.125
0.100
0.0
250
500
750
1000
0
250
500
750
1000
250
500
750
1000
(a)
# Iterations
(b)
#
Iterations
(c)
#
Iterations
Figure 3: Illustration of the use of our Theorem 4.4 in moments accountant. We plot the the privacy
loss for 8 = 10 after different rounds of composition. We set dg 10 here to allow more iterations for Strong Composition of (E, 6D-D.
optimization problem with n stochastic gradient oracles; at each iteration there are up to F gradient oracles are corrupted (usually referred as Byzantine agents in the context of distributed SGD). The identity of corrupted oracles a priori unknown. As the corrupted gradients can be arbitrarily skewed, this attack model is able capture many important scenarios including corruption in feature (e.g.. existence of outliers), corruption in gradients (c.g., hardware failure, unreliable communication channels during distributed training) and corruption in labels (c.g. label flip (backdoor) attacks).
popular class of defense strategies against Byzantine failure to use robust gradient aggregation rules such as trimmed-mean [GLV21], coordinate- -oree median [YCKB18], and geometric median 21 Since both privacy and robustness are essential for ML applications, is important to develop learning algorithms that achieve differential privacy and robustness simultaneously.
natural (but naive) way to accomplish such goal for SGD-based algorithms is to privatize each iteration of robust SGD through Gaussian mechanism. Specifically, in each iteration, we add Gaussian noise to the aggregated gradient, where noise magnitude scale with the global sensitivity of the robust aggregation function. The privacy parameter for the entire process computed through Moment Accountant. The global sensitivity can be obtained by either upper bounding the Lipschitz constant of the objective function, or clipping each gradient according to a certain threshold. However, this method could potentially add ever-conservative noise to the aggregated gradients, as the local sensitivity of robust aggregation functions usually very low for most input gradient sets.
Baseline: privatizing robust SGD with Gaussian Mechanism.
Privatizing robust SGD with PTR. We improve the naive method with the PTR framework, where we instantiate it by showing how to privatize trimmed-ment SGD method from GLV2II. We first define trimmed-sumfi aggregation function, and show that the A for trimmed-sum could be computed efficiently. Given a dataset
{zI...., Im let T(k) denote the kth smallest data point among S &2 norm, i.e., |لرييا||| S ||<(2) S ... S ||=(m) Il. The F-rrimmed sum of S is defined as (SUMs(S) Em- 2(() if m F, simply 0 if S F. De- fine (S) su LL, which is the maximum local sensitivity that can be achieved by adding/removing elements from S. Thus, I (S) LS)(S), and the safety margin ASS) = min(r: L (S) > 7). Therefore, long as we can efficiently compute (S), can efficiently compute ASS) linear time by simply enumerate all r from m and terminate once / (S) > In fact. TSUMp (S) can be computed in O(1) time.
Theorem 5.1. IS (S) = (100==((mmma-a |m |l ifr < 1, or CSTSUM ifr> Tr>F--1
Back to the goal of designing differentially private and robust SGD. Fix a positive integer F which is a potential upper bound for the number of corrupted gradients. We instantiate PTR -TR-based gradient aggregation algorithm by instantiating f.) as SUM(S) Exes x, and fz(:) as TSUM We simply plugging in this PTR algorithm as the gradient aggregation function for regular SGD. We show
'ee use trimmed- sum instead of trimmed- hinmed--maan mean for the ease of analysis, as trimmed mean essentially just scales the learning rate.
8

---

Dataset
Corruption Type
CR
3.0
==
GaGsia
TSGD+PTR
TSGD+Gaussia
TSGD+PTR
87.53%
91.43%
(+3.9%
81.31%
92.8%
(+11.49%)
MNIST
Label
0.1
90.15%
93.29%
(+3.138%)
89.15%
94.608%
(+5.456%)
91.33%
92.704%
(11.374%)
92.47%
94.084%
(.611%%
0.1
89.47%
92.28%
(+2.812%)
86.53%
93.388%
+6.854%)
Feature
0.2
91.71%
92.29%
(+0.582%)
86.99%
92.864%
++5.872%)
0.1
90.27%
91.7%
(+1.43%)
88.41%
91.68%
(+3.2%%)
Gradient
0.2
91.13%
91.45%
(+0.32%)
88.70%
90.31
(+1.6%)
7.0
10.0
TSGD+Gausian
ISGD+PTR
TSGD+Gaussan
ISGD+PTR
0
57.94%
58.92%
(+00.8%%
58 38.82%
60.13% (+1.31%)
CIFARIO Label
0.1
55.48%
56.262%
(10.78%)
57.42%
58.218%
(.088)
0,2
49.69%
50.946% (+1.26%%
52.95%
53.106%
(+0.152%)
55.70%
56.628%
(+-0.93%)
57.36%
58.678%
+1.118%
Feature
0.2
55.13%
55.526%
0.3396%)
56.93%
57.336%
0.404%)
0.1
55.81%
57.29%
(+1.48%)
57.21%
58.96%
+11+11110 +.75%)
Gradient
0.2
54.45%
56.31%
(+1.86%
56.11%
57.48%
1.37%)
2.0
2.5
TSGD+Gaussan
TSGD+PTR
TSGD+Gausian
TSGD+PTR
0
72.94%
76.44%
(+3.5%)
79.15%
81.02%
(+1.87%)
EMNIST
Label
0.1
72.60%
75.66%
(+3.06%)
79.38%
80.63%
[+1.25%)
0.2
70.03%
72.62% (+.2.99%)
77.48%
79.19%
[+1.71%)
69.60%
74.01%
14.41%)
77. 77.80%
81.04%
3..44%
Feature
0.2
70.04%
74.76%
(+4.722%)
78.99%
80.74%
(+1.75%)
0.1
7 71.75%
76.19%
(+-4.44%)
77.32%
77.73%
++0.41%)
Gradient
0.2
70.76%
74.65%
(13.89%)
76.68%
77.17%
0.4.9%
Table 1: Model Accuracy under different privacy budgets and corruption settings. Every statistic averaged over runs with different random seed. The improvement of TSGD PTR over TSGD + Gaussian is highlighted in the red text. Es are chosen differently for different datasets since the best eccuracy-privaee tradeoff point varied for datasets. 'CR' means corruption ratio.
the convergence guarantee of this algorithm in the presence at most gradients being corrupted for the that the loss function is Lipschitz.
Theorem 5.2 (Informal). When the loss function is Lipschitz in model parameters, SGD with PTR instantiated by SUM and TSUM provides convergence guarantee for update F gradients being corrupted arbitrarily for any F < m/2.
We make remarks of specific design choices for implementing PTR- (RR-based SGD in practice. Remark 5.3. (1) In practice, F could be adjusted dynamically during the model training, based the value of 2 That is, if B, means that the current gradient batch has many outliers, thus we increase F for the next iteration; if Â B, it means that gradients are relatively concentrated and few of them are corrupted, thus we can decrease F afterwards. (2) We set S1 as SUM instead of
TSUM since F is usually set to be larger than the actual corrupted gradients; in this case, Â B means that there are many benign gradients also have large norms. These benign gradients usually correspond the data points that are misclassified by the partially trained models, which is important for improving model performance. The pseudocode for the algorithm is deferred to the Appendix
5.1 Evaluation
In this section, we empirically evaluate the performance of PTR-based private and robust SGD, Specifically, compare the utility arlivay tradcoff between the algorithm that privatize trimmed mean-based SGD with PTR (TSGD + PTR), and the baseline algorithm that privatize trimmed mean-based SGD with Gaussian mechanism (TSGD Gaussian).
Experiment Settings. We evaluate the Sellitt-privccy tradeoff of the two robust and differentially private SGD algorithms under three common types of attack: label, feature, and communicated gradient corruption. For label corruption, we randomly flip of label of certain amount of data points. For feature corruption, we add Gaussian noise from (00, 100) directly to the corrupted images. For
Thii does not introduce extra privacy leakage DP closed under post-processing

---

gradient corruption, we add Gaussian noise from (O,, 100) to the true gradients. We experiment on three classic datasets, MNIST, CIFARIO, and EMNIST. We vary different corruption ratios and privacy parameter Experiment details are deferred to Appendix.
Results. The comparison of model test accuracy under given corruption settings and privacy parameters are summarized in Table D We highlight the improvement of TSGD + PTR over the baseline TSGD + Gaussian in red texts. As we can see, for all settings, TSGD + PTR outperforms and often works significantly better than TSGD + Gaussian. This demonstrates that, while TSGD PTR may introduce extra privacy loss in the test step, the performance gain from adding smaller noise in the release step overshadows it.
We also observe two interesting phenomena in the experiment: (1) higher corruption ratio may not necessarily lead to worse model performance for trimmed mean-based robust SGD, especially for MNIST dataset. This is because the high norm gradients be either corrupted, benign but the partially-traindd model misclassifies the corresponding data points. The latter case is extremely important for improving model performance compared with the gradients of data points are already being classified correctly. When the corruption ratio is small, more benign gradients are being trimmed, which may lead to worse model performance. (2) For TSGD Gaussian, larger privacy budget may not lead to better model performance on MNIST dataset. This is because when the training accuracy reaches the peak, there are many trimmed gradients whose corresponding training data points are already correctly classified; continuing training without those data points and with large noise may result in catastrophic forgetting.
Conclusion and Limitation
This work derives the Rényi Differential Privacy for propose-test-relesee framework as well as its subsampled version. With the RDP bound for the PTR framework, this work demonstrate the application of PTR in training differentially private and robust models. One limitation of PTR is that it does not work well privatizing coordinate-we wise median in high-dimensional space. The global sensitivity of coordinate- median is far greater than the one for mean, which results in huge privacy loss.
Acknowledgement
We are grateful to anonymous reviewers NeurIPS for valuable feedback. This work was supported in part by the National Science Foundation under grants CNS2131910, CNS-1553437, CNS-1553301, ENS-1704105, and CNS- 1953786, the ARL's Army Artificial Intelligence Innovation Institute (A212), the Office of Naval Research Young Investigator Award, the Army Research Office Young Investigator Prize, Schmidt DataX award, Princeton E-ffiliates Award, Amazon- Virginia Tech Initiative Efficient and Robust Machine Learning, and Princeton's 's Gordon Y. S. Wu Fellowship.
10

---

References
[ACG*16] Martín Abadi, Andy Chu, lan J. Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24-28, 2016, pages 308-318. ACM, 2016.
[AH]*21] Anish Acharya, Abolfazl Hashemi, Prateek Jain, Sujay Sanghavi, Inderjit S Dhillon, and Ufuk Topcu. Robust training in high dimensions via block coordinate geometric median descent. arXiv preprint
2021.
[ALC*21] Shahab Asoodeh, Jiachun Liao, Flavio Calmon, Oliver Kosut, and Lalitha Sankar. Three variants of differential privacy: Lossless conversion and applications. IEEE Journal on Selected Areas in Information Theory, 2(1):208-222, 2021.
[BAM20]
Victor-Emmanuel Brunel and Marco Avella-Medina. Propose, test, release: Differ- entially private estimation with high probability. arXiv preprint arXiv:2002.08774 2020.
[BBC11] Dimitris Bertsimas, David B Brown, and Constantine Caramanis. Theory and applica- tions of robust optimization. SIAM review, 53(3):464 -60551,6 2011.
[BBG18] Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsam- pling: Tight analyses via couplings and divergences. Advances in Neural Information Processing Systems, 31, 2018.
[BBG+20] Borja Balle, Gilles Barthe, Marco Gaboardi, Justin Hsu, and Tetsuya Sato. Hypothesis testing interpretations and renyi differential privacy. In International Conference on Artificial Intelligence and Statisties, pages 2496-254005 PMLR, 2020.
[BDR118] Mark Bun, Cynthia Dwork, Guy N Rothblum, and Thomas Steinke. Composable and versatile privacy via truncated edp. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 74-86, 2018.
[BTN00] Aharon Ben- Tal and Arkadi Nemirovski. Robust solutions of linear programming problems contaminated with uncertain data. Mathematical programming, 88(3):411- 424, 2000.
[CATVS17] Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik. Emnist: Extending mnist to handwritten letters. In 20/7 international joint conference on neural networks (IJCNN), pages 2921-2926. IEEE, 2017.
[DKK*17 17] Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Being robust (in high dimensions) can be practical. In International Conference on Machine Learning, pages 999-1008. PMLR, 2017.
[DL09] Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 371-380, 2009.
[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
Foundations and Trends in Theoretical Computer Science, 9(3-4):21 (--4)):2114477, 2014. [DR* 14] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differrnniill privacy.
[MM21]] Hossein Esfandiari, Vahab Mirrokni, and Shyam Narayanan. Tight and robust private mean estimation with few users. arXiv preprint arXiv:21 1 2021.
[GGP+21] Rachid Guerraoui, Nirupam Gupta, Rafael Pinot, Sebastien Rouault, and John Stephan. Combining differential privacy and byzantine resilience distributed sgd. arXiv preprint arXiv:21 10.09911 2021.

---

[GLV21] Nirupam Gupta, Shuo Liu, and Nitin Vaidya. Byzantine fault-tolerant distributed machine learning with norm- based comparative gradient elimination. In 2021 51st Annual IEEE/FFP International Conference on Dependable Systems and Networks Workshops (DSN-W) W), pages 175-181. IEEE, 2021.
[HD18] Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. In International Conference on Learning Representations, 2018.
[HKJ20] Lie He, Sai Praneeth Karimireddy, and Martin Jaggi. Secure byzantine-robust machine learning. arXiv preprini 44X14:2006.04747, 2020.
[HZRS16] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[KNRSI3] Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Analyzing graphs with node differential privacy. In Theory of Cryptography Conference, pages 457-476. Springer, 2013.
[KOV15] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference on machine learning, pages 1376-1385. PMLR, 2015.
[Kri09] Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
[LeC98] Yann LeCun. The mnist database of handwritten digits. com/exdb/mmis/// 1998.
http://yann. lecun.
[LKKO21] Xiyang Liu, Weihao Kong, Sham Kakade, and Sewoong Oh. Robust and differentially private mean estimation. Advances in Neural Information Processing Systems, 34, 2021.
[LKO21] Xiyang Liu, Weihao Kong, and Sewoong Oh. Differential privacy and robust statistics in high dimensions. arXiv preprint arXiv:2111.06574 2021.
[LQS112] Ninghui Li, Wahbeh Qardaji, and Dong Su. On sampling, anonymization, and differ- ential privacy or, k-anonymization meets differential privacy. In Proceedings of the 7th ACM Symposium on Information, Computer and Communications Security, pages 32-33, 2012.
[LSP82] LESLIE LAMPORT, ROBERT SHOSTAK, and MARSHALL PEASE. The byzan- tine generals problem. ACM Transactions on Programming Languages and Systems, 4(3):382 401, 1982.
[Mir17] Ilya Mironov. Rényi differential privacy. In 2017 JEEE 30th Computer Security Foundations Symposium (CSF), pages 263-275. IEEE, 2017.
[MTZ19] Ilya Mironov, Kunal Talwar, and Li Zhang. Rényi differential privacy of the sampled gaussian mechanism. arXiv preprint arXiv: 10530, 2019.
[MZH19] Yuzhe Ma, Xiaojin Zhu, and Justin Hsu. Data poisoning against differentially- learners: Attacks and defenses. arXiv preprint arXiv: Net::1903309880 2019.
[NRS07] Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sam- pling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 75- 84, 2007.
[SGA20] Jinhyun So, Başak Güler, and A Salman Avestimehr. Byzantine-resilien secure feder- ated learning. IEEE Journal on Selected Areas in Communications, 39(7):2168-2183 2020.
[SZ.4] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large- scale image recognition. arXiv preprint
2014.
12

---

[TS13] Abhradeep Guha Thakurta and Adam Smith. Differentially private feature selection via stability arguments, and the robustness of the lasso. In Conference on Learning Theory, pages 819-850, 2013.
[Vad17] Salil Vadhan. The complexity of differential privacy. In Tutorials the Foundations of Cryptography, pages 347-450. Springer, 2017.
[VEH14] Tim Van Erven and Peter Harremos. Rényi divergence and kullback-leibler divergence. IEEE Transactions Information Theory, 60(7):3797-3820, 2014.
[WBK19] Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled rényi differential privacy and analytical moments accountant. In The 22nd International Conference Artificial Intelligence and Statistics, pages 1226-1235, PMLR, 2019.
[XKG19] Cong Xie, Sanmi Koyejo, and Indranil Gupta. Zeno: Distributed stochastic gradient descent with suspicion-based fault-tolerance. In International Conference on Machine Learning, pages 6893-6901. PMLR, 2019.
[YCKB18] Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robus distributed learning: Towards optimal statistical rates. In International Conference Machine Learning, pages 5650-5659. PMLR, 2018.
[ZW19] Yuqing Zhu and Yu-Xiang Wang. Poission subsampled rényi differential privacy. volume 97 of Proceedings of Machine Learning Research, pages 7634-7642, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] See Section and 5 in particular Figure 2 and Table
(b) Did you describe the limitations of your work? [Yes] See Section 6 for discussion on limitations.
(c) Did you discuss any potential negative societal impacts of your work? [No] We do not see any potential negative societal impacts of our work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Appendix
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix A
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] We provide our code in supplementary material.
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix B for full details.
(c) Did you report error bars (e.g.. with respect to the random seed after running experi-
ments multiple times)? [Yes] We report error bars for Table in Appendix B
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Appendix for full details.
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [es]] We cite each dataset and model architecture we use, see full details in Appendix
(b) Did you mention the license of the assets? [Yes] See Appendix
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "rVaeyqTY5Tf", "reviewer": "Reviewer_6cEn", "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.\n", "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?\n\n2. 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?\n", "limitations": "The authors adequately address the limitations of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nAs 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).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Zoo_825raDC", "reviewer": "Reviewer_ebzu", "summary": "The paper\n1. shows the first RDP bound of Propose-Test-Release (PTR) algorithm in differential privacy.\n2. shows another RDP bound of subsampled PTR\n3. demonstrates that it is tighter in composition and applies it to robust SGD", "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?\n\nI 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.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "SDnRL7IeuXD", "reviewer": "Reviewer_Tbda", "summary": "\nPropose-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\n\n1.   modifying the PTR algorithm allows ``privacy for free'' when the safety margin is small. \n2.  deriving the RDP bound for PTR approach as well as its subsampled variant. \n3. applying PTR to the private SGD with robust estimates.\n\nI have checked the appendix except the part of convergence analysis. ", "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.\n\n2. 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.\n\nSmall comments:\n1. 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.\n2. 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.\n\n\n[1] Ryan M Rogers, Aaron Roth, Jonathan Ullman, and Salil Vadhan. Privacy odometers and filters:\npay-as-you-go composition", "limitations": "Not applicable. ", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": " \nThe 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "BAFgYEPCem", "reviewer": "Reviewer_tPa6", "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.", "questions": "1. Can the authors clarify the setting of robustness here?\n2. Any results or intuition for the robustness of the proposed method?", "limitations": "I haven't found any negative social impact in this paper", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The framework is very interesting, and it considers two \"big issues\", robustness and privacy, at the same time\n2. The PTR framework indeed provides an improvement in accuracy.\n\nWeakness:\n1. 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?\n2. I didn't see any experimental results for the robustness.\n3. In Table 1, CR is not defined. I think it means corruption rate.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept