|
Abstract:
|
In recent years, a new framework has emerged that allows rigorous analysis of online learning methods and the development of computationally efficient algorithms. The theoretical techniques can be viewed as a martingale generalization of empirical process theory, while the algorithmic toolkit can be seen as a form of approximate dynamic programming. These new tools bring forth fascinating connections to statistics, probability theory, and optimization.
In this talk, we will outline some of the key results and consider a particular example of node classification in a network, as well as its "contextual bandit" version. We will develop new prediction algorithms that circumvent computational hardness of estimating a model while achieving near-optimal performance, both in theory and in practice.
|
