10 papers
Tight Margin-Based Generalization Bounds for Voting Classifiers over Finite Hypothesis Sets
Kasper Green Larsen, Natascha Schalburg
We prove the first margin-based generalization bound for voting classifiers, that is asymptotically tight in the tradeoff between the size of the hypothesis set, the margin, the fr…
Optimal Parallelization of Boosting
Arthur da Cunha, Mikael Møller Høgsgaard, Kasper Green Larsen
Recent works on the parallel complexity of Boosting have established strong lower bounds on the tradeoff between the number of training rounds and the total parallel work per r…
Improved Margin Generalization Bounds for Voting Classifiers
Mikael Møller Høgsgaard, Kasper Green Larsen
In this paper we establish a new margin-based generalization bound for voting classifiers, refining existing results and yielding tighter generalization guarantees for widely used…
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…
Boosting, Voting Classifiers and Randomized Sample Compression Schemes
Arthur da Cunha, Kasper Green Larsen, Martin Ritzert
In boosting, we aim to leverage multiple weak learners to produce a strong learner. At the center of this paradigm lies the concept of building the strong learner as a voting class…