PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Shaddin Dughmi, Alireza F. Pour

arXiv:2609.10886v1cs.LGstat.ML

TL;DR

The paper asks whether relatively smart learning can be achieved by standard learners and with quadratic overhead confined to unlabeled data. It proves positive results for ERM and semi-supervised learning, while showing that substantially subquadratic labeled overhead is intractable in a natural oracle model.

  • Problem

    Prior work established quadratic relatively smart learning via OIG but left open whether ERM could match it and whether unlabeled data alone could absorb the blowup.

  • Method

    The paper analyzes proper consistent learners in binary distribution-free learning and semi-supervised learners using an OIG-based transductive approach, then studies tractability through agnostic ERM-oracle access.

  • Results

    ERM and every proper consistent learner are relatively smart with quadratic labeled-sample blowup; semi-supervised learning can avoid labeled blowup, but no efficient oracle learner achieves substantially subquadratic labeled overhead.

  • Takeaways & Limitations

    Relatively smart learning is information-theoretically achievable with label efficiency, but exploiting that advantage can require substantially more complex learning procedures.

  • Takeaways & Limitations

    The tractability impossibility concerns semi-supervised learners whose only access to the hypothesis class is through agnostic ERM-oracle calls, although it holds even with full marginal knowledge.

Abstract

from arXiv · show

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.

1 Introduction

The paper studies whether relatively smart learning can be achieved by standard learners and whether unlabeled data can remove labeled-sample blowups tractably. It answers ERM and semi-supervised information-theoretic questions positively, but finds a strong oracle-based tractability barrier.

  • ERM is relatively smart.: ERM and every proper consistent learner are relatively smart in the distribution-free setting with a quadratic labeled-sample blowup.This resolves the corresponding open question about natural and typically tractable learners.
  • ERM is relatively smart.: Leave-one-out optimality is sufficient but not necessary for relatively smart learning.ERM lacks OIG’s comparable transductive optimality yet still achieves the relatively smart guarantee.
  • Semi-supervised learning: Semi-supervised relatively smart learning can use the same number of labeled samples and quadratically more unlabeled samples.Thus the entire sample-complexity blowup can be shifted to unlabeled data.
  • Semi-supervised learning: The semi-supervised learner has a leave-most-out transductive interpretation using a natural generalization of the One-Inclusion Graph.A subset of a finite pool is labeled, and the learner predicts the remaining labels.
  • Tractability: No efficient oracle learner achieves substantially subquadratic labeled-sample blowup, even when the marginal distribution is given explicitly.This also creates a tractability barrier for distribution-fixed learning.

2 Preliminaries

The paper formalizes binary PAC learning, distribution-dependent error, sound certification, and relative smartness. It focuses on arbitrary marginals under standard measurability assumptions.

  • Setting: Binary PAC learning uses a marginal D over inputs and a target hypothesis h∈H to induce labeled data distribution D_h.Learner error is measured as expected classification loss under D_h.
  • Error rates: A distribution-dependent error rate assigns an error value to each marginal D and sample size m.For a learner, the rate is the worst-case expected error over target hypotheses.
  • Certification: A sound certifier is an unlabeled-data function whose expected value upper-bounds a learner’s distribution-dependent error rate.Soundness must hold for every marginal, sample size, and sampled unlabeled dataset.
  • Certification: A certifiable error rate is witnessed, for every marginal, by a marginal-specific learner and a sound certifier whose expected value is no larger than that rate.This defines the benchmark that relatively smart learners must compete with.
  • Relative smartness: A learner is relatively smart when it competes with every certifiable distribution-dependent error rate, up to a constant and sample-complexity transformation.The definition quantifies over all certifiable rates, marginals, sample sizes, and additive error parameters.
  • Scope: The positive results allow general domains, classes, and distributions satisfying standard measurability assumptions, while negative results use countable domains.The paper does not detail the measure-theoretic conditions.

3 ERM is relatively smart

