Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

First- and second-order optimality conditions of the objective (Chen–Li Lemma 4.3; GLM Prop. 5.1)

Proved
MatrixCompletion.NoSpuriousMin.optimality_conditions

by Shuze Chen · Aug 4, 2026 · Mathlib c5ea003 (Lean v4.30.0)

matrix-completionmc-no-spuriousnonconvex-optimization

Let 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 λ≥0\lambda\ge0λ≥0, threshold α>0\alpha>0α>0, and a symmetric observation set Ω\OmegaΩ (as in Chen–Li's off-diagonal symmetric sampling model, where symmetry is ambient). If XXX is a local minimum of fff, then XXX satisfies the explicit first-order condition

2 PΩ(ZZ⊤)X=2 PΩ(XX⊤)X+λ∇R(X)2\,P_\Omega(ZZ^\top)X=2\,P_\Omega(XX^\top)X+\lambda\nabla R(X)2PΩ​(ZZ⊤)X=2PΩ​(XX⊤)X+λ∇R(X)

and, for every direction V∈Rd×rV\in\mathbb{R}^{d\times r}V∈Rd×r, the second-order condition

∥PΩ(VX⊤+XV⊤)∥F2+λ ⟨V,∇2R(X)[V]⟩ ≥ 2 ⟨PΩ(ZZ⊤−XX⊤), VV⊤⟩.\|P_\Omega(VX^\top+XV^\top)\|_F^2+\lambda\,\langle V,\nabla^2R(X)[V]\rangle\ \ge\ 2\,\langle P_\Omega(ZZ^\top-XX^\top),\,VV^\top\rangle.∥PΩ​(VX⊤+XV⊤)∥F2​+λ⟨V,∇2R(X)[V]⟩ ≥ 2⟨PΩ​(ZZ⊤−XX⊤),VV⊤⟩.

Together these give K(X^)≥0K(\hat X)\ge0K(X^)≥0 at every local minimum — the entry point of the Chen–Li superlevel-set argument.

Formalization Note The symmetry of Ω\OmegaΩ is a genuine hypothesis of the first-order clause, not a convenience: the gradient of the sampled term is (PΩ(S′)+PΩ(S′)⊤)X(P_\Omega(S')+P_\Omega(S')^\top)X(PΩ​(S′)+PΩ​(S′)⊤)X for S′=XX⊤−ZZ⊤S'=XX^\top-ZZ^\topS′=XX⊤−ZZ⊤, which equals 2PΩ(S′)X2P_\Omega(S')X2PΩ​(S′)X exactly when PΩ(S′)P_\Omega(S')PΩ​(S′) is symmetric. For non-symmetric Ω\OmegaΩ there are strict local minima at which 2PΩ(S′)X+λ∇R(X)≠02P_\Omega(S')X+\lambda\nabla R(X)\ne02PΩ​(S′)X+λ∇R(X)=0, so the clause would be false as stated. The second-order clause holds regardless; the hypothesis is stated once for the conjunction.

Preamble
import Definitions.Def_MCNoSpuriousMinModel
import Mathlib.Topology.Order.LocalExtr
import Mathlib.Topology.Instances.Matrix
open Matrix MatrixCompletion.NoSpuriousMin
Formal statement
theorem MatrixCompletion.NoSpuriousMin.optimality_conditions
    {d r : ℕ} (Z X : Matrix (Fin d) (Fin r) ℝ) (Ω : Finset (Fin d × Fin d))
    (lam α : ℝ) (hlam : 0 ≤ lam) (hα : 0 < α)
    (hsym : ∀ i j : Fin d, (i, j) ∈ Ω ↔ (j, i) ∈ Ω)
    (hmin : IsLocalMin (objective Z Ω lam α) X) :
    FirstOrderPt Z Ω lam α X ∧ SecondOrderPt Z Ω lam α X := by sorry
Source
Chen, Li 2019, Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCA, JMLR 20(142), https://arxiv.org/abs/1711.01742 (v3) [THE canonical reference: all milestones follow its Section 4], pp. 16-17, Lemma 4.3 (first- and second-order optimality conditions; yields K(X) >= 0 at every local minimum). Provenance: restated there from Ge, Lee, Ma 2016, https://arxiv.org/abs/1605.07272 (v4), p. 11, Proposition 5.1. The symmetry of Omega, ambient in Chen-Li's off-diagonal symmetric Bernoulli model (their Definition 1), is carried as an explicit hypothesis; the first-order clause is false without it.
Read-back

