Introduction
Many machine learning problems, from recommendation systems to image denoising, involve finding a low-rank matrix that minimizes a convex cost function. Formally, this is expressed as: $$ \min_{\text{rank}(A) \le r^*} R(A) $$ While the objective function $R(A)$ is convex, the rank constraint makes the overall problem non-convex and notoriously NP-hard. Traditionally, researchers have relied on two main workarounds. The first is convex relaxation, which replaces the rank constraint with the nuclear norm (the sum of singular values); however, this can lead to biased or high-rank solutions. The second is alternating minimization, which factors the matrix into two smaller matrices and alternates updates, but lacks strong global guarantees.
This paper bridges the gap between theoretical guarantees and practical efficiency by introducing improved greedy and local search algorithms that tackle the rank constraint directly. By refining theoretical bounds and introducing "fast" practical variants, these general-purpose algorithms can outperform specialized state-of-the-art methods.
Algorithmic Framework
The authors focus on two primary algorithmic approaches:
- Greedy Search (GECO): Starting from a zero matrix, the algorithm iteratively adds the "best" rank-1 matrix—derived from the gradient of the objective function—to the current solution. It then re-optimizes the weights of all components.
- Local Search: Building on the greedy approach, this method introduces a "swap" step. In each iteration, it removes the least significant rank-1 component (truncation) before adding a new one. This mechanism allows the algorithm to correct previous mistakes and escape local minima, making it more robust than pure greedy search.
The "Fast" Variants: Standard versions of these algorithms are computationally expensive because they require solving a full optimization problem in every iteration. To address this, the authors introduce Fast Greedy and Fast Local Search. These variants use alternating minimization for the inner optimization step and employ a simplified rank reduction heuristic based on the magnitude of singular vectors rather than a full SVD. Crucially, they utilize early stopping—running only a few iterations (often just 2–3) instead of solving the inner problem to convergence.
Key Insights: Logarithmic Bounds and Regularization
A major theoretical contribution of the paper is a new analysis showing that the rank required to reach a certain error level depends logarithmically on the initial error. Previous bounds suggested a much more pessimistic linear dependence.
Practically, one of the most surprising findings is that not solving the inner optimization problem perfectly actually improves performance. By limiting the inner loop to a few iterations, the algorithm avoids overfitting to the training data. This "regularization via inaccuracy" leads to significantly better generalization on test sets, allowing the fast variants to maintain low test errors even as the rank increases.
Empirical Results
The authors evaluated their algorithms across several benchmarks, demonstrating strong performance against established methods:
- Matrix Completion: In synthetic matrix completion tasks, the proposed algorithms recovered lower-rank solutions with significantly higher accuracy than the popular SoftImpute method, which tended to overfit at higher ranks.
- Robust PCA: On the BMC 2012 video dataset used for background subtraction, the Fast Greedy algorithm outperformed both standard PCA and Principal Component Pursuit (PCP). It successfully separated moving foregrounds from static backgrounds while exhibiting fewer "shadow" artifacts.
- Recommender Systems: On the MovieLens 10M dataset, Fast Greedy achieved an RMSE of 0.8330. Despite being a general-purpose tool, it proved competitive with highly tuned, specialized SVD-based algorithms (0.8315) used in the Netflix Prize.
- Efficiency: The "Fast" variants achieved massive speedups. On the MovieLens 1M dataset, the Fast Greedy version was nearly 17x faster than the basic greedy implementation.
Limitations and Future Work
While highly effective, the theoretical bounds of these algorithms still depend on the "rank-restricted condition number" ($\kappa$). If the objective function is very flat or steep in certain directions, the rank required for a good solution may remain high. Additionally, while the algorithms are fast, they still rely on computing the top singular vectors of the gradient, which could become a bottleneck for extremely large, dense matrices.
Finally, the early stopping iterations act as a hyperparameter that must be tuned to balance speed and regularization. Future research could explore automated ways to tune these parameters and investigate more efficient distributed implementations.
Summary updated