Relatively Smart II: Tractable or Semi-Supervised Instance-Optimal Learning
Shaddin Dughmi, Alireza F. Pour
cs.LG · stat.ML
Quick verdict
Resolves open questions of DP26: ERM is relatively smart, unlabeled data removes the labeled-sample blowup, but tractable oracle learners cannot; rigorous.
Summary
This follow-up to Dughmi and Pour's COLT 2026 'Relatively Smart' paper answers three open questions about learning benchmarks defined by error guarantees certifiable from unlabeled data. First, Theorem 3.1 proves that ERM — indeed any proper consistent learner — is relatively smart in the distribution-free setting, with a 128 error factor and quadratic sample blowup (n ≈ 256(m+1)²/η). The proof chain: sound certification with m samples bounds the D-fixed learner's error on uniform distributions over O(m²)-size random samples (Lemma 3.2, birthday paradox); small error there caps the γ-packing number at 2^(m+1) (Lemma 3.3); a double-sampling argument (Lemma 3.4) transfers the bound to consistent learners. Second, Theorem 4.3 introduces relatively smart semi-supervised learning and shows a learner that runs an optimal learner on the pooled sample achieves the certifiable rate with no labeled blowup (σℓ = m) and σu ≈ 2m(m+1)/η; Section 4.2 sketches an Inclusion-Graph generalization for leave-most-out transduction without a formal theorem. Third, Theorem 5.2 proves a tractability barrier: learners restricted to polynomially many agnostic-ERM oracle calls cannot achieve substantially subquadratic labeled blowup, via lopsided classes hiding a random hypothesis behind a tie-breaking oracle (Lemmas 5.4–5.6), even when the marginal is given explicitly. Limitations: Section 4.2 is informal, the impossibility is specific to the oracle model, and constants are large. Section 6 transparently discloses GPT-5.6 proof assistance, with flaws caught by the authors.
Review complete
Assessment at a glance
3
risk flags identified
● high 0
● medium 2
● low 1
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Every proper consistent learner, including ERM, is relatively (128, ≈256(m+1)²/η)-smart for binary classification in the distribution-free setting (Theorem 3.1), resolving Open Question 3.3 of Dughmi-Pour (2026).
- A semi-supervised learner that computes an optimal learner for the uniform distribution on the pooled sample is relatively (1, 2m(m+1)/η, m)-smart: no labeled-sample blowup at all (Theorem 4.3).
- A natural Inclusion-Graph generalization is optimal for the leave-most-out transductive problem and yields a relatively (1, O(m²/η), m)-smart learner (Section 4.2, stated informally).
- No oracle-efficient learner (polynomially many agnostic-ERM calls) can be relatively smart with labeled blowup σℓ = O(m^(2−β)) for any β > 0, even with the marginal given explicitly — implying a tractability barrier for distribution-fixed learning (Theorem 5.2).
Strengths
Resolves a named open problem with a more general answer than asked
Open Question 3.3 of Dughmi-Pour (DP26) asked whether ERM is relatively smart; Theorem 3.1 answers it for every proper consistent learner, with explicit constants (error factor 128; blowup n ≈ 256(m+1)²/η), using packing + double-sampling rather than OIG's transductive optimality — showing leave-one-out optimality is sufficient but not necessary.
Semi-supervised result in the strongest possible form
Theorem 4.3 (Algorithm 1) achieves multiplicative factor α = 1 (not just a constant like 128) with σℓ = m labeled samples independent of η and σu = 2m(m+1)/η unlabeled samples; the entire quadratic blowup shifts to unlabeled data, with the Γ_{M,m+1} birthday-paradox correction carefully tracked.
Nontrivial hardness construction that also bites in a stronger model
Exemplary AI-assistance disclosure
Complete appendix proofs with explicit constants
Weaknesses
Section 4.2 is informal and unproven as stated
The tractability barrier is narrower than the abstract's framing
Large, unoptimized constants in the positive result
Heavy dependence on DP26 machinery without restated proofs
Distribution-free scope for the ERM result
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
This sequel to Dughmi and Pour's 'Relatively Smart' (COLT 2026, [DP26]) targets three open questions about a benchmark where supervised learners compete, marginal by marginal, with error guarantees *soundly certifiable from unlabeled data*. DP26 showed the One-Inclusion-Graph (OIG) learner achieves this with a quadratic sample blowup and that no better blowup is possible fully supervised, but left open whether ERM suffices (Q1), whether the blowup can be moved to unlabeled data (Q2), and whether that move can be made tractable (Q3).
Answers: **Theorem 3.1** — every *proper consistent* learner (strictly broader than ERM) is relatively (128, ≈256(m+1)²/η)-smart, distribution-free. **Theorem 4.3** — a semi-supervised learner running an optimal learner for the uniform distribution on the pooled sample T = U ∪ dom(S) ∪ x is relatively (1, 2m(m+1)/η, m)-smart: α = 1 and σℓ = m, the strongest form imaginable. **Section 4.2** — an Inclusion-Graph learner for 'leave-most-out' transduction, relatively (1, O(m²/η), m), stated informally. **Theorem 5.2** — no learner restricted to polynomially many agnostic-ERM oracle calls achieves substantially subquadratic labeled blowup, even with the marginal given explicitly, implying a tractability barrier for distribution-fixed learning itself. Section 6 discloses GPT-5.6 assistance on Theorems 3.1 and 5.2.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 3 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What does 'relatively smart learning' mean?
Introduced by Dughmi and Pour (COLT 2026), it asks whether one supervised learner can, for every data distribution, nearly match (up to a constant error factor, using quadratically more samples) every error guarantee that can be soundly certified from unlabeled data — a benchmark sitting between worst-case PAC learning and instance-optimal distribution-fixed learning, where the learner knows the marginal exactly.
Is ERM instance-optimal according to this paper?
For the 'relatively smart' benchmark, yes with a catch: Theorem 3.1 shows ERM (or any proper consistent learner) matches every certifiable error rate given about 256(m+1)²/η samples instead of m, at a constant-factor (128) error loss. It does not achieve the certifiable rate with the original sample size, which is impossible in general.
Can unlabeled data remove the quadratic sample-complexity blowup?
Information-theoretically yes: Theorem 4.3 gives a semi-supervised learner using m labeled samples (no blowup) plus about 2m(m+1)/η unlabeled samples. However, it requires computing an optimal learner for the uniform distribution over the observed pool, and Theorem 5.2 shows learners limited to polynomially many agnostic-ERM oracle calls provably cannot exploit unlabeled data this way.
Did AI write this paper?
No. Section 6 discloses that GPT-5.6 helped find proofs of Theorems 3.1 and 5.2 and slightly polished prose. The authors report that several AI suggestions contained substantive flaws which they caught and corrected, that all proofs were rederived and written by humans, and that they take full responsibility for all content.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- PDF extraction garbles some inline math: Theorem 3.1's σ reads 'l 256(m+1)2 η m' and Section 5.1's final scaling reads 'M(n)/2 = ω(m(n))2−14β'; both were reconstructed from the cleanly extracted proofs, so the reviewed constants in those two spots are inferred rather than quoted verbatim.
- The provided text ends naturally after the Appendix B.4 proof with a page number; no truncation of body or appendices was detected.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.