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

arXiv: https://arxiv.org/abs/2309.05135 · HTML: https://mlsanity.com/paper/2309.05135/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Sep 2023.

## Built on by (most cited first, 5 of 5)

- [How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation](https://mlsanity.com/paper/2310.04064/) (2023)
- [Bypassing the Exponential Dependency: Looped Transformers Efficiently Learn In-context by Multi-step Gradient Descent](https://mlsanity.com/paper/2410.11268/) (2024)
- [HSR-Enhanced Sparse Attention Acceleration](https://mlsanity.com/paper/2410.10165/) (2024)
- [Accept More, Reject Less: Reducing up to 19% Unnecessary Desk-Rejections over 11 Years of ICLR Data](https://mlsanity.com/paper/2506.20141/) (2025)
- [Towards Sampling Data Structures for Tensor Products in Turnstile Streams](https://mlsanity.com/paper/2510.03678/) (2025)

## Abstract (arXiv)

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).