arXiv：cs.LG· Arthur da Cunha, Kasper Green Larsen, Liang-Yu Zou·· 4 小时前AI 评分32
通过 γ-VC 维数提升简单弱学习器的表达能力
Boosting and the Expressive Power of Simple Weak Learners via the $\gamma$-VC Dimension
AI 导读
研究利用 Alon 等人（STOC 2021）提出的 γ-VC 维数刻画 boosting 中弱到强学习的样本复杂度，证明该参数在 γ 的常数因子范围内可表征弱到强学习的样本复杂度。研究进一步厘清了经典 VC 维数与 γ-VC 维数之间的一般关系，并为决策树桩与 R^d 中轴平行矩形这两类基本概念类给出了改进的 γ-VC 维数上下界。
正文
Abstract:Boosting converts weak hypotheses with a small edge over random guessing into highly accurate predictors, but the expressive power of the resulting classifier can depend strongly on the structure of the base class. We study this phenomenon through the $\gamma$-VC dimension introduced by Alon et al. (STOC 2021). Our first result shows that this parameter characterizes the sample complexity for weak-to-strong learning up to a constant factor scaling in $\gamma$. We then sharpen the general relationship between the classic VC dimension and the $\gamma$-VC dimension. Finally, we also give improved upper and lower bounds on the $\gamma$-VC dimension for the fundamental concept classes of decision stumps and axis-parallel rectangles in $\mathbb{R}^d$.
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.10383 [cs.LG] |
| (or arXiv:2610.10383v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.10383 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Liang-Yu Zou [view email]
[v1]
Wed, 7 Oct 2026 16:42:44 UTC (358 KB)
来源：arXiv：cs.LG · arxiv.org