Markus Engelund Mathiasen

collaborators

3 papers

cs.LG2026

An Optimal Agnostic PAC Algorithm

Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy

Let $H \subseteq {- 1, + 1}^{X}$ be a class of finite VC dimension $d \geq 1$ . Writing $L$ for the binary risk and $L^{*} = min_{h \in H} L (h)$ , we construct a learner achieving the statistical…

cs.LG2026

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…

cs.LG2025

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…