Jessica Sorrell (Theory Seminar)

"Efficient, Noise-Tolerant, and Private Learning via Boosting"

Jessica Sorrell (UC San Diego)
Monday, November 25, 2019, 2:00pm
EBU3B, Room 4258


We introduce a simple framework for writing private boosting algorithms, and give natural conditions under which these algorithms are private, efficient, and noise-tolerant PAC learners. Our results triply-leverage privacy: for its own sake, for generalization, and for noise tolerance. As an application, we construct PAC learners for large-margin halfspaces, with sample complexity independent of dimension.

This is joint work with Mark Bun (Boston University) and Marco Carmosino (Simon Fraser University)