Skip to yearly menu bar Skip to main content


Poster

Online Learning with Transductive Regret

Scott Yang · Mehryar Mohri

Pacific Ballroom #65

Keywords: [ Learning Theory ] [ Online Learning ] [ Theory ] [ Game Theory and Computational Economics ] [ Algorithms ]


Abstract:

We study online learning with the general notion of transductive regret, that is regret with modification rules applying to expert sequences (as opposed to single experts) that are representable by weighted finite-state transducers. We show how transductive regret generalizes existing notions of regret, including: (1) external regret; (2) internal regret; (3) swap regret; and (4) conditional swap regret. We present a general and efficient online learning algorithm for minimizing transductive regret. We further extend that to design efficient algorithms for the time-selection and sleeping expert settings. A by-product of our study is an algorithm for swap regret, which, under mild assumptions, is more efficient than existing ones, and a substantially more efficient algorithm for time selection swap regret.

Live content is unavailable. Log in and register to view live content