We study the problem of online multiclass classification in a setting where the learner’s feedback is determined by an arbitrary directed graph. While including bandit feedback as a special case, feedback graphs allow a much richer set of applications, including filtering and label efficient classification. We introduce GAPPLETRON, the first online multiclass algorithm that works with arbitrary feedback graphs. For this new algorithm, we prove surrogate regret bounds that hold, both in expectation and with high probability, for a large class of surrogate losses. Our bounds are of order B√ρKT, where B is the diameter of the prediction space, K is the number of classes, T is the time horizon, and ρ is the domination number (a graph-theoretic parameter affecting the amount of exploration). In the full information case, we show that GAPPLETRON achieves a constant surrogate regret of order B2K. We also prove a general lower bound of order max {B2K, √T } showing that our upper bounds are not significantly improvable. Experiments on synthetic data show that for various feedback graphs our algorithm is competitive against known baselines.

Beyond Bandit Feedback in Online Multiclass Classification / van der Hoeven, D.; Fusco, F.; Cesa-Bianchi, N.. - 16:(2021), pp. 13280-13291. (Intervento presentato al convegno Advances in Neural Information Processing Systems (was NIPS) tenutosi a Virtual; Online).

Beyond Bandit Feedback in Online Multiclass Classification

Fusco F.
Secondo
;
2021

Abstract

We study the problem of online multiclass classification in a setting where the learner’s feedback is determined by an arbitrary directed graph. While including bandit feedback as a special case, feedback graphs allow a much richer set of applications, including filtering and label efficient classification. We introduce GAPPLETRON, the first online multiclass algorithm that works with arbitrary feedback graphs. For this new algorithm, we prove surrogate regret bounds that hold, both in expectation and with high probability, for a large class of surrogate losses. Our bounds are of order B√ρKT, where B is the diameter of the prediction space, K is the number of classes, T is the time horizon, and ρ is the domination number (a graph-theoretic parameter affecting the amount of exploration). In the full information case, we show that GAPPLETRON achieves a constant surrogate regret of order B2K. We also prove a general lower bound of order max {B2K, √T } showing that our upper bounds are not significantly improvable. Experiments on synthetic data show that for various feedback graphs our algorithm is competitive against known baselines.
2021
Advances in Neural Information Processing Systems (was NIPS)
multi-armed bandits; feedback graph; online learning
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Beyond Bandit Feedback in Online Multiclass Classification / van der Hoeven, D.; Fusco, F.; Cesa-Bianchi, N.. - 16:(2021), pp. 13280-13291. (Intervento presentato al convegno Advances in Neural Information Processing Systems (was NIPS) tenutosi a Virtual; Online).
File allegati a questo prodotto
File Dimensione Formato  
VanDerHoeven_preprint_Beyond_2021.pdf

accesso aperto

Note: https://proceedings.neurips.cc/paper_files/paper/2021/file/6e79ed05baec2754e25b4eac73a332d2-Paper.pdf
Tipologia: Documento in Pre-print (manoscritto inviato all'editore, precedente alla peer review)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 794.33 kB
Formato Adobe PDF
794.33 kB Adobe PDF
VanDerHoeven_Beyond_2021.pdf

accesso aperto

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 151.29 kB
Formato Adobe PDF
151.29 kB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1649672
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 1
social impact