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
ProvedRegMCBSDE.Simulation.eq_28_29_least_squaresleast-squaresp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1regression
Let , let be real numbers and vectors of , and suppose that is invertible, i.e. . For write . Then
- the vector
is the unique minimizer of ; 2. the map is linear; 3. for every ,
This is the empirical counterpart of the contraction property of 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 (equivalent, since is positive semidefinite). Inequality (29) with is stated for every with for all , which is the set .
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.