Decentralized nearest-neighbor learning over noisy channels: The uncoded way

The theory of nonparametric regression is a well-established discipline, one branch of which deals with nearest-neighbor (NN) estimation. Only recently, however, the NN regression problem has been addressed in distributed scenarios, such as a wireless sensor network. In this setting, each sensor of the network owns one example (X_i, Y_i) from the training set T_n = {(X_i, Y_i)}_i=1ⁿ and, at a certain time, the fusion center (FC) collects some X₀. What is the corresponding Y₀? By learning from the training set, the answer is known; but now T_n is not directly available to the FC, and computing such an estimate is an open problem. Some clever channel access policy is needed such that, without inter-sensor coordination, the FC recovers the training-set labels it needs to compute the NN regression, while less informative labels are not delivered at all. Even if this access policy were available, in the presence of noisy channels the labels can be recovered only approximately, and how to build a suitable regression function remains not obvious. Less obvious still is to design distributed NN regression functions that are univerally consistent, in the presence of coherent or noncoherent communication channels. In this paper we present a suitable access policy and design two nonparametric NN estimators based upon uncoded communication schemes between sensors and FC; the universal asymptotic consistency of the proposed regression functions is proved.