48 citations · 181 across the 49 of their papers we have counts for
10 papers · 1 filter
AdaBoost is not an Optimal Weak to Strong Learner
Mikael Møller Høgsgaard, Kasper Green Larsen, Martin Ritzert
AdaBoost is a classic boosting algorithm for combining multiple inaccurate classifiers produced by a weak learner, to produce a strong learner with arbitrarily high accuracy when g…
The Impossibility of Parallelizing Boosting
Amin Karbasi, Kasper Green Larsen
The aim of boosting is to convert a sequence of weak learners into a strong learner. At their heart, these methods are fully sequential. In this paper, we investigate the possibili…
Bagging is an Optimal PAC Learner
Kasper Green Larsen
Determining the optimal sample complexity of PAC learning in the realizable setting was a central open problem in learning theory for decades. Finally, the seminal work by Hanneke…
Optimal Weak to Strong Learning
Kasper Green Larsen, Martin Ritzert
The classic algorithm AdaBoost allows to convert a weak learner, that is an algorithm that produces a hypothesis which is slightly better than chance, into a strong learner, achiev…
Compression Implies Generalization
Allan Grønlund, Mikael Høgsgaard, Lior Kamma +1
Explaining the surprising generalization performance of deep neural networks is an active and important line of research in theoretical machine learning. Influential work by Arora…
Margins are Insufficient for Explaining Gradient Boosting
Allan Grønlund, Lior Kamma, Kasper Green Larsen
Boosting is one of the most successful ideas in machine learning, achieving great practical performance with little fine-tuning. The success of boosted classifiers is most often at…
Near-Tight Margin-Based Generalization Bounds for Support Vector Machines
Allan Grønlund, Lior Kamma, Kasper Green Larsen
Support Vector Machines (SVMs) are among the most fundamental tools for binary classification. In its simplest formulation, an SVM produces a hyperplane separating two classes of d…
Margin-Based Generalization Lower Bounds for Boosted Classifiers
Allan Grønlund, Lior Kamma, Kasper Green Larsen +2
Boosting is one of the most successful ideas in machine learning. The most well-accepted explanations for the low generalization error of boosting algorithms such as AdaBoost stem…
Optimal Minimal Margin Maximization with Boosting
Allan Grønlund, Kasper Green Larsen, Alexander Mathiasen
Boosting algorithms produce a classifier by iteratively combining base hypotheses. It has been observed experimentally that the generalization error keeps improving even after achi…
Fully Understanding the Hashing Trick
Casper Benjamin Freksen, Lior Kamma, Kasper Green Larsen
Feature hashing, also known as {\em the hashing trick}, introduced by Weinberger et al. (2009), is one of the key techniques used in scaling-up machine learning algorithms. Loosely…