Name
Abstract | ||
|---|---|---|
We give the first approximation algorithm for mixed packing and covering semidefinite programs (SDPs) with polylogarithmic dependence on width. Mixed packing and covering SDPs constitute a fundamental algorithmic primitive with applications in combinatorial optimization, robust learning, and quantum complexity. The current approximate solvers for positive semidefinite programming can handle only pure packing instances, and technical hurdles prevent their generalization to a wider class of positive instances. For a given multiplicative accuracy of є, our algorithm takes O(log3(ndρ) · є−3) parallelizable iterations, where n, d are the problem dimensions and ρ is a width parameter of the instance, generalizing or improving all previous parallel algorithms in the positive linear and semidefinite programming literature. When specialized to pure packing SDPs, our algorithm’s iteration complexity is O(log2 (nd) · є−2), a slight improvement and derandomization of the state-of-the-art due to Allen-Zhu et. al. ’16, Peng et. al. ’16, and Wang et. al. ’15. For several common structured instances, the iterations of our algorithm run in nearly-linear time. In doing so, we give matrix analytic techniques to overcome obstacles that have stymied prior approaches to this problem, as stated in Peng et. al. ’16 and Mahoney et. al. ’16. Crucial to our analysis are a simplification of existing algorithms for mixed positive linear programs, achieved by removing an asymmetry from modifying covering constraints, and a suite of matrix inequalities with proofs based on analyzing the Schur complements of matrices in a higher dimension. We hope that our algorithm and techniques open the door to improved solvers for positive semidefinite programming and its applications.
|
Year | DOI | Venue |
|---|---|---|
2020 | 10.1145/3357713.3384338 | STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing
Chicago
IL
USA
June, 2020 |
Keywords | DocType | ISSN |
semidefinite programming, mixed packing and covering, approximation algorithm, parallel algorithm, width-independent algorithm | Conference | 0737-8017 |
ISBN | Citations | PageRank |
978-1-4503-6979-4 | 1 | 0.35 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jambulapati Arun | 1 | 1 | 0.35 |
| Yin Tat Lee | 2 | 396 | 36.67 |
| Jerry Li | 3 | 229 | 22.67 |
| Swati Padmanabhan | 4 | 5 | 2.08 |
| Kevin Tian | 5 | 3 | 6.47 |