1 citations · 4 across the 17 of their papers we have counts for
21 papers
Reconciling Universal and Uniform Learning with -Aggregation
Mikael Møller Høgsgaard, Patrick Rebeschini, Tobias Wegel
We study regression under bounded responses in terms of excess mean squared error. When the comparator class is finite, this setting is known as model selection aggregation, and ac…
Tight Generalization Bound for AdaBoost
Mikael Møller Høgsgaard
In this paper we show that the generalization error of AdaBoost is , where is the advantage guaranteed by the weak…
Aggregation with Exponential Weights is Optimal in Expectation
Mikael Møller Høgsgaard, Patrick Rebeschini, Tobias Wegel
The aggregation with exponential weights (AEW) estimator is not fully understood in the basic setting of model selection aggregation with squared loss. In particular, whether it is…
The Interplay Between Interpolation and Aggregation in Regression: Optimal Sample Complexity
Mikael Møller Høgsgaard, Kasper Green Larsen, Liang-Yu Zou
This work investigates theoretically the interplay between interpolation and aggregation in regression. We establish that the -graph dimension characterizes learnability for a b…
Agnostic Language Identification and Generation
Mikael Møller Høgsgaard, Chirag Pabbaraju
Recent works on language identification and generation have established tight statistical rates at which these tasks can be achieved. These works typically operate under a strong r…
The Optimal Sample Complexity of Linear Contracts
Mikael Møller Høgsgaard
In this paper, we settle the problem of learning optimal linear contracts from data in the offline setting, where agent types are drawn from an unknown distribution and the princip…
Uniform Mean Estimation for Heavy-Tailed Distributions via Median-of-Means
Mikael Møller Høgsgaard, Andrea Paudice
The Median of Means (MoM) is a mean estimator that has gained popularity in the context of heavy-tailed data. In this work, we analyze its performance in the task of simultaneously…
Revisiting Agnostic Boosting
Arthur da Cunha, Mikael Møller Høgsgaard, Andrea Paudice +1
Boosting is a key method in statistical learning, allowing for converting weak learners into strong ones. While well studied in the realizable case, the statistical properties of w…
Efficient Optimal PAC Learning
Mikael Møller Høgsgaard
Recent advances in the binary classification setting by Hanneke [2016b] and Larsen [2023] have resulted in optimal PAC learners. These learners leverage, respectively, a clever det…
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…
On Agnostic PAC Learning in the Small Error Regime
Julian Asilis, Mikael Møller Høgsgaard, Grigoris Velegkas
Binary classification in the classic PAC model exhibits a curious phenomenon: Empirical Risk Minimization (ERM) learners are suboptimal in the realizable case yet optimal in the ag…
Understanding Aggregations of Proper Learners in Multiclass Classification
Julian Asilis, Mikael Møller Høgsgaard, Grigoris Velegkas
Multiclass learnability is known to exhibit a properness barrier: there are learnable classes which cannot be learned by any proper learner. Binary classification faces no such bar…
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…
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…
Sparse Dimensionality Reduction Revisited
Mikael Møller Høgsgaard, Lion Kamma, Kasper Green Larsen +2
The sparse Johnson-Lindenstrauss transform is one of the central techniques in dimensionality reduction. It supports embedding a set of points in into $m=O(\vare…
Optimally Interpolating between Ex-Ante Fairness and Welfare
Mikael Møller Høgsgaard, Panagiotis Karras, Wenyue Ma +2
For the fundamental problem of allocating a set of resources among individuals with varied preferences, the quality of an allocation relates to the degree of fairness and the colle…
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…
Barriers for Faster Dimensionality Reduction
Ora Nova Fandina, Mikael Møller Høgsgaard, Kasper Green Larsen
The Johnson-Lindenstrauss transform allows one to embed a dataset of points in into while preserving the pairwise distance between any pair of po…
The Fast Johnson-Lindenstrauss Transform is Even Faster
Ora Nova Fandina, Mikael Møller Høgsgaard, Kasper Green Larsen
The seminal Fast Johnson-Lindenstrauss (Fast JL) transform by Ailon and Chazelle (SICOMP'09) embeds a set of points in -dimensional Euclidean space into optimal $k=O(\vareps…
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…