Back to search

Boston University

New algorithms for private estimation of fundamental statistics

Abstract

dc:description.abstract

Insights derived from individuals' data have become indispensable across numerous domains, raising concerns about the leakage of private information contained in said data. Differential privacy (Dwork, McSherry, Nissim, Smith `06) has emerged as a widely studied and deployed framework for analyses that publish summary statistics, as it offers rigorous privacy guarantees while aiming to maintain data utility. In this thesis, we design differentially private algorithms, accompanied with theoretical utility guarantees, for three foundational data tasks: (1) counting connected components in a network, (2) counting distinct items in turnstile streams, and (3) testing conditional independence. These tasks are fundamental building blocks for more complex data analyses, but previously, have been studied either in restricted settings, or not all, through the lens of privacy. Despite the widespread adoption of differential privacy, its application to complex data structures such as networks and streams and sophisticated statistical techniques such as hypothesis testing remains under-explored. Our work contributes to these settings, where new challenges to practical differential privacy arise. For network and stream datasets, these challenges are due to the strong interdependence amongst datapoints themselves and between the datapoints and the output. In hypothesis testing, the introduction of noise to achieve privacy significantly affects the validity of statistical tests, especially with small sample sizes. We show that, in the worst-case, strong lower bounds apply to the utility of differentially private algorithms for all of our tasks. We overcome such lower bounds by adopting the approach of instance-based guarantees, where the error of our algorithm is bounded based on a specific parameter of the input dataset. The privacy noise is adapted to the hardness of the dataset at hand, where easier instances correspond to lower values of said parameter. We provide novel technical contributions in all three stages of our algorithmic design: the careful identification of parameters that are expected to be low for natural inputs and enable bypassing the worst-case lower bounds; the design of families of low-sensitivity, efficiently computable candidate functions, based on the specified parameter, that approximate the desired statistics; and, developing methods to select the optimal function from these candidates. This strategy enhances the practicality of differential privacy across the three settings we examine.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Computer Science
Grantor
Boston University
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Kalemaj, Iden
Advisor dc:contributor.advisor
  • Raskhodnikova, Sofya
ORCID dc:identifier.orcid

Subjects

dc:subject × 5

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/2144/53110

Chain of custody

source
Harvested from
Boston University
Base URL
open.bu.edu/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Kalemaj, Iden. New algorithms for private estimation of fundamental statistics. doctoral thesis, Boston University, 2024. https://hdl.handle.net/2144/53110