Abstract
Matrix factorization tries to recover a low-rank matrix from limited observations. A state-of-the-art algorithm is the Soft-Impute, which exploits a special "sparse plus low-rank" structure of the matrix iterates to allow efficient SVD in each iteration. Though Soft-Impute is also a proximal gradient algorithm, it is generally believed that acceleration techniques are not useful and will destroy the special structure. In this paper, we show that Soft-Impute can indeed be accelerated without compromising the "sparse plus low-rank" structure. To further reduce the per-iteration time complexity, we propose an approximate singular value thresholding scheme based on the power method. Theoretical analysis shows that the proposed algorithm enjoys the fast $O(1/T^2)$ convergence rate of accelerated proximal gradient algorithms. Extensive experiments on both synthetic and large recommendation data sets show that the proposed algorithm is much faster than Soft-Impute and other state-of-the-art matrix completion algorithms.
Introduction
Matrix completion is the task of filling in missing entries in a massive, partially observed matrix—the classic example being the "Netflix Prize" problem of predicting user movie ratings. Mathematically, this is often solved by minimizing the nuclear norm, which encourages a low-rank solution.
The state-of-the-art algorithm for this is Soft-Impute. Its efficiency stems from exploiting a "sparse plus low-rank" structure in its iterations, which allows for very fast Singular Value Decompositions (SVDs). However, Soft-Impute is a standard proximal gradient method with a relatively slow convergence rate of $O(1/T)$. While "accelerated" versions of these algorithms exist (converging at $O(1/T^2)$), researchers previously believed that applying them to Soft-Impute would destroy the "sparse plus low-rank" structure, making each iteration prohibitively slow. This paper demonstrates that Soft-Impute can be accelerated without sacrificing this critical structure.
Methodology: AIS-Impute
The authors propose AIS-Impute (Accelerated Inexact Soft-Impute), which introduces two major innovations to overcome the limitations of standard proximal methods.
Structure-Preserving Acceleration
The authors demonstrate that the matrix used in the accelerated step maintains a "sparse plus two low-rank" structure. Specifically, the accelerated iterate $Z_t$ is essentially $P_\Omega(O - Y_t) + (1+\theta_t)X_t - \theta_t X_{t-1}$. Since $X_t$ and $X_{t-1}$ are low-rank and the first term is sparse, matrix-vector multiplications—the bottleneck of the SVD—can still be performed very efficiently.
Inexact SVD via the Power Method
Instead of computing an exact partial SVD, AIS-Impute uses the Power Method to find an approximate singular subspace. This approach is advantageous because it is easy to "warm-start" using the subspace from the previous iteration, making subsequent iterations much faster. The authors provide a formal proof that AIS-Impute converges to the optimal solution at the accelerated $O(1/T^2)$ rate even with the approximation errors introduced by the power method.
The algorithm also incorporates practical techniques such as continuation (starting with a large regularization parameter and decreasing it) and restarting (resetting the acceleration if the objective function increases) to ensure stability and speed.
Experimental Results
The authors evaluated AIS-Impute against several competitors, including Soft-Impute, APG, and ALT-Impute, using synthetic data and large-scale real-world datasets like MovieLens and Netflix.
Convergence Performance
AIS-Impute achieves massive speedups over traditional methods. On the Netflix dataset, AIS-Impute reached the solution in 0.79 hours, compared to 24.47 hours for Soft-Impute—a ~30x speedup. On the MovieLens-10M dataset, AIS-Impute converged in about 47 minutes, while standard Soft-Impute and several other state-of-the-art methods failed to converge within 27 hours.
As shown in Figure 2, while AIS-Impute and APG have similar iteration counts, AIS-Impute is significantly faster in wall-clock time, validating the effectiveness of the structure-preserving approach.
Rank Recovery and Accuracy
AIS-Impute achieved the same Root Mean Squared Error (RMSE) and recovered the same matrix rank as exact methods, proving that the inexact approximations do not sacrifice prediction quality. Figure 6 shows the evolution of the rank of iterates on the MovieLens datasets, demonstrating stable convergence to the target rank.
Conclusion
AIS-Impute provides a powerful framework for large-scale matrix completion by combining Nesterov’s acceleration with an inexact SVD scheme. It maintains the computational benefits of Soft-Impute while achieving the superior $O(1/T^2)$ convergence rate. Future work could involve extending this accelerated inexact framework to non-convex penalties for potentially better rank recovery.
Summary updated