Every proper consistent learner, including ERM, is relatively smart in the distribution-free setting with a quadratic sample-complexity blowup. The proof converts certifiable error into a small sample-dependent cover, then uses double sampling to control consistent learners’ population error.

  • Every proper consistent learner is relatively smart in the distribution-free setting with O(m^2) samples.This gives a positive resolution of the open question concerning ERM.
  • A certifiable error rate at sample size m implies that a tailored learner has error O(ϵ) on the uniform distribution over a random sample of size O(m^2).The argument uses indistinguishability between samples drawn from the marginal and subsamples drawn from the larger random multiset.
  • Small error on that uniform distribution bounds the 4γ-packing number and yields a cover of H with size roughly 2^m and radius O(ϵ).At most 2^m labelings can occur on a typical m-instance sample, limiting the number of well-separated hypotheses.
  • A double-sampling argument transfers the cover guarantee to proper consistent learners trained on M/2 = O(m^2) labeled examples.Consistency gives zero error on one half of the sample, while concentration transfers comparable error to the other half and hence to the marginal.
  • The packing lower-bound argument shows that if pack_γ(H,Q) is at least 2^m+1, every learner has expected error at least γ/4 on one target.This connects bounded learner error under Q to a bound on the hypothesis class’s packing number.

4 Relatively Smart Semi-Supervised Learners

The paper shows that semi-supervised relatively smart learning can preserve the original labeled sample size while using a quadratic number of unlabeled samples. It also gives an inclusion-graph implementation with the same sample-complexity guarantee.

  • 4 Relatively Smart Semi-Supervised Learners: The construction answers whether unlabeled data can absorb the quadratic sample-complexity blow-up while retaining the original number of labels.The earlier fully supervised bound is quadratic, whereas the semi-supervised construction places that blow-up in unlabeled samples.
  • 4 Relatively Smart Semi-Supervised Learners: Semi-supervised relative smartness is defined by comparing a learner’s distribution-dependent error with every certifiable error rate after separate unlabeled and labeled sample transformations.The definition quantifies over certifiable rates, marginals, sample sizes, and additive error parameters.
  • 4.1 A Relatively Smart Semi-Supervised Learner with No Blow-Up in Labeled Sample Complexity: O(m^2) unlabeled samples and m labeled samples suffice for a semi-supervised relatively smart learner.The learner achieves σu(m, η) = Oη(m^2) and σℓ(m, η) = m.
  • 4.1 A Relatively Smart Semi-Supervised Learner with No Blow-Up in Labeled Sample Complexity: The learner uses unlabeled data to construct an optimal learner for the uniform distribution over a finite sample and then predicts with it.Algorithm 1 receives unlabeled data U, labeled data S, and a test point, constructs an optimal learner over T, and returns its prediction.
  • 4.2 An Inclusion Graph Relatively (1, O(m^2/η), m)-Smart Learner: A natural inclusion-graph generalization of OIG achieves relative (1, O(m^2/η), m)-smartness.It solves a leave-most-out transductive problem on the union of unlabeled, labeled, and test points.

5 An Impossibility Result for Tractable Semi-Supervised Learners

