Differential Privacy via Distributionally Robust Optimization

References

• Abadi M, Chu A, Goodfellow I, McMahan HB, Mironov I, Talwar K, Zhang L (2016) Deep learning with differential privacy. Weippl ER, Katzenbeisser S, Kruegel C, Myers AC, Halevi S, eds. Proc. 2016 ACM SIGSAC Conf. Comput. Comm. Security (ACM, New York), 308–318.Google Scholar
• Alvim MS, Andres ME, Chatzikokolakis K, Degano P, Palamidessi C (2011) Differential privacy: On the trade-off between utility and information leakage. Barthe G, Datta A, Etalle S, eds. Formal Aspects Security Trust – 8th Internat. Workshop, FAST 2011, Lecture Notes in Computer Science, vol. 7140 (Springer, Berlin, Heidelberg), 39–54.Google Scholar
• Anderson EJ, Nash P (1987) Linear Programming in Infinite-Dimensional Spaces: Theory and Applications (John Wiley & Sons, New York).Google Scholar
• Apple Differential Privacy Team (2017) Learning with privacy at scale. White paper, Apple Inc., Cupertino, CA.Google Scholar
• Asi H, Duchi JC (2020a) Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms. Hadsell R, Balcan MF, Lin HT, eds. Proc. 34th Internat. Conf. Neural Inform. Processing Systems, Advances in Neural Information Processing Systems, vol. 33 (Curran Associates Inc., Red Hook, NY), 14106–14117.Google Scholar
• Asi H, Duchi JC (2020b) Near instance-optimality in differential privacy. Preprint, submitted May 16, https://arxiv.org/abs/2005.10630.Google Scholar
• Balle B, Wang YX (2018) Improving the Gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. Proc. 35th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 80 (PMLR, New York), 394–403.Google Scholar
• Bavadekar S, Boulanger A, Davis J, Desfontaines D, Gabrilovich E, Gadepalli K, Ghazi B, et al. (2021) Google COVID-19 vaccination search insights: Anonymization process description. Preprint, submitted July 2, https://arxiv.org/abs/2107.01179.Google Scholar
• Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust Optimization (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Bertsimas D, den Hertog D (2022) Robust and Adaptive Optimization (Dynamic Ideas, Waltham, MA).Google Scholar
• Bertsimas D, Sim M (2004) The price of robustness. Oper. Res. 52(1):35–53.Link, Google Scholar
• Bertsimas D, Dunning I, Lubin M (2016) Reformulation versus cutting-planes for robust optimization: A computational study. Comput. Management Sci. 13(1):195–217.Crossref, Google Scholar
• Bienstock D, Özbay N (2008) Computing robust basestock levels. Discrete Optim. 5(2):389–414.Crossref, Google Scholar
• Cai N, Kou S (2019) Econometrics with privacy preservation. Oper. Res. 67(4):905–926.Abstract, Google Scholar
• Canonne CL, Kamath G, Steinke T (2020) The discrete Gaussian for differential privacy. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds. Annual Conf. Neural Inform. Processing Systems 2020, Advances in Neural Information Processing Systems, vol. 33 (Curran Associates, Inc., Red Hook, NY), 15676–15688.Google Scholar
• Chang CC, Lin CJ (2011) LIBSVM: A library for support vector machines. ACM Trans. Intelligent Systems Tech. 2(3):1–27.Crossref, Google Scholar
• Chaudhuri K, Monteleoni C (2009) Privacy-preserving logistic regression. Koller D, Schuurmans D, Bengio Y, Bottou L, eds. Proc. Twenty-Second Annual Conf. Neural Inform. Processing Systems, Advances in Neural Information Processing Systems, vol. 21 (Curran Associates, Inc., Red Hook, NY), 289–296.Google Scholar
• Chaudhuri K, Monteleoni C, Sarwate AD (2011) Differentially private empirical risk minimization. J. Machine Learn. Res. 12(3):1069–1109.Google Scholar
• Chen X, Miao S, Wang Y (2023) Differential privacy in personalized pricing with nonparametric demand models. Oper. Res. 71(2):581–602.Link, Google Scholar
• Chen X, Simchi-Levi D, Wang Y (2022) Privacy-preserving dynamic personalized pricing with demand learning. Management Sci. 68(7):4878–4898.Link, Google Scholar
• Delage E, Ye Y (2010) Distributionally robust optimization under moment uncertainty with application to data-driven problems. Oper. Res. 58(3):596–612.Link, Google Scholar
• Desfontaines D (2020) Lowering the cost of anonymization. PhD thesis, ETH Zurich, Zurich.Google Scholar
• Desfontaines D, Pejó B (2020) SoK: Differential privacies. Chatzikokolakis K, Johnson A, eds. Proc. Privacy Enhancing Tech., 288–313.Google Scholar
• Dinur I, Nissim K (2003) Revealing information while preserving privacy. Neven F, Beeri C, Milo T, eds. Proc. 22nd ACM SIGMOD-SIGACT-SIGART Sympos. Principles Database Systems (ACM, New York), 202–210.Google Scholar
• Dua D, Graff C (2017) Welcome to the UC Irvine machine learning repository. Accessed December 17, 2024, http://archive.ics.uci.edu/ml.Google Scholar
• Dwork C (2011) The promise of differential privacy: A tutorial on algorithmic techniques. Ostrovsky R, ed. Proc. 52nd Annual IEEE Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 1–2.Google Scholar
• Dwork C, Roth A (2014) The algorithmic foundations of differential privacy. Foundations Trends Theoret. Comput. Sci. 9(3–4):211–407.Crossref, Google Scholar
• Dwork C, Rothblum GN (2016) Concentrated differential privacy. Preprint, submitted March 6, https://arxiv.org/abs/1603.01887.Google Scholar
• Dwork C, McSherry F, Nissim K, Smith A (2006a) Calibrating noise to sensitivity in private data analysis. Halevi S, Rabin T, eds. Proc. 3rd Conf. Theory Cryptography, Lecture Notes in Computer Science, vol. 3876 (Springer, Berlin, Heidelberg), 265–284.Google Scholar
• Dwork C, Kenthapadi K, McSherry F, Mironov I, Naor M (2006b) Our data, ourselves: Privacy via distributed noise generation. Vaudenay S, ed. Proc. 25th Annual Internat. Conf. Theory Appl. Cryptographic Techniques, Lecture Notes in Computer Science, vol. 4004 (Springer, Berlin, Heidelberg), 486–503.Google Scholar
• Foote AD, Machanavajjhala A, McKinney K (2019) Releasing earnings distributions using differential privacy: Disclosure avoidance system for post-secondary employment outcomes (PSEO). J. Privacy Confidentiality 9(2):1–19.Crossref, Google Scholar
• Friedman A, Schuster A (2010) Data mining with differential privacy. Rao B, Krishnapuram B, Tomkins A, Yang Q, eds. Proc. 16th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (ACM, New York), 493–502.Google Scholar
• Friedman JH, Hastie T, Tibshirani R (2010) Regularization paths for generalized linear models via coordinate descent. J. Statist. Software 33(1):1–22.Crossref, Google Scholar
• Geng Q, Viswanath P (2014) The optimal mechanism in differential privacy. Proc. IEEE Internat. Sympos. Inform. Theory (IEEE Computer Society, Washington, DC), 2371–2375.Google Scholar
• Geng Q, Viswanath P (2015) Optimal noise adding mechanisms for approximate differential privacy. IEEE Trans. Inform. Theory 62(2):952–969.Crossref, Google Scholar
• Geng Q, Ding W, Guo R, Kumar S (2019) Optimal noise-adding mechanism in additive differential privacy. Chaudhuri K, Sugiyama M, eds. Proc. 22nd Internat. Conf. Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol. 89 (PMLR, New York), 11–20.Google Scholar
• Geng Q, Ding W, Guo R, Kumar S (2020) Tight analysis of privacy and utility tradeoff in approximate differential privacy. Chiappa S, Calandra R, eds. Proc. 23rd Internat. Conf. Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol. 108 (PMLR, New York), 89–99.Google Scholar
• Han S, Topcu U, Pappas GJ (2016) Differentially private distributed constrained optimization. IEEE Trans. Automatic Control 62(1):50–64.Crossref, Google Scholar
• Han S, Tao M, Topcu U, Owhadi H, Murray RM (2015) Convex optimal uncertainty quantification. SIAM J. Optim. 25(3):1368–1387.Crossref, Google Scholar
• Hanasusanto GA, Roitch V, Kuhn D, Wiesemann W (2015) A distributionally robust perspective on uncertainty quantification and chance constrained programming. Math. Programming 151(1):35–62.Crossref, Google Scholar
• Hastie T, Tibshirani R, Friedman J (2009) The Elements of Statistical Learning: Data Mining, Inference, and Prediction (Springer, Cham, Switzerland).Crossref, Google Scholar
• Heffetz O, Ligett K (2014) Privacy and data-based research. J. Econom. Perspect. 28(2):75–98.Crossref, Google Scholar
• Hsu J, Huang Z, Roth A, Wu ZS (2016) Jointly private convex programming. Krauthgamer R, ed. Proc. Twenty-seventh Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 580–599.Google Scholar
• Hsu J, Roth A, Roughgarden T, Ullman J (2014) Privately solving linear programs. Esparza J, Fraigniaud P, Husfeldt T, Koutsoupias E, eds. Proc. 41st Internat. Colloquium Automata Languages Programming, Lecture Notes in Computer Science, vol. 8572 (Springer, Berlin, Heidelberg), 612–624.Google Scholar
• Johnson A, Shmatikov V (2013) Privacy-preserving data exploration in genome-wide association studies. Dhillon IS, Koren Y, Ghani R, Senator TE, Bradley P, Parekh R, He J, Grossman RL, Uthurusamy R, eds. Proc. 19th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (ACM, New York), 1079–1087.Google Scholar
• Kuhn D, Mohajerin Esfahani P, Nguyen VA, Shafieezadeh-Abadeh S (2019) Wasserstein distributionally robust optimization: Theory and applications in machine learning. INFORMS TutORials Oper. Res., 130–166.Google Scholar
• Lei Y, Miao S, Momot R (2024) Privacy-preserving personalized revenue management. Management Sci. 70(7):4875–4892.Link, Google Scholar
• Long DZ, Sim M, Zhou M (2023) Robust satisficing. Oper. Res. 71(1):61–82.Link, Google Scholar
• Lopuhaä-Zwakenberg M, Alishahi M, Kivits J, Klarenbeek J, van der Velde GJ, Zannone N (2021) Comparing classifiers’ performance under differential privacy. Vimercati SDCD, Samarati P, eds. Proc. Internat. Conf. Security Cryptography (SciTePress, Setúbal, Portugal), 50–61.Google Scholar
• Machanavajjhala A, Kifer D, Gehrke J, Venkitasubramaniam M (2007) ℓ-Diversity: Privacy beyond k-anonymity. ACM Trans. Knowledge Discovery Data 1(1):1556–4681.Google Scholar
• Mangasarian OL (2011) Privacy-preserving linear programming. Optim. Lett. 5(1):165–172.Crossref, Google Scholar
• Mangold P, Bellet A, Salmon J, Tommasi M (2022) Differentially private coordinate descent for composite empirical risk minimization. Chaudhuri K, Jegelka S, Song L, Szepesvári C, Niu G, Sabato S, eds. Proc. 39th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 162 (PMLR, New York), 14948–14978.Google Scholar
• McSherry F, Talwar K (2007) Mechanism design via differential privacy. Proc. 48th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 94–103.Google Scholar
• Meiser S (2018) Approximate and probabilistic differential privacy definitions. Preprint, submitted March 21, https://eprint.iacr.org/2018/277.Google Scholar
• Messing S, DeGregorio C, Hillenbrand B, King G, Mahanti S, Mukerjee Z, Nayak C, Persily N, State B, Wilkins A (2020) Facebook privacy-protected full URLs data set. https://doi.org/10.7910/DVN/TDOAPG.Google Scholar
• Mutapcic A, Boyd S (2009) Cutting-set methods for robust convex optimization with pessimizing oracles. Optim. Methods Software 24(3):381–406.Crossref, Google Scholar
• Neelakantan A, Vilnis L, Le QV, Sutskever I, Kaiser L, Kurach K, Martens J (2015) Adding gradient noise improves learning for very deep networks. Preprint, submitted November 21, https://arxiv.org/abs/1511.06807.Google Scholar
• Nergiz ME, Atzori M, Clifton C (2007) Hiding the presence of individuals from shared databases. Chan CY, Ooi BC, Zhou A, eds. Proc. 2007 ACM SIGMOD Internat. Conf. Management Data (ACM, New York), 665–676.Google Scholar
• Nissim K, Raskhodnikova S, Smith A (2007) Smooth sensitivity and sampling in private data analysis. Johnson DS, Feige U, eds. Proc. 39th Annual ACM Sympos. Theory Comput. (ACM, New York), 75–84.Google Scholar
• Owhadi H, Scovel C, Sullivan TJ, McKerns M, Ortiz M (2013) Optimal uncertainty quantification. SIAM Rev. 55(2):271–345.Crossref, Google Scholar
• Parikh N, Boyd S (2014) Proximal algorithms. Foundations Trends Optim. 1(3):127–239.Crossref, Google Scholar
• Pätzold J, Schöbel A (2020) Approximate cutting plane approaches for exact solutions to robust optimization problems. Eur. J. Oper. Res. 284(1):20–30.Crossref, Google Scholar
• Pereira M, Kim A, Allen J, White K, Ferres JL, Dodhia R (2021) U.S. broadband coverage data set: A differentially private data release. Preprint, submitted March 24, https://arxiv.org/abs/2103.14035.Google Scholar
• Richtárik P, Takáč M (2014) Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function. Math. Programming 144(1):1–38.Crossref, Google Scholar
• Rogers R, Cardoso AR, Mancuhan K, Kaura A, Gahlawat N, Jain N, Ko P, Ahammad P (2020) A members first approach to enabling LinkedIn’s labor market insights at scale. Preprint, submitted March 24, https://arxiv.org/abs/2103.14035.Google Scholar
• Salzberg SL (1997) On comparing classifiers: Pitfalls to avoid and a recommended approach. Data Mining Knowledge Discovery 1(3):317–328.Crossref, Google Scholar
• Sommer DM (2021) Fighting uphill battles: Improvements in personal data privacy. PhD thesis, ETH Zurich, Zurich.Google Scholar
• Soria-Comas J, Domingo-Ferrer J (2013) Optimal data-independent noise for differential privacy. Inform. Sci. 250:200–214.Crossref, Google Scholar
• Sweeney L (1997) Weaving technology and policy together to maintain confidentiality. J. Law Medicine Ethics 25(2–3):98–110.Crossref, Google Scholar
• Sweeney L (2001) Computational disclosure control: A primer on data privacy protection. PhD thesis, Massachusetts Institute of Technology, Cambridge.Google Scholar
• Sweeney L (2002) k-Anonymity: A model for protecting privacy. Internat. J. Uncertainty Fuzziness Knowledge-Based Systems 10(5):557–570.Crossref, Google Scholar
• Vadhan S (2017) The complexity of differential privacy. Lindell Y, ed. Tutorials on the Foundations of Cryptography, Information Security and Cryptography (Springer, Cham, Switzerland), 347–450.Crossref, Google Scholar
• Vaidya J, Shafiq B, Basu A, Hong Y (2013) Differentially private naïve Bayes classification. Proc. 12th IEEE/WIC/ACM Internat. Joint Conf. Web Intelligence Intelligent Agent Tech. (IEEE Computer Society, Washington, DC), 571–576.Google Scholar
• Wiesemann W, Kuhn D, Sim M (2014) Distributionally robust convex optimization. Oper. Res. 62(6):1358–1376.Link, Google Scholar
• Zhao J, Wang T, Bai T, Lam KY, Xu Z, Shi S, Ren X, Yang X, Liu Y, Yu H (2019) Reviewing and improving the Gaussian mechanism for differential privacy. Preprint, submitted November 27, http://arxiv.org/abs/1911.12060.Google Scholar