Information-theoretic lower bounds for distributed statistical estimation with communication constraints

By Yuchen Zhang, John C. Duchi, Michael I. Jordan, Martin J. Wainwright. 2013

284 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Scaling & Learning Theory

Citations in the corpus

Federated Optimization: Distributed Optimization Beyond the Datacenter (2015, background): “With the exception of CoCoA [4, 7], the existing work concerning communication efficient optimization [10, 14] and/or statistical estimation [13, 12] presupposes, and in fact requires, that the number of nodes is (much) smaller than the number of datapoints available to each node, and that each node”
Advances and Open Problems in Federated Learning (2019, background): “Characterizing such fundamental trade-offs between accuracy and communication has been of recent interest in theoretical statistics [434, 81, 195, 11, 47, 380].”
Breaking the Communication-Privacy-Accuracy Trilemma (2020, background): “While there has been significant recent progress on understanding how to achieve optimal accuracy under separate privacy [12, 51] and communication [42, 52] constraints, as illustrated above a simple concatenated application of these optimal schemes can yield a highly suboptimal performance.”
rTop-k: A Statistical Estimation Approach to Distributed SGD (2020, background): “ic gradients and use these models to inform the design of more efﬁcient training techniques? This statistical perspective has been the focus of a recent research line in distributed estimation theory [18]–[26]. Motivated by similar observations as above, these works focus on characterizing the impac”
Communication trade-offs for synchronized distributed SGD with large step size (2019, background): “Similar bounds have also been provided for the generally easier statistical estimation setting in Duchi et al. (2014); Braverman et al. (2015); Zhang et al. (2013).”
Learning Distributions from their Samples under Communication Constraints (2019, methodology): “As an application of our framework, we use upper bounds on Fisher information to derive lower bounds on the minimax risk of the distributed estimation problems we discuss above and recover many of the existing results in the literature [6], [12], [13], [4], which are known to be (order-wise) tight.”
Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction (2018, background): “This is along the line of recent work on distributed mean estimation under communication constraints [58], [28], [45], [14], [55], although some of these works consider more general communication models than what we allow.”
Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization (2018, background): “There is work focusing on speciﬁc statistical estimation problems that establishes communication lower bounds via information-theoretic arguments [8, 12, 28].”
Geometric Lower Bounds for Distributed Parameter Estimation Under Communication Constraints (2018, neutral): “Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints Yanjun Han YJHAN@STANFORD.EDU Department of Electrical Engineering, Stanford University Ayfer Özgür AOZGUR@STANFORD.EDU Department of Electrical Engineering, Stanford University Tsachy Weissman TSACHY@STANFOR”
Communication-Efficient Learning of Deep Networks from Decentralized Data (2016, background): “In the convex setting, the problem of distributed optimization and estimation has received significant attention [4, 15, 33], and some algorithms do focus specifically on communication efficiency [45, 34, 40, 27, 43].”
Bayesian Nonparametric Federated Learning of Neural Networks (2019, background): “Yet others explore distributed optimization with a speciﬁc emphasis on communication ef-ﬁciency (Zhang et al., 2013; Shamir et al., 2014; Yang, 2013; Ma et al., 2015; Zhang & Lin, 2015).”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, background): “Eﬃcient algorithms and lower bounds for distributed statistical estimation are established in [104, 103].”
Tighter Theory for Local SGD on Identical and Heterogeneous Data (2019, methodology): “Under a Lipschitz Hessian assumption, Zhang et al. (2013) show that one-shot averaging can attain a linear speedup in the number of nodes, so one may do analysis of local SGD under this additional assumption to try to remove this gap, but this is beyond the scope of our work.”