A biconvex optimization for solving semidefinite programs via bilinear factorization
This work addresses scalability issues for researchers and practitioners using SDPs in machine learning, though it appears incremental as it builds on the Burer-Monteiro method with a modified factorization.
The paper tackles the computational expense of solving large-scale semidefinite programs (SDPs) in machine learning by proposing a biconvex optimization method via bilinear factorization, which is shown to be effective and equivalent to existing methods under certain theoretical conditions.
Many problems in machine learning can be reduced to learning a low-rank positive semidefinite matrix (denoted as $Z$), which encounters semidefinite program (SDP). Existing SDP solvers by classical convex optimization are expensive to solve large-scale problems. Employing the low rank of solution, Burer-Monteiro's method reformulated SDP as a nonconvex problem via the {\emph{quadratic}} factorization ($Z$ as $XX^\top$). However, this would lose the structure of problem in optimization. In this paper, we propose to convert SDP into a biconvex problem via the {\emph{bilinear}} factorization ($Z$ as $XY^\top$), and while adding the term $\frac{\g}{2}\normfs{X-Y}$ to penalize the difference of $X$ and $Y$. Thus, the biconvex structure (w.r.t. $X$ and $Y$) can be exploited naturally in optimization. As a theoretical result, we provide a bound to the penalty parameter $\g$ under the assumption of $L$-Lipschitz smoothness and $σ$-strongly biconvexity, such that, at stationary points, the proposed bilinear factorization is equivalent to Burer-Monteiro's factorization when the bound is arrived, that is $\g>\frac{1}{4}(L-σ)_+$. Our proposal opens up a new way to surrogate SDP by biconvex program. Experiments on two SDP-related applications demonstrate that the proposed method is effective as the state-of-the-art.