Abstract
Matrix factorization is a core technique in many machine learning problems, yet also presents a nonconvex and often difficult-to-optimize problem. In this paper we present an approach based upon polynomial optimization techniques that both improves the convergence time of matrix factorization algorithms and helps them escape from local optima. Our method is based on the realization that given a joint search direction in a matrix factorization task, we can solve the "subspace search" problem (the task of jointly finding the steps to take in each direction) by solving a bivariate quartic polynomial optimization problem. We derive two methods for solving this problem based upon sum of squares moment relaxations and the Durand-Kerner method, then apply these techniques on matrix factorization to derive a direct coordinate descent approach and a method for speeding up existing approaches. On three benchmark datasets we show the method substantially improves convergence speed over state-of-the-art approaches, while also attaining lower objective value.
Introduction
Matrix Factorization (MF) is a cornerstone of modern recommendation systems, used to decompose large, sparse matrices—such as user-movie ratings—into two lower-rank matrices ($A$ and $B$). However, the objective function involves quartic (fourth-degree) terms, making it inherently non-convex. Standard solvers like Alternating Minimization (ALS) and Stochastic Gradient Descent (SGD) often stall in sub-optimal local minima.
This paper introduces PolyMF, an approach that leverages polynomial optimization to perform "exact subspace searches." By solving the joint update of $A$ and $B$ as a bivariate quartic polynomial optimization problem, PolyMF can converge significantly faster and "jump" over the ridges that trap traditional gradient-based methods.
Methodology
The core innovation lies in addressing the "subspace search" problem: given search directions for both $A$ and $B$ simultaneously, how can we find the absolute best step sizes ($\alpha, \beta$)?
Exact Subspace Search
Instead of updating one variable at a time, we optimize the objective $L(A + \alpha\Delta A, B + \beta\Delta B)$. This is a polynomial of degree 4 in two variables ($\alpha$ and $\beta$). While this could be solved using Semidefinite Programming (SDP) via "Sum of Squares" (SOS) relaxations, SDP is computationally expensive.
The Durand-Kerner Solver
The authors demonstrate that the problem can be reduced to finding the roots of a single quintic (5th-degree) polynomial. They employ the Durand-Kerner method, an iterative root-finding algorithm, to solve this in near-instant time—approximately $2 \times 10^{-6}$ seconds per solve, which is roughly 70x faster than the SDP approach.
Proposed Algorithms
- polyMF-CD: A coordinate descent approach that optimizes pairs of coefficients $(a_{ik}, b_{jk})$ simultaneously.
- polyMF-SS: A "subspace search" wrapper that takes search directions from existing fast algorithms (like CCD++) and uses the polynomial solver to find the optimal global step size.
Experimental Results
The methods were evaluated on three massive collaborative filtering benchmarks: Movielens10m (~10M ratings), Netflix (~99M ratings), and Yahoo-Music (~252M ratings).
Convergence and Accuracy
On all datasets, polyMF-SS reached a lower objective value faster than state-of-the-art methods like LIBMF (high-performance SGD) and CCD++. In the Movielens10m test, polyMF-SS escaped a local optimum where CCD++ had plateaued, eventually reaching a significantly lower loss.
Scalability
The method inherits the parallelizability of Coordinate Descent. As shown in Figure 6, polyMF-SS demonstrates near-linear speedup as more CPU cores are added, making it suitable for large-scale production environments.
Conclusion
PolyMF demonstrates that while global matrix factorization is "hard," the sub-problem of joint subspace search is a low-degree polynomial that can be solved globally and efficiently. While polyMF-CD is theoretically interesting, polyMF-SS is the practical winner for large-scale applications. Future work may extend this polynomial framework to more complex models like Tensor Factorization or Factorization Machines, which are even more prone to local optima.
Summary updated