Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma A.1, p. 40 — ‖J₁‖∞ ≲ (r₁+r₄)(r₁²+r₂), ‖J₂‖∞ ≲ r₁²r₅, ‖J₃‖∞ ≲ r₁r₃

Proved
LagrangeRank.Debias.lemma_A_1

by mikedeng1 · Oct 22, 2026 · Mathlib 0df444a (Lean v4.33.1)

constrained-inferencedebiased-estimatorp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1taylor-remainder

Let c1,c2,L1,L2∈Rc_1,c_2,L_1,L_2\in\mathbb Rc1​,c2​,L1​,L2​∈R and c3>0c_3>0c3​>0. There are constants C,δ>0C,\delta>0C,δ>0, depending only on c1,c2,c3,L1,L2c_1,c_2,c_3,L_1,L_2c1​,c2​,c3​,L1​,L2​ and not on the dimension, such that the following holds for every ddd.

Let F:Rd→RF:\mathbb R^d\to\mathbb RF:Rd→R be C2C^2C2 (one realization of the loss LLL), f:Rd→Rf:\mathbb R^d\to\mathbb Rf:Rd→R be C1C^1C1 with f(θ∗)=0f(\theta^*)=0f(θ∗)=0, Ω^,Ω∗∈Rd×d\widehat\Omega,\Omega^*\in\mathbb R^{d\times d}Ω,Ω∗∈Rd×d, θ^,θ∗∈Rd\widehat\theta,\theta^*\in\mathbb R^dθ,θ∗∈Rd and ρ1,…,ρ5≥0\rho_1,\dots,\rho_5\ge0ρ1​,…,ρ5​≥0 with ρ1+ρ4≤δ\rho_1+\rho_4\le\deltaρ1​+ρ4​≤δ. Write θt=θ∗+t(θ^−θ∗)\theta_t=\theta^*+t(\widehat\theta-\theta^*)θt​=θ∗+t(θ−θ∗). Assume

  1. ∥θ^−θ∗∥∞≤ρ1\|\widehat\theta-\theta^*\|_\infty\le\rho_1∥θ−θ∗∥∞​≤ρ1​ and ∥∇F(θ∗)∥∞≤ρ2\|\nabla F(\theta^*)\|_\infty\le\rho_2∥∇F(θ∗)∥∞​≤ρ2​;
  2. ∥∇2F(θt)−∇2F(θ∗)∥∞≤L1∥θt−θ∗∥∞\|\nabla^2F(\theta_t)-\nabla^2F(\theta^*)\|_\infty\le L_1\|\theta_t-\theta^*\|_\infty∥∇2F(θt​)−∇2F(θ∗)∥∞​≤L1​∥θt​−θ∗∥∞​ and ∥∇f(θt)−∇f(θ∗)∥1≤L2∥θt−θ∗∥∞\|\nabla f(\theta_t)-\nabla f(\theta^*)\|_1\le L_2\|\theta_t-\theta^*\|_\infty∥∇f(θt​)−∇f(θ∗)∥1​≤L2​∥θt​−θ∗∥∞​ for all t∈[0,1]t\in[0,1]t∈[0,1];
  3. ∥∇f(θ∗)∥1≤c1\|\nabla f(\theta^*)\|_1\le c_1∥∇f(θ∗)∥1​≤c1​;
  4. ∥I−Ω^∇2F(θ^)∥∞≤ρ3\|I-\widehat\Omega\nabla^2F(\widehat\theta)\|_\infty\le\rho_3∥I−Ω∇2F(θ)∥∞​≤ρ3​, ∥Ω^−Ω∗∥∞≤ρ4\|\widehat\Omega-\Omega^*\|_\infty\le\rho_4∥Ω−Ω∗∥∞​≤ρ4​, ∥Ω∗∥∞≤c2\|\Omega^*\|_\infty\le c_2∥Ω∗∥∞​≤c2​, ∇f(θ∗)⊤Ω∗∇f(θ∗)≥c3\nabla f(\theta^*)^\top\Omega^*\nabla f(\theta^*)\ge c_3∇f(θ∗)⊤Ω∗∇f(θ∗)≥c3​ and ∥Θ∗∥∞≤ρ5\|\Theta^*\|_\infty\le\rho_5∥Θ∗∥∞​≤ρ5​.

Then for the remainders J1,J2,J3J_1,J_2,J_3J1​,J2​,J3​ of (A.1), writing [ ⋅ ]θ[\,\cdot\,]_\theta[⋅]θ​ for the first ddd coordinates,

∥[J1]θ∥∞≤C(ρ1+ρ4)(ρ12+ρ2),∥J2∥∞≤Cρ12ρ5,∥[J3]θ∥∞≤Cρ1ρ3,\|[J_1]_\theta\|_\infty\le C(\rho_1+\rho_4)(\rho_1^2+\rho_2),\qquad \|J_2\|_\infty\le C\rho_1^2\rho_5,\qquad \|[J_3]_\theta\|_\infty\le C\rho_1\rho_3,∥[J1​]θ​∥∞​≤C(ρ1​+ρ4​)(ρ12​+ρ2​),∥J2​∥∞​≤Cρ12​ρ5​,∥[J3​]θ​∥∞​≤Cρ1​ρ3​,

and ∥[J1+J2+J3]θ∥∞≤C(ρ12ρ5+(ρ1+ρ4)(ρ12+ρ2)+ρ1ρ3)\|[J_1+J_2+J_3]_\theta\|_\infty\le C\big(\rho_1^2\rho_5+(\rho_1+\rho_4)(\rho_1^2+\rho_2)+\rho_1\rho_3\big)∥[J1​+J2​+J3​]θ​∥∞​≤C(ρ12​ρ5​+(ρ1​+ρ4​)(ρ12​+ρ2​)+ρ1​ρ3​).

