Matrix completion means recovering a large low-rank matrix, such as a user-by-movie rating table, from a small set of observed entries. The scalable way to do this is to write the matrix as a product of two thin factors and run gradient descent on the fit to the observed entries. When the observed entries are scattered uniformly at random, this non-convex problem is known to be well behaved: every local minimum is a global one. When the observation pattern is structured, gradient descent can instead get stuck in a huge number of "spurious local minima", meaning bad solutions from which no small step improves the fit. Real observation patterns are never uniform. Popular items and heavy users are over-sampled. So the regime practitioners actually face sits between these two theories, and neither covers it.
We propose to treat that intermediate regime through uniform gradient convergence. This is the idea that, if the gradient and curvature of the finite-sample objective stay close to those of an idealized "population" objective everywhere in the relevant region, then the finite-sample landscape inherits the population's lack of traps. For a fixed, non-random mask, one quantity controls this closeness over all incoherent low-rank factors: the spectral norm of the difference between the weighted observation mask and a uniform matrix. Incoherent here means the energy is spread across rows rather than concentrated in a few. Because this quantity depends on per-entry weights that we are free to choose, we can minimize it directly. Doing so turns a landscape property into a small convex problem solved on the mask before any factorization. It also removes the paradox that adding observations can make the landscape worse.
Core Claim
The claim has two parts, one theoretical and one algorithmic. Write the weighted factored objective as $$f_W(U) = \sum_{(i,j)\in\Omega} w_{ij}\big((UU^\top)_{ij} - M^*_{ij}\big)^2 + \lambda R(U),$$ where $\Omega$ is the set of observed entries, $w_{ij}\ge 0$ are per-entry weights normalized to sum to $n^2$, $M^*$ is the rank-$r$ ground truth of size $n\times n$, $U\in\mathbb{R}^{n\times r}$ is the factor, and $R$ is the incoherence regularizer of Matrix Completion has No Spurious Local Minimum. Define the mask discrepancy $$\gamma(W) = \tfrac{1}{n}\,\big\| W\circ A_\Omega - J \big\|_2,$$ where $A_\Omega$ is the 0/1 indicator of observed entries, $\circ$ is the entrywise product, and $J$ is the all-ones matrix.
The gradient and Hessian of $f_W$ are sums of bilinear forms in low-rank matrices, weighted by the mask. For factors with bounded row norms (incoherence), each such form deviates from its full-observation value by at most $\gamma(W)$ times a factor polynomial in rank, incoherence and condition number. This follows from the standard inequality bounding a bilinear form by a spectral norm times row-norm factors. That gives uniform gradient proximity and uniform Hessian proximity over the whole incoherent region. These are exactly the two conditions under which The Landscape of Non-convex Empirical Risk with Degenerate Population Risk transfers a benign population landscape to the empirical one, working on the quotient by rotations. The theorem we aim to prove: if $\gamma(W)$ lies below a threshold polynomial in $(\mu, r, \kappa)$, the weighted objective has no spurious local minima, and every non-global critical point is a strict saddle. A strict saddle is a point with a direction of negative curvature that gradient descent can escape.
The algorithmic consequence is to choose $W$ to minimize $\gamma(W)$. This is a convex problem, since it minimizes the spectral norm of an affine function of $W$, and it can be solved with sparse matrix-vector products costing $O(|\Omega|)$ each. A reweighting with zero weights on new entries is always available, so the optimized discrepancy $\gamma^\star(\Omega)=\min_W\gamma(W)$ can never increase when entries are added. The "data paradox" of Factorization Approach for Low-complexity Matrix Completion Problems says that observing more entries can create new traps. Our prediction is that this paradox is a property of uniform weighting, not of the information in the data.
Relation to Prior Work
Two lines of work motivate the proposal by bracketing the gap. Matrix Completion has No Spurious Local Minimum proves a benign landscape under uniform Bernoulli sampling. There, concentration comes from the randomness of the mask. We replace randomness with a deterministic, optimizable spectral quantity. Factorization Approach for Low-complexity Matrix Completion Problems proves the opposite extreme for low-complexity deterministic graphs: at least $2^{r(|S|-1)}-1$ classes of spurious minima, and failure of gradient flow with probability $1-O(2^{-\lceil n/2\rceil})$. It offers a diagnosis but no remedy. Our certificate should come out large on those graphs for every choice of weights, which is a consistency check rather than a contradiction.
Three papers supply the method. The landscape of empirical risk for nonconvex losses established that uniform convergence of gradients and Hessians transfers the population landscape. It required non-degenerate critical points, which factorization violates. The Landscape of Non-convex Empirical Risk with Degenerate Population Risk relaxed this to strict saddles on quotient manifolds, but only for Gaussian sensing. We reuse their transfer theorem and supply a completion-specific proximity bound. That bound is not a probabilistic supremum over parameters, so it avoids the parameter-dimension blow-up they flag as an artifact.
Characterization of Excess Risk for Locally Strongly Convex Population Risk shows that removing spurious minima improves excess risk from $\tilde O(1/\sqrt n)$ to $\tilde O(1/n)$. This constrains the claim: reweighting changes the estimator, so in noisy settings we must check that any landscape gain is not paid back in variance. Finally, lifting (Over-parametrization via Lifting for Low-rank Matrix Sensing) is a competing remedy. It turns traps into saddles, at a cost in variables that grows exponentially with the lifting order. The file contains no weighted matrix completion papers, so we cannot position against that literature here. Checking it is a first task, and the proposal's specific novelty is the link between weights, uniform landscape inheritance, and the data paradox.
Research Program
The theoretical work has three parts. First, prove the deterministic gradient and Hessian proximity bound in terms of $\gamma(W)$ over the incoherent region, on the quotient by $O(r)$. Second, combine it with the transfer theorem of Li et al. to obtain the no-spurious-minima statement. Third, show that the regularizer keeps gradient descent inside the incoherent region, following Ge et al.'s argument. The asymmetric case $UV^\top$ is added last with the usual balancing term.
On the computational side, we solve the weight problem by projected subgradient descent on the top singular pair. We also compare it with a much cheaper heuristic: Sinkhorn balancing, which rescales the observed entries so that every row and column carries equal total weight. Both produce a mask whose $\gamma$ we report next to the resulting trap rate.
Baselines
The naive reference is unweighted factored gradient descent from random initialization, with Ge et al.'s regularizer. It is the method whose failure motivates the work, and the proposal must beat it on the trap rate. The trap rate is the fraction of random initializations whose endpoint has relative recovery error above $10^{-3}$. On Yalcin et al.'s deterministic instances the reported failure probability for gradient flow is at least $1-O(2^{-\lceil n/2\rceil})$. That is the number to beat there, with the expectation that no weighting beats it on the pure instances.
The strongest cheap competitor is Sinkhorn degree balancing. It is the obvious heuristic fix for skewed sampling and may capture most of the benefit. It gets the same initializations, iteration budget and step-size grid. The spectrally optimized weights beat it only if they lower the trap rate at matched $\gamma$ budgets or on masks where balancing leaves $\gamma$ large.
The strongest existing trap-removal method is lifting. The only reported figure in the file is on a sensing instance, not completion: success rises from 47.5% unlifted to 75% at lifting order 3 on the $n=5$ synthetic problem. No reported result found on Lacuna for lifting on matrix completion. We run it only on small $n$ where it is feasible. We also run rank over-parameterization, meaning a search rank of $2r$, and the convex nuclear-norm program at small $n$ as an optimality oracle.
The key ablation isolates the ingredient: random weights with the same variance as the optimized ones. If these help equally, the benefit comes from perturbation rather than from reducing $\gamma$. The same ablation run under the regularizer-free objective separates the contribution of weighting from that of incoherence control.
Why not just…?
Why not just use spectral initialization? A warm start can land inside the good basin, and How many samples is a good initial point worth in Low-rank Matrix Recovery? shows good initial points trade against sample requirements. But spectral initialization is itself built from the mask. Under skewed sampling it is biased toward heavily observed rows, and Yalcin et al. report failure where spectral tricks do not avoid the traps. We include spectral initialization, both unweighted and weighted, as a baseline. If unweighted spectral initialization alone matches our trap rate on real masks, the landscape claim loses practical force and we will say so.
Why not just solve the convex relaxation? On the problems it can handle it removes the question entirely. But it works on the full $n\times n$ matrix, which rules it out at MovieLens-10M or Netflix scale, as argued in Semidefinite Programming versus Burer-Monteiro Factorization for Matrix Sensing. We use it only as a small-$n$ oracle.
Why not just row/column-normalize the mask? This is the real threat. On masks whose irregularity is purely in degrees, Sinkhorn balancing may achieve nearly the optimal $\gamma$. If experiments show that, the method we recommend becomes balancing, and the contribution narrows to the certificate and theory explaining why it works and where it fails. The optimized weights should matter on masks with community structure, where degrees are balanced but the spectral gap is poor. We construct such masks explicitly to settle the question.
Why not just over-parameterize the rank or add noise? Noise injection escapes saddles but not true local minima, and Yalcin et al.'s traps are true minima. Rank over-parameterization is run directly as a baseline.
Proposed Experiments
We use planted ground truth throughout, so that recovery is measurable. We generate random incoherent rank-$r$ matrices and observe them through four families of masks. The first is Yalcin et al.'s deterministic low-complexity graphs. The second interpolates between those graphs and uniform Bernoulli masks by adding a fraction $\rho$ of random edges. The third is power-law and block-community masks. The fourth is the real observation patterns of MovieLens 100K and 1M, with the ratings replaced by planted values; the file lists no reported RMSE for these. We record trap rate, number of distinct spurious endpoints (found by clustering endpoints modulo rotation), wall-clock time, and $\gamma$ before and after weighting.
The first decisive check is whether trap rate is a monotone, threshold-like function of $\gamma(W)$ across all masks and weighting schemes. If it is not, the certificate is wrong. The second is whether, on the interpolation family, optimized weights shift the value of $\rho$ at which traps disappear to substantially smaller $\rho$ than uniform weights do. The third is whether, under the paradox construction, trap counts under optimized weights stay non-increasing as entries are added while uniform weighting reproduces Yalcin et al.'s increase. A final noisy experiment on the MovieLens masks compares held-out planted-entry error of weighted and unweighted solutions. It tests whether a cleaner landscape costs statistical accuracy, the concern raised by the excess-risk analysis of Yi et al.
References
- Matrix Completion has No Spurious Local Minimum
- The Landscape of Non-convex Empirical Risk with Degenerate Population Risk
- Factorization Approach for Low-complexity Matrix Completion Problems: Exponential Number of Spurious Solutions and Failure of Gradient Methods
- The landscape of empirical risk for nonconvex losses
- Characterization of Excess Risk for Locally Strongly Convex Population Risk
- Over-parametrization via Lifting for Low-rank Matrix Sensing: Conversion of Spurious Solutions to Strict Saddle Points
- How many samples is a good initial point worth in Low-rank Matrix Recovery?
- Semidefinite Programming versus Burer-Monteiro Factorization for Matrix Sensing