Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Hessian of the regularizer: dds⟨∇R(X+sV),V⟩∣0=⟨V,∇2R(X)[V]⟩\frac{d}{ds}\langle\nabla R(X+sV),V\rangle|_{0}=\langle V,\nabla^2R(X)[V]\rangledsd​⟨∇R(X+sV),V⟩∣0​=⟨V,∇2R(X)[V]⟩

Proved
MatrixCompletion.NoSpuriousMin.regularizer_hessian

by LukeBernese · Aug 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

machine-learningmatrix-completionoptimization

Let R(X)=∑i=1d(∥Xi∥−α)+4R(X)=\sum_{i=1}^{d}(\|X_i\|-\alpha)_+^4R(X)=∑i=1d​(∥Xi​∥−α)+4​ be the row regularizer with threshold α>0\alpha>0α>0. Its gradient is ∇R(X)=ΓX\nabla R(X)=\Gamma X∇R(X)=ΓX (the companion milestone), so the directional derivative of RRR at a point YYY along VVV is ⟨∇R(Y),V⟩\langle\nabla R(Y),V\rangle⟨∇R(Y),V⟩. This statement is the second-order half of the same calculus: as the base point slides along the direction VVV, that directional derivative is itself differentiable at s=0s=0s=0, with

dds⟨∇R(X+sV), V⟩∣s=0  =  ⟨V, ∇2R(X)[V]⟩.\frac{d}{ds}\Big\langle \nabla R(X+sV),\,V\Big\rangle\bigg|_{s=0} \;=\; \big\langle V,\ \nabla^2 R(X)[V]\big\rangle .dsd​⟨∇R(X+sV),V⟩​s=0​=⟨V, ∇2R(X)[V]⟩.

Equivalently, s↦R(X+sV)s\mapsto R(X+sV)s↦R(X+sV) is twice differentiable at 000 and its second derivative is the Hessian quadratic form vec(V)⊤∇2R(X) vec(V)\mathrm{vec}(V)^\top\nabla^2R(X)\,\mathrm{vec}(V)vec(V)⊤∇2R(X)vec(V). Row by row, for the radial function x↦h(∥x∥)x\mapsto h(\|x\|)x↦h(∥x∥) with h(t)=(t−α)+4h(t)=(t-\alpha)_+^4h(t)=(t−α)+4​, the Hessian is

h′′(t) uu⊤+h′(t)t(I−uu⊤),t=∥Xi∥,u=Xi/t,h''(t)\,uu^\top+\frac{h'(t)}{t}\left(I-uu^\top\right),\qquad t=\|X_i\|,\quad u=X_i/t,h′′(t)uu⊤+th′(t)​(I−uu⊤),t=∥Xi​∥,u=Xi​/t,

with h′(t)=4(t−α)+3h'(t)=4(t-\alpha)_+^3h′(t)=4(t−α)+3​ and h′′(t)=12(t−α)+2h''(t)=12(t-\alpha)_+^2h′′(t)=12(t−α)+2​, which is exactly the quantity the mission's model layer records.

Formalization Note The statement is phrased as a directional derivative of the directional gradient, mirroring the gradient milestone, so that no norm has to be fixed on matrix space and no second-order Frechet machinery is needed. The hypothesis α>0\alpha>0α>0 is what makes the formula correct at rows with Xi=0X_i=0Xi​=0: there RRR vanishes identically in a neighbourhood, and the formula's 0/00/00/0 terms are 000 under Lean's division convention, so both sides are zero. This is the missing analytic input to the first- and second-order optimality conditions (Chen-Li Lemma 4.3): the smooth part of the objective is a quartic polynomial along any line, so the regularizer is the only term whose second derivative needs an argument.

Preamble
import Definitions.Def_MCNoSpuriousMinModel
import Mathlib.Analysis.Calculus.Deriv.Basic
open Matrix MatrixCompletion.NoSpuriousMin
Formal statement
theorem MatrixCompletion.NoSpuriousMin.regularizer_hessian
    {d r : ℕ} (α : ℝ) (hα : 0 < α) (X V : Matrix (Fin d) (Fin r) ℝ) :
    HasDerivAt (fun s : ℝ => innerM (regGrad α (X + s • V)) V) (regHessQF α X V) 0 := by sorry
Source
Ge, Lee, Ma 2016, Matrix Completion has No Spurious Local Minimum, https://arxiv.org/abs/1605.07272 (v4), p. 11, Proposition 5.2 (the Hessian half; the printed exponent 4 in the gradient is corrected to 3 per the derivative of (t-alpha)_+^4 and the rank-1 form on its p. 9). Explicit Hessian form: Ge, Jin, Zheng 2017, No Spurious Local Minima in Nonconvex Low Rank Problems, https://arxiv.org/abs/1704.00708, Lemma 18. Used by: Chen, Li 2019, Model-free Nonconvex Matrix Completion, JMLR 20(142), https://arxiv.org/abs/1711.01742 (v3), pp. 16-19, Lemma 4.3 (second-order optimality condition).

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