Tight Generalization Bound for AdaBoost

• URL: http://arxiv.org/abs/2607.26838v1
• Date: Wed, 29 Jul 2026 12:27:29 GMT
• Title: Tight Generalization Bound for AdaBoost
• Abstract summary: We show that the generalization error of AdaBoost is $big(tfracdln(n2/d)n2+tfracln (1/)nbig)$.
• Score: 6.768558752130311
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper we show that the generalization error of AdaBoost is $Θ\big(\tfrac{d\ln(nγ^{2}/d)}{nγ^2}+\tfrac{\ln(1/δ)}{n}\big)$, where $γ$ 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 $δ$ 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 $γ/2$-margin loss with what is, to the best of our knowledge, a new margin-based generalization bound for voting classifiers.

Related papers

• Inevitability of Encrypted Traffic Side-Channel Leakage in the Multi-Class Setting [20.06940271479014]
  We extend the Side-Channel Existence Theorem to $k$ classes via the per-class decomposition $I(X;Y)=sum_i_i D_mathrmKL(P_Y|i|P_Y)$, with defense cost modelled by per-class Wasserstein-1 constraints.<n>Three results follow: (1) a summation-form MI lower bound over all active classes; (2) a cascade critical cost theorem and a per-class budget corollary, nonzero where the uniform-budget bound vanishes; (3) an accuracy $mathrmAcc*
  arXiv  Detail & Related papers  (2026-09-06T00:48:40Z)
• Factorized AdaBoost.MH Achieves the Same Convergence Rate as AdaBoost.MH [11.157319736363823]
  A more structured variant, Factorized AdaBoost.MH, uses base classifiers of the form $mathbfh(x)=mathbfv bmvarphi(x)$.<n>We show that Factorized AdaBoost.MH achieves the same boosting-type convergence rate as AdaBoost.MH up to a universal constant factor.
  arXiv  Detail & Related papers  (2026-08-02T08:46:38Z)
• Boosting with List-Decodable Codes [4.3070965805068875]
  We present a new boosting algorithm for any class $mathcalF$ closed under $O(log frac1)$-XOR.<n>Our algorithm arises from a new and simple connection between boosting and list-decodable codes.
  arXiv  Detail & Related papers  (2026-07-07T03:34:53Z)
• Rényi exponent landscape of multipartite entanglement in free-fermion systems [51.56484100374058]
  We show that the Rényi tripartite information $I_3() exhibits a qualitatively $exclusion-dependent scaling at small Fermi momentum.<n>A direct consequence is a replica obstruction: $I_m(n)/I_m(1) sim zm-1 to 0$ for all integer $n geq 2$, so the leading von Neumann signal cannot be reconstructed from integer Rényi data.
  arXiv  Detail & Related papers  (2026-03-09T22:27:00Z)
• Proofs as Explanations: Short Certificates for Reliable Predictions [25.157401709060064]
  We consider a model for explainable AI in which an explanation for a prediction $h(x)=y$ consists of a subset $S'$ of the training data.<n>A set $S'$ of size $d+1$ could be released as an explanation for a positive prediction, and would serve as a short proof of correctness of the prediction under the assumption of realizability.
  arXiv  Detail & Related papers  (2025-04-11T09:26:37Z)
• The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem [53.446980306786095]
  Smooth boosters generate distributions that do not place too much weight on any given example. Originally introduced for their noise-tolerant properties, such boosters have also found applications in differential privacy, mildly, and quantum learning theory.
  arXiv  Detail & Related papers  (2024-09-17T23:09:25Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  We study multiclass PAC learning with bandit feedback, where inputs are classified into one of $K$ possible labels and feedback is limited to whether or not the predicted labels are correct. Our main contribution is in designing a novel learning algorithm for the agnostic $(varepsilon,delta)$PAC version of the problem.
  arXiv  Detail & Related papers  (2024-06-18T08:54:04Z)
• Boosting with Tempered Exponential Measures [40.961820572346426]
  A popular ML algorithm, AdaBoost, can be derived from the dual of a relative entropy minimization problem. We generalize this setup to the recently introduced it tempered exponential measures (TEMs) where normalization is enforced on a specific power of the measure and not the measure itself. Our algorithm, $t$-AdaBoost, recovers AdaBoostas a special case ($t=1$)
  arXiv  Detail & Related papers  (2023-06-08T18:17:48Z)
• Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient [88.86699022151598]
  We give a statistical characterization of the $gamma$-regret for arbitrary structured bandit problems. The $gamma$-regret emerges in structured bandit problems over a function class $mathcalF$ where finding an exact optimum of $f in mathcalF$ is intractable.
  arXiv  Detail & Related papers  (2023-03-06T17:54:33Z)
• Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
  Ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
  arXiv  Detail & Related papers  (2023-02-27T16:34:21Z)
• Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization [10.787390511207683]
  We consider a twice-differentiable, $L$-smooth, $mu$-strongly convex objective $phimph over an $ntimes n$fracfrac14(L/mu-1)2rstar$. Despite non-locality, local optimization is guaranteed to globally converge from any initial point to the global optimum.
  arXiv  Detail & Related papers  (2022-07-05T03:18:17Z)
• High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize [55.0090961425708]
  We propose a new, simplified high probability analysis of AdaGrad for smooth, non- probability problems. We present our analysis in a modular way and obtain a complementary $mathcal O (1 / TT)$ convergence rate in the deterministic setting. To the best of our knowledge, this is the first high probability for AdaGrad with a truly adaptive scheme, i.e., completely oblivious to the knowledge of smoothness.
  arXiv  Detail & Related papers  (2022-04-06T13:50:33Z)
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
  We study the fundamental problems of agnostically learning halfspaces and ReLUs under Gaussian marginals. Our lower bounds provide strong evidence that current upper bounds for these tasks are essentially best possible.
  arXiv  Detail & Related papers  (2020-06-29T17:10:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.