2019

Obfuscation via Information Density Estimation

Hsu, Hsiang, Asoodeh, Shahab, Calmon, Flavio du Pin

Understand

Identifying features that leak information about sensitive attributes is a key challenge in the design of information obfuscation mechanisms.

In this paper, we propose a framework to identify information-leaking features via information density estimation.
Here, features whose information densities exceed a pre-defined threshold are deemed information-leaking features.
Once these features are identified, we sequentially pass them through a targeted obfuscation mechanism with a provable leakage guarantee in terms of $\mathsf{E}_\gamma$-divergence.

Built on

M. S. Pinsker, Information and information stability of random variables and processes . San Francisco: Holden-Day, 1964
1964
Earlier work this paper cites.
I. Csiszár, “Information-type measures of difference of probability distributions and indirect observations,” Studia Sci. Math. Hungar. , vol. 2, pp. 299–318, 1967
1967
Earlier work this paper cites.
M. D. Donsker and S. S. Varadhan, “Asymptotic evaluation of certain markov process expectations for large time. iv,” Communications on Pure and Applied Mathematics , vol. 36, no. 2, pp. 183–212, 1983
1983
Earlier work this paper cites.
T. Amemiya, “Asymptotic properties of extremum estimators,” Advanced econometrics, Harvard university press , 1985
1985
Earlier work this paper cites.
K. W. Church and P. Hanks, “Word association norms, mutual information, and lexicography,” Computational linguistics , vol. 16, no. 1, pp. 22–29, 1990
1990
Earlier work this paper cites.
T. S. Han and S. Verdú, “Approximation theory of output statistics,” IEEE Transactions on Information Theory , vol. 39, no. 3, pp. 752–772, 1993
1993
Earlier work this paper cites.
W. K. Newey and D. McFadden, “Large sample estimation and hypothesis testing,” Handbook of econometrics , vol. 4, pp. 2111–2245, 1994
1994
Earlier work this paper cites.
W. Hoeffding, “Probability inequalities for sums of bounded random variables,” in The Collected Works of Wassily Hoeffding . Springer, 1994, pp. 409–426
1994
Earlier work this paper cites.
S. van de Geer, Empirical Processes in M-estimation . Cambridge university press, 2000, vol. 6
2000
Earlier work this paper cites.
A. Evfimievski, J. Gehrke, and R. Srikant, “Limiting privacy breaches in privacy preserving data mining,” in Proc. of ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , 2003
2003
Earlier work this paper cites.
C. M. Bishop, Pattern recognition and machine learning . springer, 2006
2006
Earlier work this paper cites.
K. Nissim, S. Raskhodnikova, and A. Smith, “Smooth sensitivity and sampling in private data analysis,” in Proceedings of the thirty-ninth annual ACM symposium on Theory of computing . ACM, 2007, pp. 75–84
2007
Earlier work this paper cites.
M. Sugiyama, M. Krauledat, and K.-R. MÃžller, “Covariate shift adaptation by importance weighted cross validation,” Journal of Machine Learning Research (JMLR) , vol. 8, no. May, pp. 985–1005, 2007
2007
Earlier work this paper cites.
T. MPLab, “The MPLab GENKI Database, GENKI-4K Subset,” http://mplab.ucsd.edu , 2009
2009
Earlier work this paper cites.
A. Smola, L. Song, and C. H. Teo, “Relative novelty detection,” in Proc. of International Conference on Artificial Intelligence and Statistics (AISTATS) , 2009
2009
Earlier work this paper cites.
X. Nguyen, M. J. Wainwright, and M. I. Jordan, “Estimating divergence functionals and the likelihood ratio by convex risk minimization,” IEEE Transactions on Information Theory , vol. 56, no. 11, pp. 5847–5861, 2010
2010
Earlier work this paper cites.
Y. Polyanskiy, H. V. Poor, and S. Verdú, “Channel coding rate in the finite blocklength regime,” IEEE Transactions on Information Theory , vol. 56, no. 5, pp. 2307–2359, 2010
2010
Earlier work this paper cites.
Y. Polyanskiy and S. Verdú, “Arimoto channel coding converse and Rényi divergence,” in 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton) , Sep. 2010, pp. 1327–1333
2010
Earlier work this paper cites.
C. Manning, P. Raghavan, and H. Schütze, “Introduction to information retrieval,” Natural Language Engineering , vol. 16, no. 1, pp. 100–103, 2010
2010
Earlier work this paper cites.
K. Chaudhuri, C. Monteleoni, and A. D. Sarwate, “Differentially private empirical risk minimization,” Journal of Machine Learning Research , vol. 12, no. Mar, pp. 1069–1109, 2011
2011
Earlier work this paper cites.
G. Valiant and P. Valiant, “Estimating the unseen: an n/log (n)-sample estimator for entropy and support size, shown optimal via new clts,” in Proc. of ACM symposium on Theory of computing (STOC) , 2011
2011
Earlier work this paper cites.
D. Kifer and A. Machanavajjhala, “No free lunch in data privacy,” in Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data , ser. SIGMOD ’11. New York, NY, USA: ACM, 2011, pp. 193–204. [Online]. Available: http://doi.acm.org/10.1145/1989323.1989345
2011
Earlier work this paper cites.

