Structure and Sensitivity in Differential Privacy: Comparing K-Norm Mechanisms

References

• Acharya, J., Sun, Z., and Zhang, H. (2018), “Differentially Private Testing of Identity and Closeness of Discrete Distributions,” in Advances in Neural Information Processing Systems, pp. 6878–6891.
   Google Scholar
• Awan, J., Kenney, A., Reimherr, M., and Slavković, A. (2019), “Benefits and Pitfalls of the Exponential Mechanism With Applications to Hilbert Spaces and Functional PCA,” in Proceedings of the 36th International Conference on International Conference on Machine Learning, ICML’19, JMLR.org, pp. 374–384.
   Google Scholar
• Awan, J., and Slavković, A. (2018), “Differentially Private Uniformly Most Powerful Tests for Binomial Data,” in Advances in Neural Information Processing Systems (Vol. 31), eds. S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, Curran Associates, Inc., pp. 4208–4218.
   Google Scholar
• Awan, J., and Slavković, A. (2020), “Differentially Private Inference for Binomial Data,” Journal of Privacy and Confidentiality, 10, 725, DOI: https://doi.org/10.29012/jpc.725.
   Google Scholar
• Bishop, C. M. (2006), Pattern Recognition and Machine Learning, Information Science and Statistics, Secaucus, NJ: Springer-Verlag New York, Inc.
   Google Scholar
• Blyth, C. R. (1972), “On Simpson’s Paradox and the Sure-Thing Principle,” Journal of the American Statistical Association, 67, 364–366. DOI: https://doi.org/10.1080/01621459.1972.10482387.
   Web of Science ®Google Scholar
• Bun, M., Ullman, J., and Vadhan, S. (2018), “Fingerprinting Codes and the Price of Approximate Differential Privacy,” SIAM Journal on Computing, 47, 1888–1938. DOI: https://doi.org/10.1137/15M1033587.
   Web of Science ®Google Scholar
• Cai, B., Daskalakis, C., and Kamath, G. (2017), “Priv’IT: Private and Sample Efficient Identity Testing,” in Proceedings of the 34th International Conference on Machine Learning (Vol. 70), JMLR. org, pp. 635–644.
   Google Scholar
• Canonne, C. L., Kamath, G., McMillan, A., Smith, A., and Ullman, J. (2019), “The Structure of Optimal Private Tests for Simple Hypotheses,” in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, ACM, pp. 310–321. DOI: https://doi.org/10.1145/3313276.3316336.
   Google Scholar
• Casella, G., and Berger, R. L. (2002), Statistical Inference (Vol. 2), Pacific Grove, CA: Duxbury.
   Google Scholar
• Chaudhuri, K., and Monteleoni, C. (2009), “Privacy-Preserving Logistic Regression,” in Advances in Neural Information Processing Systems (Vol. 21), eds. D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, Curran Associates, Inc., pp. 289–296.
   Google Scholar
• Chaudhuri, K., Monteleoni, C., and Sarwate, D. (2011), “Differentially Private Empirical Risk Minimization,” Journal of Machine Learning Research, 12, 1069–1109.
   PubMed Web of Science ®Google Scholar
• Chaudhuri, K., Sarwate, A. D., and Sinha, K. (2013), “A Near-Optimal Algorithm for Differentially-Private Principal Components,” Journal of Machine Learning Research, 14, 2905–2943.
   Web of Science ®Google Scholar
• Cover, T. M., and Thomas, J. A. (2012), Elements of Information Theory, Hoboken, NJ: Wiley.
   Google Scholar
• Cuff, P., and Yu, L. (2016), “Differential Privacy as a Mutual Information Constraint,” in Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, ACM, pp. 43–54.
   Google Scholar
• Dalenius, T. (1977), “Towards a Methodology for Statistical Disclosure Control,” Statistik Tidskrift, 15, 429–444.
   Google Scholar
• Duchi, J. C., Jordan, M. I., and Wainwright, M. J. (2013), “Local Privacy and Statistical Minimax Rates,” in 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, IEEE, pp. 429–438.
   Google Scholar
• Duncan, G., and Lambert, D. (1986), “Disclosure-Limited Data Dissemination,” Journal of the American Statistical Association, 81, 10–18. DOI: https://doi.org/10.1080/01621459.1986.10478229.
   Web of Science ®Google Scholar
• Duncan, G., and Lambert, D. (1989), “The Risk of Disclosure for Microdata,” Journal of Business & Economic Statistics, 7, 207–217, DOI: https://doi.org/10.1080/07350015.1989.10509729.
   Web of Science ®Google Scholar
