1 citations · 1 across the 9 of their papers we have counts for
12 papers
Boosting and the Expressive Power of Simple Weak Learners via the -VC Dimension
Arthur da Cunha, Kasper Green Larsen, Liang-Yu Zou
Boosting converts weak hypotheses with a small edge over random guessing into highly accurate predictors, but the expressive power of the resulting classifier can depend strongly o…
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…
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…
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…
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…
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…
Revisiting Agnostic PAC Learning
Steve Hanneke, Kasper Green Larsen, Nikita Zhivotovskiy
PAC learning, dating back to Valiant'84 and Vapnik and Chervonenkis'64,'74, is a classic model for studying supervised learning. In the agnostic setting, we have access to a hypoth…
Majority-of-Three: The Simplest Optimal Learner?
Ishaq Aden-Ali, Mikael Møller Høgsgaard, Kasper Green Larsen +1
Developing an optimal PAC learning algorithm in the realizable setting, where empirical risk minimization (ERM) is suboptimal, was a major open problem in learning theory for decad…
Replicable Learning of Large-Margin Halfspaces
Alkis Kalavasis, Amin Karbasi, Kasper Green Larsen +2
We provide efficient replicable algorithms for the problem of learning large-margin halfspaces. Our results improve upon the algorithms provided by Impagliazzo, Lei, Pitassi, and S…
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…