What the Lean code literally says, in plain math · claude-fable-5

Read-back — MatrixCompletion.NoSpuriousMin.optimality_conditions

For every pair of natural numbers d,rd, rd,r (including the degenerate cases d=0d = 0d=0 or r=0r = 0r=0, where all matrices below are trivial and all sums over rows or entries are empty), every pair of real d×rd \times rd×r matrices ZZZ and XXX, every finite set Ω\OmegaΩ of index pairs (i,j)∈{1,…,d}×{1,…,d}(i,j) \in \{1,\dots,d\} \times \{1,\dots,d\}(i,j)∈{1,…,d}×{1,…,d}, and all real numbers λ\lambdaλ and α\alphaα, under the hypotheses

  • λ≥0\lambda \ge 0λ≥0 (non-strict),
  • α>0\alpha > 0α>0 (strict),
  • Ω\OmegaΩ is symmetric: for all i,ji, ji,j, (i,j)∈Ω(i,j) \in \Omega(i,j)∈Ω if and only if (j,i)∈Ω(j,i) \in \Omega(j,i)∈Ω,
  • XXX is a local minimum of the function fff defined below, in the sense that there exists a neighborhood of XXX (in the standard entrywise topology on the space of d×rd \times rd×r real matrices) on which f(X)≤f(Y)f(X) \le f(Y)f(X)≤f(Y) for every matrix YYY in that neighborhood (a non-strict local minimum, so e.g. any point of a locally constant function qualifies),

the theorem concludes the conjunction of two conditions, (A) and (B) below. Throughout, ΠΩ(M)\Pi_\Omega(M)ΠΩ​(M) denotes the d×dd \times dd×d matrix that keeps the entry MijM_{ij}Mij​ when (i,j)∈Ω(i,j) \in \Omega(i,j)∈Ω and sets it to 000 otherwise; ⟨A,B⟩=∑i,jAijBij\langle A, B \rangle = \sum_{i,j} A_{ij} B_{ij}⟨A,B⟩=∑i,j​Aij​Bij​ is the entrywise (Frobenius) inner product; ∥M∥F2=∑i,jMij2\|M\|_F^2 = \sum_{i,j} M_{ij}^2∥M∥F2​=∑i,j​Mij2​ is the sum of squared entries; ∥Xi⋅∥=∑jXij2\|X_{i\cdot}\| = \sqrt{\sum_j X_{ij}^2}∥Xi⋅​∥=∑j​Xij2​​ is the Euclidean norm of row iii; and [t]+=max⁡(t,0)[t]_+ = \max(t, 0)[t]+​=max(t,0). The objective is

f(Y)  =  12 ∥ΠΩ(ZZ⊤−YY⊤)∥F2  +  λ∑i=1d[∥Yi⋅∥−α]+4.f(Y) \;=\; \tfrac{1}{2}\,\bigl\|\Pi_\Omega\bigl(ZZ^\top - YY^\top\bigr)\bigr\|_F^2 \;+\; \lambda \sum_{i=1}^{d} \bigl[\|Y_{i\cdot}\| - \alpha\bigr]_+^{4}.f(Y)=21​​ΠΩ​(ZZ⊤−YY⊤)​F2​+λi=1∑d​[∥Yi⋅​∥−α]+4​.

(A) First-order condition. The d×rd \times rd×r matrix

2 ΠΩ(XX⊤−ZZ⊤) X  +  λ G(X)2\,\Pi_\Omega\bigl(XX^\top - ZZ^\top\bigr)\,X \;+\; \lambda\, G(X)2ΠΩ​(XX⊤−ZZ⊤)X+λG(X)

is the zero matrix, where G(X)G(X)G(X) is the explicitly given matrix with entries