• Dwork, C., Feldman, V., Hardt, M., Pitassi, T., Reingold, O., and Roth, A. L. (2015), “Preserving Statistical Validity in Adaptive Data Analysis,” in Proceedings of the 47th Annual ACM Symposium on Theory of Computing, STOC ’15, ACM, New York, NY, USA, pp. 117–126, DOI: https://doi.org/10.1145/2746539.2746580.
   Google Scholar
• Dwork, C., and Lei, J. (2009), “Differential Privacy and Robust Statistics,” in Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC ’09, ACM, New York, NY, USA, pp. 371–380, DOI: https://doi.org/10.1145/1536414.1536466.
   Google Scholar
• Dwork, C., McSherry, F., Nissim, K., and Smith, A. (2006), Calibrating Noise to Sensitivity in Private Data Analysis, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 265–284, DOI: https://doi.org/10.1007/11681878_14.
   Google Scholar
• Dwork, C., Nikolov, A., and Talwar, K. (2014), “Using Convex Relaxations for Efficiently and Privately Releasing Marginals,” in Proceedings of the 13th Annual Symposium on Computational Geometry, ACM, p. 261. DOI: https://doi.org/10.1145/2582112.2582123.
   Google Scholar
• Dwork, C., Nikolov, A., and Talwar, K. (2015), “Efficient Algorithms for Privately Releasing Marginals via Convex Relaxations,” Discrete & Computational Geometry, 53, 650–673.
   Web of Science ®Google Scholar
• Dwork, C., and Roth, A. (2014), The Algorithmic Foundations of Differential Privacy (Vol. 9), Boston, MA: Now Publishers, Inc.
   Google Scholar
• Dwork, C., Smith, A., Steinke, T., and Ullman, J. (2017), “Exposed! A Survey of Attacks on Private Data,” Annual Review of Statistics and Its Application, 4, 61–84, DOI: https://doi.org/10.1146/annurev-statistics-060116-054123.
   Web of Science ®Google Scholar
• Fienberg, S. E., Makov, U. E., and Steele, R. J. (1998), “Disclosure Limitation Using Perturbation and Related Methods for Categorical Data,” Journal of Official Statistics, 14, 485–502.
   Google Scholar
• Fienberg, S. E., Rinaldo, A., and Yang, X. (2010), “Differential Privacy and the Risk-Utility Tradeoff for Multi-Dimensional Contingency Tables,” in Privacy in Statistical Databases, eds. J. Domingo-Ferrer and E. Magkos, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 187–199.
   Google Scholar
• Gaboardi, M., Lim, H., Rogers, R., and Vadhan, S. (2016), “Differentially Private Chi-Squared Hypothesis Testing: Goodness of Fit and Independence Testing,” in Proceedings of the 33rd International Conference on Machine Learning, Proceedings of Machine Learning Research (Vol. 48), eds. M. F. Balcan and K. Q. Weinberger, PMLR, New York, New York, USA, June 20–22, 2016, pp. 2111–2120.
   Google Scholar
• Geng, Q., and Viswanath, P. (2013), “The Optimal Mechanism in Differential Privacy: Multidimensional Setting,” arXiv no. 1312.0655.
   Google Scholar
• Geng, Q., and Viswanath, P. (2015), “The Optimal Noise-Adding Mechanism in Differential Privacy,” IEEE Transactions on Information Theory, 62, 925–951.
   Web of Science ®Google Scholar
• Ghosh, A., Roughgarden, T., and Sundararajan, M. (2012), “Universally Utility-Maximizing Privacy Mechanisms,” SIAM Journal on Computing, 41, 1673–1693. DOI: https://doi.org/10.1137/09076828X.
   Web of Science ®Google Scholar
• Hall, R. (2012), “New Statistical Applications for Differential Privacy,” PhD thesis, Carnegie Mellon.
   Google Scholar
• Hall, R., Rinaldo, A., and Wasserman, L. (2013), “Differential Privacy for Functions and Functional Data,” Journal of Machine Learning Research, 14, 703–727.
   Web of Science ®Google Scholar
• Hardt, M., and Talwar, K. (2010), “On the Geometry of Differential Privacy,” in Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC ’10, ACM, New York, NY, USA, pp. 705–714, DOI: https://doi.org/10.1145/1806689.1806786.
   Google Scholar
• Karwa, V., Krivitsky, P. N., and Slavković, A. B. (2016), “Sharing Social Network Data: Differentially Private Estimation of Exponential Family Random-Graph Models,” Journal of the Royal Statistical Society, Series C, 66, 481–500, DOI: https://doi.org/10.1111/rssc.12185.
   Web of Science ®Google Scholar
