Online Learning with Kernels

Online learning is concerned with the task of making decisions on-the-fly as observations are received. We describe and analyze several online learning tasks through the same algorithmic prism. We start with online binary classification and show how to build simple yet efficient and effective online algorithms that incorporate kernel functions. We describe how to analyze the algorithms in the mistake bound model for both separable and inseparable settings. We then describe numerous generalizations of online learning with kernels to other, often more complex, problems. Specifically, we discuss learning algorithms for uniclass prediction, regression, multiclass problems, and sequence prediction. We conclude with discussion on implications to batch learning and generalization. Based on joint works with Koby Crammer, Ofer Dekel, Vineet Gupta, Joseph Keshet, Andrew Ng, Shai Shalev-Shwartz?, Lavi Shpigelman.