G(X)ij  =  4 [∥Xi⋅∥−α]+3∥Xi⋅∥  Xij,G(X)_{ij} \;=\; \frac{4\,[\|X_{i\cdot}\| - \alpha]_+^{3}}{\|X_{i\cdot}\|}\; X_{ij},G(X)ij​=∥Xi⋅​∥4[∥Xi⋅​∥−α]+3​​Xij​,

with the convention (from the ambient division on the reals) that division by zero yields zero — so when ∥Xi⋅∥=0\|X_{i\cdot}\| = 0∥Xi⋅​∥=0 the entry G(X)ijG(X)_{ij}G(X)ij​ is 000 by that convention (its numerator also vanishes since α>0\alpha > 0α>0). Note that GGG is a fixed closed-form formula, not a derivative computed by the theorem: condition (A) asserts that this particular expression equals zero, not that fff is differentiable at XXX. (B) Second-order condition. For every d×rd \times rd×r real matrix VVV (not merely directions in some restricted set),

2 ⟨ΠΩ(ZZ⊤−XX⊤),  VV⊤⟩  ≤  ∥ΠΩ(VX⊤+XV⊤)∥F2  +  λ H(X,V),2\,\bigl\langle \Pi_\Omega\bigl(ZZ^\top - XX^\top\bigr),\; VV^\top \bigr\rangle \;\le\; \bigl\|\Pi_\Omega\bigl(VX^\top + XV^\top\bigr)\bigr\|_F^2 \;+\; \lambda\, H(X, V),2⟨ΠΩ​(ZZ⊤−XX⊤),VV⊤⟩≤​ΠΩ​(VX⊤+XV⊤)​F2​+λH(X,V),

where H(X,V)H(X,V)H(X,V) is the explicitly given quantity

H(X,V)  =  ∑i=1d[ 12 [∥Xi⋅∥−α]+2(⟨Xi⋅, Vi⋅⟩∥Xi⋅∥) ⁣2  +  4 [∥Xi⋅∥−α]+3∥Xi⋅∥(∥Vi⋅∥2−(⟨Xi⋅, Vi⋅⟩∥Xi⋅∥) ⁣2)],H(X,V) \;=\; \sum_{i=1}^{d} \left[\, 12\,[\|X_{i\cdot}\| - \alpha]_+^{2} \left(\frac{\langle X_{i\cdot},\, V_{i\cdot}\rangle}{\|X_{i\cdot}\|}\right)^{\!2} \;+\; \frac{4\,[\|X_{i\cdot}\| - \alpha]_+^{3}}{\|X_{i\cdot}\|} \left( \|V_{i\cdot}\|^2 - \left(\frac{\langle X_{i\cdot},\, V_{i\cdot}\rangle}{\|X_{i\cdot}\|}\right)^{\!2} \right) \right],H(X,V)=i=1∑d​[12[∥Xi⋅​∥−α]+2​(∥Xi⋅​∥⟨Xi⋅​,Vi⋅​⟩​)2+∥Xi⋅​∥4[∥Xi⋅​∥−α]+3​​(∥Vi⋅​∥2−(∥Xi⋅​∥⟨Xi⋅​,Vi⋅​⟩​)2)],

with ⟨Xi⋅,Vi⋅⟩=∑jXijVij\langle X_{i\cdot}, V_{i\cdot}\rangle = \sum_j X_{ij} V_{ij}⟨Xi⋅​,Vi⋅​⟩=∑j​Xij​Vij​, and again the division-by-zero-equals-zero convention applying wherever ∥Xi⋅∥=0\|X_{i\cdot}\| = 0∥Xi⋅​∥=0 (in which case both summands for row iii vanish). As in (A), HHH is a fixed closed-form formula asserted directly; the theorem makes no claim that it coincides with an actual second derivative of fff. The hypotheses on λ\lambdaλ, α\alphaα, and the symmetry of Ω\OmegaΩ are assumptions of the theorem; nothing in the statement constrains ZZZ, and Ω\OmegaΩ may be empty (in which case ΠΩ\Pi_\OmegaΠΩ​ is identically zero and the projection terms in fff, (A), and (B) all vanish).

Human review
  • Endorsed by Community (Bot) · Aug 4, 2026

  • Endorsed by Shuze Chen · Aug 4, 2026

    Confirmed by the mission captain (proposal self-audit).

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