With ρk≍rk\rho_k\asymp r_kρk​≍rk​ these are (A.2)–(A.4) and the bound that follows them in the proof of Theorem 3.1.

Formalization Note. Lemma A.1 is stated "under the conditions of Theorem 3.1"; here it is the deterministic statement for one realization, with the rates replaced by numbers ρk\rho_kρk​ and the smallness of r1,r4r_1,r_4r1​,r4​ by ρ1+ρ4≤δ\rho_1+\rho_4\le\deltaρ1​+ρ4​≤δ. The bounds on J1J_1J1​ and J3J_3J3​ are for the first ddd coordinates (the ones Theorem 3.1 uses): the last coordinate involves the lower-left block of Θ^−Θ∗\widehat\Theta-\Theta^*Θ−Θ∗ and of I−Θ^Σ^I-\widehat\Theta\widehat\SigmaI−ΘΣ, which Assumption 3.4 does not control (see Corollaries 3.1–3.2). The hypothesis f(θ∗)=0f(\theta^*)=0f(θ∗)=0 is used in C.1.1 to write −f(θ^)+∇f(θ^)⊤(θ^−θ∗)-f(\widehat\theta)+\nabla f(\widehat\theta)^\top(\widehat\theta-\theta^*)−f(θ)+∇f(θ)⊤(θ−θ∗) as a Taylor remainder.

Preamble
import Mathlib
import Definitions.Def_LagrangeRank_Debias_Setting
Formal statement
namespace LagrangeRank.Debias
open Matrix
theorem lemma_A_1 (c1 c2 c3 L1 L2 : ℝ) (hc3 : 0 < c3) :
    ∃ C δ : ℝ, 0 < C ∧ 0 < δ ∧
      ∀ (d : ℕ) (F f : (Fin d → ℝ) → ℝ) (OmHat OmStar : Matrix (Fin d) (Fin d) ℝ)
        (thetaHat thetaStar : Fin d → ℝ) (ρ1 ρ2 ρ3 ρ4 ρ5 : ℝ),
        ContDiff ℝ 2 F → ContDiff ℝ 1 f → f thetaStar = 0 →
        0 ≤ ρ1 → 0 ≤ ρ2 → 0 ≤ ρ3 → 0 ≤ ρ4 → 0 ≤ ρ5 → ρ1 + ρ4 ≤ δ →
        ‖thetaHat - thetaStar‖ ≤ ρ1 →
        ‖grad F thetaStar‖ ≤ ρ2 →
        (∀ t ∈ Set.Icc (0 : ℝ) 1,
          rowSumNorm (hess F (thetaStar + t • (thetaHat - thetaStar)) - hess F thetaStar)
            ≤ L1 * ‖(thetaStar + t • (thetaHat - thetaStar)) - thetaStar‖) →
        l1Norm (grad f thetaStar) ≤ c1 →
        (∀ t ∈ Set.Icc (0 : ℝ) 1,
          l1Norm (grad f (thetaStar + t • (thetaHat - thetaStar)) - grad f thetaStar)
            ≤ L2 * ‖(thetaStar + t • (thetaHat - thetaStar)) - thetaStar‖) →
        rowSumNorm (1 - OmHat * hess F thetaHat) ≤ ρ3 →
        rowSumNorm (OmHat - OmStar) ≤ ρ4 →
        rowSumNorm OmStar ≤ c2 →
        c3 ≤ grad f thetaStar ⬝ᵥ (OmStar *ᵥ grad f thetaStar) →
        rowSumNorm (thetaBlock OmStar (grad f thetaStar)) ≤ ρ5 →
        ‖fun k => remJ1 (thetaBlock OmHat (grad f thetaHat)) (thetaBlock OmStar (grad f thetaStar))
            (grad F) (hess F thetaHat) f (grad f) thetaHat thetaStar (Sum.inl k)‖
            ≤ C * ((ρ1 + ρ4) * (ρ1 ^ 2 + ρ2)) ∧
        ‖remJ2 (thetaBlock OmStar (grad f thetaStar))
            (grad F) (hess F thetaHat) f (grad f) thetaHat thetaStar‖
            ≤ C * (ρ1 ^ 2 * ρ5) ∧
        ‖fun k => remJ3 (thetaBlock OmHat (grad f thetaHat))
            (borderedHessian (hess F thetaHat) (grad f thetaHat)) thetaHat thetaStar (Sum.inl k)‖
            ≤ C * (ρ1 * ρ3) ∧
        ‖fun k => (remJ1 (thetaBlock OmHat (grad f thetaHat)) (thetaBlock OmStar (grad f thetaStar))
              (grad F) (hess F thetaHat) f (grad f) thetaHat thetaStar
            + remJ2 (thetaBlock OmStar (grad f thetaStar))
              (grad F) (hess F thetaHat) f (grad f) thetaHat thetaStar
            + remJ3 (thetaBlock OmHat (grad f thetaHat))
              (borderedHessian (hess F thetaHat) (grad f thetaHat)) thetaHat thetaStar) (Sum.inl k)‖
            ≤ C * (ρ1 ^ 2 * ρ5 + (ρ1 + ρ4) * (ρ1 ^ 2 + ρ2) + ρ1 * ρ3) := by sorry
end LagrangeRank.Debias
Source
Liu, Fang, Lu, Lagrangian Inference for Ranking Problems, arXiv:2110.00151v1, p. 40, Lemma A.1, (A.2)–(A.4) and the display following them; proof in Appendix C.1.1, pp. 45–46
Human review
  • Endorsed by Shuze Chen · Oct 23, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 23, 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