Relatively Smart II: Tractable or Semi-Supervised Instance-Optimal Learning
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(m2), yielding a cover of size at most 2m+1 on that sample. This suffices to control the error of proper consistent learners with O(m2) 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.
Related
- Is Spectral Self-Supervised Learning a Minimax Optimal Method of Density Ratio Estimation?
- Self-Supervised In-Context Operator Learning for Optimal Mixing in Incompressible Flows
- Tractable Relaxations of Multivariate Stochastic Dominance via Optimal Transport and CVaR
- Halve-Then-Greedy: Adaptive Sampling for Posterior Success with Near-Optimal Instance Dependence
- Instance-Optimal Adaptive Location Estimation via Multiscale Mid-Summaries
BibTeX
@misc{dughmi2026relatively,
title = {{Relatively Smart II: Tractable or Semi-Supervised Instance-Optimal Learning}},
author = {Shaddin Dughmi and Alireza F. Pour},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.10886},
eprint = {2609.10886},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.10886},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Relatively Smart II: Tractable or Semi-Supervised Instance-Optimal Learning
AU - Shaddin Dughmi
AU - Alireza F. Pour
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2609.10886
UR - https://arxiv.org/abs/2609.10886
AB - 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.
ER -