Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 3, Eqs. (28)–(29) — empirical least squares: θ_x = [V^M]⁻¹(1/M)Σ v^m x^m and λ_min|θ_x|² ≤ |θ_x·v|²_M ≤ |x|²_M

Proved
RegMCBSDE.Simulation.eq_28_29_least_squares

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

least-squaresp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1regression

Let M≥1M\ge1M≥1, let x=(xm)1≤m≤Mx=(x^m)_{1\le m\le M}x=(xm)1≤m≤M​ be real numbers and (vm)1≤m≤M(v^m)_{1\le m\le M}(vm)1≤m≤M​ vectors of Rn\mathbb R^nRn, and suppose that VM=1M∑m=1Mvm[vm]∗V^M=\frac1M\sum_{m=1}^Mv^m[v^m]^*VM=M1​∑m=1M​vm[vm]∗ is invertible, i.e. λmin⁡(VM)>0\lambda_{\min}(V^M)>0λmin​(VM)>0. For y∈RMy\in\mathbb R^My∈RM write ∣y∣M2=1M∑m=1M∣ym∣2|y|_M^2=\frac1M\sum_{m=1}^M|y_m|^2∣y∣M2​=M1​∑m=1M​∣ym​∣2. Then

  1. the vector
θx=[VM]−1M∑m=1Mvmxm(28)\theta_x=\frac{[V^M]^{-1}}{M}\sum_{m=1}^Mv^mx^m \qquad (28)θx​=M[VM]−1​m=1∑M​vmxm(28)

is the unique minimizer of θ↦∣x−θ⋅v∣M2\theta\mapsto|x-\theta\cdot v|_M^2θ↦∣x−θ⋅v∣M2​; 2. the map x↦θxx\mapsto\theta_xx↦θx​ is linear; 3. for every c≤λmin⁡(VM)c\le\lambda_{\min}(V^M)c≤λmin​(VM),

c ∣θx∣2≤∣θx⋅v∣M2≤∣x∣M2.(29)c\,|\theta_x|^2\le|\theta_x\cdot v|^2_M\le|x|^2_M. \qquad (29)c∣θx​∣2≤∣θx​⋅v∣M2​≤∣x∣M2​.(29)

This is the empirical counterpart of the contraction property of L2\mathbf L_2L2​ projections, and it is the tool behind every bound on the empirical regression coefficients in the proof of Theorem 3.

Formalization Note The vectors are indexed by an arbitrary finite type. Invertibility is stated as positive definiteness of VMV^MVM (equivalent, since VMV^MVM is positive semidefinite). Inequality (29) with λmin⁡(VM)\lambda_{\min}(V^M)λmin​(VM) is stated for every ccc with c∣y∣2≤y∗VMyc|y|^2\le y^*V^Myc∣y∣2≤y∗VMy for all yyy, which is the set c≤λmin⁡(VM)c\le\lambda_{\min}(V^M)c≤λmin​(VM).

Preamble
import Mathlib
import Definitions.Def_RegMCBSDE_Simulation_Setting
Formal statement
namespace RegMCBSDE.Simulation

/-- Proof of Theorem 3, Eqs. (28)–(29), p. 18: the empirical least-squares problem in `ℝ^M`.
Let `x^1, …, x^M ∈ ℝ` and `v^1, …, v^M ∈ ℝ^ι`, `M ≥ 1`, and suppose
`V^M = (1/M) ∑_m v^m [v^m]^*` is invertible (positive definite, `λ_min(V^M) > 0`). Then
`θ_x = (V^M)^{-1} (1/M) ∑_m v^m x^m` (28) is the unique minimizer of `θ ↦ |x - θ·v|²_M`, where
`|y|²_M = (1/M) ∑_m y_m²`; the map `x ↦ θ_x` is linear; and for every `c ≤ λ_min(V^M)` (encoded as
`c |y|² ≤ y^* V^M y` for all `y`), `c |θ_x|² ≤ |θ_x·v|²_M ≤ |x|²_M` (29). -/
theorem eq_28_29_least_squares {ι : Type*} [Fintype ι] [DecidableEq ι] (M : ℕ) (hM : 0 < M)
    (v : Fin M → ι → ℝ)
    (hV : ((1 / (M : ℝ)) • ∑ s, Matrix.vecMulVec (v s) (v s)).PosDef) :
    let V : Matrix ι ι ℝ := (1 / (M : ℝ)) • ∑ s, Matrix.vecMulVec (v s) (v s)
    let empSq : (Fin M → ℝ) → ℝ := fun y => (1 / (M : ℝ)) * ∑ s, y s ^ 2
    let θ : (Fin M → ℝ) → (ι → ℝ) := fun x => V⁻¹.mulVec ((1 / (M : ℝ)) • ∑ s, x s • v s)
    (∀ x : Fin M → ℝ, ∀ θ' : ι → ℝ, θ' ≠ θ x →
        empSq (fun s => x s - θ x ⬝ᵥ v s) < empSq (fun s => x s - θ' ⬝ᵥ v s)) ∧
    (∀ (a b : ℝ) (x y : Fin M → ℝ), θ (a • x + b • y) = a • θ x + b • θ y) ∧
    (∀ (c : ℝ), (∀ y : ι → ℝ, c * sqn y ≤ y ⬝ᵥ V.mulVec y) → ∀ x : Fin M → ℝ,
        c * sqn (θ x) ≤ empSq (fun s => θ x ⬝ᵥ v s) ∧ empSq (fun s => θ x ⬝ᵥ v s) ≤ empSq x) := by sorry

end RegMCBSDE.Simulation
Source
Gobet, Lemor and Warin, A regression-based Monte Carlo method to solve backward stochastic differential equations, arXiv:math/0508491v1, p. 18, Proof of Theorem 3, Eqs. (28)–(29)
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

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