DescriptionData analysts use outlier analysis to discover non-conforming patterns in data to gen- erate actionable insights. It is an incredibly useful approach, but like all data-driven approaches, it raises privacy-related serious ethical and legal concerns when data is about peoples’ information. Is it possible to accurately analyze data for outliers while protecting the privacy of people whose data we analyze? In this dissertation, we explicate methods to answer this question for the most practically relevant case, where outliers are defined in a data-dependent way and current privacy methods such as differential privacy fail to achieve practically meaningful utility.
To define what it means to protect privacy in outlier analysis, we conceptualize sensitive privacy — it not only admits efficient algorithmic constructions but is also amenable to analysis. We introduce novel constructions to develop sensitively private mechanisms to accurately identify outliers, and to compile low-accuracy differentially private mechanisms into high-accuracy sensitively private mechanisms. Furthermore, to address the lack of a principled approach to private outlier analysis, we provide a framework to help a data analyst identify the right problem-specification and a practical solution for her application.
Finally, we develop mechanisms — which guarantee privacy and practically mean- ingful utility — to identify (β,r)-anomalies as well as covid-19 hotspots (an outlying event). An extensive empirical evaluation of these private mechanisms over a range of real-world datasets and use cases overwhelmingly supports the effectiveness of our approach.