Distributed function estimation: adaptation using minimal communication

Distributed methods have attracted a lot of attention in the statistics and machine learning communities recently. There are several reasons for this, the most prominent ones being that they provide a way of dealing with large datasets and with privacy considerations. The theoretical literature on distributed methods is still rather minimal at the moment. A number of papers have recently investigated fundamental performance limits in distributed models, in particular pointing out issues that occur in high-dimensional or nonparametric problems, see for instance [1, 2, 4, 8, 16, 17, 21, 24, 27]. For example, optimal rates in distributed function estimation depend on the amount of communication that is allowed, and the relation of that amount with the regularity of the unknown function. The lower bounds obtained in [25] and [28] and the subsequent adaptation results in [25] show that in particular, automatically adapting to the smoothness of the unknown function is a complicated issue in communication restricted distributed settings. In the present paper we study this problem from a different, we think relevant and interesting perspective, not restricting communication a priori, but asking for rate-optimal procedures that require minimal communication.