Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Regularizer contribution to KKK: ⟨Δ,∇2R(X)[Δ]⟩−4⟨∇R(X),Δ⟩≤199.54 α2∥Δ∥F2−0.3∑i∥Δi∥4\langle\Delta,\nabla^2 R(X)[\Delta]\rangle-4\langle\nabla R(X),\Delta\rangle \le 199.54\,\alpha^2\|\Delta\|_F^2-0.3\sum_i\|\Delta_i\|^4⟨Δ,∇2R(X)[Δ]⟩−4⟨∇R(X),Δ⟩≤199.54α2∥Δ∥F2​−0.3∑i​∥Δi​∥4

Proved
MatrixCompletion.NoSpuriousMin.regularizer_perturbation_bound

by LukeBernese · Aug 14, 2026 · Mathlib c5ea003 (Lean v4.30.0)

matrix-analysismatrix-completionnonconvex-optimization

Setting for the Ge–Lee–Ma / Chen–Li matrix-completion objective f(X)=12∥PΩ(ZZ⊤−XX⊤)∥F2+λR(X)f(X)=\tfrac12\|P_\Omega(ZZ^\top-XX^\top)\|_F^2+\lambda R(X)f(X)=21​∥PΩ​(ZZ⊤−XX⊤)∥F2​+λR(X) with the row regularizer

R(X)=∑i(∥Xi,⋅∥2−α)+4.R(X)=\sum_i\big(\|X_{i,\cdot}\|_2-\alpha\big)_+^4 .R(X)=i∑​(∥Xi,⋅​∥2​−α)+4​.

Let Z∈Rd×rZ\in\mathbb R^{d\times r}Z∈Rd×r be the ground-truth factor, let UUU be any other factorization of the same matrix (UU⊤=ZZ⊤UU^\top=ZZ^\topUU⊤=ZZ⊤), and write Δ=X−U\Delta=X-UΔ=X−U for the error direction. Assume the regularization radius is above the row-norm scale of ZZZ, i.e. α≥100 ∥Z∥2→∞\alpha\ge 100\,\|Z\|_{2\to\infty}α≥100∥Z∥2→∞​, where ∥Z∥2→∞=max⁡i∥Zi,⋅∥2\|Z\|_{2\to\infty}=\max_i\|Z_{i,\cdot}\|_2∥Z∥2→∞​=maxi​∥Zi,⋅​∥2​.

Then the regularizer's contribution to the auxiliary function K(X)=⟨Δ,∇2f(X)[Δ]⟩−4⟨∇f(X),Δ⟩K(X)=\langle\Delta,\nabla^2f(X)[\Delta]\rangle-4\langle\nabla f(X),\Delta\rangleK(X)=⟨Δ,∇2f(X)[Δ]⟩−4⟨∇f(X),Δ⟩ obeys

⟨Δ,∇2R(X)[Δ]⟩−4⟨∇R(X),Δ⟩  ≤  199.54 α2∥Δ∥F2  −  0.3∑i∥Δi,⋅∥24.\big\langle \Delta,\nabla^2R(X)[\Delta]\big\rangle-4\big\langle\nabla R(X),\Delta\big\rangle \;\le\; 199.54\,\alpha^2\|\Delta\|_F^2\;-\;0.3\sum_i\|\Delta_{i,\cdot}\|_2^4 .⟨Δ,∇2R(X)[Δ]⟩−4⟨∇R(X),Δ⟩≤199.54α2∥Δ∥F2​−0.3i∑​∥Δi,⋅​∥24​.

This is Chen–Li's Lemma 4.10, a sharpened form of Lemma 11 of Ge–Jin–Zheng (2017): the point of the sharpening is the negative quartic term −0.3∑i∥Δi,⋅∥24-0.3\sum_i\|\Delta_{i,\cdot}\|_2^4−0.3∑i​∥Δi,⋅​∥24​, which is what later absorbs the 19∥Ω−pJ∥∑i∥Δi,⋅∥2419\|\Omega-pJ\|\sum_i\|\Delta_{i,\cdot}\|_2^419∥Ω−pJ∥∑i​∥Δi,⋅​∥24​ produced by the sampling estimate (Lemma 4.9) once λ≥100∥Ω−pJ∥\lambda\ge 100\|\Omega-pJ\|λ≥100∥Ω−pJ∥.

