Distributed Adaptive Learning Under Communication Constraints
Marco Carpentiero, Vincenzo Matta, Ali H. Sayed
Abstract
We consider a network of agents that must solve an online optimization problem from continual observation of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">streaming</i> data. To this end, the agents implement a distributed <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">cooperative</i> strategy where each agent is allowed to perform <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">local</i> exchange of information with its neighbors. In order to cope with communication constraints, the exchanged information must be compressed to reduce the communication load. We propose a distributed diffusion strategy nicknamed as ACTC (Adapt-Compress-Then-Combine), which implements the following three operations: adaptation, where each agent performs an individual stochastic-gradient update; compression, which leverages a recently introduced class of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">stochastic compression operators</i> ; and combination, where each agent combines the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">compressed</i> updates received from its neighbors. The main elements of novelty of this work are as follows: <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$i)$</tex-math></inline-formula> <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">adaptive</i> strategies, where constant (as opposed to diminishing) step-sizes are critical to infuse the agents with the ability of responding in real time to nonstationary variations in the observed model; <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$ii)$</tex-math></inline-formula> <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">directed</i> , i.e., non-symmetric combination policies, which allow us to enhance the role played by the network topology in the learning performance; <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$iii)$</tex-math></inline-formula> <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">global strong convexity</i> , a condition under which the individual agents might feature even non-convex cost functions. Under this demanding setting, we establish that the iterates of the ACTC strategy fluctuate around the exact global optimizer with a mean-square-deviation on the order of the step-size, achieving remarkable savings of communication resources. Comparison against up-to-date learning strategies with compressed data highlights the benefits of the proposed solution.