Private data analysis beyond the worst case
Abstract/Contents
- Abstract
- Differential Privacy (DP) provides strong guarantees on the risk of compromising a user's data in statistical and machine learning applications. However, privacy-preserving algorithms often suffer considerable loss in accuracy compared to non-private algorithms, both in theory and practice. In this thesis, we investigate and study several approaches towards improving the cost of private algorithms and closing the gap between private and non-private performance. While there exist many privacy-preserving algorithms with optimality certificates, most of these hold only in the worst case setting; that is, the performance of the algorithm is measured by it's performance on the worst-case input. Therefore a (worst-case) optimal algorithm may not be achieving the best possible performance for certain functions with more natural inputs. Building on this observation, we propose three general directions for designing algorithms that can improve the privacy cost and outperform existing (worst-case) optimal algorithms. In our first approach, we move beyond worst-case optimality and define a new notion of instance-optimality in differential privacy. Instance-optimal algorithms adapt to the difficulty of the underlying input and therefore result in improved performance for natural inputs. We develop an algorithm, namely the inverse sensitivity mechanism, which is nearly instance optimal and present several instantiations for statistical and machine learning applications such as median estimation, regression problems, and principal component analysis. As our instance-optimal algorithm may be computationally intractable in some settings, our second approach moves beyond worst-case optimality by identifying natural properties of the inputs that hold in practice. This will allow to (i) design efficient and optimal algorithms for these families, and (ii) improve the rates compared to worst-case inputs as these inputs do not satisfy the properties we consider. Our final approach builds on the observation that differential privacy may be too stringent for some use cases. To address this, we propose element level differential privacy, which extends differential privacy to provide protection against leaking information about any particular ``element'' a user has, allowing better utility and more robust results than classical DP. By carefully choosing these ``elements, '' it is possible to provide privacy protections at a desired granularity and result in better utility.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2022; ©2022 |
| Publication date | 2022; 2022 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Asi, Hilal |
|---|---|
| Degree supervisor | Duchi, John |
| Thesis advisor | Duchi, John |
| Thesis advisor | Feldman, Vitaly |
| Thesis advisor | Pilanci, Mert |
| Thesis advisor | Weissman, Tsachy |
| Degree committee member | Feldman, Vitaly |
| Degree committee member | Pilanci, Mert |
| Degree committee member | Weissman, Tsachy |
| Associated with | Stanford University, Department of Electrical Engineering |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Hilal Asi. |
|---|---|
| Note | Submitted to the Department of Electrical Engineering. |
| Thesis | Thesis Ph.D. Stanford University 2022. |
| Location | https://purl.stanford.edu/wm997hg1681 |
Access conditions
- Copyright
- © 2022 by Hilal Asi
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...