The Price of Differential Privacy For Online Learning

In the paradigm of online learning, a learning algorithm makes a sequence of predictions given the (possibly incomplete) knowledge of the correct answers for the past queries. In contrast to statistical learning, online learning algorithms typically offer distribution-free guarantees. Consequently, online learning algorithms are well suited to dynamic and adversarial environments, where real-time learning from changing data is essential making them ubiquitous in practical applications such as servicing search advertisements.