Lemma D.1, p. 26 — Σ_{i=1}^t φ_i^⊤(Λ_t)^{-1}φ_i ≤ d for Λ_t = λI + Σφ_iφ_i^⊤
ProvedLinearMDPRL.Misspec.lemma_D_1gram-matrixlinear-algebrap2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1ridge-regression
Let , let , and let . Then
A deterministic trace inequality for regularized Gram matrices; it is the last step of the proof of Lemma C.4.
Formalization Note The vectors are a sequence indexed by , of which are used. The same lemma is drafted in the companion mission on Theorem 3.1; it is restated here because draft items cannot import each other.
Preamble
import Mathlib open Matrix
Formal statement
namespace LinearMDPRL.Misspec
/-- **Lemma D.1** (p. 26). Let `Λ_t = λI + Σ_{i=1}^t φ_i φ_i^⊤` with `φ_i ∈ ℝ^d` and `λ > 0`. Then
`Σ_{i=1}^t φ_i^⊤ (Λ_t)^{-1} φ_i ≤ d`. -/
theorem lemma_D_1 {d : ℕ} (lam : ℝ) (hlam : 0 < lam) (t : ℕ) (φ : ℕ → Fin d → ℝ) :
∑ i ∈ Finset.Icc 1 t,
φ i ⬝ᵥ (lam • (1 : Matrix (Fin d) (Fin d) ℝ) +
∑ j ∈ Finset.Icc 1 t, vecMulVec (φ j) (φ j))⁻¹ *ᵥ φ i ≤ d := by sorry
end LinearMDPRL.Misspec
Source
arXiv:1907.05388v2, Lemma D.1, p. 26
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.