论文标题
积极的半决赛编程：混合，平行和与宽度无关
Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent
论文作者
论文摘要
我们给出了与宽度依赖性的混合填料和覆盖半标准程序（SDP）的第一个近似算法（SDPS）。混合填料和覆盖SDP构成了一种基本算法原始的原始性，在组合优化，健壮学习和量子复杂性中的最新应用。当前用于正半数编程的近似求解器只能处理纯包装实例，而技术障碍则阻止了它们对更广泛的积极实例的概括。 For a given multiplicative accuracy of $ε$, our algorithm takes $O(\log^3(ndρ) \cdot ε^{-3})$ parallelizable iterations, where $n$, $d$ are dimensions of the problem and $ρ$ is a width parameter of the instance, generalizing or improving all previous parallel algorithms in the positive linear and semidefinite programming literature.当专门针对纯包装SDP时，我们的算法的迭代复杂性为$ O（\ log^2（nd）\ cdotε^{ - 2}）$，对先进的先进的略有改进和降低（Allen-Zhu等人（Allen-Zhu等）（Allen-Zhu等。对于应用中常见的各种结构化实例，我们的算法的迭代在几乎线的时间内运行。 在此过程中，我们为克服障碍的矩阵分析技术提供了阻碍了对这种开放问题的先前方法的障碍（Peng etal。16，Mahoney等人的16）。对我们的分析至关重要的是对混合正线性程序的现有算法的简化，这是通过删除通过修改覆盖约束而引起的不对称性和一套基于矩阵不平等的不平衡来实现的，其证明是基于分析较高尺寸中矩阵的Schur互补的证明。我们希望我们的算法和技术都为改进求解器及其应用及其应用打开了求解器的大门。
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 recent 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(\log^3(ndρ) \cdot ε^{-3})$ parallelizable iterations, where $n$, $d$ are dimensions of the problem 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(\log^2 (nd) \cdot ε^{-2})$, a slight improvement and derandomization of the state-of-the-art (Allen-Zhu et. al. '16, Peng et. al. '16, Wang et. al. '15). For a wide variety of structured instances commonly found in applications, the iterations of our algorithm run in nearly-linear time. In doing so, we give matrix analytic techniques for overcoming obstacles that have stymied prior approaches to this open problem, as stated in past works (Peng et. al. '16, Mahoney et. al. '16). Crucial to our analysis are a simplification of existing algorithms for mixed positive linear programs, achieved by removing an asymmetry caused by modifying covering constraints, and a suite of matrix inequalities whose proofs are based on analyzing the Schur complements of matrices in a higher dimension. We hope that both our algorithm and techniques open the door to improved solvers for positive semidefinite programming, as well as its applications.
