Relatively Smart II: Tractable or Semi-Supervised Instance-Optimal Learning
Updated 31 min ago · first seen 11 Sept 2026
paper_01M294FNW0VN99KS55SSQY6DVJ
- Published
- 11 Sept 2026
- T1 · 31 min ago
- arXiv
- 2609.10886
- T1 · 31 min ago
- Category
- cs.LG
- T1 · 31 min ago
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(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.
Authors 2
Shaddin Dughmi, Alireza F. Pour
Specification
- Official page
Source:arXiv (Atom API + RSS)T1observed 31 min agohigh
- Arxiv announce type
- new
Source:arXiv (Atom API + RSS)T1observed 31 min agohigh
- arXiv id
- 2609.10886
Source:arXiv (Atom API + RSS)T1observed 31 min agohigh
- Categories
- cs.LG, stat.ML
Source:arXiv (Atom API + RSS)T1observed 31 min agohigh
Source:arXiv (Atom API + RSS)T1observed 31 min agohigh
- Primary category
- cs.LG
Source:arXiv (Atom API + RSS)T1observed 31 min agohigh
- Published
- 11 Sept 2026
Source:arXiv (Atom API + RSS)T1observed 31 min agohigh
Each value shows its source, tier and observation time. Conflicting claims are kept side by side and flagged — never averaged. How AI Atlas records facts →
Provenance
Attributed facts
9
Source tiers
T19
Freshest observation
31 min ago
Conflicts
None
No models linked to this paper yet.
- Authors
- Shaddin Dughmi, Alireza F. Pour
As of
Rewind the record: see this entity's attributes exactly as AI Atlas knew them on a given day.
Claim history · Authors
Claims are temporal and append-only: a new observation closes the previous claim (valid_to) instead of overwriting it. Conflicting claims from different sources are kept side by side and flagged — never averaged. Methodology →
New paper: Relatively Smart II: Tractable or Semi-Supervised Instance-Optimal Learning
arxiv
| Source | Document | Type | Tier | Last observed | Snapshots |
|---|---|---|---|---|---|
| arXiv (Atom API + RSS) | rss.arxiv.org/rss/cs.LG | feed | T1· Official | 31 min ago | 1 |
Tier 1 = official/primary, 2 = quality secondary, 3 = community, 4 = unverified. Every snapshot is archived; see all sources and the methodology.