Abstract
Many problems in machine learning can be reduced to learning a low-rank positive semidefinite (PSD) matrix $Z$, which typically requires solving a Semidefinite Program (SDP). While SDPs are convex, classical solvers like interior-point methods are computationally prohibitive for large-scale datasets. To address this, the Burer-Monteiro method reformulates the SDP as a nonconvex problem using quadratic factorization ($Z = XX^\top$). However, this approach often loses the problem's inherent structure during optimization, resulting in quartic objectives that are difficult to optimize. In this paper, we propose a novel surrogate: converting the SDP into a biconvex problem via bilinear factorization ($Z = XY^\top$) while incorporating a penalty term $\frac{\gamma}{2}\|X-Y\|_F^2$ to ensure $X$ and $Y$ converge. We provide a theoretical bound for the penalty parameter $\gamma$ under $L$-Lipschitz smoothness and $\sigma$-strong biconvexity, proving that stationary points of our bilinear model are equivalent to those of the Burer-Monteiro model when $\gamma > \frac{1}{4}(L-\sigma)_+$. Experiments on Nonparametric Kernel Learning and Colored Maximum Variance Unfolding demonstrate that our method is as effective as state-of-the-art solvers while offering superior scalability.
Introduction
Semidefinite Programming (SDP) is a fundamental tool in modern machine learning, underpinning applications such as matrix completion, sparse Principal Component Analysis (PCA), clustering, and manifold learning. Despite their theoretical elegance, SDPs suffer from a significant practical drawback: standard convex optimization solvers scale poorly. As the dimensionality of the data increases, the computational cost of maintaining the PSD constraint becomes a bottleneck.
To mitigate this, researchers frequently turn to the Burer-Monteiro factorization, which exploits the low-rank nature of many ML solutions by substituting the $n \times n$ matrix $Z$ with $XX^\top$, where $X$ is $n \times r$ and $r \ll n$. While this reduces the number of variables, it introduces a new set of challenges. Specifically, if the original objective function was quadratic, the factorized objective becomes a quartic (fourth-degree) function. This transformation makes the optimization landscape more complex, often requiring expensive line searches to find stable step sizes and leading to slower convergence.
The Bilinear Factorization Approach
We propose a "middle ground" between the original convex SDP and the nonconvex Burer-Monteiro factorization. Our approach utilizes bilinear factorization, representing the target matrix as $Z = XY^\top$. To maintain the requirement that $Z$ must be symmetric and positive semidefinite, we introduce a penalty term to the objective function:
$$\min_{X,Y} f(XY^\top) + \frac{\gamma}{2}\|X - Y\|_F^2$$
This formulation offers several distinct advantages:
- Biconvexity: The problem is biconvex with respect to $X$ and $Y$. When one variable is fixed, the sub-problem for the other remains convex. This allows us to leverage efficient alternating optimization strategies.
- Structure Preservation: Unlike the quartic objective in the $XX^\top$ model, the sub-problems in our bilinear model remain quadratic (assuming the original $f$ was quadratic). This allows for the calculation of analytical step sizes, removing the need for iterative line searches and significantly reducing the computational overhead per iteration.
- Finite Penalty Bound: A common concern with penalty methods is the need for the penalty parameter $\gamma$ to approach infinity to reach a valid solution. We provide a theoretical guarantee that a finite $\gamma$ is sufficient. Specifically, if $\gamma > \frac{1}{4}(L - \sigma)_+$, the stationary points of the bilinear model align with those of the Burer-Monteiro model.
Alternating Accelerated Gradient Descent (AAGD)
To solve this biconvex surrogate, we introduce the Alternating Accelerated Gradient Descent (AAGD) algorithm. AAGD incorporates Nesterov-style acceleration into the alternating updates of $X$ and $Y$. Because the sub-problems are quadratic, we can compute the optimal step size $\eta$ at each step using a simple closed-form expression, ensuring rapid and stable descent. The complexity per iteration is $O(nr)$, making it highly suitable for large-scale applications where the rank $r$ is small.
Experimental Results
We evaluated the performance of AAGD against several baselines, including Frank-Wolfe (FW), standard Accelerated Gradient Descent (AGD), and Interior Point methods (SQLP), across two primary tasks:
Nonparametric Kernel Learning (NPKL)
Using the Adult datasets (ranging from 1,600 to 32,500 samples), we observed that AAGD consistently outperformed other first-order methods in speed. For instance, on the $a9a$ dataset, AAGD reached the target objective in 389 seconds, whereas AGD required 529 seconds and Frank-Wolfe exceeded 2,134 seconds.
Colored Maximum Variance Unfolding (CMVU)
On manifold learning tasks using USPS Digits and Newsgroups 20 datasets, AAGD demonstrated high accuracy. In clustering evaluations using the Rand Index, AAGD achieved results identical to or better than the more computationally intensive baselines, proving that the speed gains do not come at the cost of solution quality.
Conclusion
By reframing the SDP problem as a biconvex bilinear factorization with a proximity penalty, we provide a scalable and theoretically grounded alternative to traditional solvers. The ability to use analytical step sizes and the existence of a finite penalty bound make this approach particularly attractive for large-scale machine learning. Future work will focus on automating rank selection and extending the framework to handle more complex constraints via Augmented Lagrangian methods.
Summary updated