{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T15:06:30Z","timestamp":1775228790631,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":19,"publisher":"ACM","license":[{"start":{"date-parts":[[2016,6,19]],"date-time":"2016-06-19T00:00:00Z","timestamp":1466294400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2016,6,19]]},"DOI":"10.1145\/2897518.2897582","type":"proceedings-article","created":{"date-parts":[[2016,6,10]],"date-time":"2016-06-10T13:04:07Z","timestamp":1465563847000},"page":"1011-1020","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":68,"title":["Communication lower bounds for statistical estimation problems via a distributed data processing inequality"],"prefix":"10.1145","author":[{"given":"Mark","family":"Braverman","sequence":"first","affiliation":[{"name":"Princeton University, USA"}]},{"given":"Ankit","family":"Garg","sequence":"additional","affiliation":[{"name":"Princeton University, USA"}]},{"given":"Tengyu","family":"Ma","sequence":"additional","affiliation":[{"name":"Princeton University, USA"}]},{"given":"Huy L.","family":"Nguyen","sequence":"additional","affiliation":[{"name":"Toyota Technological Institute at Chicago, USA"}]},{"given":"David P.","family":"Woodruff","sequence":"additional","affiliation":[{"name":"IBM Research, USA"}]}],"member":"320","published-online":{"date-parts":[[2016,6,19]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"e_1_3_2_1_2_1","volume-title":"Optimal principal component analysis in distributed and streaming models. CoRR, abs\/1504.06729","author":"Boutsidis Christos","year":"2015","unstructured":"{BWZ15} Christos Boutsidis , David P. Woodruff , and Peilin Zhong . Optimal principal component analysis in distributed and streaming models. CoRR, abs\/1504.06729 , 2015 . {BWZ15} Christos Boutsidis, David P. Woodruff, and Peilin Zhong. Optimal principal component analysis in distributed and streaming models. CoRR, abs\/1504.06729, 2015."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"issue":"3","key":"e_1_3_2_1_4_1","first-page":"592","article-title":"Dual averaging for distributed optimization: convergence analysis and network scaling. Automatic Control","volume":"57","author":"Duchi John C","year":"2012","unstructured":"{DAW12} John C Duchi , Alekh Agarwal , and Martin J Wainwright . Dual averaging for distributed optimization: convergence analysis and network scaling. Automatic Control , IEEE Transactions on , 57 ( 3 ): 592 \u2013 606 , 2012 . {DAW12} John C Duchi, Alekh Agarwal, and Martin J Wainwright. Dual averaging for distributed optimization: convergence analysis and network scaling. Automatic Control, IEEE Transactions on, 57(3):592\u2013606, 2012.","journal-title":"IEEE Transactions on"},{"key":"e_1_3_2_1_5_1","volume-title":"Information-theoretic lower bounds for distributed statistical estimation with communication constraints. CoRR, abs\/1405.0782","author":"Duchi John C.","year":"2014","unstructured":"{DJWZ14} John C. Duchi , Michael I. Jordan , Martin J. Wainwright , and Yuchen Zhang . Information-theoretic lower bounds for distributed statistical estimation with communication constraints. CoRR, abs\/1405.0782 , 2014 . {DJWZ14} John C. Duchi, Michael I. Jordan, Martin J. Wainwright, and Yuchen Zhang. Information-theoretic lower bounds for distributed statistical estimation with communication constraints. CoRR, abs\/1405.0782, 2014."},{"key":"e_1_3_2_1_6_1","first-page":"2734","volume-title":"NIPS","author":"Garg Ankit","year":"2014","unstructured":"{GMN14} Ankit Garg , Tengyu Ma , and Huy L. Nguyen . On communication cost of distributed statistical estimation and dimensionality . In NIPS , pages 2726\u2013 2734 , 2014 . {GMN14} Ankit Garg, Tengyu Ma, and Huy L. Nguyen. On communication cost of distributed statistical estimation and dimensionality. In NIPS, pages 2726\u20132734, 2014."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_42"},{"key":"e_1_3_2_1_8_1","first-page":"1057","volume-title":"Proceedings of The 27th Conference on Learning Theory, COLT 2014","author":"Kannan Ravi","year":"2014","unstructured":"{KVW14} Ravi Kannan , Santosh Vempala , and David P. Woodruff . Principal component analysis and higher correlations for distributed data . In Proceedings of The 27th Conference on Learning Theory, COLT 2014 , Barcelona, Spain , June 13-15, 2014 , pages 1040\u2013 1057 , 2014. {KVW14} Ravi Kannan, Santosh Vempala, and David P. Woodruff. Principal component analysis and higher correlations for distributed data. In Proceedings of The 27th Conference on Learning Theory, COLT 2014, Barcelona, Spain, June 13-15, 2014, pages 1040\u20131057, 2014."},{"key":"e_1_3_2_1_9_1","first-page":"3121","volume-title":"NIPS","author":"Liang Yingyu","year":"2014","unstructured":"{LBKW14} Yingyu Liang , Maria-Florina Balcan , Vandana Kanchanapally , and David P. Woodruff . Improved distributed principal component analysis . In NIPS , pages 3113\u2013 3121 , 2014 . {LBKW14} Yingyu Liang, Maria-Florina Balcan, Vandana Kanchanapally, and David P. Woodruff. Improved distributed principal component analysis. In NIPS, pages 3113\u20133121, 2014."},{"key":"e_1_3_2_1_10_1","volume-title":"Communication-efficient sparse regression: a one-shot approach. arXiv preprint arXiv:1503.04337","author":"Lee Jason D","year":"2015","unstructured":"{LSLT15} Jason D Lee , Yuekai Sun , Qiang Liu , and Jonathan E Taylor . Communication-efficient sparse regression: a one-shot approach. arXiv preprint arXiv:1503.04337 , 2015 . {LSLT15} Jason D Lee, Yuekai Sun, Qiang Liu, and Jonathan E Taylor. Communication-efficient sparse regression: a one-shot approach. arXiv preprint arXiv:1503.04337, 2015."},{"key":"e_1_3_2_1_11_1","volume-title":"Strong data processing inequalities and $\u03a6$-sobolev inequalities for discrete channels. CoRR, abs\/1411.3575","author":"Raginsky Maxim","year":"2014","unstructured":"{Rag14} Maxim Raginsky . Strong data processing inequalities and $\u03a6$-sobolev inequalities for discrete channels. CoRR, abs\/1411.3575 , 2014 . {Rag14} Maxim Raginsky. Strong data processing inequalities and $\u03a6$-sobolev inequalities for discrete channels. CoRR, abs\/1411.3575, 2014."},{"key":"e_1_3_2_1_12_1","first-page":"1587","volume-title":"Proceedings of The 28th Conference on Learning Theory, COLT 2015","author":"Steinhardt Jacob","year":"2015","unstructured":"{SD15} Jacob Steinhardt and John C. Duchi . Minimax rates for memory-bounded sparse linear regression . In Proceedings of The 28th Conference on Learning Theory, COLT 2015 , Paris, France , July 3-6, 2015 , pages 1564\u2013 1587 , 2015. {SD15} Jacob Steinhardt and John C. Duchi. Minimax rates for memory-bounded sparse linear regression. In Proceedings of The 28th Conference on Learning Theory, COLT 2015, Paris, France, July 3-6, 2015, pages 1564\u20131587, 2015."},{"key":"e_1_3_2_1_13_1","first-page":"171","volume-title":"NIPS","author":"Shamir Ohad","year":"2014","unstructured":"{Sha14} Ohad Shamir . Fundamental limits of online and distributed algorithms for statistical learning and estimation . In NIPS , pages 163\u2013 171 , 2014 . {Sha14} Ohad Shamir. Fundamental limits of online and distributed algorithms for statistical learning and estimation. In NIPS, pages 163\u2013171, 2014."},{"key":"e_1_3_2_1_14_1","first-page":"1008","volume-title":"Proceedings of the 31th International Conference on Machine Learning, ICML 2014","author":"Shamir Ohad","year":"2014","unstructured":"{SSZ14} Ohad Shamir , Nathan Srebro , and Tong Zhang . Communication-efficient distributed optimization using an approximate newton-type method . In Proceedings of the 31th International Conference on Machine Learning, ICML 2014 , pages 1000\u2013 1008 , 2014 . {SSZ14} Ohad Shamir, Nathan Srebro, and Tong Zhang. Communication-efficient distributed optimization using an approximate newton-type method. In Proceedings of the 31th International Conference on Machine Learning, ICML 2014, pages 1000\u20131008, 2014."},{"key":"e_1_3_2_1_15_1","volume-title":"STOC","author":"David","year":"2012","unstructured":"{WZ12} David P. Woodruff and Qin Zhang. Tight bounds for distributed functional monitoring . STOC , 2012 . {WZ12} David P. Woodruff and Qin Zhang. Tight bounds for distributed functional monitoring. STOC, 2012."},{"key":"e_1_3_2_1_16_1","volume-title":"Woodruff and Peilin Zhong. Distributed low rank approximation of implicit functions of a matrix. CoRR, abs\/1601.07721","author":"David","year":"2016","unstructured":"{WZ16} David P. Woodruff and Peilin Zhong. Distributed low rank approximation of implicit functions of a matrix. CoRR, abs\/1601.07721 , 2016 . {WZ16} David P. Woodruff and Peilin Zhong. Distributed low rank approximation of implicit functions of a matrix. CoRR, abs\/1601.07721, 2016."},{"key":"e_1_3_2_1_17_1","first-page":"2336","volume-title":"NIPS","author":"Zhang Yuchen","year":"2013","unstructured":"{ZDJW13} Yuchen Zhang , John C. Duchi , Michael I. Jordan , and Martin J. Wainwright . Information-theoretic lower bounds for distributed statistical estimation with communication constraints . In NIPS , pages 2328\u2013 2336 , 2013 . {ZDJW13} Yuchen Zhang, John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. Information-theoretic lower bounds for distributed statistical estimation with communication constraints. In NIPS, pages 2328\u20132336, 2013."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/2567709.2567769"},{"key":"e_1_3_2_1_19_1","volume-title":"Communication-efficient distributed optimization of self-concordant empirical loss. CoRR, abs\/1501.00263","author":"Zhang Yuchen","year":"2015","unstructured":"{ZX15} Yuchen Zhang and Lin Xiao . Communication-efficient distributed optimization of self-concordant empirical loss. CoRR, abs\/1501.00263 , 2015 . {ZX15} Yuchen Zhang and Lin Xiao. Communication-efficient distributed optimization of self-concordant empirical loss. CoRR, abs\/1501.00263, 2015."}],"event":{"name":"STOC '16: Symposium on Theory of Computing","location":"Cambridge MA USA","acronym":"STOC '16","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-eighth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2897518.2897582","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2897518.2897582","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:55:57Z","timestamp":1750222557000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2897518.2897582"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,19]]},"references-count":19,"alternative-id":["10.1145\/2897518.2897582","10.1145\/2897518"],"URL":"https:\/\/doi.org\/10.1145\/2897518.2897582","relation":{},"subject":[],"published":{"date-parts":[[2016,6,19]]},"assertion":[{"value":"2016-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}