Matrix completion — recovering a low-rank matrix from a small random subset of its entries — powers recommender systems and collaborative filtering. In practice it is solved by running (stochastic) gradient descent on the non-convex objective
where and is a certain regularizer. from a random starting point, and it just works.
Ge, Lee and Ma (NeurIPS 2016 Best student paper award) explained why: the regularized objective has no spurious local minima — every local minimum is global and exactly recovers . This mission formalizes that landmark theorem in Lean 4, in its strongest known form and along its simplest known proof: the unified landscape analysis of Ge–Jin–Zheng (ICML 2017) and an improved sampling bound in Chen–Li (JMLR 2019). Conditional on an explicit good-sample predicate (which holds with high probability under Bernoulli sampling), every local minimum of satisfies .
theorem MatrixCompletion.NoSpuriousMin.no_spurious_local_minimum_corrected
{d r : ℕ} (hd : 2 ≤ d) (hr : 1 ≤ r)
(Z X : Matrix (Fin d) (Fin r) ℝ) (Ω : Finset (Fin d × Fin d))
(p μ κ lam α : ℝ)
(hμ : 1 ≤ μ) (hκ : 1 ≤ κ) (hcond : sigmaMax Z ≤ κ * sigmaMin Z)
(hσ : 0 < sigmaMin Z)
(hinc : Incoherent μ Z) (hZnorm : frobSq Z = (r : ℝ))
(hα1 : 100 * twoInftyNorm Z ≤ α) (hα2 : α ≤ 200 * twoInftyNorm Z)
(hlam1 : 100 * sampDevNorm Ω p ≤ lam) (hlam2 : lam ≤ 200 * sampDevNorm Ω p)
(hp : SampleCondition d r p μ κ)
(hpC : 10 ^ 28 * μ ^ 4 * κ ^ 4 * (r : ℝ) ^ 2 * (1 + Real.log d) / d ≤ p)
(hgood : GoodSample Z Ω p)
(hmin : IsLocalMin (objective Z Ω lam α) X) :
objective Z Ω lam α X = 0 ∧ X * Xᵀ = Z * Zᵀ := by sorryMatrix completion has no spurious local minimum (Ge–Lee–Ma Theorem 5.3 in Chen–Li's Corollary 2.2 form), with a sampling constant the proof can actually use.
Let with -incoherent (Ge–Lee–Ma Assumption 1), , and . Tune data-adaptively inside Chen–Li's windows, and , and let be a good sample. If the sampling rate satisfies
then every local minimum of the regularized objective
is a global minimum: and . Non-convexity notwithstanding, the landscape hides no traps, which is why gradient descent from an arbitrary initialization provably solves positive semidefinite matrix completion.
Relation to the mission's goal theorem. This is the mission's no_spurious_local_minimum (45993f97-a08e-45fe-8944-932c4d74532f) with one extra hypothesis: the sampling rate is required with the constant in place of the hard-coded in the SampleCondition definition, and is replaced by so that the hypothesis also bites at small . Everything else — the statement, the model layer, the good-sample predicate — is unchanged, so this theorem is strictly weaker and implies nothing the original does not.
The strengthening is not cosmetic. The Chen–Li route reaches the goal through perturbation_terms_bound and K_superlevel_bound, and both of those are false at the instantiation: explicit machine-checked counterexamples are recorded on the platform (disproofs a797f42a-1928-4b1b-90ab-2234a526d06e and ac265185-c5b6-4443-867c-a3b32ea9049b). Balancing the regularizer's against the that the target offers requires , whereas SampleCondition supplies only . Chen–Li state their Lemma 4.8 "for a sufficiently large absolute constant "; is large enough. It forces before the hypothesis is satisfiable at all, which is the asymptotic regime the statement was always about.
Formalization note. This is the deterministic core of the high-probability statement: the randomness of factors through the good-sample predicate (Chen–Li Lemmas 4.1–4.2), whose probabilistic verification is a separate matter. Local minimality is Lean's topological IsLocalMin on .
No open leaves. Every sub-goal is proved or awaiting decomposition.