Please note: This PhD defence will take place in DC 2314 and online.
Anargyros Georgios Mouzakis, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Gautam Kamath
The field of private statistics focuses on solving statistical estimation tasks under the constraint of Differential Privacy (DP). In addition to privacy, several important considerations arise concerning the efficiency of the proposed algorithms, most notably sample- and time-efficiency. Despite significant progress, many fundamental questions in private statistics remain unresolved. This thesis advances our understanding of the cost of privacy in several such tasks.
First, we study private Gaussian estimation. We develop the first polynomial-time algorithm for estimating the covariance matrix of a Gaussian distribution under approximate-DP. We also establish a tight sample-complexity lower bound for this task. Our lower bound requires a broad generalization of existing techniques for proving lower bounds under approximate-DP.
Subsequently, we examine separations between private and non-private density estimation. A characterization for pure-DP density estimation yields examples of distribution classes that are learnable without privacy but not learnable with finite sample complexity under pure-DP. In contrast, no such characterization exists for approximate-DP. We present and analyze a construction that establishes a separation between non-private and approximate-DP density estimation.
Third, we investigate the problem of privately sampling from a Gaussian distribution. While privately learning an unknown Gaussian is well understood, developing an optimal algorithm for privately sampling from a general Gaussian had remained open. We provide the first private algorithm that samples from a Gaussian in polynomial time with near-optimal sample complexity.
Finally, we turn our attention to lower bounds under differential privacy. Existing techniques for approximate-DP do not yield tight guarantees for many basic statistical estimation problems. We address this by developing a private analogue of the mutual information method, including a version of Fano’s method for approximate-DP. We illustrate the framework through applications to density estimation and supervised learning.
To attend this PhD defence in person, please go to DC 2314. You can also attend virtually on Zoom.