We derive lower bounds on the Bayes risk in decentralized estimation, where the estimator does not have direct access to the random samples generated conditionally on the random parameter of interest, but only to the data received from local processors that observe the samples. The received data are subject to communication constraints, due to quantization and the noise in the communication channels from the processors to the estimator. We first derive general lower bounds on the Bayes risk using information-theoretic quantities, such as mutual information, information density, small ball probability, and differential entropy. We then apply these lower bounds to the decentralized case, using strong data processing inequalities to quantify the contraction of information due to communication constraints. We treat the cases of a single processor and of multiple processors, where the samples observed by different processors may be conditionally dependent given the parameter, for noninteractive and interactive communication protocols. Our results recover and improve recent lower bounds on the Bayes risk and the minimax risk for certain decentralized estimation problems, where previously only conditionally independent sample sets and noiseless channels have been considered. Moreover, our results provide a general way to quantify the degradation of estimation performance caused by distributing resources to multiple processors, which is only discussed for specific examples in existing works.
@cite_19: We establish lower bounds on minimax risks for distributed statistical estimation under a communication budget. Such lower bounds reveal the minimum amount of communication required by any procedure to achieve the centralized minimax-optimal rates for statistical estimation. We study two classes of protocols: one in which machines send messages independently, and a second allowing for interactive communication. We establish lower bounds for several problems, including various types of location models, as well as for parameter estimation in regression models.
@cite_17: Many machine learning approaches are characterized by information constraints on how they interact with the training data. These include memory and sequential access constraints (e.g. fast first-order methods to solve stochastic optimization problems); communication constraints (e.g. distributed learning); partial access to the underlying data (e.g. missing features and multi-armed bandits) and more. However, currently we have little understanding how such information constraints fundamentally affect our performance, independent of the learning problem semantics. For example, are there learning problems where any algorithm which has small memory footprint (or can use any bounded number of bits from each example, or has certain communication constraints) will perform worse than what is possible without such constraints? In this paper, we describe how a single set of results implies positive answers to the above, for several different settings.
By contrast, we derive general lower bounds on the Bayes risk, which automatically serve as lower bounds on the minimax risk. We use strong data processing inequalities as a unifiying general method for quantifying the contraction of mutual information in decentralized estimation. Our results apply to general priors, sample generating models, and distortion functions. When particularized to the examples in the existing works, our results can lead to sharper lower bounds on both the Bayes and the minimax risk. For example, we improve the lower bound for the mean estimation on the unit cube studied in @cite_19 , as well as the lower bound for the meta-problem of Shamir @cite_17 . Moreover, we consider the situations where the sample sets are conditionally dependent and where the communication channels are noisy. We also provide a general way to quantify the degradation of estimation performance caused by distributing resources to multiple processors, which is only discussed for specific examples in existing works.