The upper bound proof follows by combining the known fact that AdaBoost outputs a voting classifier whose voting function has zero empirical $\gamma/2$-margin loss with what is, to the best of the authors' knowledge, a new margin-based generalization bound for voting classifiers.
Abstract
In this paper we show that the generalization error of AdaBoost is $\Theta\big(\tfrac{d\ln(n\gamma^{2}/d)}{n\gamma^2}+\tfrac{\ln(1/\delta)}{n}\big)$, where $\gamma$ is the advantage guaranteed by the weak learner, $d$ is the VC-dimension of the class containing the weak hypotheses, $n$ is the sample size, and $\delta$ is the confidence parameter. The contribution of this paper is the upper bound; the matching lower bound follows from prior work. The upper bound proof follows by combining the known fact that AdaBoost outputs a voting classifier whose voting function has zero empirical $\gamma/2$-margin loss with what is, to the best of our knowledge, a new margin-based generalization bound for voting classifiers.
Factorized {AdaBoost.MH} achieves the same boosting-type convergence rate as {AdaBoost.MH} up to a universal constant factor, removing the previously suggested additional dependence on $n$ or $K$ in the number of boosting rounds.
Worst-case multiclass bounds do not become smaller when the best classifier is already nearly correct: what is missing is an optimistic rate, a guarantee whose fluctuation scales with the oracle risk itself. For a class of Natarajan dimension $d_N$ and Daniely-Shalev-Shwartz dimension $d_{DS}$, the optimal excess risk...
Xiao-Yu Li, Andi Han, Jiao-Jiao Jiang et al.· 1 citation
This paper settles the sample complexity of agnostic PAC learning up to universal constants at every fixed $L^*$, matching the lower bounds of Devroye, Gyorfi, and Lugosi.
Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy· 2 citations· ⚡1
This work presents a new boosting algorithm that, for any class $\mathcal{F}$ closed under $O(\log \frac{1}{\gamma})$-XOR, strong learns $\mathcal{F}$ using $O(\log \frac{1}{\epsilon})$ calls to a $\gamma$-advantage weak learner and a single batch of $\tilde{O}(\log(\frac{1}{\epsilon
This work improves the upper bound to match the best known lower bound, thus establishing the optimal error guarantee for learning under Tsybakov noise.
Steve Hanneke, Hongao Wang, Mingyue Xu· 0 citations
The Johnson--Lindenstrauss lemma asserts that every set of $n$ points in $d$-dimensional Euclidean space embeds into $O(\varepsilon^{-2}\log n)$-dimensional Euclidean space with distortion at most $1+\varepsilon$. Larsen and Nelson conjectured that the optimal target dimension throughout the full range of the parameter...
Vishesh Jain· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
