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.
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.
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