Faster and Simpler Width-Independent Parallel Algorithms for Positive Semidefinite Programming

Abstract

This paper studies the problem of finding an $(1+\epsilon )$-approximate solution to positive semidefinite programs. These are semidefinite programs in which all matrices in the constraints and objective are positive semidefinite and all scalars are non-negative. We present a simpler \NC parallel algorithm that on input with $n$ constraint matrices, requires $O(\frac{1}{{\epsilon }^3}lo{g}^{3}n)$ iterations, each of which involves only simple matrix operations and computing the trace of the product of a matrix exponential and a positive semidefinite matrix. Further, given a positive SDP in a factorized form, the total work of our algorithm is nearly-linear in the number of non-zero entries in the factorization.

Fixed a mistake in the runtime analyses of previous versions

References in corpus (1)

• A parallel approximation algorithm for mixed packing and covering semidefinite programs

Cited by in corpus (11)

• Parallel approximation of min-max problems
• Faster Algorithms for High-Dimensional Robust Covariance Estimation
• Optimal Robust Linear Regression in Nearly Linear Time
• Non-Convex Matrix Completion Against a Semi-Random Adversary
• A parallel approximation algorithm for mixed packing and covering semidefinite programs
• A Rank-1 Sketch for Matrix Multiplicative Weights
• Lecture Notes: Selected topics on robust statistical learning theory
• An SDP-Based Algorithm for Linear-Sized Spectral Sparsification
• High-Dimensional Robust Mean Estimation via Gradient Descent
• Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent
• Fast and Near-Optimal Diagonal Preconditioning