Spotlight
Online Learning via the Differential Privacy Lens
Jacob Abernethy · Young Hun Jung · Chansoo Lee · Audra McMillan · Ambuj Tewari

Wed Dec 11th 04:55 -- 05:00 PM @ West Exhibition Hall A
in Track 2 Session 4 »

In this paper, we use differential privacy as a lens to examine online learning in both full and partial information settings. The differential privacy framework is, at heart, less about privacy and more about algorithmic stability, and thus has found application in domains well beyond those where information security is central. Here we develop an algorithmic property called one-step differential stability which facilitates a more refined regret analysis for online learning methods. We show that tools from the differential privacy literature can yield regret bounds for many interesting online learning problems including online convex optimization and online linear optimization. Our stability notion is particularly well-suited for deriving first-order regret bounds for follow-the-perturbed-leader algorithms, something that all previous analyses have struggled to achieve. We also generalize the standard max-divergence to obtain a broader class called Tsallis max-divergences. These define stronger notions of stability that are useful in deriving bounds in partial information settings such as multi-armed bandits and bandits with experts.

Author Information

Jacob Abernethy (Georgia Institute of Technology)
Young Jung (University of Michigan)
Chansoo Lee (Google)
Audra McMillan (Northeastern/Boston University)
Ambuj Tewari (University of Michigan)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors