Bandit Learning under Differential Privacy
summary
Defines event-level pure differential privacy for bandit pulls, proves a lower bound that private algorithms must pull any suboptimal arm roughly Omega(log T /(epsilon · Delta)) times, and gives a matching algorithm: a private, epoched successive-elimination that partitions rounds, resets private histograms, uses sparse-vector-style queries on exponentially growing epochs to reduce noise, and achieves near nonprivate regret plus a polylog(T)/epsilon overhead. Includes a private stopping rule, experiments, and an optimal algorithm for the multivariate problem plus discussion of the private stopping point.
AI-written summary · about
chapters (14)
- 0:00Road Map
- 0:55Motivating Story
- 2:29Multi-Armed Bandits
- 4:07Exploration vs. Exploitation
- 4:50Optimism in the Face of Uncertainty
- 8:33Optimism for Linear Bandits
- 9:47Ellipsoidal Confidence Sets
- 11:43Contextual Bandits
- 21:06Lower Bounds
- 28:43Successive Elimination EMM02
- 29:58The Stopping Rule Problem
- 32:51The Private Stopping Rule
- 34:45Back to MAB
- 35:31Private Successive Elimination Algorithm
related talks
17mData privacy and reliable learning
43mDifferential Privacy Meets Robust Statistics
30mAccuracy First: Selecting a Differential Privacy Level for Accuracy-Constrained...
58mLarge-Scale Private Learning, Part III
01h 21mAdversarial Bandits: Theory and Algorithms
47mPrivate targeting strategies
19mPractical Considerations for Differential Privacy
42mDifferential Privacy