Metraipolis › archive › dc_f33f95c41fcd

Agnostic Learning by Imitating — arXiv:2611.05346

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.05346
License (as archived)
CC0-1.0
Archived
2026-11-04T18:55:36.468Z
SHA-256 of the archived text
2e42bc618fafd5d4a4646f389be5b8b8be925bc375c02127344b75688655f5ff
Stable URL of this page
https://metraipolis.com/documento/dc_f33f95c41fcd

How to cite

Agnostic Learning by Imitating — arXiv:2611.05346 — arXiv (en), https://arxiv.org/abs/2611.05346 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f33f95c41fcd (Metraipolis archive dc_f33f95c41fcd, sha256 2e42bc618fafd5d4a4646f389be5b8b8be925bc375c02127344b75688655f5ff)
BibTeX
@misc{dcf33f95c41fcd,
  title = {Agnostic Learning by Imitating — arXiv:2611.05346},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.05346},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f33f95c41fcd; sha256 2e42bc618fafd5d4a4646f389be5b8b8be925bc375c02127344b75688655f5ff},
  year = {2026}
}

Archived text

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

Given a class of machine learning models and sample access to a data distribution with binary labels, which computational task is harder: training a discriminative model that distinguishes positive and negative labels as well as the best member of the class, or training a generative model whose outputs are indistinguishable from real data by all members of the class? We prove that these two fundamental tasks in computational learning theory are not just closely related, but actually equivalent to each other in complexity. One direction of this equivalence was previously known. Indeed, the powerful regularity lemma in complexity theory gives an efficient oracle reduction from the indistinguishability task (a.k.a. multiaccuracy) to the distinguishing task (a.k.a. agnostic learning) in the style of boosting algorithms. Our main contribution is an efficient oracle reduction in the other direction. Taking this idea further, we show that a multiaccuracy oracle is a remarkably powerful primitive, achieving not just agnostic learning but also a wide range of seemingly more demanding learning objectives via similarly efficient and direct constructions. Our results crucially use the power of making adaptive queries to the oracle, and stand in stark contrast to prior work, which showed that post-processing a single multiaccurate predictor is insufficient for even weak forms of learning. On a technical level, we draw a connection between our (offline) problem and a version of no-regret learning in the online setting, which allows us to use follow-the-leader type algorithms to modify the label distribution and aggregate the predictions of the multiaccuracy oracle.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG) ; Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.05346 — 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-04T18:35:37.498Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).