arXiv stat.ML· Shaddin Dughmi, Alireza F. Pour·· 3 小时前AI 评分17
Relatively Smart II：可处理或半监督的实例最优学习
Relatively Smart II: Tractable or Semi-Supervised Instance-Optimal Learning
AI 导读
研究证明 ERM 及任何 proper consistent learner 在二分类分布无关设定下均具备 relatively smart 性质，用 O(m²) 样本即可控制误差。半监督场景下，仅无标签样本复杂度有二次膨胀，有标签样本复杂度无膨胀，但若仅通过 agnostic ERM oracle 访问假设类，实现亚二次有标签样本膨胀需超多项式次 oracle 调用。
来源：arXiv stat.ML · arxiv.org