From the 1 of 13 linked papers with an AI index.
10 papers · 1 filter
Tight Generalization Bound for AdaBoost
Mikael Møller Høgsgaard
The paper derives a tight upper bound on the generalization error of AdaBoost, expressed in terms of the weak learner's advantage, VC-dimension, sample size, and confidence level,…
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…
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…
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…
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…
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…