en
0.25
0.5
0.75
1.25
1.5
1.75
2
Combinatorial prediction games
Published on 2012-01-254384 Views
Combinatorial prediction games are problems of online linear optimization in which the action space is a combinatorial space. These games can be studied under different feedback models: full, semi-ban
Related categories
Presentation
Combinatorial Prediction Games00:00
Example: Keeping a low-cost spanning tree - 100:33
Example: Keeping a low-cost spanning tree - 201:10
Example: Keeping a low-cost spanning tree - 301:24
Example: Keeping a low-cost spanning tree - 401:33
Feedback models - 102:16
Feedback models - 202:48
Feedback models - 303:09
Combinatorial prediction games03:50
Regret06:26
Algorithm ExpandedHedge13:10
Player’s strategy16:21
Legendre potentials and Bregman divergences16:42
Online Stochastic Mirror Descent (OSMD) - 118:11
Online Stochastic Mirror Descent (OSMD) - 218:55
Online Stochastic Mirror Descent (OSMD) - 319:05
Online Stochastic Mirror Descent (OSMD) - 419:13
Online Stochastic Mirror Descent (OSMD) - 519:54
Efficient decomposition and sampling for OSMD21:00
Various instances23:14
Known regret bounds25:38
Algorithm GeometricHedge29:38
Analysis31:32
Some cases is which uniform exploration is optimal35:54
Sampling problem35:56
Routing: when uniform exploration fails36:28
Change of representation37:14
Barycentric spanners - 138:14
Barycentric spanners - 238:34
Remarks on barycentric spanners39:05
Löwner ellipsoid - 140:07
Löwner ellipsoid - 240:22
Remarks on Löwner ellipsoid40:48
Regret bounds43:22
Conclusions43:36