Differential Privacy, Property Testing, and Perturbations
dc.contributor.author | McMillan, Audra | |
dc.date.accessioned | 2018-06-07T17:45:01Z | |
dc.date.available | NO_RESTRICTION | |
dc.date.available | 2018-06-07T17:45:01Z | |
dc.date.issued | 2018 | |
dc.date.submitted | 2018 | |
dc.identifier.uri | https://hdl.handle.net/2027.42/143940 | |
dc.description.abstract | Controlling the dissemination of information about ourselves has become a minefield in the modern age. We release data about ourselves every day and don’t always fully understand what information is contained in this data. It is often the case that the combination of seemingly innocuous pieces of data can be combined to reveal more sensitive information about ourselves than we intended. Differential privacy has developed as a technique to prevent this type of privacy leakage. It borrows ideas from information theory to inject enough uncertainty into the data so that sensitive information is provably absent from the privatised data. Current research in differential privacy walks the fine line between removing sensitive information while allowing non-sensitive information to be released. At its heart, this thesis is about the study of information. Many of the results can be formulated as asking a subset of the questions: does the data you have contain enough information to learn what you would like to learn? and how can I affect the data to ensure you can’t discern sensitive information? We will often approach the former question from both directions: information theoretic lower bounds on recovery and algorithmic upper bounds. We begin with an information theoretic lower bound for graphon estimation. This explores the fundamental limits of how much information about the underlying population is contained in a finite sample of data. We then move on to exploring the connection between information theoretic results and privacy in the context of linear inverse problems. We find that there is a discrepancy between how the inverse problems community and the privacy community view good recovery of information. Next, we explore black-box testing for privacy. We argue that the amount of information required to verify the privacy guarantee of an algorithm, without access to the internals of the algorithm, is lower bounded by the amount of information required to break the privacy guarantee. Finally, we explore a setting where imposing privacy is a help rather than a hindrance: online linear optimisation. We argue that private algorithms have the right kind of stability guarantee to ensure low regret for online linear optimisation. | |
dc.language.iso | en_US | |
dc.subject | differential privacy | |
dc.title | Differential Privacy, Property Testing, and Perturbations | |
dc.type | Thesis | en_US |
dc.description.thesisdegreename | PhD | en_US |
dc.description.thesisdegreediscipline | Mathematics | |
dc.description.thesisdegreegrantor | University of Michigan, Horace H. Rackham School of Graduate Studies | |
dc.contributor.committeemember | Gilbert, Anna Catherine | |
dc.contributor.committeemember | Tewari, Ambuj | |
dc.contributor.committeemember | Esedoglu, Selim | |
dc.contributor.committeemember | Schotland, John Carl | |
dc.subject.hlbsecondlevel | Mathematics | |
dc.subject.hlbtoplevel | Science | |
dc.description.bitstreamurl | https://deepblue.lib.umich.edu/bitstream/2027.42/143940/1/amcm_1.pdf | |
dc.identifier.orcid | 0000-0003-4231-6110 | |
dc.identifier.name-orcid | McMillan, Audra; 0000-0003-4231-6110 | en_US |
dc.owningcollname | Dissertations and Theses (Ph.D. and Master's) |
Files in this item
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
Accessibility
If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.