Information-theoretic lower bounds for distributed statistical estimation with communication constraints
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.
This paper considers minimax lower bounds on the mean 
      squared error for statistical estimation problems, in a setting where 
      available data is distributed i.i.d. across several machines and there is 
      a constraint on the number of bits that may be communicated. The paper 
      considers both interactive and non-interactive protocols, where the final 
      estimate is a function of the messages sent by the machines. For 
      interactive protocols, these include lower bounds for estimating the mean 
      of a uniform distribution in a unit cube, and the mean of a univariate 
      Gaussian distribution. For non-interactive protocols, the lower bounds are 
      for estimating the mean of a multivariate Gaussian distribution, and 
      applications for linear and probit regression in a fixed (known) design 
      setting. The issue of distributed learning and estimation has 
      received plenty of attention in recent years, mostly in the form of 
      algorithms and upper bounds. This paper is among the first (see remarks 
      below) to explicitly consider lower bounds. Since lower bounds are crucial 
      to understanding the limits of achievable performance, I consider this a 
      very interesting line of research. The results presented here seem to be 
      interesting first steps in this direction. Also, I found the paper clear 
      and quite easy to follow. Finally, the results seem overall correct, 
      although I haven't checked the proofs in the supplementary carefully. 
      My main criticism is that the results focus on somewhat limited 
      regimes, which may not correspond to realistic applications of distributed 
      learning. To be more specific: 1) The setting considered here is 
      only harder than the standard (non-distributed) setting of statistical 
      estimation. Thus, all the standard (non-distributed) lower bounds 
      trivially hold. The lower bounds presented here are stronger than those 
      standard bounds, only in the regime where the average amount of 
      communication B_i per machine is smaller than the data dimension d. 
      However, this is a very harsh constraint. For example, in standard linear 
      prediction, it means that each machine can't even output a single 
      predictor. For most applications of distributed learning, one is very 
      happy with protocols where B_i is order of d, and for such a regime, the 
      results here do not improve on the existing standard lower bounds. For 
      fairness, it should be said that it's not known whether the standard lower 
      bounds are improvable when B_i >= d, except in some cases, such as 
      statistical estimation with sufficiently smooth loss functions (see Zhang 
      et al. 2012 - reference [18] in the paper). These results do not apply to 
      non-smooth losses, e.g. when we try to distribute support vector machines. 
      Moreover, all these results are in terms of mean-squared-error, and do not 
      give tight results when converting them to optimization error / excess 
      risk (e.g. in terms of dependence on the strong-convexity parameter, which 
      can be small in regularized statistical learning problems). Anyway, the 
      results in this paper do not shed light on these issues. 2) Most 
      of the results here are for non-interactive protocols, where each machine 
      can only send a single message based on its data, and the final estimator 
      is a function of these messages. This is restrictive, since one can easily 
      imagine algorithms which require several communication rounds between the 
      machines. The concrete results for interactive protocols (proposition 1 
      and theorem 2) seem much more limited, focusing either on a uniform 
      distribution in a unit cube, or a 1-dimensional setting. As to the more 
      generic theorem 1, I may be wrong, but I think the same proof would apply 
      to a non-distributed setting, where the only constraint it that the output 
      \hat{\theta} is limited to B bits. So in a certain sense, it may not 
      capture an interesting aspect of the distributed setting. 3) The 
      regression lower bounds focus on a fixed design setting, where the 
      design/instances are known by all machines in advance, and the uncertainty 
      is in the target values. In a distributed setting, it's much more 
      realistic to assume unknown instances partitioned between the machines. 
      Technical Comments ------------------ - Line 
      41: "Currently there is little theoretical understanding of the role of 
      communication complexity in statistical inference, and thus the design 
      and analysis of distributed inference algorithms is more art than 
      science". I think this is exaggerated. Principled approaches to design and 
      analyze distributed inference and learning have been well-studied in the 
      literature. It is true that lower bounds have not been as carefully 
      studied. - It would be good to explain why the dependence on B is 
      so different between the two settings of proposition 1 and theorem 2. 
      - Line 111: "an protocol" - Line 119, definition of 
      minimax risk - why is the protocol Pi separated from the estimator 
      function \Theta? Pehaps it would make more sense to include the final 
      estimate computation as part of the protocol. - Line 148: If I 
      understood correctly, example 1 shows the tightness of Theorem 1 only for 
      one particular choice of B. It would be better if one can come up with an 
      example which shows the tightness of the bound for *any* choice of B. 
      - Line 1120 in supplementary: "achieves minimax" -> "which 
      achieves the"(?) - In discussing related work, the authors should 
      also mention the COLT 2012 paper "Distributed Learning, Communication 
      Complexity and Privacy" by Balcan et al., which also discuss lower bounds 
      for distributed learning (although in a different setting). - 
      Section 2: When defining A_ind and A_inter, do any of the lower bounds 
      become better if we require L<=B always rather just in expectation? 
      Assuming that not, it might be worthwhile to point this out.