Sign inSign up
On-Line Learning Algorithms for Path Experts with Non-Additive Losses thumbnail
Pause
Mute
Subtitles not available
Playback speed
0.25
0.5
0.75
1
1.25
1.5
1.75
2
Full screen

On-Line Learning Algorithms for Path Experts with Non-Additive Losses

Published on Aug 20, 20152139 Views

Vitaly Kuznetsov

We consider two broad families of non-additive loss functions covering a large number of applications: rational losses and tropical losses. We give new algorithms extending the Follow-the-Perturbed-Le

COLT 2015 - Paris

Related categories

Active LearningComputational Learning TheoryOn-line LearningReinforcement LearningSemi-supervised Learning

Chapter list

On-Line Learning Algorithms for Path Experts with Non-Additive Losses00:00
Prediction with Expert Advice00:17
Path Experts01:10
Problem02:43
Outline03:52
Semirings04:52
Weighted Automata and Transducers06:29
Composition08:26
Determinization09:20
Non-Additive Losses10:21
Extension of FPL to Rational Loss12:45
Key Ideas13:18
Follow-the-Perturbed-Rational-Leader14:37
Running-Time Complexity15:04
Regret Guarantees15:41
Conclusion16:46