Contraction of $E_γ$-Divergence and Its Applications to Privacy
This work addresses privacy concerns in machine learning by providing a theoretical framework to precisely measure privacy loss, with applications to both local and differential privacy settings, though it is incremental in extending existing contraction concepts to a new divergence.
The paper tackles the problem of analyzing privacy in machine learning by deriving contraction coefficients for the $E_\\gamma$-divergence, leading to closed-form expressions that quantify the impact of local differential privacy on estimation and hypothesis testing, and enable new techniques for analyzing privacy guarantees in online algorithms like gradient descent.
We investigate the contraction coefficients derived from strong data processing inequalities for the $E_γ$-divergence. By generalizing the celebrated Dobrushin's coefficient from total variation distance to $E_γ$-divergence, we derive a closed-form expression for the contraction of $E_γ$-divergence. This result has fundamental consequences in two privacy settings. First, it implies that local differential privacy can be equivalently expressed in terms of the contraction of $E_γ$-divergence. This equivalent formula can be used to precisely quantify the impact of local privacy in (Bayesian and minimax) estimation and hypothesis testing problems in terms of the reduction of effective sample size. Second, it leads to a new information-theoretic technique for analyzing privacy guarantees of online algorithms. In this technique, we view such algorithms as a composition of amplitude-constrained Gaussian channels and then relate their contraction coefficients under $E_γ$-divergence to the overall differential privacy guarantees. As an example, we apply our technique to derive the differential privacy parameters of gradient descent. Moreover, we also show that this framework can be tailored to batch learning algorithms that can be implemented with one pass over the training dataset.