4 papers
Tight Generalization Bounds for Large-Margin Halfspaces
Kasper Green Larsen, Natascha Schalburg
We prove the first generalization bound for large-margin halfspaces that is asymptotically tight in the tradeoff between the margin, the fraction of training points with the given…
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…
Derandomizing Multi-Distribution Learning
Kasper Green Larsen, Omar Montasser, Nikita Zhivotovskiy
Multi-distribution or collaborative learning involves learning a single predictor that works well across multiple data distributions, using samples from each during training. Recen…
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…