Similar

M. Yamada, T. Suzuki, T. Kanamori, H. Hachiya, and M. Sugiyama, “Relative density-ratio estimation for robust distribution comparison,” in Proc. of Advances in neural information processing systems (NeurIPS) , 2011
2011
Cited alongside, same era.
F. du Pin Calmon and N. Fawaz, “Privacy against statistical inference,” in Proc. of IEEE Allerton Conference on Communication, Control, and Computing (Allerton) , 2012, pp. 1401–1408
2012
Cited alongside, same era.
M. Sugiyama, T. Suzuki, and T. Kanamori, Density ratio estimation in machine learning . Cambridge University Press, 2012
2012
Cited alongside, same era.
T. M. Cover and J. A. Thomas, Elements of information theory . John Wiley & Sons, 2012
2012
Cited alongside, same era.
R. Zemel, Y. Wu, K. Swersky, T. Pitassi, and C. Dwork, “Learning fair representations,” in International Conference on Machine Learning , 2013, pp. 325–333
2013
Cited alongside, same era.
A. D. Sarwate and K. Chaudhuri, “Signal processing and machine learning with differential privacy: Algorithms and challenges for continuous data,” IEEE signal processing magazine , vol. 30, no. 5, pp. 86–94, 2013
2013
Cited alongside, same era.
V. Vapnik, The nature of statistical learning theory . Springer science & business media, 2013
2013
Cited alongside, same era.
L. Sankar, S. R. Rajagopalan, and H. V. Poor, “Utility-privacy tradeoffs in databases: An information-theoretic approach,” IEEE Transactions on Information Forensics and Security , vol. 8, no. 6, pp. 838–852, 2013
2013
Cited alongside, same era.
G. Barthe and F. Olmedo, “Beyond differential privacy: Composition theorems and relational logic for f-divergences between probabilistic programs,” in Automata, Languages, and Programming . Berlin, Heidelberg: Springer Berlin Heidelberg, 2013, pp. 49–60
2013
Cited alongside, same era.
A. Makhdoumi, S. Salamatian, N. Fawaz, and M. Médard, “From the information bottleneck to the privacy funnel,” in Proc. of IEEE Information Theory Workshop (ITW) , 2014
2014
Cited alongside, same era.
I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio, “Generative adversarial nets,” in Advances in neural information processing systems , 2014, pp. 2672–2680
2014
Cited alongside, same era.
S. Shalev-Shwartz and S. Ben-David, Understanding machine learning: From theory to algorithms . Cambridge university press, 2014
2014
Cited alongside, same era.

Then

