Agnostic multiclass transductive learning versus PAC learning

For every multiclass hypothesis class $\mathcal H$ with arbitrary label space, determine the minimax agnostic transductive excess error from a population of size $n$ in terms of the complexity of $\mathcal H$ , and determine whether it has the same rate, up to logarithmic factors, as agnostic multiclass PAC learning. In particular, the claimed rate is $\widetilde\Theta\!\left(\frac{d_{\mathrm{DS}}(\mathcal H)}{n}+\sqrt{\frac{d_{\mathrm N}(\mathcal H)}{n}}\right)$ , where $d_{\mathrm{DS}}(\mathcal H)$ is the DS dimension and $d_{\mathrm N}(\mathcal H)$ is the Natarajan dimension.

References

Primary source

arXiv

Additional references

Two Dimensions Govern Agnostic Multiclass Transductive Learning — arXiv

empirical-processes statistical-learning-theory transductive-learning

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed progress

A new unrefereed paper claims a sharp two-part learning-rate law, but the broader multiclass comparison with PAC learning remains unsettled.

The problem asks how agnostic multiclass transductive learning compares with agnostic PAC learning, and which complexity measures control its sample requirements. Earlier work establishes one-way reduction and settles equivalence only in the binary case.

Known results

Agnostic PAC learning reduces to transductive learning for bounded losses, including multiclass classification (Dughmi, Kalayci, and York, 2025).
The converse reduction is proved for agnostic binary classification, but not multiclass classification (Dughmi, Kalayci, and York, 2025).
A 2024 preprint gives the reduction with an additive lower-order sample-complexity term and says broader agnostic equivalence remains open.

August 26, 2026 claimed two-dimension law

A newly reported arXiv paper claims a multiclass transductive minimax rate, up to logarithmic factors, of approximately $d_{\mathrm{DS}}/n+\sqrt{d_{\mathrm{N}}/n}$ , with both terms necessary. This is a substantive claimed advance, but the result is unrefereed and the supplied evidence does not verify it.

Current status (as of August 2026): One-way PAC-to-transductive reduction is established and binary equivalence is known; the multiclass equivalence question remains open, alongside an unverified claim of the stated two-dimension minimax rate.

Sources

No solutions have been posted yet.