The paper proves that the label-efficient semi-supervised guarantee is not generally tractable through agnostic ERM oracle access. Any learner using only polynomially many oracle calls requires substantially more than quadratic labeled-sample efficiency, even when the marginal is known.

  • 5 An Impossibility Result for Tractable Semi-Supervised Learners: The positive semi-supervised result therefore comes with a tractability cost: it uses O(m^2) unlabeled samples and m labels but lacks a general efficient implementation.The impossibility applies to learners restricted to polynomially many oracle calls.
  • 5 An Impossibility Result for Tractable Semi-Supervised Learners: Tractability is formalized by allowing the learner to access the hypothesis class only through an agnostic ERM oracle.An efficient oracle learner is required to make a number of calls bounded by a polynomial in m.
  • 5 An Impossibility Result for Tractable Semi-Supervised Learners: No efficient oracle learner achieves substantially subquadratic labeled-sample complexity for relative smartness, even with the marginal distribution given.For σℓ(m, η) = Oη(m^(2−β)), no learner making polynomially many agnostic ERM oracle calls works for every hypothesis class.
  • 5 An Impossibility Result for Tractable Semi-Supervised Learners: The lower-bound construction augments lopsided hypothesis classes with random row labelings that the oracle reveals only with exponentially small probability.The proof uses agreement among lopsided hypotheses and an oracle tie-breaking rule that exposes little information about the hidden labeling.
  • 5.1 Formal Proof of Theorem 5.2: The certifiable benchmark is established using a uniformity tester that detects when the marginal is close to the relevant uniform row.The certifier is adapted from the modified uniformity tester MTestUnif.
  • 5.1 Formal Proof of Theorem 5.2: For sufficiently small labeled samples, the learner’s prediction remains nearly independent of unseen random labels, yielding error close to 1/2 despite a certifiable error of O(n^-β).The construction gives error at least 1/2 − 2n^-β while the certifiable rate is O(n^-β), producing the contradiction to relative smartness.

6 AI Disclosure

The authors disclose that GPT-5.6 assisted with some proofs and limited writing, while the authors rederived, formalized, and wrote all proofs and retained responsibility for the paper.

  • 6 AI Disclosure: GPT-5.6 helped develop proof approaches for the ERM result and the tractability lower bound.The authors state that the contributions were rederived and formalized by the human authors.
  • 6 AI Disclosure: The semi-supervised definitions and positive result were developed without AI assistance.The disclosure specifically attributes those Section 4 contributions to the human authors.
  • 6 AI Disclosure: The authors state that all proofs were written by humans and that they take full responsibility for the content and proofs.AI was used only marginally to sharpen some writing for readability.

A Missing Proof from Section 3: Proof of Lemma 3.4

The appendix supplies a missing proof based on relating a bad consistent hypothesis to a random split of two independent samples. A packing-cover argument and a hypergeometric concentration bound control the resulting event.

  • A Missing Proof from Section 3: Proof of Lemma 3.4: The proof reduces the event of a consistent hypothesis with large distributional error to an event where it makes many errors on an independent test sample.For a fixed bad hypothesis, a probability lower bound yields the reduction between the events.
  • A Missing Proof from Section 3: Proof of Lemma 3.4: A maximal packing of the hypothesis class on the combined sample also serves as a cover, allowing the argument to union-bound over finitely many representatives.The packing is taken under the disagreement metric induced by the combined sample.
  • A Missing Proof from Section 3: Proof of Lemma 3.4: After randomly splitting the combined sample, the number of errors in one half is hypergeometric with mean at least 3nγ/16.A Chernoff bound then controls the probability that the split produces the required imbalance.

B Missing Proofs from Section 5

The modified uniformity tester wraps a standard uniformity test to reject samples leaving the target row. Its guarantees distinguish exact uniformity from distributions separated in total variation.

  • Modified uniformity tester: MTestUnifY accepts the uniform distribution on Y with probability at least 1 − δ.The sample size must satisfy m ≥ mTest(n, ξ/2, δ).
  • Modified uniformity tester: MTestUnifY rejects any distribution more than ξ away from uniformity on Y in total variation with probability at least 1 − δ.This includes distributions whose support is not confined to the desired row, because the wrapper returns 0 when samples leave Y.
  • Algorithm: TestUnifY partitions the sample into ℓ = 18 ln(2/δ) consecutive sub-samples and uses a threshold tr = 1 + 2ξ^2n.The modified tester inherits this standard uniformity-testing procedure after its support check.
  • Algorithm: The tester first checks whether every sample lies in Y, then invokes TestUnifY with parameter ξ/2 when that condition holds.Otherwise, it immediately returns 0.

B.1 Proof of Lemma 5.3

