Nearest-Neighbor distributed learning under communication constraints

A wireless sensor network is engaged in a statistical learning task, to be accomplished in a decentralized fashion. The focus here is in distributed Nearest-Neighbor (NN) regression, in the presence of communication constraints. We first introduce a general channel access policy which allows the fusion center to recover training-set labels ordered according to the NN criterion, in the absence of any data exchange among sensors. Then, two different paradigms are considered, where the communication cost is measured as: i) the channel accesses; ii) the quantization bits. In the former scenario, we propose a distributed NN strategy reaching an asymptotic performance of twice the minimum achievable mean-square error, with only one sensor transmitting information. In the latter case, we achieve universally consistent distributed NN regression even with one-bit quantized labels.