Recent frameworks in differential privacy (DP), such as privacy loss distributions and f-DP, provide lossless representations of the privacy leakage of mechanisms. These approaches are often considered to yield tighter (ε,δ)-DP guarantees than those obtained from relaxed notions such as Rényi DP. But is that always the case? We study this question for differentially private stochastic gradient descent (DP-SGD) with fixed-size batches under replace adjacency. Our key observation is that in this setting, privacy accounting based on Rényi DP can use a pair of worst-case distributions (i.e., a dominating pair) that differs from the one used in the lossless frameworks. In particular, we characterize the worst-case distributions as two-dimensional Gaussian mixtures and derive an improved Rényi DP bound for DP-SGD. Numerical and asymptotic comparisons show that across various hyperparameter settings, a Rényi DP accountant based on the new bound can yield better privacy guarantees than those obtained from the lossless frameworks.
Figures & tables
Figure 1: Illustration of the Gaussian mixtures that serve as a Rényi dominating pair for DP-SGD (see ( 5 )); here p=0.2,Δ=4.5,u=0.3 . The points (0,0) , Δ(1,0) , and Δ(u,2u−u2) (each corresponding to the mean of the mixture component) form an isosceles.
Figure 2
Figure 4: Illustration of privacy bounds for finite T and their asymptotic limit (Lemma 3 and Proposition 4 ; note that the latter is a limit superior). Here, p depends on T , keeping Tp2=ν . As ε increases, our bounds provide better privacy guarantees than those from lossless accountants. The privacy bounds become closer to their limits as T increases.
Figure 5: Illustration of Rényi DP bounds and their asymptotic expansions (Proposition 5 , truncated at p3 terms). For ( BEBP, 24 ) , we set the tuning parameter to be m=4 . The actual bounds are close to the asymptotic expansions when the Rényi order α is small, but they deviate more as α increases, in particular for the bounds from ( BEBP, 24 ) .
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
σ
T
Rényi accountants
Lossless accountants
Relative difference
Our bounds
Birrell et al.
Wang et al.
1
250
6.40
≥100
6.84
5.10
{\color[rgb]{1,0,0}+25.48\%}
500
6.84
≥100
7.73
5.68
{\color[rgb]{1,0,0}+20.32\%}
1000
7.72
≥100
9.51
6.53
{\color[rgb]{1,0,0}+18.26\%}
2000
9.49
≥100
13.06
7.80
{\color[rgb]{1,0,0}+21.63\%}
4000
13.03
≥100
15.16
9.76
{\color[rgb]{1,0,0}+33.46\%}
Appendix
Table 1: Accounted privacy ε for δ=10−6 and p=0.0025 .
σ
T
Rényi accountants
Lossless accountants
Relative difference
Our bounds
Birrell et al.
Wang et al.
1
250
13.77
≥100
15.14
10.27
{\color[rgb]{1,0,0}+34.03\%}
500
15.11
≥100
17.86
12.90
{\color[rgb]{1,0,0}+17.13\%}
1000
17.79
≥100
23.29
16.96
{\color[rgb]{1,0,0}+4.85\%}
≥2000
≥20 for all accountants
2
250
1.77
3.27
2.21
1.34
{\color[rgb]{1,0,0}+31.35\%}
Appendix
Table 2: Accounted privacy ε for δ=10−6 and p=0.01 .
σ
T
Rényi accountants
Lossless accountants
Relative difference
Our bounds
Birrell et al.
Wang et al.
1
≥250
≥20 for all accountants
2
250
5.45
16.66
9.07
5.45
{\color[rgb]{1,0,0}+0.01\%}
500
7.31
20.89
13.02
7.79
{\color[rgb]{0,1,0}-6.22\%}
1000
10.59
29.34
20.08
11.48
{\color[rgb]{0,1,0}-7.82\%}
2000
15.22
46.26
29.75
17.37
{\color[rgb]{0,1,0}-12.39\%}
Appendix
Table 3: Accounted privacy ε for δ=10−6 and p=0.04 .
σ
T
Rényi accountants
Lossless accountants
Relative difference
Our bounds
Birrell et al.
Wang et al.
1
250
8.70
≥100
9.14
7.11
{\color[rgb]{1,0,0}+22.41\%}
500
9.14
≥100
10.03
7.83
{\color[rgb]{1,0,0}+16.75\%}
1000
10.03
≥100
11.81
8.85
{\color[rgb]{1,0,0}+13.31\%}
2000
11.79
≥100
15.36
10.32
{\color[rgb]{1,0,0}+14.31\%}
4000
15.33
≥100
19.76
12.53
{\color[rgb]{1,0,0}+22.37\%}
Appendix
Table 4: Accounted privacy ε for δ=10−8 and p=0.0025 .
σ
T
Rényi accountants
Lossless accountants
Relative difference
Our bounds
Birrell et al.
Wang et al.
1
250
18.37
≥100
19.75
13.45
{\color[rgb]{1,0,0}+36.60\%}
500
19.71
≥100
22.46
16.45
{\color[rgb]{1,0,0}+19.82\%}
≥1000
≥20 for all accountants
2
250
2.36
4.19
2.87
1.89
{\color[rgb]{1,0,0}+24.53\%}
500
2.65
5.11
3.54
2.33
{\color[rgb]{1,0,0}+13.65\%}
Appendix
Table 5: Accounted privacy ε for δ=10−8 and p=0.01 .
σ
T
Rényi accountants
Lossless accountants
Relative difference
Our bounds
Birrell et al.
Wang et al.
1
≥250
≥20 for all accountants
2
250
6.60
20.32
10.60
6.67
{\color[rgb]{0,1,0}-1.07\%}
500
8.84
25.49
15.32
9.31
{\color[rgb]{0,1,0}-5.05\%}
1000
12.29
33.95
22.39
13.46
{\color[rgb]{0,1,0}-8.69\%}
2000
17.52
50.86
34.36
20.03
{\color[rgb]{0,1,0}-12.53\%}
Appendix
Table 6: Accounted privacy ε for δ=10−8 and p=0.04 .
Figure 6: Median runtimes of Rényi accountants, for p=0.01,σ∈{2,6},δ=10−8 , and T∈{1000,10000} . The error bars represent the 10th and 90th percentiles. In this setting, our accountant runs faster for T=10000 because the binary search based on the unimodality in Rényi order (see Proposition 3 ) terminates earlier.