§4.2.1 —
ProvedForecastAggLearn.hstar_norm_boundforecast-aggregationonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1probability
Let be a real matrix and with , i.e. for every . Then is injective, , and satisfies
This is the verification that the ball of radius used by online gradient descent contains the optimal aggregation vector .
Formalization Note Norms are Euclidean. , where is the least eigenvalue of (p.12), is encoded as for all ; for the two are the same.
Differences from the source:
- generalization: A the 0/1 evidence matrix → any real n × m matrix; reason: the evidence matrix is the 0/1 case
- encoding: σ_min(A) ≥ σ with σ_min(A)² = λ_min(AᵀA); ‖h*‖² ≤ m/σ_min(A)² ≤ n/σ² → σ‖y‖ ≤ ‖Ay‖ for all y; ‖h*‖² ≤ m/σ², m ≤ n, ‖h*‖ ≤ √n/σ; reason: the norm inequality is λ_min(AᵀA) ≥ σ² for m ≥ 1; taking σ = σ_min(A) gives the middle bound
Preamble
import Mathlib import Definitions.Def_ForecastAggLearn_hstar
Formal statement
namespace ForecastAggLearn
/-- **Norm bound on `h*`.**
Babichenko, Garber, arXiv:1802.07107v1, §4.2.1, display, p.19:
`‖A_l^{−1⊤} 1_m‖²₂ = ‖A(A^⊤A)^{−1} 1_m‖²₂ ≤ ‖A(A^⊤A)^{−1}‖²₂ · ‖1_m‖²₂ = m · ‖Σ^{−1}‖²₂
= m / σ_min(A)² ≤ n/σ² = W²`, "where the last inequality holds using the fact that A is
injective, which implies that m ≤ n, and our assumption that σ_min(A) ≥ σ."
For `σ > 0` with `σ_min(A) ≥ σ`: `‖h*‖² ≤ m/σ²`, `m ≤ n`, and `‖h*‖ ≤ √n/σ = W`.
**Formalization Note.** `σ_min(A) ≥ σ` (with `σ_min(A)²` the least eigenvalue of `A^⊤A`, p.12)
is encoded as `σ‖y‖ ≤ ‖Ay‖` for all `y ∈ ℝ^m`, Euclidean norms; it implies that `A` is
injective. Stated for every real `n × m` matrix (the evidence matrix is the 0/1 case). -/
theorem hstar_norm_bound {n m : ℕ} (A : Matrix (Fin n) (Fin m) ℝ) (σ : ℝ) (hσ : 0 < σ)
(hA : ∀ y : EuclideanSpace ℝ (Fin m),
σ * ‖y‖ ≤ ‖(WithLp.toLp 2 (A.mulVec y.ofLp) : EuclideanSpace ℝ (Fin n))‖) :
‖(WithLp.toLp 2 (hstar A) : EuclideanSpace ℝ (Fin n))‖ ^ 2 ≤ m / σ ^ 2 ∧ m ≤ n ∧
‖(WithLp.toLp 2 (hstar A) : EuclideanSpace ℝ (Fin n))‖ ≤ Real.sqrt n / σ := by sorry
end ForecastAggLearn
Source
Babichenko, Garber, Learning of Optimal Forecast Aggregation in Partial Evidence Environments, arXiv:1802.07107v1, §4.2.1, display, p.19
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.