There is no required textbook for this course, but the following are the most related textbooks and monographs:
This course is an introduction to the foundations of online learning, also known as sequential prediction. Online learning, together with its sibling online convex optimization, has mostly developed in the last 25 years, with rapid progress over the last 10 years. The area builds upon fundamental algorithmic ideas and mathematical foundations dating as far back to the 1950's. What is online learning? Well, let's see an example:
Suppose that for each day in a sequence of days, a learning agent observes the weather predictions of \(K\) experts (like "30% rain" or "90% rain", etc.) and then must aggregate these predictions somehow to give its own prediction (like the probability forecast "40% rain"). At the end of each day, the agent observes the actual weather outcome (like "rain"), and depending on the accuracy of its prediction, it suffers some error. The learning agent wishes that, at the end of the sequence of days, its cumulative error is not much larger than the cumulative error of the best expert. What algorithmic strategy might the agent use to decide its prediction each day? This type of question is precisely what we study in online learning.
Along the way to learning about foundational algorithms in online learning and online convex optimization, we will learn fundamental concepts from convex analysis and probability. We will begin by seeing algorithms in the area, and then we will see how they are derived as well as how to prove guarantees on their performance. We also will see applications of online learning to other areas, such as (standard) convex optimization, finding approximate Nash equilibria for twoplayer zerosum games, strategies for rapidly growing wealth (portfolio selection), and (maybe!) strategies for data compression.
In the schedule below, any information about future lectures is just a rough guide and might change.
Lectures
