Relatively Smart: A New Approach for Instance-Optimal Learning

Shaddin Dughmi, Alireza F. Pour
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2107-2144, 2026.

Abstract

We revisit the framework of \emph{Smart PAC learning}, which seeks supervised learners which compete with semi-supervised learners that are provided full knowledge of the \emph{marginal} distribution on unlabeled data. Prior work has shown that such marginal-by-marginal guarantees are possible for “most” marginals, with respect to an arbitrary fixed and known measure, but not more generally. We discover that this failure can be attributed to an “indistinguishability” phenomenon: There are marginals which cannot be statistically distinguished from other marginals that require different learning approaches. In such settings, semi-supervised learning cannot certify its guarantees from unlabeled data, rendering them arguably non-actionable. We propose \emph{relatively smart learning}, a new framework which demands that a supervised learner compete only with the best “certifiable” semi-supervised guarantee. We show that such modest relaxation suffices to bypass the impossibility results from prior work. In the distribution-free setting, we show that the One-Inclusion Graph learner is relatively smart up to squaring the sample complexity, and show that no supervised learning algorithm can do better. For distribution-family settings, we show that relatively smart learning can be impossible or can require idiosyncratic learning approaches, and its difficulty can be non-monotone in the inclusion order on distribution families.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-dughmi26a, title = {Relatively Smart: A New Approach for Instance-Optimal Learning}, author = {Dughmi, Shaddin and Pour, Alireza F.}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {2107--2144}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/dughmi26a/dughmi26a.pdf}, url = {https://proceedings.mlr.press/v336/dughmi26a.html}, abstract = {We revisit the framework of \emph{Smart PAC learning}, which seeks supervised learners which compete with semi-supervised learners that are provided full knowledge of the \emph{marginal} distribution on unlabeled data. Prior work has shown that such marginal-by-marginal guarantees are possible for “most” marginals, with respect to an arbitrary fixed and known measure, but not more generally. We discover that this failure can be attributed to an “indistinguishability” phenomenon: There are marginals which cannot be statistically distinguished from other marginals that require different learning approaches. In such settings, semi-supervised learning cannot certify its guarantees from unlabeled data, rendering them arguably non-actionable. We propose \emph{relatively smart learning}, a new framework which demands that a supervised learner compete only with the best “certifiable” semi-supervised guarantee. We show that such modest relaxation suffices to bypass the impossibility results from prior work. In the distribution-free setting, we show that the One-Inclusion Graph learner is relatively smart up to squaring the sample complexity, and show that no supervised learning algorithm can do better. For distribution-family settings, we show that relatively smart learning can be impossible or can require idiosyncratic learning approaches, and its difficulty can be non-monotone in the inclusion order on distribution families.} }
Endnote
%0 Conference Paper %T Relatively Smart: A New Approach for Instance-Optimal Learning %A Shaddin Dughmi %A Alireza F. Pour %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-dughmi26a %I PMLR %P 2107--2144 %U https://proceedings.mlr.press/v336/dughmi26a.html %V 336 %X We revisit the framework of \emph{Smart PAC learning}, which seeks supervised learners which compete with semi-supervised learners that are provided full knowledge of the \emph{marginal} distribution on unlabeled data. Prior work has shown that such marginal-by-marginal guarantees are possible for “most” marginals, with respect to an arbitrary fixed and known measure, but not more generally. We discover that this failure can be attributed to an “indistinguishability” phenomenon: There are marginals which cannot be statistically distinguished from other marginals that require different learning approaches. In such settings, semi-supervised learning cannot certify its guarantees from unlabeled data, rendering them arguably non-actionable. We propose \emph{relatively smart learning}, a new framework which demands that a supervised learner compete only with the best “certifiable” semi-supervised guarantee. We show that such modest relaxation suffices to bypass the impossibility results from prior work. In the distribution-free setting, we show that the One-Inclusion Graph learner is relatively smart up to squaring the sample complexity, and show that no supervised learning algorithm can do better. For distribution-family settings, we show that relatively smart learning can be impossible or can require idiosyncratic learning approaches, and its difficulty can be non-monotone in the inclusion order on distribution families.
APA
Dughmi, S. & Pour, A.F.. (2026). Relatively Smart: A New Approach for Instance-Optimal Learning. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:2107-2144 Available from https://proceedings.mlr.press/v336/dughmi26a.html.

Related Material