Back to search

Boston University

Practical learning in a private and noisy world

Abstract

dc:description.abstract

This thesis studies two fundamental settings in theoretical machine learning where worst-case formulations impose sharp computational hardness barriers: learning under privacy constraints and learning under noise. In both settings, we show that carefully chosen relaxations of the standard models, reflecting structure present in practical deployments, enable computationally efficient algorithms while preserving meaningful theoretical guarantees. The first part concerns the relationship between online learning and differentially private PAC learning. A celebrated equivalence shows that a hypothesis class is privately PAC learnable if and only if it is online learnable, raising the question of whether efficient online learners can be generically converted into efficient private learners. We answer this in the negative: under standard cryptographic assumptions, we exhibit a concept class that is efficiently online learnable but for which no polynomial-time differentially private PAC learner exists. Since efficient private learning cannot be obtained generically from online learning, we study a relaxation of the standard model allowing access to public unlabeled data and design efficient private learners (inspired by classical online learning algorithms) for regression and classification as long as there exists an efficient non-private learner for the same task. The second part examines learning under noise through relaxations of agnostic learning. Specifically, we study the relaxed models of testable learning and PAC verification. We show that a variant of distribution testing (which we introduce in our work) serves as a unifying tool to design computationally efficient algorithms for these relaxed models. Our variant of istribution testing relies on fooling distance (also known as integral probability metric), where the distance between two distributions is measured with respect to a structured family F of Boolean distinguishers. We study distribution testing with respect to this distance and show that the Rademacher complexity captures the sample complexity of this problem (up to a quadratic gap). As a consequence, we obtain new computationally efficient algorithms for testable proper learning of halfspaces and decision trees, sample-efficient verification protocols for unions of rectangles, and uniformity testers for structured high-dimensional distributions.

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
2026

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Desai, Rathin
Advisor dc:contributor.advisor
  • Bun, Mark
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/53594

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

Desai, Rathin. Practical learning in a private and noisy world. doctoral thesis, Boston University, 2026. https://hdl.handle.net/2144/53594