Streaming Semidefinite Programs: O(√n) Passes, Small Space and Fast Runtime

We study the problem of solving semidefinite programs (SDP) in the streaming model. Specifically, m constraint matrices and a target matrix C, all of size n× n together with a vector b∈ ℝm are streamed to us one-by-one. The goal is to find a matrix X∈ ℝn× n such that langle C, Xrangle is maximized, subject to langle Ai, Xrangle=bi for all i∈ [m] and Xsucceq 0. Previous algorithmic studies of SDP primarily focus on time-efficiency, and all of them require a prohibitively large Omega(mn2) space in order to store all the constraints. Such space consumption is necessary for fast algorithms as it is the size of the input. In this work, we design an interior point method (IPM) that uses widetilde O(m2+n2) space, which is strictly sublinear in the regime ngg m. Our algorithm takes O(√ nlog(1/ε)) passes, which is standard for IPM. Moreover, when m is much smaller than n, our algorithm also matches the time complexity of the state-of-the-art SDP solvers. To achieve such a sublinear space bound, we design a novel sketching method that enables one to compute a spectral approximation to the Hessian matrix in O(m2) space. To the best of our knowledge, this is the first method that successfully applies sketching technique to improve SDP algorithm in terms of space (also time).