I. Žliobaitė and B. Custers, “Using sensitive personal data may be necessary for avoiding discrimination in data-driven decision models,” Artificial Intelligence and Law , vol. 24, no. 2, pp. 183–201, 2016
2016
Later among the works it cites.
C. Huang, P. Kairouz, X. Chen, L. Sankar, and R. Rajagopal, “Context-aware generative adversarial privacy,” Entropy , vol. 19, no. 12, p. 656, 2017
2017
Later among the works it cites.
W. Gao, S. Kannan, S. Oh, and P. Viswanath, “Estimating mutual information for discrete-continuous mixtures,” in Proc. of Advances in Neural Information Processing Systems (NeurIPS) , 2017, pp. 5986–5997
2017
Later among the works it cites.
S. Liu, A. Takeda, T. Suzuki, and K. Fukumizu, “Trimmed density ratio estimation,” in Proc. of Advances in Neural Information Processing Systems (NeurIPS) , 2017
2017
Later among the works it cites.
S. J. Oh, M. Fritz, and B. Schiele, “Adversarial image perturbation for privacy protection a game theory perspective,” in 2017 IEEE International Conference on Computer Vision (ICCV) . IEEE, 2017, pp. 1491–1500
2017
Later among the works it cites.
I. Mironov, “Rényi differential privacy,” in 2017 IEEE 30th Computer Security Foundations Symposium (CSF) . IEEE, 2017, pp. 263–275
2017
Later among the works it cites.
J. Liu, P. Cuff, and S. Verdú, “ e γ e_{{\gamma}} -resolvability,” IEEE Transactions on Information Theory , vol. 63, no. 5, pp. 2629–2658, May 2017
2017
Later among the works it cites.
C. Huang, P. Kairouz, X. Chen, L. Sankar, and R. Rajagopal, “Generative adversarial privacy,” arXiv preprint arXiv:1807.05306 , 2018
Original
2018
Later among the works it cites.
S. Asoodeh, M. Diaz, F. Alajaji, and T. Linder, “Estimation efficiency under privacy constraints,” IEEE Transactions on Information Theory , vol. 65, no. 3, pp. 1512–1534, 2018
2018
Later among the works it cites.
I. Issa, A. B. Wagner, and S. Kamath, “An operational approach to information leakage,” arXiv preprint arXiv:1807.07878 , 2018
Original
2018
Later among the works it cites.
H. Hsu, S. Asoodeh, S. Salamatian, and F. P. Calmon, “Generalizing bottleneck problems,” in Proc. of IEEE International Symposium on Information Theory (ISIT) , 2018
2018
Later among the works it cites.
M. Diaz, H. Wang, F. P. Calmon, and L. Sankar, “On the robustness of information-theoretic privacy measures and mechanisms,” arXiv preprint arXiv:1811.06057 , 2018
Original
2018
Later among the works it cites.
B. Balle and Y.-X. Wang, “Improving the Gaussian mechanism for differential privacy: Analytical calibration and optimal denoising,” in in Proc. of the International Conference on Machine Learning , 2018
2018
Later among the works it cites.
I. Belghazi, S. Rajeswar, A. Baratin, R. D. Hjelm, and A. Courville, “Mine: mutual information neural estimation,” arXiv preprint arXiv:1801.04062 , 2018
Original
2018
Later among the works it cites.
Z. Wu, Z. Wang, Z. Wang, and H. Jin, “Towards privacy-preserving visual recognition via adversarial training: A pilot study,” in Proceedings of the European Conference on Computer Vision (ECCV) , 2018, pp. 606–624
2018
Later among the works it cites.
J. Liao, O. Kosut, L. Sankar, and F. P. Calmon, “A tunable measure for information leakage,” arXiv preprint arXiv:1806.03332 , 2018
Original
2018
Later among the works it cites.
M. Alzantot, Y. Sharma, A. Elgohary, B.-J. Ho, M. Srivastava, and K.-W. Chang, “Generating natural language adversarial examples,” arXiv preprint arXiv:1804.07998 , 2018
Original
2018
Later among the works it cites.
M. Bertran, N. Martinez, A. Papadaki, Q. Qiu, M. Rodrigues, G. Reeves, and G. Sapiro, “Adversarially learned representations for information obfuscation and inference,” in Proc. of International Conference on Machine Learning (ICML) , 2019
2019
Closest in time.
X. Chen, T. Navidi, S. Ermon, and R. Rajagopal, “Distributed generation of privacy preserving data with user customization,” arXiv preprint arXiv:1904.09415 , 2019
Original
2019
Closest in time.
A. Rachez, “Predicting political bias with python,” https://medium.com/linalgo/predict-political-bias-using-python-b8575eedef13, 2017, accessed: 2019-03-21
2019
Closest in time.
B. Balle, G. Barthe, M. Gaboardi, and J. Geumlek, “Privacy amplification by mixing and diffusion mechanisms,” ArXiv , vol. abs/1905.12264, 2019
Original
2019
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…