• Karwa, V., and Slavković, A. (2016), “Inference Using Noisy Degrees: Differentially Private β-Model and Synthetic Graphs,” The Annals of Statistics, 44, 87–112, DOI: https://doi.org/10.1214/15-AOS1358.
   Web of Science ®Google Scholar
• Karwa, V., and Vadhan, S. P. (2017), “Finite Sample Differentially Private Confidence Intervals,” CoRR, arXiv no. 1711.03908.
   Google Scholar
• Kattis, A., and Nikolov, A. (2016), “Lower Bounds for Differential Privacy From Gaussian Width,” arXiv no. 1612.02914.
   Google Scholar
• Kifer, D., and Lin, B.-R. (2012), “An Axiomatic View of Statistical Privacy and Utility,” Journal of Privacy and Confidentiality, 4, 610. DOI: https://doi.org/10.29012/jpc.v4i1.610.
   Google Scholar
• Kifer, D., Smith, A., and Thakurta, A. (2012), “Private Convex Empirical Risk Minimization and High-Dimensional Regression,” Journal of Machine Learning Research, 1, 1–41.
   Google Scholar
• Lei, J. (2011), “Differentially Private M-Estimators,” in Advances in Neural Information Processing Systems (Vol. 24), eds. J. Shawe-Taylor, R. S. Zemel, P. L. Bartlett, F. Pereira, and K. Q. Weinberger, Curran Associates, Inc., pp. 361–369.
   Google Scholar
• Lei, J., Charest, A.-S., Slavković, A., Smith, A., and Fienberg, S. (2018), “Differentially Private Model Selection With Penalized and Constrained Likelihood,” Journal of the Royal Statistical Society, Series A, 181, 609–633, DOI: https://doi.org/10.1111/rssa.12324.
   Web of Science ®Google Scholar
• Liu, R. Y. (1988), “On a Notion of Simplicial Depth,” Proceedings of the National Academy of Sciences of the United States of America, 85, 1732–1734. DOI: https://doi.org/10.1073/pnas.85.6.1732.
   PubMed Web of Science ®Google Scholar
• Liu, R. Y. (1990), “On a Notion of Data Depth Based on Random Simplices,” The Annals of Statistics, 18, 405–414.
   Web of Science ®Google Scholar
• Mirshani, A., Reimherr, M., and Slavković, A. (2019), “Formal Privacy for Functional Data with Gaussian Perturbations,” in International Conference on Machine Learning, pp. 4595–4604.
   Google Scholar
• Mosler, K. (2013), “Depth Statistics,” in Robustness and Complex Data Structures, eds. C. Becker, R. Fried, and S. Kuhnt, Berlin, Heidelberg: Springer, pp. 17–34.
   Google Scholar
• Nikolov, A. (2015), “An Improved Private Mechanism for Small Databases,” in International Colloquium on Automata, Languages, and Programming, Springer, pp. 1010–1021.
   Google Scholar
• Nissim, K., Steinke, T., Wood, A., Altman, M., Bembenek, A., Bun, M., Gaboardi, M., O’Brien, D. R., and Vadhan, S. (2017), “Differential Privacy: A Primer for a Non-Technical Audience,” in Privacy Law Scholars Conference.
   Google Scholar
• Quirk, J. P., and Saposnik, R. (1962), “Admissibility and Measurable Utility Functions,” The Review of Economic Studies, 29, 140–146. DOI: https://doi.org/10.2307/2295819.
   Web of Science ®Google Scholar
• Reimherr, M., and Awan, J. (2019), “KNG: The K-Norm Gradient Mechanism,” in Advances in Neural Information Processing Systems, pp. 10208–10219.
   Google Scholar
• Rogers, R., Roth, A., Smith, A., and Thakkar, O. (2016), “Max-Information, Differential Privacy, and Post-Selection Hypothesis Testing,” in 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, pp. 487–494. DOI: https://doi.org/10.1109/FOCS.2016.59.
   Google Scholar
• Serfling, R. (2006), “Depth Functions in Nonparametric Multivariate Inference,” DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 72, 1–16.
   Google Scholar
• Shannon, C. E. (1948), “A Mathematical Theory of Communication,” Bell System Technical Journal, 27, 379–423. DOI: https://doi.org/10.1002/j.1538-7305.1948.tb01338.x.
   Web of Science ®Google Scholar
• Smith, A. (2011), “Privacy-Preserving Statistical Estimation With Optimal Convergence Rates,” in Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, STOC ’11, ACM, New York, NY, USA, pp. 813–822, DOI: https://doi.org/10.1145/1993636.1993743.
   Google Scholar
• Song, S., Chaudhuri, K., and Sarwate, A. D. (2013), “Stochastic Gradient Descent With Differentially Private Updates,” in Proceedings of the Global Conference on Signal and Information Processing, IEEE, pp. 245–248.
   Google Scholar
