Sign inSign up
An Almost Optimal PAC Algorithm thumbnail
slide-image
Pause
Mute
Subtitles not available
Playback speed
0.25
0.5
0.75
1
1.25
1.5
1.75
2
Full screen

An Almost Optimal PAC Algorithm

Published on Aug 20, 20152216 Views

Hans U. Simon

The best currently known general lower and upper bounds on the number of labeled examples needed for learning a concept class in the PAC framework (the realizable case) do not perfectly match: they le

COLT 2015 - Paris

Related categories

Active LearningComputational Learning TheoryOn-line LearningReinforcement LearningSemi-supervised Learning

Chapter list

An Almost Optimal PAC Algorithm00:00
Outline - 100:53
Outline - 201:03
PAC Learning and Sample Complexity01:08
Warmuth’s Open Problem from COLT 200402:15
Our Contribution03:03
Our Contribution (continued)04:00
Outline - 304:56
The Old and the New Policy05:26
Learner Transformation: from L to LK06:24
Outline - 407:01
A Central Feature of the Proof07:19
Step 1: Decomposition of the Total Error Set09:15
Step 2: Decomposition of P(EJ)10:46
Step 3: Setting Up a Recursion on εk13:08
Step 4: Solving the Recursion13:38
Step 5: Putting Everything Together14:20
Outline - 515:16
Final Remarks15:21