Private Boosting and Noise-tolerant Learning
summary
Constructs a private booster that enforces Sigma-smooth distributions by doing multiplicative-weights updates on an unnormalized measure and then Bregman-projecting into the smooth set, which preserves differential privacy via small statistical-distance changes. Uses Gaussian-noised centroids as the weak learner so advantage drops by about Sigma/epsilon, composes to a concentrated-DP booster, and yields a private learner for large-margin halfspaces with final sample complexity on the order of 1/(epsilon · gamma^2). The method tolerates malicious noise ~alpha·gamma and generalizes via margin or DP.
AI-written summary · about
chapters (19)
- 0:00Introduction
- 1:30Boosting
- 3:21Boosting Algorithms
- 5:40Example of Boosting
- 14:29What are we doing
- 16:07The framework
- 19:34The main question
- 20:59Smooth Boosting
- 26:39Boosting for People
- 30:04Lazy Normalization
- 31:20Theorem
- 32:09Analysis
- 33:24Application
- 38:26Properties
- 39:39Generalization
- 40:11Marginbased generalization
- 42:46Differentially private generalization
- 44:04Noise tolerant learning
- 45:42Further directions
related talks
01h 07mLarge-Scale Private Learning, Part II
01h 02mLarge-Scale Private Learning, Part I
01h 14mTutorial: Privacy, Part II
01h 14mTutorial: Privacy, Part III
36mPrivately Learning High-Dimensional Distributions
30mLarge Scale Private Learning on Data Streams, and the BLTs
17mData privacy and reliable learning
31mScaling privacy embedded distributed ML systems