• Steinke, T., and Ullman, J. (2017), “Between Pure and Approximate Differential Privacy,” Journal of Privacy and Confidentiality, 7, 648. DOI: https://doi.org/10.29012/jpc.v7i2.648.
   Google Scholar
• Tukey, J. W. (1975), “Mathematics and the Picturing of Data,” in Proceedings of the International Congress of Mathematicians (Vol. 2), Vancouver, pp. 523–531.
   Google Scholar
• Vu, D., and Slavković, A. (2009), “Differential Privacy for Clinical Trial Data: Preliminary Evaluations,” in Proceedings of the 2009 IEEE International Conference on Data Mining Workshops, ICDMW ’09, IEEE Computer Society, Washington, DC, USA, pp. 138–143, DOI: https://doi.org/10.1109/ICDMW.2009.52.
   Google Scholar
• Wang, W., Ying, L., and Zhang, J. (2016), “On the Relation Between Identifiability, Differential Privacy, and Mutual-Information Privacy,” IEEE Transactions on Information Theory, 62, 5018–5029. DOI: https://doi.org/10.1109/TIT.2016.2584610.
   Web of Science ®Google Scholar
• Wang, X. (2005), “Volumes of Generalized Unit Balls,” Mathematics Magazine, 78, 390–395. DOI: https://doi.org/10.2307/30044198.
   Google Scholar
• Wang, Y., Huang, Z., Mitra, S., and Dullerud, G. E. (2014), “Entropy-Minimizing Mechanism for Differential Privacy of Discrete-Time Linear Feedback Systems,” in 53rd IEEE Conference on Decision and Control, IEEE, pp. 2130–2135.
   Google Scholar
• Wang, Y., Lee, J., and Kifer, D. (2015), “Revisiting Differentially Private Hypothesis Tests for Categorical Data,” arXiv no. 1511.03376.
   Google Scholar
• Wang, Y.-X. (2017), “Per-Instance Differential Privacy and the Adaptivity of Posterior Sampling in Linear and Ridge Regression,” Stat, 1050, 18.
   Google Scholar
• Wasserman, L., and Zhou, S. (2010), “A Statistical Framework for Differential Privacy,” Journal of the American Statistical Association, 105, 375–389. DOI: https://doi.org/10.1198/jasa.2009.tm08651.
   Web of Science ®Google Scholar
• Xiao, Y., and Xiong, L. (2015), “Protecting Locations With Differential Privacy Under Temporal Correlations,” in Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, CCS ’15, ACM, New York, NY, USA, pp. 1298–1309, DOI: https://doi.org/10.1145/2810103.2813640.
   Google Scholar
• Xiao, Y., Xiong, L., Zhang, S., and Cao, Y. (2017), “Loclok: Location Cloaking With Differential Privacy via Hidden Markov Model,” Proceedings of the VLDB Endowment, 10, 1901–1904. DOI: https://doi.org/10.14778/3137765.3137804.
   Web of Science ®Google Scholar
• Yu, F., Rybar, M., Uhler, C., and Fienberg, S. E. (2014), “Differentially-Private Logistic Regression for Detecting Multiple-SNP Association in GWAS Databases,” in Privacy in Statistical Databases: UNESCO Chair in Data Privacy, International Conference, PSD 2014, Ibiza, Spain, September 17–19, 2014, Proceedings, Springer International Publishing, Cham, pp. 170–184, DOI: https://doi.org/10.1007/978-3-319-11257-2_14.
   Google Scholar
• Zhang, J., Zhang, Z., Xiao, X., Yang, Y., and Winslett, M. (2012), “Functional Mechanism: Regression Analysis Under Differential Privacy,” Proceedings of the VLDB Endowment, 5, 1364–1375, DOI: https://doi.org/10.14778/2350229.2350253.
   Google Scholar
• Zuo, Y., and Serfling, R. (2000a), “General Notions of Statistical Depth Function,” The Annals of Statistics, 28, 461–482. DOI: https://doi.org/10.1214/aos/1016218226.
   Web of Science ®Google Scholar
• Zuo, Y., and Serfling, R. (2000b), “Nonparametric Notions of Multivariate ‘Scatter Measure’ and ‘More Scattered’ Based on Statistical Depth Functions,” Journal of Multivariate Analysis, 75, 62–78.
   Web of Science ®Google Scholar
• Zuo, Y., and Serfling, R. (2000c), “Structural Properties and Convergence Results for Contours of Sample Statistical Depth Functions,” The Annals of Statistics, 28, 483–499.
   Web of Science ®Google Scholar