{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T16:19:14Z","timestamp":1772727554692,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":62,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"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":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384315","type":"proceedings-article","created":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T21:45:25Z","timestamp":1591479925000},"page":"450-462","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Interaction is necessary for distributed learning with privacy or communication constraints"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7940-4002","authenticated-orcid":false,"given":"Yuval","family":"Dagan","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vitaly","family":"Feldman","sequence":"additional","affiliation":[{"name":"Google Research, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Jayadev Acharya Cl\u00e9ment L Canonne and Himanshu Tyagi. 2018. Inference under Information Constraints I: Lower Bounds from Chi-Square Contraction. arXiv preprint arXiv:1812.11476."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Jayadev Acharya Cl\u00e9ment L Canonne and Himanshu Tyagi. 2019. Inference under information constraints II: Communication constraints and shared randomness. arXiv preprint arXiv:1905.08302.","DOI":"10.1109\/TIT.2020.3028439"},{"key":"e_1_3_2_1_3_1","volume-title":"Distributed Learning with Sublinear Communication. In International Conference on Machine Learning. 40\u201350","author":"Acharya Jayadev","year":"2019","unstructured":"Jayadev Acharya, Chris De Sa, Dylan Foster, and Karthik Sridharan. 2019. Distributed Learning with Sublinear Communication. In International Conference on Machine Learning. 40\u201350."},{"key":"e_1_3_2_1_4_1","volume-title":"The 22nd International Conference on Artificial Intelligence and Statistics. 1120\u20131129","author":"Acharya Jayadev","year":"2019","unstructured":"Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. 2019. Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication. In The 22nd International Conference on Artificial Intelligence and Statistics. 1120\u20131129."},{"key":"e_1_3_2_1_5_1","unstructured":"M. A. Aizerman E. A. Braverman and L. Rozonoer. 1964. Theoretical foundations of the potential function method in pattern recognition learning.. In Automation and Remote Control (Automation and Remote Control ). 821\u2013837."},{"key":"e_1_3_2_1_6_1","unstructured":"Naum Il\u2019ich Akhiezer and N Kemmer. 1965. The classical moment problem: and some related questions in analysis. 5 Oliver & Boyd Edinburgh."},{"key":"e_1_3_2_1_7_1","article-title":"Learning with Privacy at Scale","volume":"1","author":"Privacy Team Apple\u2019s Differential","year":"2017","unstructured":"Apple\u2019s Differential Privacy Team. 2017. Learning with Privacy at Scale. Apple Machine Learning Journal, 1, 9 (2017), Dec..","journal-title":"Apple Machine Learning Journal"},{"key":"e_1_3_2_1_8_1","volume-title":"Parallelization does not Accelerate Convex Optimization: Adaptivity Lower Bounds for Non-smooth Convex Minimization. CoRR, abs\/1808.03880","author":"Balkanski Eric","year":"2018","unstructured":"Eric Balkanski and Yaron Singer. 2018. Parallelization does not Accelerate Convex Optimization: Adaptivity Lower Bounds for Non-smooth Convex Minimization. CoRR, abs\/1808.03880 (2018), arxiv:1808.03880. arxiv:1808.03880"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","unstructured":"Raef Bassily and Adam Smith. 2015. Local Private Efficient Protocols for Succinct Histograms. STOC https:\/\/doi.org\/10.1145\/2746539.2746632 10.1145\/2746539.2746632","DOI":"10.1145\/2746539.2746632"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1569"},{"key":"e_1_3_2_1_11_1","first-page":"441","article-title":"Limitations of Learning Via Embeddings in Euclidean Half Spaces","volume":"3","author":"Ben-David Shai","year":"2002","unstructured":"Shai Ben-David, Nadav Eiron, and Hans Ulrich Simon. 2002. Limitations of Learning Via Embeddings in Euclidean Half Spaces. Journal of Machine Learning Research, 3 (2002), 441\u2013461. http:\/\/www.jmlr.org\/papers\/v3\/bendavid02a.html","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_1_12_1","unstructured":"Itai Benjamini Ori Gurel-Gurevich and Ron Peled. 2012. On k-wise independent distributions and boolean functions. arXiv preprint arXiv:1201.3261."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00013833"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Bernhard E. Boser Isabelle Guyon and Vladimir Vapnik. 1992. A Training Algorithm for Optimal Margin Classifiers. In COLT. ACM 144\u2013152.","DOI":"10.1145\/130385.130401"},{"key":"e_1_3_2_1_15_1","volume-title":"International Conference on Machine Learning. 831\u2013840","author":"Bubeck Sebastien","year":"2019","unstructured":"Sebastien Bubeck, Yin Tat Lee, Eric Price, and Ilya Razenshteyn. 2019. Adversarial examples from computational constraints. In International Conference on Machine Learning. 831\u2013840."},{"key":"e_1_3_2_1_16_1","volume-title":"Heavy Hitters and the Structure of Local Privacy. In Symposium on Principles of Database Systems. 435\u2013447","author":"Bun Mark","year":"2018","unstructured":"Mark Bun, Jelani Nelson, and Uri Stemmer. 2018. Heavy Hitters and the Structure of Local Privacy. In Symposium on Principles of Database Systems. 435\u2013447."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316375"},{"key":"e_1_3_2_1_18_1","volume-title":"Extended abstract in NeurIPS","author":"Daniely Amit","year":"2019","unstructured":"Amit Daniely and Vitaly Feldman. 2018. Locally private learning without interaction requires separation. arXiv preprint arXiv:1809.09165, Extended abstract in NeurIPS 2019."},{"key":"e_1_3_2_1_19_1","volume-title":"Open Problem: Is Margin Sufficient for Non-Interactive Private Distributed Learning? In COLT. 3180\u20133184","author":"Daniely Amit","year":"2019","unstructured":"Amit Daniely and Vitaly Feldman. 2019. Open Problem: Is Margin Sufficient for Non-Interactive Private Distributed Learning? In COLT. 3180\u20133184. http:\/\/proceedings.mlr.press\/v99\/daniely19a.html"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.16"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.170"},{"key":"e_1_3_2_1_22_1","volume-title":"Lower Bounds for Parallel and Randomized Convex Optimization. CoRR, abs\/1811.01903","author":"Diakonikolas Jelena","year":"2018","unstructured":"Jelena Diakonikolas and Crist\u00f3bal Guzm\u00e1n. 2018. Lower Bounds for Parallel and Randomized Convex Optimization. CoRR, abs\/1811.01903 (2018), arxiv:1811.01903. arxiv:1811.01903"},{"key":"e_1_3_2_1_23_1","volume-title":"Collecting Telemetry Data Privately. In 31st Conference on Neural Information Processing Systems (NIPS). 3574\u20133583","author":"Ding Bolin","year":"2017","unstructured":"Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. 2017. Collecting Telemetry Data Privately. In 31st Conference on Neural Information Processing Systems (NIPS). 3574\u20133583."},{"key":"e_1_3_2_1_24_1","unstructured":"John Duchi and Ryan Rogers. 2019. Lower Bounds for Locally Private Estimation via Communication Complexity. arXiv preprint arXiv:1902.00582."},{"key":"e_1_3_2_1_25_1","volume-title":"Wainwright","author":"Duchi John C.","year":"2013","unstructured":"John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. 2013. Local Privacy and Statistical Minimax Rates. In FOCS. 429\u2013438."},{"key":"e_1_3_2_1_26_1","unstructured":"John C. Duchi Feng Ruan and Chulhee Yun. 2018. Minimax Bounds on Stochastic Batched Convex Optimization. In COLT. 3065\u20133162. http:\/\/proceedings.mlr.press\/v75\/duchi18a.html"},{"key":"e_1_3_2_1_27_1","volume-title":"Jordan","author":"Duchi John C.","year":"2013","unstructured":"John C. Duchi, Martin J. Wainwright, and Michael I. Jordan. 2013. Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation. In NIPS. 1529\u20131537."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"crossref","unstructured":"C. Dwork F. McSherry K. Nissim and A. Smith. 2006. Calibrating noise to sensitivity in private data analysis. In TCC. 265\u2013284.","DOI":"10.1007\/11681878_14"},{"key":"e_1_3_2_1_29_1","volume-title":"Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity. CoRR, abs\/1811.12469","author":"Erlingsson \u00dalfar","year":"2018","unstructured":"\u00dalfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. 2018. Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity. CoRR, abs\/1811.12469 (2018), arxiv:1811.12469. arxiv:1811.12469 Extended abstract in SODA 2019."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660348"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Alexandre V. Evfimievski Johannes Gehrke and Ramakrishnan Srikant. 2003. Limiting privacy breaches in privacy preserving data mining. In PODS. 211\u2013222.","DOI":"10.1145\/773153.773174"},{"key":"e_1_3_2_1_32_1","volume-title":"CoRR, abs\/1201.1214","author":"Feldman Vitaly","year":"2012","unstructured":"Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, and Ying Xiao. 2012. Statistical Algorithms and a Lower Bound for Detecting Planted Cliques. arXiv, CoRR, abs\/1201.1214 (2012), Extended abstract in STOC 2013."},{"key":"e_1_3_2_1_33_1","volume-title":"Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization. CoRR, abs\/1512.09170","author":"Feldman Vitaly","year":"2015","unstructured":"Vitaly Feldman, Cristobal Guzman, and Santosh Vempala. 2015. Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization. CoRR, abs\/1512.09170 (2015), arxiv:1512.09170 Extended abstract in SODA 2017."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44581-1_26"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Justin Hsu Sanjeev Khanna and Aaron Roth. 2012. Distributed Private Heavy Hitters. In ICALP. 461\u2013472.","DOI":"10.1007\/978-3-642-31594-7_39"},{"key":"e_1_3_2_1_36_1","volume-title":"The Role of Interactivity in Local Differential Privacy. CoRR, abs\/1904.03564","author":"Joseph Matthew","year":"2019","unstructured":"Matthew Joseph, Jieming Mao, Seth Neel, and Aaron Roth. 2019. The Role of Interactivity in Local Differential Privacy. CoRR, abs\/1904.03564 (2019), arxiv:1904.03564. arxiv:1904.03564"},{"key":"e_1_3_2_1_37_1","volume-title":"Exponential Separations in Local Differential Privacy Through Communication Complexity. CoRR, abs\/1907.00813","author":"Joseph Matthew","year":"2019","unstructured":"Matthew Joseph, Jieming Mao, and Aaron Roth. 2019. Exponential Separations in Local Differential Privacy Through Communication Complexity. CoRR, abs\/1907.00813 (2019), arxiv:1907.00813. arxiv:1907.00813"},{"key":"e_1_3_2_1_38_1","unstructured":"M. Kallweit and H. Simon. 2011. A Close Look to Margin Complexity and Related Parameters. In COLT. 437\u2013456."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/090756090"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293351"},{"key":"e_1_3_2_1_41_1","volume-title":"The Markov moment problem and extremal problems: ideas and problems of PL Cebysev and AA Markov and their further development","author":"Krein Mark Grigorevich","unstructured":"Mark Grigorevich Krein and Adol\u2019f Abramovich Nudel\u2019man. 1977. The Markov moment problem and extremal problems: ideas and problems of PL Cebysev and AA Markov and their further development. American Mathematical Society."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548308009656"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.847692"},{"key":"e_1_3_2_1_44_1","volume-title":"Proceedings of the Symposium on Mathematical Theory of Automata. XII, 615\u2013622","author":"Novikoff A.","year":"1962","unstructured":"A. Novikoff. 1962. On convergence proofs on perceptrons. In Proceedings of the Symposium on Mathematical Theory of Automata. XII, 615\u2013622."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2006.261731"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2005.863009"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-008-0242-4"},{"key":"e_1_3_2_1_48_1","unstructured":"Adam Smith and Di Wang. Nov 2019. Personal communication."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2017.35"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"crossref","unstructured":"Doman Brian George Spencer. 2015. The classical orthogonal polynomials. World Scientific.","DOI":"10.1142\/9700"},{"key":"e_1_3_2_1_51_1","volume-title":"Duchi","author":"Steinhardt Jacob","year":"2015","unstructured":"Jacob Steinhardt and John C. Duchi. 2015. Minimax rates for memory-bounded sparse linear regression. In COLT. 1564\u20131587. http:\/\/jmlr.org\/proceedings\/papers\/v40\/Steinhardt15.html"},{"key":"e_1_3_2_1_52_1","unstructured":"J. Steinhardt G. Valiant and S. Wager. 2016. Memory Communication and Statistical Queries. In COLT. 1490\u20131516."},{"key":"e_1_3_2_1_53_1","unstructured":"Ananda Theertha Suresh Felix X Yu H Brendan McMahan and Sanjiv Kumar. 2016. Distributed mean estimation with limited communication. arXiv preprint arXiv:1611.00429."},{"key":"e_1_3_2_1_54_1","volume-title":"Tight Lower Bounds for Locally Differentially Private Selection. CoRR, abs\/1802.02638","author":"Ullman Jonathan","year":"2018","unstructured":"Jonathan Ullman. 2018. Tight Lower Bounds for Locally Differentially Private Selection. CoRR, abs\/1802.02638 (2018), arxiv:1802.02638. arxiv:1802.02638"},{"key":"e_1_3_2_1_55_1","unstructured":"Di Wang Marco Gaboardi and Jinhui Xu. 2018. Empirical Risk Minimization in Non-interactive Local Differential Privacy Revisited. In Advances in Neural Information Processing Systems 31. 965\u2013974. http:\/\/papers.nips.cc\/paper\/7375-empirical-risk-minimization-in-non-interactive-local-differential-privacy-revisited.pdf"},{"key":"e_1_3_2_1_56_1","volume-title":"Proceedings of the 30th International Conference on Algorithmic Learning Theory (Proceedings of Machine Learning Research","volume":"903","author":"Wang Di","year":"2019","unstructured":"Di Wang, Adam Smith, and Jinhui Xu. 2019. Noninteractive Locally Private Learning of Linear Models via Polynomial Approximations. In Proceedings of the 30th International Conference on Algorithmic Learning Theory (Proceedings of Machine Learning Research, Vol. 98). 898\u2013903. http:\/\/proceedings.mlr.press\/v98\/wang19c.html"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2019\/666"},{"key":"e_1_3_2_1_58_1","unstructured":"Di Wang Huanyu Zhang Marco Gaboardi and Jinhui Xu. 2019. Estimating Smooth GLM in Non-interactive Local Differential Privacy Model with Public Unlabeled Data. arXiv preprint arXiv:1910.00482."},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1965.10480775"},{"key":"e_1_3_2_1_60_1","unstructured":"Blake E. Woodworth Jialei Wang Adam D. Smith Brendan McMahan and Nati Srebro. 2018. Graph Oracle Models Lower Bounds and Gaps for Parallel Stochastic Optimization. In NeurIPS. 8505\u20138515. http:\/\/papers.nips.cc\/paper\/8069-graph-oracle-models-lower-bounds-and-gaps-for-parallel-stochastic-optimization"},{"key":"e_1_3_2_1_61_1","volume-title":"Wainwright","author":"Zhang Yuchen","year":"2013","unstructured":"Yuchen Zhang, John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. 2013. Information-theoretic lower bounds for distributed statistical estimation with communication constraints. In NIPS. 2328\u20132336."},{"key":"e_1_3_2_1_62_1","volume-title":"Proceedings of the 34th International Conference on Machine Learning-Volume 70","author":"Zheng Kai","year":"2017","unstructured":"Kai Zheng, Wenlong Mou, and Liwei Wang. 2017. Collect at once, use effectively: making non-interactive locally private learning possible. In Proceedings of the 34th International Conference on Machine Learning-Volume 70. 4130\u20134139."}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384315","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384315","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T20:48:39Z","timestamp":1755809319000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384315"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":62,"alternative-id":["10.1145\/3357713.3384315","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384315","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}