Abstract: Many machine learning problems can be reduced to learning a low-rank positive semidefinite matrix (denoted as $Z$), which encounters semidefinite program (SDP). Existing SDP solvers are often expensive for large-scale learning. To avoid directly solving SDP, some works convert SDP into a nonconvex program by factorizing $Z$ quadraticly as $XX^\top$. However, this would bring higher-order nonlinearity, resulting in scarcity of structure in subsequent optimization. In this paper, we propose a novel surrogate for SDP-related learning, in which the structure of subproblem is exploited. More specifically, we surrogate unconstrained SDP by a biconvex problem, through factorizing $Z$ bilinearly as $XY^\top$ and using a Courant penalty to penalize the difference of $X$ and $Y$, in which the resultant subproblems are convex. Furthermore, we provide a theoretical bound for the associated penalty parameter under the assumption that the subobjective function is $L$-Lipschitz-smooth and $\sigma$-strongly convex, such that the proposed surrogate will solve the original SDP when the penalty parameter is larger than this bound, that is $\gamma > \frac{1}{4}(L-\sigma)$. Experiments on two SDP-related machine learning applications demonstrate that the proposed algorithm is as accurate as the state-of-the-art, but is faster on large-scale learning.
Introduction
Semidefinite Programming (SDP) is a cornerstone of modern machine learning, utilized in diverse applications ranging from clustering and matrix completion to dimensionality reduction. Despite their utility, standard SDP solvers, such as interior-point methods, suffer from poor scalability—often scaling at $O(n^3)$ or higher. This computational bottleneck makes them impractical for the large-scale datasets common in contemporary research.
To address this, researchers frequently employ the Burer-Monteiro method, which factorizes the target matrix $Z$ into $XX^\top$. While this removes the expensive positive semidefinite (PSD) constraint, it introduces a significant optimization challenge: if the original objective function was quadratic, the factorized version becomes a fourth-order (quartic) polynomial. This high-order nonlinearity destroys the mathematical structure of the original problem and makes finding optimal stepsizes difficult.
The Bilinear Factorization Surrogate
This paper proposes a structural rethink of low-rank SDP learning. Instead of the traditional quadratic factorization, the authors introduce a bilinear factorization surrogate. The target matrix $Z$ is factorized as $XY^\top$, and a Courant penalty term is added to the objective to ensure that $X$ and $Y$ remain close to each other:
$$ \min_{X,Y} f(XY^\top) + \frac{\gamma}{2} \|X - Y\|_F^2 $$
The Advantage of Biconvexity
By decoupling the variables into $X$ and $Y$, the problem is transformed into a biconvex program. In this framework, if one variable (e.g., $Y$) is held constant, the resulting subproblem for $X$ is convex. This structural preservation is the "secret sauce" of the method, as it allows the use of efficient alternating optimization techniques that are far more robust than those available for general nonconvex quartic functions.
Theoretical Equivalence
A primary concern with penalty-based methods is the requirement for the penalty parameter $\gamma$ to approach infinity to ensure convergence to the original problem's solution, which often leads to numerical instability. The authors provide a rigorous theoretical bound to mitigate this. They prove that if $\gamma > \frac{1}{4}(L - \sigma)$ (where $L$ represents the smoothness and $\sigma$ represents the strong convexity of the objective), the stationary points of the bilinear surrogate are equivalent to those of the original quadratic factorization. This ensures that a finite, stable $\gamma$ is sufficient for accurate learning.
Optimization: Alternating Accelerated Gradient Descent
To solve the biconvex problem, the paper introduces Alternating Accelerated Gradient Descent (AAGD). This algorithm functions as a biconvex adaptation of the popular FISTA (Fast Iterative Shrinkage-Thresholding Algorithm).
A key advantage of AAGD in this context is the ability to calculate analytical stepsizes. Because the subproblems are quadratic, the algorithm can determine the optimal stepsize in every iteration through a closed-form calculation, entirely bypassing the need for computationally expensive line searches.
Experimental Evaluation
The proposed method was evaluated against state-of-the-art solvers on two primary machine learning applications:
- Nonparametric Kernel Learning (NPKL): Conducted using the Adult datasets ($a1a$ through $a9a$), with sample sizes up to 32,500.
- Colored Maximum Variance Unfolding (CMVU): Conducted using USPS Digits and Newsgroups 20 benchmark datasets.
Key Findings
- Superior Speed: In NPKL experiments, AAGD consistently outperformed competitors. For the largest dataset ($a9a$), AAGD completed the task in approximately 390 seconds. In contrast, the standard Frank-Wolfe (FW) algorithm required over 2,100 seconds, and Accelerated Gradient Descent (AGD) on the quadratic form took 529 seconds.
- Maintained Accuracy: Despite the increase in speed, AAGD achieved accuracy levels (measured by Rand Index for clustering) identical to those of high-precision solvers like L-BFGS and interior-point methods (SQLP).
- Scalability: While interior-point methods became prohibitively slow or failed as sample sizes increased, AAGD scaled gracefully, maintaining a per-iteration complexity of $O(nr)$.
Conclusion
By shifting from quadratic to bilinear factorization, this work provides a more efficient optimization path for low-rank SDPs without sacrificing theoretical rigor. The combination of biconvex structure, finite penalty bounds, and analytical stepsizes allows for a solver that is both faster and more numerically stable than traditional Burer-Monteiro approaches. Future work may extend this bilinear framework to more complex constrained SDPs using augmented Lagrangian schemes or explore second-order optimization methods to further accelerate convergence.
Summary updated