In the talk we describe and analyze online algorithms based on the notion of duality.
Using the weak duality theorem we distill the process of online learning to the task of incrementally increasing the dual objective function. The amount by which the dual increases serves as a new and natural notion of progress for analyzing online learning algorithms. This view lets us view old algorithms in a new perspective as well as devise new algorithms for large scale prediction problems. Time permitting, we demonstrate the power of the primal-dual view in the design and analysis of algorithms for classification, ranking, regression, and distance learning.
Based on joint works with Shai Shalev-Shwartz, Koby Crammer, Ofer Dekel, Sam Roweis, and Phil Long.
Copyright. All Rights Reserved.