Privacy, Stability, and Online Learning

Explore the intersection of privacy, stability, and online learning in this 37-minute lecture by Mark Bun from Boston University. Delve into motivating questions surrounding non-private classification, focusing on learning one-dimensional thresholds. Examine the sample complexity of learning and private learning, characterizing private sample complexity and learnability. Investigate online learning, the Littlestone dimension, and compare mistake-bounded learning with differential privacy. Part of the "Workshop on Differential Privacy and Statistical Data Analysis" at the Fields Institute, this talk provides insights into crucial aspects of data privacy and machine learning.

Intro
Motivating Questions
Non-Private Classification
Example: Learning 1-Dim Thresholds Space of examples X - 7 - 1....I
Sample Complexity of Learning Rest of this talk: Fix learning parameters a = 0.01,49 = 0.01 Learning Thresholds: Possible with a number of samples n = 0(1) independent of T
Sample Complexity of Private Learning
Characterizing Private Sample Complexit
Characterizing Private Learnability
Online Learning / Littlestone Dimension
Mistake Bounded Learning vs. DP