|
3.30 pm,Seminar Hall On Adaptivity in Information-Constrained Online Learning Siddharth Mitra MSc, Chennai Mathematical Institute. 18-09-19 Abstract Adapting to easy environments and going beyond conventional worst case bounds is a topic of great interest in algorithm design. In this talk, we will discuss how to adapt to easy environments in classes of information-constrained online learning problems. We will first consider label efficient prediction, a budgeted version of the classical prediction with expert advice problem. We will then extend our analysis to handle label efficient prediction with bandit feedback— a problem aptly termed as label efficient bandits. For all of these settings, we will discuss regret minimization algorithms which scale optimally with the quadratic variation of the loss sequence— a measure of the easiness of the environment, and with epsilon— a parameter governed by the constraint on information. Our algorithms are built upon the Online Mirror Descent framework and leverage optimistic messages, second order corrections, along with a carefully weighted hybrid regularizer to ensure optimal dependence on the problem parameters. Time permitting, we will also comment upon adaptivity for partial monitoring problems— a general paradigm which extends prediction with expert advice and multi-armed bandits. This is joint work with Aditya Gopalan.
|
