Metraipolis › archive › dc_f4450d3928db

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

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.10886
License (as archived)
CC0-1.0
Archived
2026-10-16T05:54:50.374Z
SHA-256 of the archived text
d9bdd4337621d09f26ef50b51e954e39c85591460350bd953d7969ab0779d868
Stable URL of this page
https://metraipolis.com/documento/dc_f4450d3928db

How to cite

Relatively Smart II: Tractable or Semi-Supervised Instance-Optimal Learning — arXiv:2609.10886 — arXiv (en), https://arxiv.org/abs/2609.10886 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f4450d3928db (Metraipolis archive dc_f4450d3928db, sha256 d9bdd4337621d09f26ef50b51e954e39c85591460350bd953d7969ab0779d868)
BibTeX
@misc{dcf4450d3928db,
  title = {Relatively Smart II: Tractable or Semi-Supervised Instance-Optimal Learning — arXiv:2609.10886},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.10886},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f4450d3928db; sha256 d9bdd4337621d09f26ef50b51e954e39c85591460350bd953d7969ab0779d868},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.10886. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-11 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG) ; Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2609.10886 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T05:44:24.958Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).