The proof establishes certifier soundness by splitting distributions into three cases relative to the reference distribution D(n). In each case, the learner’s error is bounded by the certifier’s expected error guarantee.

  • Case analysis: The certifier’s error is at most 6ξ(n) when D = D(n), while the learner’s error is at most 4ξ(n).The argument uses the uniformity tester’s acceptance guarantee and consistency with the empirical sample.
  • Case analysis: For D = D(n), one candidate among fn,gn,h1,h0 has error at most ξ(n), enabling the empirical-risk minimizer to achieve at most 3ξ(n).The candidate depends on whether the target labeling belongs to H(n,G).
  • Case analysis: When dTV(D, D(n)) ≤ ξ(n), the learner’s error is at most 4ξ(n), and the certifier bounds it by 5ξ(n).The proof handles separately whether the target labeling equals fn,gn and whether it belongs to H(n).
  • Case analysis: When dTV(D, D(n)) > ξ(n), the tester rejects with probability at least 1 − ξ(n), so the certifier’s expected value is at least 1 − ξ(n).A majority-label hypothesis still gives a comparator with error at most 1/2, and the proof invokes 1/2 + 3ξ(n) ≤ 1 − ξ(n) for large n.

B.2 Proof of Lemma 5.4

The proof bounds the diameter of a family of unseen labelings by constructing two hypotheses that would violate the class constraints if the diameter were too large. A Boolean-cube diameter lemma then controls the family’s size.

  • Diameter bound: Lemma B.3 bounds a subset of {0,1}^d whose diameter is at most d − r − 1.The proof invokes this result with d = n − s and r = M(n) − s.
  • Setup: For any labeling a on S0 with |S0| = s < M(n), the resulting family is analyzed over every finite labeled multiset T.The construction exploits that fn,gn and every h in H(n) agree outside Xn.
  • Conditioning: The proof conditions on the labels over S0, leaving the restriction on V = Xn \ S0 uniformly random over {0,1}^V.This isolates the unseen-label randomness used in the counting argument.
  • Diameter bound: The family of feasible restrictions has diameter less than n − M(n).Assuming a larger diameter produces two labelings whose extensions define h0 and h1 in H(n), contradicting the construction.

B.3 Proof of Lemma 5.5

The proof bounds the probability that the oracle returns fn,gn by conditioning on the first oracle call that returns it. Before that call, the learner’s query is fixed independently of the unseen labels.

  • Oracle-call analysis: The event that OH(G) returns fn,gn is decomposed according to the first oracle call at which the return occurs.This converts the adaptive interaction into a sum over round-specific events.
  • Oracle-call analysis: Lemma 5.4 bounds the probability that any fixed query causes the oracle to return fn,gn.The proof applies this bound separately to each possible first-return round.
  • Oracle-call analysis: Before fn,gn is first returned, each oracle query is fixed with respect to the remaining unseen labels of gn.Conditioning on the labeled sample, test point, and learner randomness makes the query at round t deterministic relative to those labels.
  • Conclusion: The proof concludes after applying the resulting probability bound for sufficiently large n.The final step uses an exponential bound in n.

B.4 Proof of Lemma 5.6

The proof fixes the labeled sample and analyzes the learner on a randomly labeled finite domain. It shows that, unless a particular oracle event occurs, predictions on unseen points are independent of the unseen labels and therefore incur expected error one-half.

  • Proof setup: Fixing the labeled sample, its distinct-point support S0 has size s≤m, while the target labeling on S0 is fixed.The proof also fixes a test point and the learner’s internal randomness.
  • Proof setup: Conditioned on the observed labels, the target labeling outside S0 is uniform, so the learner’s oracle-independent prediction has expected error 1/2 on every unseen point.This holds whenever the oracle interaction does not return the target function.
  • Error bound: Because the domain distribution is uniform, an independently drawn test point lies outside S0 with probability 1−s/n, which is at least 1−m/n.The proof combines this unseen-point probability with a bound on the exceptional oracle event E.
  • Conclusion: Averaging over the labeled sample and learner randomness, then over target labelings, yields the claimed lower bound on the learner’s expected error.For each fixed target labeling, the target function belongs to the hypothesis class, so the learner’s distribution-fixed error is at least its expected error on that target.
Loading 2609.10886v1…