arXiv：cs.LG· Shaddin Dughmi, Alireza F. Pour·· 7 小时前
相对智能学习 II：可处理或半监督的实例最优学习
Relatively Smart II: Tractable or Semi-Supervised Instance-Optimal Learning
AI 导读
研究表明，ERM 及任何恰当一致学习器在二分类无分布假设下均具备相对智能性质：m 个样本下的小可认证误差意味着在 O(m²) 随机样本均匀分布上误差同样小。半监督相对智能学习在信息论上可实现，仅未标注样本复杂度有二次膨胀，而标注样本复杂度无膨胀。但若仅通过 agnostic ERM oracle 访问假设类，要实现显著亚二次标注样本膨胀需超多项式次 oracle 调用。
正文
Abstract:We continue the study of relatively smart learning, introduced by Dughmi and Pour (2026), which asks a supervised learner to compete, marginal by marginal, with every distribution-fixed error guarantee soundly certifiable from unlabeled data. They showed that the One-Inclusion Graph (OIG) learner is relatively smart with a quadratic sample-complexity blowup, and that no relatively smart learner can do better, leaving open whether ERM or another natural or tractable learner achieves comparable guarantees. They also left open whether the blowup can be restricted to unlabeled data.
Our firs results shows that ERM---and in fact any proper consistent learner---is relatively smart for binary classification in the distribution-free setting. We show that a small certifiable error with $m$ samples implies a similarly small error on the uniform distribution over a random sample of size $O(m^2)$, yielding a cover of size at most $2^{m+1}$ on that sample. This suffices to control the error of proper consistent learners with $O(m^2)$ samples.
We then show that semi-supervised relatively smart learning is information-theoretically possible with a quadratic blowup only in unlabeled sample complexity and no blowup in labeled sample complexity. The learner uses a natural generalization of OIG to a leave-most-out transductive problem, where labels of part of a finite pool are revealed and the remaining labels are predicted.
Finally, this label efficiency comes at a cost in simplicity and tractability. If the hypothesis class is accessed only through an agnostic ERM oracle, any semi-supervised relatively smart learner with substantially sub-quadratic labeled-sample blowup requires super-polynomially many oracle calls. This holds even when the marginal is given explicitly, and thus also yields an intractability result for distribution-fixed learning that may be of independent interest.
| Subjects: | Machine Learning (cs.LG); Machine Learning (stat.ML) |
| Cite as: | arXiv:2609.10886 [cs.LG] |
| (or arXiv:2609.10886v2 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2609.10886 arXiv-issued DOI via DataCite |
Submission history
From: Alireza F. Pour [view email]
[v1]
Wed, 9 Sep 2026 22:45:18 UTC (113 KB)
[v2]
Wed, 14 Oct 2026 03:51:27 UTC (114 KB)
来源：arXiv：cs.LG · arxiv.org