{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:01:54Z","timestamp":1750309314390,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":81,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-sa\/4.0\/"}],"funder":[{"name":"NSF (National Science Foundation)","award":["DMS-2022448, CCF-1749609, DMS-1839116"],"award-info":[{"award-number":["DMS-2022448, CCF-1749609, DMS-1839116"]}]},{"name":"Simons Foundation","award":["Simons Investigator Award"],"award-info":[{"award-number":["Simons Investigator Award"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649787","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"1130-1140","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Improving the Bit Complexity of Communication for Distributed Convex Optimization"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0934-1322","authenticated-orcid":false,"given":"Mehrdad","family":"Ghadiri","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4692-5442","authenticated-orcid":false,"given":"Yin Tat","family":"Lee","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, USA \/ Microsoft Research, Redmond, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4834-2136","authenticated-orcid":false,"given":"Swati","family":"Padmanabhan","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-5010-2126","authenticated-orcid":false,"given":"William","family":"Swartworth","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2158-1380","authenticated-orcid":false,"given":"David P.","family":"Woodruff","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1197-0649","authenticated-orcid":false,"given":"Guanghao","family":"Ye","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"International conference on machine learning.","author":"Agarwal Alekh","year":"2015","unstructured":"Alekh Agarwal and Leon Bottou. 2015. A lower bound for the optimization of finite sums. In International conference on machine learning."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Alekh Agarwal and John C Duchi. 2011. Distributed delayed stochastic optimization. Advances in neural information processing systems.","DOI":"10.1109\/CDC.2012.6426626"},{"key":"e_1_3_2_1_3_1","article-title":"Katyusha: The first direct acceleration of stochastic gradient methods","author":"Allen-Zhu Zeyuan","year":"2017","unstructured":"Zeyuan Allen-Zhu. 2017. Katyusha: The first direct acceleration of stochastic gradient methods. The Journal of Machine Learning Research.","journal-title":"The Journal of Machine Learning Research."},{"key":"e_1_3_2_1_4_1","unstructured":"Emile Anand Jan van den Brand Mehrdad Ghadiri and Daniel Zhang. 2024. The Bit Complexity of Dynamic Algebraic Formulas and their Determinants. arXiv preprint arXiv:2401.11127."},{"key":"e_1_3_2_1_5_1","volume-title":"Jaros\u0142 aw B\u0142 asiok, and Arnold Filtser","author":"Andoni Alexandr","year":"2022","unstructured":"Alexandr Andoni, Jaros\u0142 aw B\u0142 asiok, and Arnold Filtser. 2022. Communication Complexity of Inner Product in Symmetric Normed Spaces. arXiv preprint arXiv:2211.13473."},{"key":"e_1_3_2_1_6_1","unstructured":"David Applegate Mateo D\u00edaz Oliver Hinder Haihao Lu Miles Lubin Brendan O\u2019Donoghue and Warren Schudy. 2021. Practical large-scale linear programming using primal-dual hybrid gradient. Advances in Neural Information Processing Systems."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","unstructured":"David Applegate Oliver Hinder Haihao Lu and Miles Lubin. 2023. Faster first-order primal-dual methods for linear programming using restarts and sharpness. Mathematical Programming.","DOI":"10.1007\/s10107-022-01901-9"},{"key":"e_1_3_2_1_8_1","volume-title":"International Conference on Machine Learning.","author":"Axiotis Kyriakos","year":"2021","unstructured":"Kyriakos Axiotis, Adam Karczmarz, Anish Mukherjee, Piotr Sankowski, and Adrian Vladu. 2021. Decomposable submodular function minimization via maximum flow. In International Conference on Machine Learning."},{"key":"e_1_3_2_1_9_1","volume-title":"Conference on Learning Theory.","author":"Balcan Maria Florina","year":"2012","unstructured":"Maria Florina Balcan, Avrim Blum, Shai Fine, and Yishay Mansour. 2012. Distributed learning, communication complexity and privacy. In Conference on Learning Theory."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"volume-title":"Parallel and distributed computation: numerical methods","author":"Bertsekas Dimitri","key":"e_1_3_2_1_11_1","unstructured":"Dimitri Bertsekas and John Tsitsiklis. 2015. Parallel and distributed computation: numerical methods. Athena Scientific."},{"key":"e_1_3_2_1_12_1","volume-title":"Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms.","author":"Bhojanapalli Srinadh","year":"2014","unstructured":"Srinadh Bhojanapalli, Prateek Jain, and Sujay Sanghavi. 2014. Tighter low-rank approximation via sampling the leveraged element. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms."},{"key":"e_1_3_2_1_13_1","volume-title":"Proceedings of machine learning and systems.","author":"Bonawitz Keith","year":"2019","unstructured":"Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Kone\u010dn\u1ef3, Stefano Mazzocchi, and Brendan McMahan. 2019. Towards federated learning at scale: System design. Proceedings of machine learning and systems."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897646"},{"key":"e_1_3_2_1_15_1","unstructured":"Stephen P. Boyd Neal Parikh Eric Chu Borja Peleato and Jonathan Eckstein. 2011. Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers. Foundations and Trends in Machine Learning."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976496.1"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Mark Braverman and Ankit Garg. 2014. Public vs private coin in bounded-round information. In International Colloquium on Automata Languages and Programming.","DOI":"10.1007\/978-3-662-43948-7_42"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/201019.201036"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688073.2688113"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746567"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Jeffrey Dean and Sanjay Ghemawat. 2008. MapReduce: simplified data processing on large clusters. Commun. ACM.","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_3_2_1_22_1","article-title":"Optimal distributed online prediction using mini-batches","author":"Dekel Ofer","year":"2012","unstructured":"Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, and Lin Xiao. 2012. Optimal distributed online prediction using mini-batches. Journal of Machine Learning Research.","journal-title":"Journal of Machine Learning Research."},{"key":"e_1_3_2_1_23_1","unstructured":"Jelena Diakonikolas Chenghui Li Swati Padmanabhan and Chaobing Song. 2022. A Fast Scale-Invariant Algorithm for Non-negative Least Squares with Non-negative Data. Advances in Neural Information Processing Systems."},{"key":"e_1_3_2_1_24_1","unstructured":"Huaian Diao Rajesh Jayaram Zhao Song Wen Sun and David Woodruff. 2019. Optimal sketching for kronecker product regression and low rank approximation. Advances in neural information processing systems."},{"key":"e_1_3_2_1_25_1","volume-title":"Swati Padmanabhan, and Guanghao Ye.","author":"Dong Sally","year":"2022","unstructured":"Sally Dong, Haotian Jiang, Yin Tat Lee, Swati Padmanabhan, and Guanghao Ye. 2022. Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity. Advances in Neural Information Processing Systems, 35 (2022)."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2011.2161027"},{"key":"e_1_3_2_1_27_1","volume-title":"Decomposable submodular function minimization: discrete and continuous. Advances in neural information processing systems, 30","author":"Ene Alina","year":"2017","unstructured":"Alina Ene, Huy Nguyen, and L\u00e1szl\u00f3 A V\u00e9gh. 2017. Decomposable submodular function minimization: discrete and continuous. Advances in neural information processing systems, 30 (2017)."},{"key":"e_1_3_2_1_28_1","unstructured":"Matthew Fahrbach Gang Fu and Mehrdad Ghadiri. 2022. Subquadratic kronecker regression with applications to tensor decomposition. Advances in Neural Information Processing Systems."},{"key":"e_1_3_2_1_29_1","series-title":"SIAM J. Comput..","volume-title":"PCA, and Projective Clustering","author":"Feldman Dan","unstructured":"Dan Feldman, Melanie Schmidt, and Christian Sohler. 2020. Turning Big Data Into Tiny Data: Constant-Size Coresets for k-Means, PCA, and Projective Clustering. SIAM J. Comput.."},{"key":"e_1_3_2_1_30_1","volume-title":"International Conference on Machine Learning.","author":"Frostig Roy","year":"2015","unstructured":"Roy Frostig, Rong Ge, Sham Kakade, and Aaron Sidford. 2015. Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization. In International Conference on Machine Learning."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Mehrdad Ghadiri Richard Peng and Santosh Vempala. 2023. The Bit Complexity of Efficient Continuous Optimization. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS). https:\/\/www.computer.org\/csdl\/proceedings-article\/focs\/2023\/189400c059\/1T9796LmQ80","DOI":"10.1109\/FOCS57990.2023.00125"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Li Huang Yifeng Yin Zeng Fu Shifa Zhang Hao Deng and Dianbo Liu. 2020. LoAdaBoost: Loss-based AdaBoost federated machine learning with reduced computational complexity on IID and non-IID intensive care data. Plos one.","DOI":"10.1371\/journal.pone.0230706"},{"key":"e_1_3_2_1_33_1","article-title":"Coordination of groups of mobile autonomous agents using nearest neighbor rules","author":"Jadbabaie Ali","year":"2003","unstructured":"Ali Jadbabaie, Jie Lin, and A Stephen Morse. 2003. Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Transactions on automatic control.","journal-title":"IEEE Transactions on automatic control."},{"key":"e_1_3_2_1_34_1","unstructured":"Stefanie Jegelka Francis Bach and Suvrit Sra. 2013. Reflection methods for user-friendly submodular optimization. Advances in Neural Information Processing Systems."},{"key":"e_1_3_2_1_35_1","series-title":"SIAM Journal on Optimization","volume-title":"A randomized incremental subgradient method for distributed optimization in networked systems","author":"Johansson Bj\u00f6rn","unstructured":"Bj\u00f6rn Johansson, Maben Rabi, and Mikael Johansson. 2010. A randomized incremental subgradient method for distributed optimization in networked systems. SIAM Journal on Optimization."},{"key":"e_1_3_2_1_36_1","volume-title":"Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26","author":"Johnson Rie","year":"2013","unstructured":"Rie Johnson and Tong Zhang. 2013. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26 (2013)."},{"key":"e_1_3_2_1_37_1","volume-title":"Kallista Bonawitz, Zachary Charles, Graham Cormode, and Rachel Cummings.","author":"Kairouz Peter","year":"2021","unstructured":"Peter Kairouz, H Brendan McMahan, Brendan Avent, Aur\u00e9lien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, and Rachel Cummings. 2021. Advances and open problems in federated learning. Foundations and Trends\u00ae in Machine Learning, 14 (2021)."},{"key":"e_1_3_2_1_38_1","volume-title":"Conference on Learning Theory.","author":"Kannan Ravi","year":"2014","unstructured":"Ravi Kannan, Santosh Vempala, and David Woodruff. 2014. Principal component analysis and higher correlations for distributed data. In Conference on Learning Theory."},{"key":"e_1_3_2_1_39_1","volume-title":"Fast decomposable submodular function minimization using constrained total variation. Advances in Neural Information Processing Systems, 32","author":"Kumar Karri Senanayak Sesh","year":"2019","unstructured":"Senanayak Sesh Kumar Karri, Francis Bach, and Thomas Pock. 2019. Fast decomposable submodular function minimization using constrained total variation. Advances in Neural Information Processing Systems, 32 (2019)."},{"key":"e_1_3_2_1_40_1","volume-title":"Ananda Theertha Suresh, and Dave Bacon","author":"Kone\u010dn\u1ef3 Jakub","year":"2016","unstructured":"Jakub Kone\u010dn\u1ef3, H Brendan McMahan, Felix X Yu, Peter Richt\u00e1rik, Ananda Theertha Suresh, and Dave Bacon. 2016. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05492."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897640"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.52"},{"key":"e_1_3_2_1_43_1","volume-title":"Efficient Inverse Maintenance and Faster Algorithms for Linear Programming. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015.","author":"Lee Yin Tat","year":"2015","unstructured":"Yin Tat Lee and Aaron Sidford. 2015. Efficient Inverse Maintenance and Faster Algorithms for Linear Programming. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015."},{"key":"e_1_3_2_1_44_1","volume-title":"Conference On Learning Theory.","author":"Lee Yin Tat","year":"2018","unstructured":"Yin Tat Lee, Aaron Sidford, and Santosh S Vempala. 2018. Efficient convex optimization with membership oracles. In Conference On Learning Theory."},{"key":"e_1_3_2_1_45_1","volume-title":"Charles L Ortiz Jr, and Milind Tambe","author":"Lesser Victor","year":"2003","unstructured":"Victor Lesser, Charles L Ortiz Jr, and Milind Tambe. 2003. Distributed sensor networks: A multiagent perspective. Springer Science & Business Media."},{"key":"e_1_3_2_1_46_1","volume-title":"The Thirty Sixth Annual Conference on Learning Theory.","author":"Li Yi","year":"2023","unstructured":"Yi Li, Honghao Lin, and David Woodruff. 2023. \u2113 _p-Regression in the Arbitrary Partition Model of Communication. In The Thirty Sixth Annual Conference on Learning Theory."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-45174-8_34"},{"key":"e_1_3_2_1_48_1","series-title":"SIAM J. Comput","volume-title":"Tight bounds for the subspace sketch problem with applications","author":"Li Yi","unstructured":"Yi Li, Ruosong Wang, and David P Woodruff. 2021. Tight bounds for the subspace sketch problem with applications. SIAM J. Comput.."},{"key":"e_1_3_2_1_49_1","unstructured":"Hongzhou Lin Julien Mairal and Zaid Harchaoui. 2015. A universal catalyst for first-order optimization. Advances in neural information processing systems."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384331"},{"key":"e_1_3_2_1_51_1","unstructured":"Naren Sarayu Manoj and Max Ovsiankin. 2023. The Change-of-Measure Method Block Lewis Weights and Approximating Matrix Block Norms. arxiv:2311.10013."},{"key":"e_1_3_2_1_52_1","unstructured":"Brendan McMahan Eider Moore Daniel Ramage Seth Hampson and Blaise Aguera y Arcas. 2017. Communication-efficient learning of deep networks from decentralized data. In Artificial Intelligence and Statistics."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"crossref","unstructured":"Angelia Nedi\u0107 Dimitri P Bertsekas and Vivek S Borkar. 2001. Distributed asynchronous incremental subgradient methods. Studies in Computational Mathematics.","DOI":"10.1016\/S1570-579X(01)80023-9"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2008.2009515"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"crossref","unstructured":"Yurii Nesterov and Arkadii Nemirovskii. 1994. Interior-point polynomial algorithms in convex programming. SIAM.","DOI":"10.1137\/1.9781611970791"},{"key":"e_1_3_2_1_56_1","unstructured":"Yurii E Nesterov. 1983. A method for solving the convex programming problem with convergence rate O(1\/k^2). In Dokl. akad. nauk Sssr. 269."},{"key":"e_1_3_2_1_57_1","volume-title":"On the convergence rate of decomposable submodular function minimization. Advances in Neural Information Processing Systems, 27","author":"Nishihara Robert","year":"2014","unstructured":"Robert Nishihara, Stefanie Jegelka, and Michael I Jordan. 2014. On the convergence rate of decomposable submodular function minimization. Advances in Neural Information Processing Systems, 27 (2014)."},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-10928-8_22"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.31"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"crossref","unstructured":"Alessandro Perelli and Martin S Andersen. 2021. Regularization by denoising sub-sampled Newton method for spectral CT multi-material decomposition. Philosophical Transactions of the Royal Society A.","DOI":"10.1098\/rsta.2020.0191"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v36i9.21275"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993642"},{"key":"e_1_3_2_1_63_1","unstructured":"Amirhossein Reisizadeh Farzan Farnia Ramtin Pedarsani and Ali Jadbabaie. 2020. Robust federated learning: The case of affine distribution shifts. Advances in Neural Information Processing Systems."},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAIT.2022.3205475"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"crossref","unstructured":"Tim Roughgarden. 2016. Communication complexity (for algorithm designers). Foundations and Trends\u00ae in Theoretical Computer Science.","DOI":"10.1561\/9781680831153"},{"key":"e_1_3_2_1_66_1","volume-title":"A stochastic gradient method with an exponential convergence rate for finite training sets. Advances in neural information processing systems, 25","author":"Roux Nicolas","year":"2012","unstructured":"Nicolas Roux, Mark Schmidt, and Francis Bach. 2012. A stochastic gradient method with an exponential convergence rate for finite training sets. Advances in neural information processing systems, 25 (2012)."},{"key":"e_1_3_2_1_67_1","article-title":"Distributed federated learning for ultra-reliable low-latency vehicular communications","author":"Samarakoon Sumudu","year":"2019","unstructured":"Sumudu Samarakoon, Mehdi Bennis, Walid Saad, and M\u00e9rouane Debbah. 2019. Distributed federated learning for ultra-reliable low-latency vehicular communications. IEEE Transactions on Communications.","journal-title":"IEEE Transactions on Communications."},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"crossref","unstructured":"Ali H Sayed. 2014. Adaptation learning and optimization over networks. Foundations and Trends\u00ae in Machine Learning.","DOI":"10.1561\/9781601988515"},{"key":"e_1_3_2_1_69_1","article-title":"Stochastic dual coordinate ascent methods for regularized loss minimization","volume":"14","author":"Shalev-Shwartz Shai","year":"2013","unstructured":"Shai Shalev-Shwartz and Tong Zhang. 2013. Stochastic dual coordinate ascent methods for regularized loss minimization.. Journal of Machine Learning Research, 14, 2 (2013).","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_1_70_1","volume-title":"International conference on machine learning.","author":"Shamir Ohad","year":"2014","unstructured":"Ohad Shamir, Nati Srebro, and Tong Zhang. 2014. Communication-efficient distributed optimization using an approximate newton-type method. In International conference on machine learning."},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29344-3_54"},{"key":"e_1_3_2_1_72_1","article-title":"Distributed stochastic subgradient projection algorithms for convex optimization","author":"Ram S Sundhar","year":"2010","unstructured":"S Sundhar Ram, Angelia Nedi\u0107, and Venugopal V Veeravalli. 2010. Distributed stochastic subgradient projection algorithms for convex optimization. Journal of optimization theory and applications.","journal-title":"Journal of optimization theory and applications."},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63500"},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384309"},{"key":"e_1_3_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.106"},{"key":"e_1_3_2_1_77_1","unstructured":"David P Woodruff. 2014. Sketching as a tool for numerical linear algebra. Foundations and Trends\u00ae in Theoretical Computer Science."},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2006.08.010"},{"key":"e_1_3_2_1_79_1","first-page":"14774","article-title":"Computational Guarantees for Restarted PDHG for LP based on","volume":"2312","author":"Xiong Zikai","year":"2023","unstructured":"Zikai Xiong and Robert Michael Freund. 2023. Computational Guarantees for Restarted PDHG for LP based on\" Limiting Error Ratios\" and LP Sharpness. arXiv preprint arXiv:2312.14774.","journal-title":"Limiting Error Ratios\" and LP Sharpness. arXiv preprint arXiv"},{"key":"e_1_3_2_1_80_1","unstructured":"Peng Xu Jiyan Yang Fred Roosta Christopher R\u00e9 and Michael W Mahoney. 2016. Sub-sampled Newton methods with non-uniform sampling. Advances in Neural Information Processing Systems."},{"key":"e_1_3_2_1_81_1","volume-title":"International conference on machine learning.","author":"Zhang Yuchen","year":"2015","unstructured":"Yuchen Zhang and Xiao Lin. 2015. DiSCO: Distributed optimization for self-concordant empirical loss. In International conference on machine learning."},{"key":"e_1_3_2_1_82_1","volume-title":"International Conference on Machine Learning.","author":"Zhang Yuchen","year":"2015","unstructured":"Yuchen Zhang and Xiao Lin. 2015. Stochastic primal-dual coordinate method for regularized empirical risk minimization. In International Conference on Machine Learning."}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Vancouver BC Canada","acronym":"STOC '24"},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649787","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649787","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:52Z","timestamp":1750291432000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649787"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":81,"alternative-id":["10.1145\/3618260.3649787","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649787","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}