Statistical Inference in the Differential Privacy Model

Abstract

In modern settings of data analysis, we may be running our algorithms on datasets that are sensitive in nature. However, classical machine learning and statistical algorithms were not designed with these risks in mind, and it has been demonstrated that they may reveal personal information. These concerns disincentivize individuals from providing their data, or even worse, encouraging intentionally providing fake data. To assuage these concerns, we import the constraint of differential privacy to the statistical inference, considered by many to be the gold standard of data privacy. This thesis aims to quantify the cost of ensuring differential privacy, i.e., understanding how much additional data is required to perform data analysis with the constraint of differential privacy. Despite the maturity of the literature on differential privacy, there is still inadequate understanding in some of the most fundamental settings. In particular, we make progress in the following problems: $\bullet$ What is the sample complexity of DP hypothesis testing? $\bullet$ Can we privately estimate distribution properties with a negligible cost? $\bullet$ What is the fundamental limit in private distribution estimation? $\bullet$ How can we design algorithms to privately estimate random graphs? $\bullet$ What is the trade-off between the sample complexity and the interactivity in private hypothesis selection?

arXiv commentThis thesis is a summary of the author's several works during his Ph.D. Besides, it has established the optimal sample complexity of differentially private closeness testing

References in corpus (33)

• Utility-Privacy Tradeoff in Databases: An Information-theoretic Approach
• Entropy and information in neural spike trains: Progress on the sampling problem
• Differential Privacy as a Mutual Information Constraint
• Optimal Algorithms for Testing Closeness of Discrete Distributions
• Does Dirichlet Prior Smoothing Solve the Shannon Entropy Estimation Problem?
• Maximum Likelihood Estimation of Functionals of Discrete Distributions
• Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication
• The Noisy Power Method: A Meta Algorithm with Applications
• Optimal Testing for Properties of Distributions
• Consistent estimation of the basic neighborhood of Markov random fields
• On Learning Discrete Graphical Models Using Greedy Methods
• Privacy and Statistical Risk: Formalisms and Minimax Bounds
• The Cost of Privacy: Rates of Convergence for Parameter Estimation with Differential Privacy
• Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models
• Improved Information Gain Estimates for Decision Tree Induction
• Revisiting Differentially Private Hypothesis Tests for Categorical Data
• Graphical-model based estimation and inference for differential privacy
• Test without Trust: Optimal Locally Private Distribution Testing
• Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters
• Linear Queries Estimation with Local Differential Privacy
• Tight Lower Bounds for Locally Differentially Private Selection
• Differentially Private Uniformly Most Powerful Tests for Binomial Data
• Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applications
• New Oracle-Efficient Algorithms for Private Synthetic Data Release
• A Primer on Private Statistics
• Density estimation in linear time
• Structure learning of antiferromagnetic Ising models
• Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data
• The Optimal Approximation Factor in Density Estimation
• Data-Dependent Differentially Private Parameter Learning for Directed Graphical Models
• Wide Network Learning with Differential Privacy
• Locally Private Learning without Interaction Requires Separation
• Robust Testing and Estimation under Manipulation Attacks