Relatively Smart II: Tractable or Semi-Supervised Instance-Optimal Learning Relatively Smart II: Tractable or Semi-Supervised Instance-Optimal Learning

TL;DR

• ERM and any proper consistent learner is relatively smart for binary classification in the distribution-free setting, resolving an open question from the prior work
• A small certifiable error with m samples implies 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)
• Semi-supervised relatively smart learning is information-theoretically possible with quadratic blowup only in unlabeled sample complexity and no blowup in labeled sample complexity
• The semi-supervised 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
• Substantial label efficiency comes at a tractability cost: any semi-supervised relatively smart learner with sub-quadratic labeled-sample blowup requires super-polynomially many ERM oracle calls

Why It Matters

This work advances the theoretical foundations of instance-optimal learning by showing that widely-used empirical risk minimization naturally satisfies the relatively smart property, bridging the gap between practical algorithms and theoretical guarantees. It also establishes that semi-supervised learning can achieve optimal label efficiency without sacrificing unlabeled sample complexity, while revealing fundamental computational trade-offs that constrain what is achievable in practice.

Technical Details

• The paper extends the framework of relatively smart learning introduced by Dughmi and Pour (2026), which requires a supervised learner to compete marginal-by-marginal with every distribution-fixed error guarantee that is soundly certifiable from unlabeled data
• For binary classification, the authors prove that ERM and any proper consistent learner achieves relative smartness with O(m^2) sample complexity, using a covering argument that bounds the hypothesis class cover size at 2^(m+1) on a random sample
• The semi-supervised extension generalizes the One-Inclusion Graph learner to a leave-most-out transductive setting, where partial labels from a finite pool are revealed and the remaining labels are predicted, achieving quadratic blowup only in unlabeled samples
• An intractability result shows that when the hypothesis class is accessed via an agnostic ERM oracle, any semi-supervised relatively smart learner with substantially sub-quadratic labeled-sample blowup requires super-polynomially many oracle calls, even when the marginal distribution is given explicitly
• The results apply in the distribution-free setting and yield an independent intractability result for distribution-fixed learning

Industry Insight

• Theoretical guarantees for ERM are strengthened: practitioners can rely on this widely-used algorithm satisfying instance-optimal properties without modification, reducing the need for specialized learners in distribution-free binary classification
• Semi-supervised learning frameworks can theoretically achieve optimal label efficiency, but the super-polynomial oracle complexity suggests that practical implementations will need to balance label savings against computational feasibility
• The tractability-bound results highlight a fundamental tension between sample efficiency and computational efficiency in instance-optimal learning, guiding future research toward approximations or restricted hypothesis classes where both goals can be simultaneously achieved

TL;DR

• 证明ERM（经验风险最小化）及任何正确一致学习器在分布自由设置下对二分类是相对智能的
• 半监督相对智能学习在信息论上可行，仅需在未标记样本复杂度上有二次增长，标记样本复杂度无增长
• 学习器通过OIG（One-Inclusion Graph）的留一法归纳推广实现，部分标签揭示后预测剩余标签
• 标签效率的提升以计算复杂性为代价：若仅通过agnostic ERM oracle访问假设类，任何半监督相对智能学习器需超多项式次oracle调用
• 该结果同时给出了分布固定学习中的不可处理性结论

为什么值得看

本文解决了相对智能学习理论中的关键开放问题，证明标准ERM算法在理论框架下具有更强的保证，同时揭示了半监督学习中标签效率与计算复杂性之间的根本权衡。

技术解析

ERM在分布自由设置下对二分类是相对智能的。证明核心：小可验证错误（m样本）意味着在大小为O(m²)的随机样本均匀分布上同样保持低错误，产生至多2^(m+1)的覆盖数，足以控制正确一致学习器的误差。

半监督相对智能学习通过OIG到留一法归纳问题的自然推广实现：在有限池子中部分标签揭示后预测剩余标签。信息论上可行，仅需未标记样本复杂度二次增长，标记样本复杂度无增长。

计算代价：若假设类仅通过agnostic ERM oracle访问，任何半监督相对智能学习器若要有显著亚二次标记样本增长，需超多项式次oracle调用。即使边际分布显式给出也成立。

行业启示

ERM作为标准学习算法在相对智能学习框架下具有理论保证，为实际应用提供了更强的理论支撑。

半监督学习在标签效率上存在理论上限：无标记样本的二次增长代价不可避免，但标记样本可完全节省。

计算复杂性与样本效率存在根本权衡：追求更优的样本效率需付出超多项式计算代价，实践中需根据场景权衡。