Metraipolis › archive › dc_ea4f6d49f33c

Marginal-Nonuniform Multiclass Learning — arXiv:2611.09543

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.09543
License (as archived)
CC0-1.0
Archived
2026-11-09T22:41:36.792Z
SHA-256 of the archived text
f158b9abb03fe833d3b922b23ab688bcf1a2d1fe721f832960e0f93b9b5b5660
Stable URL of this page
https://metraipolis.com/documento/dc_ea4f6d49f33c

How to cite

Marginal-Nonuniform Multiclass Learning — arXiv:2611.09543 — arXiv (en), https://arxiv.org/abs/2611.09543 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ea4f6d49f33c (Metraipolis archive dc_ea4f6d49f33c, sha256 f158b9abb03fe833d3b922b23ab688bcf1a2d1fe721f832960e0f93b9b5b5660)
BibTeX
@misc{dcea4f6d49f33c,
  title = {Marginal-Nonuniform Multiclass Learning — arXiv:2611.09543},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.09543},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ea4f6d49f33c; sha256 f158b9abb03fe833d3b922b23ab688bcf1a2d1fe721f832960e0f93b9b5b5660},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.09543. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study the problem of multiclass classification within the framework of marginal-nonuniform learning, where the constants in the learning rate may depend on the unknown marginal distribution generating the unlabeled data, but not on the target concept. This notion naturally lies between classical PAC learning, where the constants are independent of both the marginal distribution and the target concept, and more recent universal learning, where the constants may depend on both. We give a complete characterization of the optimal marginal-nonuniform learning rates, establishing a fundamental trichotomy: exponential, linear, and arbitrarily slow rates. This characterization is witnessed by a new combinatorial dimension, termed the uncentered DS-eluder dimension. A key ingredient in the upper-bound proofs is a set of new distributional exhaustion lemmas that exploit the sequential nature of this dimension and may be of independent interest.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG) ; Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2611.09543 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-09T22:33:47.160Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).