We study an asynchronous online learning setting with a network of agents. At each time step, some of the agents are activated, requested to make a prediction, and pay the corresponding loss. The loss function is then revealed to these agents and also to their neighbors in the network. Our results characterize how much knowing the network structure affects the regret as a function of the model of agent activations. When activations are stochastic, the optimal regret (up to constant factors) is shown to be of order $sqrtalpha T$, where $T$ is the horizon and $alpha$ is the independence number of the network. We prove that the upper bound is achieved even when agents have no information about the network structure. When activations are adversarial the situation changes dramatically: if agents ignore the network structure, a $Omega(T)$ lower bound on the regret can be proven, showing that learning is impossible. However, when agents can choose to ignore some of their neighbors based on the knowledge of the network structure, we prove a $O(sqrtoverlinechi T)$ sublinear regret bound, where $overlinechi ge alpha$ is the clique-covering number of the network.

Cooperative Online Learning: Keeping your Neighbors Updated / N. Cesa-Bianchi, T. Cesari, C. Monteleoni (PROCEEDINGS OF MACHINE LEARNING RESEARCH). - In: Algorithmic Learning Theory / [a cura di] A. Kontorovich, G. Neu. - [s.l] : PMLR, 2020. - pp. 234-250 (( Intervento presentato al 31. convegno International Conference on Algorithmic Learning Theory tenutosi a San Diego nel 2020.

Cooperative Online Learning: Keeping your Neighbors Updated

N. Cesa-Bianchi;T. Cesari;
2020

Abstract

We study an asynchronous online learning setting with a network of agents. At each time step, some of the agents are activated, requested to make a prediction, and pay the corresponding loss. The loss function is then revealed to these agents and also to their neighbors in the network. Our results characterize how much knowing the network structure affects the regret as a function of the model of agent activations. When activations are stochastic, the optimal regret (up to constant factors) is shown to be of order $sqrtalpha T$, where $T$ is the horizon and $alpha$ is the independence number of the network. We prove that the upper bound is achieved even when agents have no information about the network structure. When activations are adversarial the situation changes dramatically: if agents ignore the network structure, a $Omega(T)$ lower bound on the regret can be proven, showing that learning is impossible. However, when agents can choose to ignore some of their neighbors based on the knowledge of the network structure, we prove a $O(sqrtoverlinechi T)$ sublinear regret bound, where $overlinechi ge alpha$ is the clique-covering number of the network.
online mirror descent; regret minimization; multiagent learning
Settore INF/01 - Informatica
2020
http://proceedings.mlr.press/v117/cesa-bianchi20a.html
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
cesa-bianchi20a.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 332.3 kB
Formato Adobe PDF
332.3 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

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/2434/709099
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 9
social impact