We give a computationally-efficient PAC active learning algorithm for $d$-dimensional homogeneous halfspaces that can tolerate Massart noise (Massart and N\'ed\'elec, 2006) and Tsybakov noise (Tsybakov, 2004). Specialized to the $\eta$-Massart noise setting, our algorithm achieves an information-theoretically near-optimal label complexity of $\tilde{O}\left( \frac{d}{(1-2\eta)^2} \mathrm{polylog}(\frac1\epsilon) \right)$ under a wide range of unlabeled data distributions (specifically, the family of "structured distributions" defined in Diakonikolas et al. (2020)). Under the more challenging Tsybakov noise condition, we identify two subfamilies of noise conditions, under which our efficient algorithm provides label complexity guarantees strictly lower than passive learning algorithms.


翻译:我们给出了一个计算高效的PAC主动学习算法,用于能容忍Massart噪音(Massart和N\'ed\'elec,2006年)和Tsybakov噪音(Tsybakov,2004年)的元美元-马萨特噪音设置,我们的算法在极具挑战性的Tsybakov噪音条件下,实现了“$tilde{O ⁇ left”(\\frac{d{d{(1-2\beta)}}\mathrm{polylog}(\frac1\epsilon)\right)的信息-理论上接近最佳标签的复杂性。 在这种条件下,我们的高效算法提供标签复杂性保证的严格低于被动学习算法。

0
下载
关闭预览

相关内容

【干货书】真实机器学习,264页pdf,Real-World Machine Learning
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
浅谈主动学习(Active Learning)
凡人机器学习
31+阅读 · 2020年6月18日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
已删除
将门创投
4+阅读 · 2019年4月1日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年10月6日
Optimization for deep learning: theory and algorithms
Arxiv
104+阅读 · 2019年12月19日
Arxiv
13+阅读 · 2019年1月26日
Arxiv
5+阅读 · 2017年12月14日
Arxiv
3+阅读 · 2016年2月24日
VIP会员
相关资讯
浅谈主动学习(Active Learning)
凡人机器学习
31+阅读 · 2020年6月18日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
已删除
将门创投
4+阅读 · 2019年4月1日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员