Back to search

Boston University

New definitions, measurements, and algorithms for private data analysis

Abstract

dc:description.abstract

This thesis is about the theory of computing with data while protecting privacy. In this thesis, we study novel privacy settings and explore fundamental trade-offs between accuracy and information disclosure therein. The problems and solutions we consider are unified by a rigorous treatment of adversarial knowledge and capabilities, algorithmic accuracy, and formal privacy guarantees. We begin by considering the problem of defining data deletion in the context of the modern data ecosystem. Inspired by the numerous pieces of legislation giving data subjects the right to request the deletion of their personal information from organizations that store and process it, we present a framework for deletion that unifies prior approaches and encompasses functionalities that previous definitions fail to capture. Next, we initiate the study of a new problem we call private sampling, which abstracts the goal of privately generating small amounts of realistic-looking data. At a high level, given a dataset of observations sampled independently from an unknown distribution, a sampling algorithm must privately output one sample from a distribution that is sufficiently close to the original one. We provide tight upper and lower bounds for the dataset size needed for this task for three natural families of distributions. We demonstrate that, in some parameter regimes, privately sampling from a distribution requires asymptotically fewer observations than learning a description of the same distribution nonprivately; in other regimes, however, private sampling proves to be as difficult as private learning. Notably, for some classes of distributions, the overhead in the number of observations needed for private learning compared to non-private learning is completely captured by the number of observations needed for private sampling. Finally, we propose reconstruction advantage measures to audit label privatization mechanisms. A reconstruction advantage measure quantifies the increase in an attacker’s ability to infer the true label of an unlabeled example when provided with a private version of the labels in a dataset (e.g., aggregates of labels from different users or noisy labels output by randomized response), compared to an attacker that only observes the feature vectors, but who may have prior knowledge of the correlation between features and labels. We consider two such auditing measures: one additive, and one multiplicative. These incorporate previous approaches taken in the literature on empirical auditing and differential privacy. The measures allow us to place a variety of proposed privatization schemes—some differentially private, some not—on the same footing. We analyze these measures theoretically under a distributional model which encapsulates reasonable adversarial settings, and we also quantify their behavior empirically on real and simulated prediction tasks. Across a range of experimental settings, we find that differentially private schemes dominate or match the privacy-utility tradeoff of more heuristic approaches.

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
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Swanberg, Marika
Advisor dc:contributor.advisor
  • Smith, Adam D.
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/53311

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

Swanberg, Marika. New definitions, measurements, and algorithms for private data analysis. doctoral thesis, Boston University, 2025. https://hdl.handle.net/2144/53311