Polynomial Optimization Methods for Matrix Factorization

Po-Wei Wang, Chun-Liang Li, J. Zico KolterAAAI 2017 · OpenReview

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$)?

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.

Convergence on Netflix and Yahoo Music datasets

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.

Parallel scalability of polyMF-SS

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

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.
BibTeX
@inproceedings{wang2017polynomial,
  author = {Po-Wei Wang and Chun-Liang Li and J. Zico Kolter},
  title = {{Polynomial Optimization Methods for Matrix Factorization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  url = {https://openreview.net/forum?id=HJW9ZRxOZS},
}
Figure