The price of bandit information in multiclass online classification thumbnail
Pause
Mute
Subtitles
Playback speed
0.25
0.5
0.75
1
1.25
1.5
1.75
2
Full screen

The price of bandit information in multiclass online classification

Published on Aug 09, 20132970 Views

We consider two scenarios of multiclass online learning of a hypothesis class H⊆YX. In the full information scenario, the learner is exposed to instances together with their labels. In the bandit scen

Related categories

Chapter list

The price of bandit information in multiclass online classification00:00
Online multiclass classification: Full info vs Bandits00:13
Outline - 101:30
Hypothesis classes based online learning01:43
Setting - Mistake bounds02:20
A toy example03:05
Main Result04:30
Previous Results04:49
Outline - 206:23
The Littlestone dimension (Littlestone, 89, Daniely et al, 11)06:26
The Littlestone dimension (Littlestone, 89) - 107:44
The Littlestone dimension (Littlestone, 89) - 207:59
The Littlestone dimension (Littlestone, 89) - 308:16
The Littlestone dimension (Littlestone, 89) - 408:33
The Littlestone dimension (Littlestone, 89) - 508:45
The Littlestone dimension (Littlestone, 89) - 608:57
The Littlestone dimension (Littlestone, 89) - 709:10
The Littlestone dimension (Littlestone, 89) - 809:27
The Littlestone dimension (Littlestone, 89) - 909:31
The Littlestone dimension (Littlestone, 89) - 1009:48
The Littlestone dimension (Littlestone, 89) - 1109:56
Proof of the main theorem: a preface - 110:11
Proof of the main theorem: a preface - 211:00
Proof of the main theorem: a preface - 311:17
Proof of the main theorem: a preface - 411:18
Proof of the main theorem: a preface - 511:19
Proof of the main theorem: a preface - 611:24
Proof of the main theorem: a preface - 711:35
Proof of the main theorem: the splitting mechanism12:08
Proof of the main theorem: the algorithm12:54
Proof of the main theorem: analysis - 113:20
Proof of the main theorem: analysis - 213:56
Conclusion and open questions14:26