Cooperative Online Learning: Keeping your Neighbors Updated

We introduce and analyze a cooperative online learning setting in which a network of agents solve a common online convex optimization problem by sharing feedback with their network neighbors. Agents do not have to be synchronized. At each time step, only some of the agents are requested to make a prediction and pay the corresponding loss: we call these agents "active". As the feedback (i.e., the current loss function) received by the active agents is communicated to their neighbors, both active agents and their neighbors can use the feedback to update their local models. Asynchronous online learning settings with communication constraints naturally arise in many applications. Forexample, large-scale learning systems are often geographically distributed, and in domains such as finance or online advertising, typically each agent must serve high volumes of prediction requests. If agents keep updating their local models in an online fashion, then bandwidth and computational constraints may force them to limit communication by sharing feedbacks only with their neighbors.