4 papers · 1 filter
An Optimal Agnostic PAC Algorithm
Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy
Let be a class of finite VC dimension . Writing for the binary risk and , we construct a learner achieving the statistical…
The Sample Complexity of Replicable Realizable PAC Learning
Kasper Green Larsen, Markus Engelund Mathiasen, Chirag Pabbaraju +1
In this paper, we consider the problem of replicable realizable PAC learning. We construct a particularly hard learning problem and show a sample complexity lower bound with a clos…
Improved Replicable Boosting with Majority-of-Majorities
Kasper Green Larsen, Markus Engelund Mathiasen, Clement Svendsen
We introduce a new replicable boosting algorithm which significantly improves the sample complexity compared to previous algorithms. The algorithm works by doing two layers of majo…
The Many Faces of Optimal Weak-to-Strong Learning
Mikael Møller Høgsgaard, Kasper Green Larsen, Markus Engelund Mathiasen
Boosting is an extremely successful idea, allowing one to combine multiple low accuracy classifiers into a much more accurate voting classifier. In this work, we present a new and…