Let ( Ω , F ) (\Omega, \mathcal{F}) ( Ω , F )
α \alpha α
Definition. Given α ≥ 1 \alpha \ge 1 α ≥ 1 μ , ν \mu, \nu μ , ν ( Ω , F ) (\Omega, \mathcal{F}) ( Ω , F ) α \alpha α μ \mu μ ν \nu ν
D α ( μ ∥ ν ) ≐ sup S ∈ F ( μ ( S ) − α ⋅ ν ( S ) ) .
D_\alpha (\mu \Vert \nu) \doteq \sup_{S \in \mathcal{F}} \Big( \mu(S) - \alpha \cdot \nu(S) \Big).
D α ( μ ∥ ν ) ≐ S ∈ F sup ( μ ( S ) − α ⋅ ν ( S ) ) .
When α = 1 \alpha = 1 α = 1 D α ( μ ∥ ν ) D_\alpha (\mu \Vert \nu) D α ( μ ∥ ν ) total variational distance between μ \mu μ ν \nu ν
Properties
Theorem. D α ( μ ∥ ν ) D_\alpha (\mu \Vert \nu) D α ( μ ∥ ν )
Proof. Since ∅ ∈ F \emptyset \in \mathcal{F} ∅ ∈ F
D α ( μ ∥ ν ) ≥ μ ( ∅ ) − α ⋅ ν ( ∅ ) = 0.
D_\alpha (\mu \Vert \nu) \ge \mu(\emptyset) - \alpha \cdot \nu(\emptyset) = 0.
D α ( μ ∥ ν ) ≥ μ ( ∅ ) − α ⋅ ν ( ∅ ) = 0. □ \square □
Theorem (Joint Convexity). Let μ , ν , μ ′ , ν ′ \mu, \nu, \mu', \nu' μ , ν , μ ′ , ν ′ ( Ω , F ) (\Omega, \mathcal{F}) ( Ω , F ) α ≥ 1 \alpha \ge 1 α ≥ 1 t ∈ [ 0 , 1 ] t \in [0, 1] t ∈ [ 0 , 1 ]
D α ( ( 1 − t ) ⋅ μ + t ⋅ ν ∥ t ⋅ μ ′ + ( 1 − t ) ⋅ ν ′ ) ≤ ( 1 − t ) ⋅ D α ( μ ∥ μ ′ ) + t ⋅ D α ( ν ∥ ν ′ ) .
D_\alpha \left( (1 - t) \cdot \mu + t \cdot \nu \Big\Vert t \cdot \mu' + (1 - t) \cdot \nu' \right)
\le
(1 - t) \cdot D_\alpha \big( \mu \Vert \mu' \big)
+
t \cdot D_\alpha \big( \nu \Vert \nu' \big).
D α ( ( 1 − t ) ⋅ μ + t ⋅ ν t ⋅ μ ′ + ( 1 − t ) ⋅ ν ′ ) ≤ ( 1 − t ) ⋅ D α ( μ ∥ μ ′ ) + t ⋅ D α ( ν ∥ ν ′ ) .
Proof.
D α ( ( 1 − t ) ⋅ μ + t ⋅ ν ∥ t ⋅ μ ′ + ( 1 − t ) ⋅ ν ′ ) = sup S ∈ F ( ( 1 − t ) ⋅ μ ( S ) + t ⋅ ν ( S ) − α ( ( 1 − t ) ⋅ μ ′ ( S ) + t ⋅ ν ′ ( S ) ) ) = sup S ∈ F ( ( 1 − t ) ⋅ ( μ ( S ) − α μ ′ ( S ) ) + t ⋅ ( ν ( S ) − α ν ′ ( S ) ) ) ≤ sup S ∈ F ( ( 1 − t ) ⋅ ( μ ( S ) − α μ ′ ( S ) ) ) + sup S ∈ F ( t ⋅ ( ν ( S ) − α ν ′ ( S ) ) ) = ( 1 − t ) ⋅ D α ( μ ∥ μ ′ ) + t ⋅ D α ( ν ∥ ν ′ ) .
\begin{aligned}
&D_\alpha \left( (1 - t) \cdot \mu + t \cdot \nu \Big\Vert t \cdot \mu' + (1 - t) \cdot \nu' \right) \\
=
&\sup_{S \in \mathcal{F}} \Big(
(1 - t) \cdot \mu(S) + t \cdot \nu(S)
-
\alpha \Big(
(1 - t) \cdot \mu'(S) + t \cdot \nu'(S)
\Big)
\Big) \\
=
&\sup_{S \in \mathcal{F}} \Big(
(1 - t) \cdot \Big( \mu(S) - \alpha \mu'(S) \Big)
+
t \cdot \Big( \nu(S) - \alpha \nu'(S) \Big)
\Big) \\
\le
&\sup_{S \in \mathcal{F}} \Big(
(1 - t) \cdot \Big( \mu(S) - \alpha \mu'(S) \Big)
\Big)
+
\sup_{S \in \mathcal{F}} \Big(
t \cdot \Big( \nu(S) - \alpha \nu'(S) \Big)
\Big) \\
=
& (1 - t) \cdot D_\alpha ( \mu \Vert \mu' )
+
t \cdot D_\alpha ( \nu \Vert \nu' ).
\end{aligned}
= = ≤ = D α ( ( 1 − t ) ⋅ μ + t ⋅ ν t ⋅ μ ′ + ( 1 − t ) ⋅ ν ′ ) S ∈ F sup ( ( 1 − t ) ⋅ μ ( S ) + t ⋅ ν ( S ) − α ( ( 1 − t ) ⋅ μ ′ ( S ) + t ⋅ ν ′ ( S ) ) ) S ∈ F sup ( ( 1 − t ) ⋅ ( μ ( S ) − α μ ′ ( S ) ) + t ⋅ ( ν ( S ) − α ν ′ ( S ) ) ) S ∈ F sup ( ( 1 − t ) ⋅ ( μ ( S ) − α μ ′ ( S ) ) ) + S ∈ F sup ( t ⋅ ( ν ( S ) − α ν ′ ( S ) ) ) ( 1 − t ) ⋅ D α ( μ ∥ μ ′ ) + t ⋅ D α ( ν ∥ ν ′ ) . □ \square □
Theorem (Advanced Joint Convexity [1]). Let μ , μ ′ \mu, \mu' μ , μ ′
μ = ( 1 − t ) ⋅ μ 0 + t ⋅ μ 1 , μ ′ = ( 1 − t ) ⋅ μ 0 + t ⋅ μ 1 ′ ,
\mu = (1 - t) \cdot \mu_0 + t \cdot \mu_1, \quad \mu' = (1 - t) \cdot \mu_0 + t \cdot \mu_1',
μ = ( 1 − t ) ⋅ μ 0 + t ⋅ μ 1 , μ ′ = ( 1 − t ) ⋅ μ 0 + t ⋅ μ 1 ′ , for some t ∈ [ 0 , 1 ] t \in [0, 1] t ∈ [ 0 , 1 ] μ 0 , μ 1 , μ 1 ′ \mu_0, \mu_1, \mu_1' μ 0 , μ 1 , μ 1 ′ α ≥ 1 \alpha \ge 1 α ≥ 1 α ′ = 1 + t ⋅ ( α − 1 ) \alpha' = 1 + t \cdot (\alpha - 1) α ′ = 1 + t ⋅ ( α − 1 ) r = α ′ / α r = \alpha' / \alpha r = α ′ / α
D α ′ ( μ ∥ μ ′ ) = t ⋅ D α ( μ 1 ∥ ( 1 − r ) μ 0 + r μ 1 ′ )
D_{\alpha'} ( \mu \Vert \mu' ) = t \cdot D_\alpha ( \mu_1 \Vert (1 − r) \mu_0 + r \mu_{1}')
D α ′ ( μ ∥ μ ′ ) = t ⋅ D α ( μ 1 ∥ ( 1 − r ) μ 0 + r μ 1 ′ )
Proof.
For each S ∈ F S \in \mathcal{F} S ∈ F
μ ( S ) − α ′ μ ′ ( S ) = ( 1 − t ) ⋅ μ 0 ( S ) + t ⋅ μ 1 ( S ) − α ′ ( 1 − t ) ⋅ μ 0 ( S ) − α ′ t ⋅ μ 1 ′ ( S ) = t ⋅ ( μ 1 ( S ) − α ′ μ 1 ′ ( S ) ) − ( 1 − t ) ⋅ ( α ′ − 1 ) μ 0 ( S ) = t ⋅ ( μ 1 ( S ) − α ( α ′ α μ 1 ′ ( S ) + ( 1 − t ) ⋅ ( α ′ − 1 ) t α μ 0 ( S ) ) )
\begin{aligned}
\mu(S) - \alpha' \mu'(S)
&= (1 - t) \cdot \mu_0 (S) + t \cdot \mu_1 (S) - \alpha' (1 - t) \cdot \mu_0 (S) - \alpha' t \cdot \mu_1'(S) \\
&= t \cdot \left( \mu_1 (S) - \alpha' \mu_1'(S) \right) - (1 - t) \cdot \left( \alpha' - 1 \right) \mu_0 (S) \\
&= t \cdot \left( \mu_1 (S) - \alpha \left( \frac{\alpha'}{\alpha} \mu_1'(S) + \frac{(1 - t) \cdot (\alpha' - 1)}{t\alpha} \mu_0 (S) \right) \right)
\end{aligned}
μ ( S ) − α ′ μ ′ ( S ) = ( 1 − t ) ⋅ μ 0 ( S ) + t ⋅ μ 1 ( S ) − α ′ ( 1 − t ) ⋅ μ 0 ( S ) − α ′ t ⋅ μ 1 ′ ( S ) = t ⋅ ( μ 1 ( S ) − α ′ μ 1 ′ ( S ) ) − ( 1 − t ) ⋅ ( α ′ − 1 ) μ 0 ( S ) = t ⋅ ( μ 1 ( S ) − α ( α α ′ μ 1 ′ ( S ) + t α ( 1 − t ) ⋅ ( α ′ − 1 ) μ 0 ( S ) ) ) The following conditions are equivalent
1 − α ′ / α = ( 1 − t ) ⋅ ( α ′ − 1 ) / ( t ⋅ α ) , ⟺ t ⋅ α − t ⋅ α ′ = α ′ − t ⋅ α ′ − 1 + t , ⟺ 1 + t ⋅ ( α − 1 ) = α ′ .
\begin{array}{lrl}
&1 - \alpha' / \alpha &= (1 - t) \cdot (\alpha' - 1) / (t \cdot \alpha), \\
\Longleftrightarrow\,
&t \cdot \alpha - t \cdot \alpha' &= \alpha' - t \cdot \alpha' - 1 + t, \\
\Longleftrightarrow\,
&1 + t \cdot (\alpha - 1) &= \alpha'.
\end{array}
⟺ ⟺ 1 − α ′ / α t ⋅ α − t ⋅ α ′ 1 + t ⋅ ( α − 1 ) = ( 1 − t ) ⋅ ( α ′ − 1 ) / ( t ⋅ α ) , = α ′ − t ⋅ α ′ − 1 + t , = α ′ . Therefore, assuming that 1 + t ( α − 1 ) = α ′ 1 + t(\alpha - 1) = \alpha' 1 + t ( α − 1 ) = α ′ α ′ / α \alpha' / \alpha α ′ / α r r r
μ ( S ) − α ′ μ ′ ( S ) = t ⋅ ( μ 1 ( S ) − α ( r μ 1 ′ ( S ) + ( 1 − r ) μ 0 ( S ) ) ) , ∀ S ∈ F .
\mu(S) - \alpha' \mu'(S) = t \cdot \left( \mu_1 (S) - \alpha \left( r \mu_1'(S) + \big( 1 - r \big) \mu_0 (S) \right) \right), \quad
\forall S \in \mathcal{F}.
μ ( S ) − α ′ μ ′ ( S ) = t ⋅ ( μ 1 ( S ) − α ( r μ 1 ′ ( S ) + ( 1 − r ) μ 0 ( S ) ) ) , ∀ S ∈ F . Tanking supremum over both hand sides finishes the proof.
□ \square □
Application
Definition. Let μ , ν \mu, \nu μ , ν ( Ω , F ) (\Omega, \mathcal{F}) ( Ω , F ) ϵ , δ ≥ 0 \epsilon, \delta \ge 0 ϵ , δ ≥ 0 μ \mu μ ν \nu ν ( ϵ , δ ) (\epsilon , \delta) ( ϵ , δ )
D e ϵ ( μ ∥ ν ) ≤ δ , D e ϵ ( ν ∥ μ ) ≤ δ .
D_{e^\epsilon} (\mu \Vert \nu) \le \delta,
\qquad
D_{e^\epsilon} (\nu \Vert \mu) \le \delta.
D e ϵ ( μ ∥ ν ) ≤ δ , D e ϵ ( ν ∥ μ ) ≤ δ .
Based on advanced joint convexity, we have the following result.
Corollary. Let μ , μ ′ \mu, \mu' μ , μ ′
μ = ( 1 − t ) ⋅ μ 0 + t ⋅ μ 1 , μ ′ = ( 1 − t ) ⋅ μ 0 + t ⋅ μ 1 ′ ,
\mu = (1 - t) \cdot \mu_0 + t \cdot \mu_1, \quad \mu' = (1 - t) \cdot \mu_0 + t \cdot \mu_1',
μ = ( 1 − t ) ⋅ μ 0 + t ⋅ μ 1 , μ ′ = ( 1 − t ) ⋅ μ 0 + t ⋅ μ 1 ′ , for some t ∈ [ 0 , 1 ] t \in [0, 1] t ∈ [ 0 , 1 ] μ 0 , μ 1 , μ 1 ′ \mu_0, \mu_1, \mu_1' μ 0 , μ 1 , μ 1 ′ ϵ ≥ 0 \epsilon \ge 0 ϵ ≥ 0 ϵ ′ = ln ( 1 + t ⋅ ( e ϵ − 1 ) ) \epsilon' = \ln \left(1 + t \cdot (e^\epsilon - 1) \right) ϵ ′ = ln ( 1 + t ⋅ ( e ϵ − 1 ) ) r = e ϵ ′ / e ϵ r = e^{\epsilon'} / e^{\epsilon} r = e ϵ ′ / e ϵ
D e ϵ ′ ( μ ∥ μ ′ ) = t ⋅ D e ϵ ( μ 1 ∥ ( 1 − r ) μ 0 + r μ 1 ′ ) ≤ t ⋅ ( ( 1 − r ) ⋅ D e ϵ ( μ 1 ∥ μ 0 ) + r ⋅ D e ϵ ( μ 1 ∥ μ 1 ′ ) ) ≤ t ⋅ max ( D e ϵ ( μ 1 ∥ μ 0 ) , D e ϵ ( μ 1 ∥ μ 1 ′ ) ) .
\begin{aligned}
D_{e^{\epsilon'}} ( \mu \Vert \mu' )
&= t \cdot D_{e^{\epsilon}} ( \mu_1 \Vert (1 − r) \mu_0 + r \mu_{1}') \\
&\le t \cdot \Big( (1 − r) \cdot D_{e^{\epsilon}} ( \mu_1 \Vert \mu_0 ) + r \cdot D_{e^{\epsilon}} ( \mu_1 \Vert \mu_{1}') \Big) \\
&\le t \cdot \max \Big( D_{e^{\epsilon}} ( \mu_1 \Vert \mu_0 ), \, D_{e^{\epsilon}} ( \mu_1 \Vert \mu_{1}') \Big).
\end{aligned}
D e ϵ ′ ( μ ∥ μ ′ ) = t ⋅ D e ϵ ( μ 1 ∥ ( 1 − r ) μ 0 + r μ 1 ′ ) ≤ t ⋅ ( ( 1 − r ) ⋅ D e ϵ ( μ 1 ∥ μ 0 ) + r ⋅ D e ϵ ( μ 1 ∥ μ 1 ′ ) ) ≤ t ⋅ max ( D e ϵ ( μ 1 ∥ μ 0 ) , D e ϵ ( μ 1 ∥ μ 1 ′ ) ) .
Based on this corollary, suppose we know that μ 0 \mu_0 μ 0 μ 1 \mu_1 μ 1 ( ϵ , δ ) (\epsilon, \delta) ( ϵ , δ ) μ 1 \mu_1 μ 1 μ 1 ′ \mu_1' μ 1 ′ ( ϵ , δ ) (\epsilon, \delta) ( ϵ , δ ) μ \mu μ μ ′ \mu' μ ′ ( ϵ ′ , t δ ) (\epsilon', t \delta) ( ϵ ′ , t δ ) ϵ ≤ 1 \epsilon \le 1 ϵ ≤ 1
e ϵ ′ = 1 + t ⋅ ( e ϵ − 1 ) ⟺ e ϵ ′ − 1 = t ⋅ ( e ϵ − 1 ) ⟺ ϵ ′ ≈ t ⋅ ϵ .
\begin{array}{l}
&e^{\epsilon'} = 1 + t \cdot (e^\epsilon - 1) \\
\Longleftrightarrow
&e^{\epsilon'} - 1 = t \cdot (e^\epsilon - 1) \\
\Longleftrightarrow
&\epsilon' \approx t \cdot \epsilon.
\end{array}
⟺ ⟺ e ϵ ′ = 1 + t ⋅ ( e ϵ − 1 ) e ϵ ′ − 1 = t ⋅ ( e ϵ − 1 ) ϵ ′ ≈ t ⋅ ϵ . In comparison, if we apply the joint convexity directly, we only get
D e ϵ ( μ ∥ μ ′ ) = t ⋅ D e ϵ ( μ 1 ∥ μ 1 ′ ) ,
D_{e^{\epsilon}} ( \mu \Vert \mu' ) =
t \cdot D_{e^{\epsilon}} ( \mu_1 \Vert \mu_1' ),
D e ϵ ( μ ∥ μ ′ ) = t ⋅ D e ϵ ( μ 1 ∥ μ 1 ′ ) , and conclude that μ \mu μ μ ′ \mu' μ ′ ( ϵ , t δ ) (\epsilon, t \delta) ( ϵ , t δ ) ϵ \epsilon ϵ
Reference
[1] B. Balle, G. Barthe, and M. Gaboardi, “Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences,” arXiv:1807.01647 [cs, stat], Nov. 2018, Accessed: Apr. 29, 2022. [Online]. Available: http://arxiv.org/abs/1807.01647
← Back to all notes Back to top ↑