Regularized Loss Minimizers with Local Data Obfuscation

Zitao Li, Jean HonorioarXiv 2018 · arXiv

Abstract

This paper introduces Data Irrecoverability (DI), a novel framework for local data protection that offers a more flexible alternative to Differential Privacy (DP). While DP guarantees irrecoverability, the converse is not always true, allowing for robust data protection even when strict privacy definitions are not met. We analyze the impact of local data perturbation on Regularized Loss Minimizers across various models, demonstrating that data can be protected from adversarial reconstruction while maintaining high machine learning performance and consistent convergence rates.

Introduction

In the modern data economy, a fundamental tension exists between data utility and individual privacy. While Differential Privacy (DP) is the standard for formalizing privacy, its strict mathematical requirements can be overly restrictive, especially in "local" settings where users randomize data before transmission. This paper addresses the gap between privacy and data recoverability, asking whether a broader concept of protection can be defined based on the impossibility of adversarial reconstruction.

The Data Irrecoverability Framework

The authors formalize DI as a condition where the probability of an adversary correctly guessing original data from a perturbed version is bounded by a constant. This framework is applied to Regularized Loss Minimizers, covering models from linear regression to matrix factorization.

Key methodological components include:

  • Loss Consistency Analysis: Extending scaled uniform convergence to show that models trained on noisy data still converge to the true hypothesis.
  • Information-Theoretic Bounds: Using Fano’s Inequality and Mutual Information to calculate the minimum noise variance required for protection.
  • Broad Model Application: Analyzing five major problem types, including MLE for exponential families, GLMs, and Nonparametric regression.

To validate these theoretical proofs, the researchers utilize synthetic data models, including Ising models for discrete high-dimensional settings, exponential family distributions for various noise structures, and binary matrices for PCA and matrix factorization analysis.

Theoretical Insights

A core finding is that privacy is sufficient, but not necessary, for irrecoverability. This implies that irrecoverable algorithms exist that do not satisfy DP, potentially offering more efficient data protection schemes. Furthermore, the "price" of adding noise is often just a constant factor slowdown in learning rates. For many high-dimensional applications, the required noise variance for DI does not need to scale with the number of features, a significant advantage for "Big Data."

Convergence Rates and Noise Thresholds

The paper provides a comprehensive summary of convergence rates under noise for various models. For instance, in MLE and GLMs using $\ell_1$ regularization, the convergence rate shifts from $O(\sigma_x \sqrt{\log p / n})$ to $O(\sqrt{\sigma_x^2 + \sigma_\eta^2} \sqrt{\log p / n})$.

Table 1: Convergence rates and minimum noise thresholds for various regularized loss minimizers under local data obfuscation.

Specific lower bounds for noise variance are established. For many cases, if noise variance $\sigma_\eta^2 \geq \frac{4}{(1-\gamma)\log 2}$, adversarial recovery fails with probability greater than $\gamma$. The results demonstrate that "loss consistency" (the model getting better as you add more data) still holds even when the data is intentionally obfuscated.

Conclusion

The DI framework demonstrates that data obfuscation can protect individual inputs without sacrificing the long-term consistency of machine learning models. While the current work focuses on loss consistency, future research may extend these proofs to sign consistency and sparsistency, and broaden the scope to tasks like nonparametric clustering.

Summary updated

Abstract

We introduce a new concept, data irrecoverability, and show that the well-studied concept of data privacy is sufficient but not necessary for data irrecoverability. We show that there are several regularized loss minimization problems that can use perturbed data with theoretical guarantees of generalization, i.e., loss consistency. Our results quantitatively connect the convergence rates of the learning problems to the impossibility for any adversary for recovering the original data from perturbed observations. In addition, we show several examples where the convergence rates with perturbed data only increase the convergence rates with original data within a constant factor related to the amount of perturbation, i.e., noise.
BibTeX
@misc{li2018regularized,
  author = {Zitao Li and Jean Honorio},
  title = {{Regularized Loss Minimizers with Local Data Obfuscation}},
  year = {2018},
  eprint = {1805.07645},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1805.07645},
}
Figure