The proof is a per-row estimate. Rows with ∥Xi,⋅∥<α\|X_{i,\cdot}\|<\alpha∥Xi,⋅​∥<α contribute nothing on the left because (∥Xi,⋅∥−α)+=0(\|X_{i,\cdot}\|-\alpha)_+=0(∥Xi,⋅​∥−α)+​=0. For a row with ∥Xi,⋅∥≥α\|X_{i,\cdot}\|\ge\alpha∥Xi,⋅​∥≥α, the hypothesis ∥Ui,⋅∥=∥Zi,⋅∥≤α/100\|U_{i,\cdot}\|=\|Z_{i,\cdot}\|\le\alpha/100∥Ui,⋅​∥=∥Zi,⋅​∥≤α/100 gives ⟨Xi,⋅,Δi,⋅⟩≥0.99∥Xi,⋅∥2\langle X_{i,\cdot},\Delta_{i,\cdot}\rangle\ge 0.99\|X_{i,\cdot}\|^2⟨Xi,⋅​,Δi,⋅​⟩≥0.99∥Xi,⋅​∥2 and 0.99∥Xi,⋅∥≤∥Δi,⋅∥≤1.01∥Xi,⋅∥0.99\|X_{i,\cdot}\|\le\|\Delta_{i,\cdot}\|\le 1.01\|X_{i,\cdot}\|0.99∥Xi,⋅​∥≤∥Δi,⋅​∥≤1.01∥Xi,⋅​∥, whence the row's contribution is at most 12(∥Xi,⋅∥−α)+2∥Δi,⋅∥2−15.68(∥Xi,⋅∥−α)+3∥Xi,⋅∥12(\|X_{i,\cdot}\|-\alpha)_+^2\|\Delta_{i,\cdot}\|^2-15.68(\|X_{i,\cdot}\|-\alpha)_+^3\|X_{i,\cdot}\|12(∥Xi,⋅​∥−α)+2​∥Δi,⋅​∥2−15.68(∥Xi,⋅​∥−α)+3​∥Xi,⋅​∥; the cubic negative term then dominates and yields the stated row bound 199.54 α2∥Δi,⋅∥2−0.3∥Δi,⋅∥4199.54\,\alpha^2\|\Delta_{i,\cdot}\|^2-0.3\|\Delta_{i,\cdot}\|^4199.54α2∥Δi,⋅​∥2−0.3∥Δi,⋅​∥4.

Here regHessQF α X V is the quadratic form ⟨V,∇2R(X)[V]⟩\langle V,\nabla^2R(X)[V]\rangle⟨V,∇2R(X)[V]⟩, regGrad α X is ∇R(X)\nabla R(X)∇R(X), innerM is the trace inner product, frobSq is ∥⋅∥F2\|\cdot\|_F^2∥⋅∥F2​, rowNorm A i is ∥Ai,⋅∥2\|A_{i,\cdot}\|_2∥Ai,⋅​∥2​ and twoInftyNorm is ∥⋅∥2→∞\|\cdot\|_{2\to\infty}∥⋅∥2→∞​.

Preamble
import Definitions.Def_MCNoSpuriousMinModel
open Matrix MatrixCompletion.NoSpuriousMin
Formal statement
theorem MatrixCompletion.NoSpuriousMin.regularizer_perturbation_bound
    {d r : ℕ} (Z X U : Matrix (Fin d) (Fin r) ℝ) (α : ℝ) (hα : 0 < α)
    (hU : U * Uᵀ = Z * Zᵀ) (hα1 : 100 * twoInftyNorm Z ≤ α) :
    regHessQF α X (X - U) - 4 * innerM (regGrad α X) (X - U)
      ≤ 199.54 * α ^ 2 * frobSq (X - U) - 0.3 * ∑ i, rowNorm (X - U) i ^ 4 := by sorry
Source
Ji Chen and Xiaodong Li, Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCA, JMLR 20(142):1-39, 2019; arXiv:1711.01742v3, Lemma 4.10 and its proof in Appendix B (eqs. (B.1)-(B.6)). A modification of Lemma 11 of Rong Ge, Chi Jin, Yi Zheng, No Spurious Local Minima in Nonconvex Low Rank Problems, ICML 2017, arXiv:1704.00708.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me