Improving the Bit Complexity of Communication for Distributed Convex Optimization
STOC ’24, June 24–28, 2024, Vancouver, BC, Canada
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
ACM|Proceedings of the 56th Annual ACM Symposium on Theory of Computing
2024
|
| Online Access: | https://hdl.handle.net/1721.1/155725 |
| _version_ | 1824457958939951104 |
|---|---|
| author | Ghadiri, Mehrdad Lee, Yin Tat Padmanabhan, Swati Swartworth, William Woodruff, David P. Ye, Guanghao |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Ghadiri, Mehrdad Lee, Yin Tat Padmanabhan, Swati Swartworth, William Woodruff, David P. Ye, Guanghao |
| author_sort | Ghadiri, Mehrdad |
| collection | MIT |
| description | STOC ’24, June 24–28, 2024, Vancouver, BC, Canada |
| first_indexed | 2024-09-23T09:38:31Z |
| format | Article |
| id | mit-1721.1/155725 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2025-02-19T04:18:16Z |
| publishDate | 2024 |
| publisher | ACM|Proceedings of the 56th Annual ACM Symposium on Theory of Computing |
| record_format | dspace |
| spelling | mit-1721.1/1557252024-12-23T05:33:21Z Improving the Bit Complexity of Communication for Distributed Convex Optimization Ghadiri, Mehrdad Lee, Yin Tat Padmanabhan, Swati Swartworth, William Woodruff, David P. Ye, Guanghao Sloan School of Management Massachusetts Institute of Technology. Operations Research Center STOC ’24, June 24–28, 2024, Vancouver, BC, Canada We consider the communication complexity of some fundamental convex optimization problems in the point-to-point (coordinator) and blackboard communication models. We strengthen known bounds for approximately solving linear regression, p-norm regression (for 1≤ p≤ 2), linear programming, minimizing the sum of finitely many convex nonsmooth functions with varying supports, and low rank approximation; for a number of these fundamental problems our bounds are nearly optimal, as proven by our lower bounds. Among our techniques, we use the notion of block leverage scores, which have been relatively unexplored in this context, as well as dropping all but the “middle” bits in Richardson-style algorithms. We also introduce a new communication problem for accurately approximating inner products and establish a lower bound using the spherical Radon transform. Our lower bound can be used to show the first separation of linear programming and linear systems in the distributed model when the number of constraints is polynomial, addressing an open question in prior work. 2024-07-19T18:02:22Z 2024-07-19T18:02:22Z 2024-06-10 2024-07-01T07:52:49Z Article http://purl.org/eprint/type/ConferencePaper 979-8-4007-0383-6 https://hdl.handle.net/1721.1/155725 Ghadiri, Mehrdad, Lee, Yin Tat, Padmanabhan, Swati, Swartworth, William, Woodruff, David P. et al. 2024. "Improving the Bit Complexity of Communication for Distributed Convex Optimization." PUBLISHER_CC en 10.1145/3618260.3649787 Creative Commons Attribution-Noncommercial-ShareAlike https://creativecommons.org/licenses/by-sa/4.0/ The author(s) application/pdf ACM|Proceedings of the 56th Annual ACM Symposium on Theory of Computing Association for Computing Machinery |
| spellingShingle | Ghadiri, Mehrdad Lee, Yin Tat Padmanabhan, Swati Swartworth, William Woodruff, David P. Ye, Guanghao Improving the Bit Complexity of Communication for Distributed Convex Optimization |
| title | Improving the Bit Complexity of Communication for Distributed Convex Optimization |
| title_full | Improving the Bit Complexity of Communication for Distributed Convex Optimization |
| title_fullStr | Improving the Bit Complexity of Communication for Distributed Convex Optimization |
| title_full_unstemmed | Improving the Bit Complexity of Communication for Distributed Convex Optimization |
| title_short | Improving the Bit Complexity of Communication for Distributed Convex Optimization |
| title_sort | improving the bit complexity of communication for distributed convex optimization |
| url | https://hdl.handle.net/1721.1/155725 |
| work_keys_str_mv | AT ghadirimehrdad improvingthebitcomplexityofcommunicationfordistributedconvexoptimization AT leeyintat improvingthebitcomplexityofcommunicationfordistributedconvexoptimization AT padmanabhanswati improvingthebitcomplexityofcommunicationfordistributedconvexoptimization AT swartworthwilliam improvingthebitcomplexityofcommunicationfordistributedconvexoptimization AT woodruffdavidp improvingthebitcomplexityofcommunicationfordistributedconvexoptimization AT yeguanghao improvingthebitcomplexityofcommunicationfordistributedconvexoptimization |