Lemma C.4 — weighted least squares as a convex combination of interpolants
ProvedIAFTRL.lemma_C_4bandit-algorithmslinear-banditsonline-learningp2o-gran-per-chapterp2o-plan-bookp2o-strengthenedp2o-v1
Let , and weights be such that
For an -element index set let be the matrix with rows , , and, when is invertible, let be the exact interpolant of the data indexed by . Set
Then
The weighted least-squares coefficient is thus a convex combination of exact interpolants; Lemma C.3 uses this to bound a least-squares residual by the interpolation constant .
Formalization Note Indices are Fin m; the rows of are taken in the increasing order of , and none of , , depends on the row order.
Differences from the source:
- encoding: index set of actions, rows of unordered → a subset of
Fin mof size , rows of in increasing order of ; reason: , and the residual do not depend on the row order - generalization: for the index sets in the sum → for every -element index set; reason: true for every (, , ); specializes to the source
Preamble
import Mathlib
Formal statement
namespace IAFTRL
open Matrix
/-- **Lemma C.4 (Weighted least squares as a convex combination of interpolants).** Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits*, arXiv:2611.01299,
Lemma C.4, p.62: "If `V = Σ_a w_a x_a x_a^⊤ ≻ 0`, `w_a ≥ 0`, then
`V^{-1} Σ_a w_a x_a z_a = Σ_{I:det B_I≠0} ω_I v_I`, `ω_I = det(B_I)² Π_{a∈I} w_a / det V`, `ω_I ≥ 0`,
`Σ_I ω_I = 1`." In the proof: "Let `r = dim x_a`, let `X` have rows `x_a^⊤` … For `|I| = r`, let
`B_I = X_{I,:}`", and `v_I = B_I^{-1} z_I` ((C.44d)).
For points `x_a ∈ ℝ^r`, responses `z_a` and weights `w_a ≥ 0` (`a = 1, …, m`) with
`V = Σ_a w_a x_a x_a^⊤` positive definite: for each `r`-element index set `I`, `B_I` is the `r × r`
matrix with rows `x_a^⊤`, `a ∈ I`, `v_I = B_I^{-1}(z_a)_{a∈I}` the exact interpolant, and
`ω_I = det(B_I)² Π_{a∈I} w_a / det V`. Then the weighted least-squares coefficient
`V^{-1} Σ_a w_a z_a x_a` equals `Σ_{I : det B_I ≠ 0} ω_I v_I`, every `ω_I ≥ 0`, and the `ω_I` with
`det B_I ≠ 0` sum to `1`.
**Formalization Note.** Indices are `Fin m`; the rows of `B_I` follow the increasing order of `I`
(`I.orderEmbOfFin`); `det B_I²`, `v_I` and `ω_I` do not depend on the row order. `ω_I ≥ 0` is stated
for every `I`. -/
theorem lemma_C_4 {m r : ℕ} (x : Fin m → Fin r → ℝ) (z w : Fin m → ℝ) (hw : ∀ a, 0 ≤ w a)
(hV : (∑ a, w a • vecMulVec (x a) (x a)).PosDef) :
let V : Matrix (Fin r) (Fin r) ℝ := ∑ a, w a • vecMulVec (x a) (x a)
let B : {I : Finset (Fin m) // I.card = r} → Matrix (Fin r) (Fin r) ℝ :=
fun I => Matrix.of fun i k => x (I.1.orderEmbOfFin I.2 i) k
let vI : {I : Finset (Fin m) // I.card = r} → Fin r → ℝ :=
fun I => (B I)⁻¹ *ᵥ fun i => z (I.1.orderEmbOfFin I.2 i)
let ωI : {I : Finset (Fin m) // I.card = r} → ℝ :=
fun I => (B I).det ^ 2 * (∏ a ∈ I.1, w a) / V.det
V⁻¹ *ᵥ (∑ a, (w a * z a) • x a) =
∑ I ∈ Finset.univ.filter (fun I => (B I).det ≠ 0), ωI I • vI I ∧
(∀ I, 0 ≤ ωI I) ∧
∑ I ∈ Finset.univ.filter (fun I => (B I).det ≠ 0), ωI I = 1 := by sorry
end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits, arXiv:2611.01299, Appendix C.2, Lemma C.4, p.62
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.