# Bundle Method Sketching for Low Rank Semidefinite Programming

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Nov 2019.

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

- [Some Primal-Dual Theory for Subgradient Methods for Strongly Convex Optimization](https://mlsanity.com/paper/2305.17323/) (2023)

## Abstract (arXiv)

In this paper, we show that the bundle method can be applied to solve semidefinite programming problems with a low rank solution without ever constructing a full matrix. To accomplish this, we use recent results from randomly sketching matrix optimization problems and from the analysis of bundle methods. Under strong duality and strict complementarity of SDP, our algorithm produces primal and the dual sequences converging in feasibility at a rate of tildeO(1/ε) and in optimality at a rate of tildeO(1/ε2). Moreover, our algorithm outputs a low rank representation of its approximate solution with distance to the optimal solution at most O(√ε) within tildeO(1/ε2) iterations.