7 citations · 14 across the 5 of their papers we have counts for
9 papers
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…
Lower Bounds for Multiplication via Network Coding
Peyman Afshani, Casper Benjamin Freksen, Lior Kamma +1
Multiplication is one of the most fundamental computational problems, yet its true complexity remains elusive. The best known upper bound, by Fürer, shows that two -bit numbers…
Batch Sparse Recovery, or How to Leverage the Average Sparsity
Alexandr Andoni, Lior Kamma, Robert Krauthgamer +1
We introduce a \emph{batch} version of sparse recovery, where the goal is to report a sequence of vectors that estimate unknown signals $A_1,\ld…