首个近似最优采样复杂度的抗干扰提升算法，运行时间多项式优化。
Sample-Near-Optimal Agnostic Boosting with Improved Running Time
- 设计新型抗干扰提升框架，避免对数据分布做假设。
- 在样本量固定时，运行时间呈多项式增长，突破指数瓶颈。
- 适用于无先验假设的高精度学习场景，如噪声数据训练。
提升方法能将仅略优于随机猜测的弱学习器转化为高精度强学习器。尽管经典设定下提升理论成熟，但在无任何数据假设的抗干扰情形下仍不清晰。近期工作（arXiv:2503.09384）几乎确定了抗干扰提升的样本复杂度下界，但实现该界的算法存在指数级运行时间。本文提出首个达到近似最优样本复杂度的抗干扰提升算法，在其他问题参数固定时，运行时间关于样本量为多项式。该结果首次实现了理论最优性与高效计算的统一。
原文摘要 · Abstract (English)
Boosting is a powerful method that turns weak learners, which perform only slightly better than random guessing, into strong learners with high accuracy. While boosting is well understood in the classic setting, it is less so in the agnostic case, where no assumptions are made about the data. Indeed, only recently was the sample complexity of agnostic boosting nearly settled arXiv:2503.09384, but the known algorithm achieving this bound has exponential running time. In this work, we propose the first agnostic boosting algorithm with near-optimal sample complexity, running in time polynomial in the sample size when considering the other parameters of the problem fixed.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。