Back to search

Boston University

Memorization and privacy in learning: fundamental limits and new algorithms

Abstract

dc:description.abstract

Data analysts often work with records pertaining to specific individuals; the results of their analysis, by design, depends on the details of the individuals' data. This dependence may occur in surprising ways and have negative consequences. In this dissertation, we investigate the dependence of learning algorithms upon individual inputs through the lenses of memorization and privacy. We reveal fundamental limits on when memorization is inescapable, experimentally demonstrate the vulnerability of conventional learning methods, and design new algorithms with rigorous privacy guarantees. We present learning tasks, stylized variants of image classification and sequence prediction, and prove that any high-accuracy learner for these tasks must encode a huge amount of information about the training data. We show that much of this stored information is irrelevant to the learning task, taking the form of noise or useless features. For some tasks, we prove a further result: high-accuracy learners need to memorize almost the entirety of a large number of input examples. We identify similar phenomena in a streaming setting, where examples arrive one at a time. For natural sparse hypothesis classes, such as sparse linear classification over a polynomial kernel, we prove that nontrivial algorithms with few samples need large memories. This lower bound smoothly decreases as the sample size increases: with a longer stream, less memorization is required. Moving beyond theorems, we investigate whether this stored information can be extracted by an attacker. We show that standard classifiers may be vulnerable to data reconstruction attacks. In our experiments, the vulnerability is extreme, with an attacker able to recover high-fidelity copies of a large fraction of the training data. Finally, we approach data privacy from the other direction: how can we prevent individual data points from having a large effect on the output of an analysis? We design new differentially private algorithms for statistical estimation. Given samples from a subgaussian distribution, our algorithms accurately estimate the distribution's mean and covariance. These algorithms have low overhead relative to nonprivate estimators, requiring similar sample sizes and computational resources.

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
  • Brown, Gavin R.
Advisor dc:contributor.advisor
  • Smith, Adam D.
ORCID dc:identifier.orcid

Subjects

dc:subject × 1

Rights

dc:rights
Statement dc:rights
  • Attribution 4.0 International
Language dc:language.iso
en_US

Identifiers

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

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

Brown, Gavin R.. Memorization and privacy in learning: fundamental limits and new algorithms. doctoral thesis, Boston University, 2024. https://hdl.handle.net/2144/49747