Privacy Analysis of Online Learning Algorithms via Contraction Coefficients

Shahab Asoodeh, Mario Díaz, Flávio P. CalmonarXiv 2020 · arXiv · OpenReview

Abstract

We investigate the contraction coefficients derived from strong data processing inequalities for the $E_\gamma$-divergence. By generalizing the celebrated Dobrushin's coefficient from total variation distance to $E_\gamma$-divergence, we derive a closed-form expression for the contraction of $E_\gamma$-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_\gamma$-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_\gamma$-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.

Introduction

In the field of Differential Privacy (DP), a central challenge is "privacy accounting"—the process of tracking the cumulative privacy loss as an algorithm iteratively processes sensitive data. For complex, iterative processes like training neural networks via Stochastic Gradient Descent (SGD), standard accounting techniques often rely on Rényi Differential Privacy (RDP). While RDP simplifies the composition of privacy budgets, the final conversion back to the standard $(\epsilon, \delta)$-DP framework can be "loose," leading to overly conservative privacy estimates. This overestimation forces a trade-off where more noise is added than necessary, ultimately degrading the utility of the model.

This research introduces a novel mathematical framework to address these inefficiencies by leveraging contraction coefficients of $E_\gamma$-divergence. By viewing privacy through the lens of information theory, the authors provide a more precise method for calculating privacy budgets in online learning environments.

Theoretical Foundation: Contraction of $E_\gamma$-Divergence

The core of this work lies in the study of $E_\gamma$-divergence (also known as hockey-stick divergence), which is the natural information-theoretic measure for $(\epsilon, \delta)$-DP. The authors generalize Dobrushin’s contraction coefficient—originally defined for Total Variation (TV) distance—to $E_\gamma$-divergence.

The paper provides a closed-form expression (Theorem 2) for the contraction coefficient of $E_\gamma$-divergence across any Markov kernel. This theoretical breakthrough allows researchers to quantify exactly how much "divergence" (and thus, how much sensitive information) shrinks as it passes through a noisy channel. Because $E_\gamma$-divergence directly maps to DP parameters, this contraction coefficient provides a direct path to privacy analysis without the need for intermediate RDP conversions.

Local Differential Privacy as Contraction

One of the paper's most significant insights is the formal equivalence between Local Differential Privacy (LDP) and $E_\gamma$ contraction. Specifically, a mechanism satisfies $(\epsilon, \delta)$-LDP if and only if its $E_{e^\epsilon}$ contraction coefficient is bounded by $\delta$.

This equivalence allows for a precise quantification of the "cost" of privacy in statistical tasks. For instance, in Bayesian and minimax estimation or hypothesis testing, the requirement for LDP can be viewed as a reduction in the "effective sample size." The authors show that requiring LDP is mathematically equivalent to shrinking the dataset from $n$ samples to $n(1 - (1-\delta)e^{-\epsilon})$ samples. This provides a clear, intuitive metric for the utility loss associated with local privacy constraints.

Privacy Analysis of Online Learning

The authors apply their contraction framework to online learning algorithms, such as Projected Noisy SGD (PNSGD). They model these algorithms as a Markov chain of "amplitude-constrained Gaussian channels." In this model, each iteration of the algorithm is a noisy transformation that further "contracts" the information from the initial data points.

By analyzing the contraction coefficients directly, the authors derive $(\epsilon, \delta)$ parameters that are significantly tighter than previous state-of-the-art methods. Notably, for large privacy parameters, their method shows that privacy guarantees decay at a rate of $e^{-O(\epsilon^2)}$, a substantial improvement over the $e^{-O(\epsilon)}$ decay found in earlier literature. This suggests that as the algorithm progresses, the initial "signal" from any single individual's data is "washed out" by the cumulative noise more effectively than previously understood.

Key Results and Utility Trade-offs

The paper validates these theoretical gains through numerical simulations and synthetic examples. For PNSGD, the new bounds are shown to be tighter across a wide range of learning rates and noise levels compared to established benchmarks.

Furthermore, the research explores the trade-off between privacy and utility in Online Gradient Descent. By providing concrete bounds for "stochastic regret" (Section IV-C), the authors demonstrate exactly how much accuracy is sacrificed to maintain a specific level of central differential privacy. This framework is not limited to online settings; it can also be tailored to batch learning algorithms that operate in a single pass over the training data.

Conclusion and Future Directions

This work establishes a powerful link between information-theoretic contraction and differential privacy. By focusing on $E_\gamma$-divergence, the authors provide a more direct and precise accounting method for iterative algorithms.

However, some limitations remain. The current analysis relies on amplitude constraints (e.g., bounded gradients), which, while standard in DP via gradient clipping, may not apply to all algorithmic variations. Additionally, the analysis primarily focuses on the privacy of the final output (the "last-iterate"), rather than the privacy of the entire sequence of updates (the "trajectory"). Future research may extend these contraction-based techniques to other privacy definitions, such as $f$-DP, or explore the privacy of the full algorithmic path.

Summary updated

Abstract

We investigate the contraction coefficients derived from strong data processing inequalities for the $E_\gamma$-divergence. By generalizing the celebrated Dobrushin's coefficient from total variation distance to $E_\gamma$-divergence, we derive a closed-form expression for the contraction of $E_\gamma$-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_\gamma$-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_\gamma$-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.
BibTeX
@misc{asoodeh2020privacy,
  author = {Shahab Asoodeh and Mario Díaz and Flávio P. Calmon},
  title = {{Privacy Analysis of Online Learning Algorithms via Contraction Coefficients}},
  year = {2020},
  eprint = {2012.11035},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2012.11035},
}

Loading related content...

Figure