Accelerated Factored Gradient Descent for Low-Rank Matrix Factorization

Dongruo Zhou, Yuan Cao, Quanquan GuAISTATS 2020 · OpenReview

Abstract

We study the low-rank matrix estimation problem, where the objective function $\mathcal{L}(\mathbf{M})$ is defined over the space of positive semidefinite matrices with rank less than or equal to $r$. A fast approach to solve this problem is matrix factorization, which reparameterizes $\mathbf{M}$ as $\mathbf{U}\mathbf{U}^\top$ and performs gradient descent on $\mathbf{U}$ directly. Since the resulting problem is nonconvex, adapting Nesterov’s acceleration has been a long-standing challenge. We propose a novel Accelerated Factored Gradient Descent (AFGD) method that restricts iterates to a special convex set. AFGD achieves superior iteration and computational complexity compared to state-of-the-art algorithms, as corroborated by our theoretical analysis and experimental results.

Introduction

Low-rank matrix estimation is a cornerstone of modern machine learning, powering applications from recommendation systems to signal processing. The primary challenge lies in the trade-off between speed and reliability. While convex relaxation methods (e.g., nuclear norm) are theoretically sound, they require a Singular Value Decomposition (SVD) at every step, costing $O(d^3)$—prohibitive for large-scale data.

Nonconvex factorization (the Burer-Monteiro approach) reparameterizes the matrix as $UU^\top$, reducing per-iteration costs to $O(dr^2)$. However, adapting Nesterov’s Accelerated Gradient Descent (AGD) to this nonconvex landscape is difficult; without the "monotonic decrease" property, accelerated iterates can become unstable and escape the regions where the objective function is well-behaved.

Methodology: The AFGD Algorithm

The proposed Accelerated Factored Gradient Descent (AFGD) adapts Nesterov’s three-sequence acceleration scheme to the factored setting. The core innovation is a mechanism to keep the algorithm "well-behaved" despite nonconvexity:

  • Restricted Convexity ($\Omega$): The authors identify a specific set $\Omega(U_0)$—defined by the initial point—where the objective function locally satisfies "restricted strong convexity."
  • Efficient Projection (ACCPROJ): To prevent iterates from escaping this safe region, AFGD uses a sub-solver called ACCPROJ. Crucially, this projection is performed on small $r \times r$ matrices, keeping the per-iteration cost low.
  • Rotation Alignment: The algorithm uses Procrustes alignment to ensure distance is measured meaningfully, accounting for the fact that $UU^\top = (UP)(UP)^\top$ for any orthogonal matrix $P$.

Theoretical Results

AFGD provides a theoretical bridge between fast nonconvex heuristics and the convergence rates of convex optimization.

Table 1: Comparison of iteration and per-iteration complexities for FGD, AGD-AC, and AFGD.

As shown in Table 1, AFGD achieves an $\epsilon$-optimal solution in $O(\sqrt{\widehat{L}/\mu} \log(1/\epsilon))$ iterations. This is a square-root improvement over standard Factored Gradient Descent (FGD). Unlike previous attempts like AGD-AC, AFGD maintains a per-iteration complexity that is nearly identical to standard FGD, making it the first truly practical accelerated method for this problem.

Empirical Performance

The authors evaluated AFGD using synthetic datasets for matrix completion and matrix sensing. Tests were conducted on matrices with dimensions $d$ up to 10,000 and ranks $r$ up to 50.

Figure 1: Convergence performance of AFGD compared to FGD and AGD across various dimensions (d) and ranks (r), measured by iterations and CPU time.

Experimental results (Figure 1) demonstrate that AFGD consistently converges faster than FGD in both the number of iterations and total CPU time. The algorithm remains robust across various problem scales, confirming that local convexity is sufficient for achieving accelerated rates in practice.

Conclusion

AFGD successfully applies Nesterov’s acceleration to the nonconvex problem of low-rank matrix factorization. By restricting iterates to a specific convex set where the objective behaves predictably, the authors achieve significantly faster convergence without sacrificing computational efficiency. While current theory focuses on local acceleration from a good initialization, future work may explore global acceleration and broader applications to asymmetric matrices.

Summary updated

Abstract

We study the low-rank matrix estimation problem, where the objective function $\mathcal{L}(\Mb)$ is defined over the space of positive semidefinite matrices with rank less than or equal to $r$. A fast approach to solve this problem is matrix factorization, which reparameterizes $\mathbf{M}$ as the product of two smaller matrix such that $\mathbf{M} =\mathbf{U}\mathbf{U}^\top$ and then performs gradient descent on $\mathbf{U}$ directly, a.k.a., factored gradient descent. Since the resulting problem is nonconvex, whether Nesterov’s acceleration scheme can be adapted to it remains a long-standing question. In this paper, we answer this question affirmatively by proposing a novel and practical accelerated factored gradient descent method motivated by Nesterov’s accelerated gradient descent. The proposed method enjoys better iteration complexity and computational complexity than the state-of-the-art algorithms in a wide regime. The key idea of our algorithm is to restrict all its iterates onto a special convex set, which enables the acceleration. Experimental results demonstrate the faster convergence of our algorithm and corroborate our theory.
BibTeX
@inproceedings{zhou2020accelerated,
  author = {Dongruo Zhou and Yuan Cao and Quanquan Gu},
  title = {{Accelerated Factored Gradient Descent for Low-Rank Matrix Factorization}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=XjadYLdI32},
}
Figure