Bundle Method Sketching for Low Rank Semidefinite Programming
This work addresses computational efficiency for SDP problems in optimization and machine learning, though it appears incremental as it combines existing methods like bundle method and sketching.
The paper tackles the problem of solving semidefinite programming (SDP) problems with low-rank solutions by applying the bundle method without constructing full matrices, achieving convergence rates of $ ilde{O}(1/\epsilon)$ for feasibility and $ ilde{O}(1/\epsilon^2)$ for optimality, and outputting a low-rank solution within $ ilde{O}(1/\epsilon^2)$ iterations.
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 $\tilde{O}(1/ε)$ and in optimality at a rate of $\tilde{O}(1/ε^2)$. Moreover, our algorithm outputs a low rank representation of its approximate solution with distance to the optimal solution at most $O(\sqrtε)$ within $\tilde{O}(1/ε^2)$ iterations.