Bundle Method Sketching for Low Rank Semidefinite Programming

2019-11-11 · Lijun Ding, Benjamin Grimmer

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/\epsilon)$ and in optimality at a rate of $\tilde{O}(1/\epsilon^2)$. Moreover, our algorithm outputs a low rank representation of its approximate solution with distance to the optimal solution at most $O(\sqrt{\epsilon})$ within $\tilde{O}(1/\epsilon^2)$ iterations.

📄 PDF Abstract BibTeX arXiv:1911.04443

Code (0)

등록된 구현이 없습니다.

Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching

2023-12-19 · Rico Angell, Andrew McCallum

While semidefinite programming (SDP) has traditionally been limited to moderate-sized problems, recent algorithms augmented with matrix sketching techniques have enabled solving larger SDPs. However, these methods achiev…

Community Detection with a Subsampled Semidefinite Program

2021-02-02 · Pedro Abdalla, Afonso S. Bandeira

Semidefinite programming is an important tool to tackle several problems in data science and signal processing, including clustering and community detection. However, semidefinite programs are often slow in practice, so …

Clustering Community Detection Stochastic Block Model

Sketching semidefinite programs for faster clustering

2020-08-10 · Dustin G. Mixon, Kaiying Xie

Many clustering problems enjoy solutions by semidefinite programming. Theoretical results in this vein frequently consider data with a planted clustering and a notion of signal strength such that the semidefinite program…

Clustering Graph Clustering

The Mixing method: low-rank coordinate descent for semidefinite programming with diagonal constraints

2017-06-01 · Po-Wei Wang, Wei-Cheng Chang, J. Zico Kolter

In this paper, we propose a low-rank coordinate descent approach to structured semidefinite programming with diagonal constraints. The approach, which we call the Mixing method, is extremely simple to implement, has no f…

Learning Word Embeddings Word Embeddings

Low-rank semidefinite programming for the MAX2SAT problem

2018-12-15 · Po-Wei Wang, J. Zico Kolter

This paper proposes a new algorithm for solving MAX2SAT problems based on combining search methods with semidefinite programming approaches. Semidefinite programming techniques are well-known as a theoretical tool for ap…