Theorem 5 (kNN), case 2 of Assumption 5 — asymptotic optimality and consistency for unbounded feasible sets
OpenPrescAnalytics.KNN.theorem_5_knn_unbounded_caseLet be independent and identically distributed with law of on , with and almost surely. Let be a cost and a feasible set satisfying Assumption 3 (existence) and Assumption 4 (equicontinuity of in , uniformly over ), and case 2 of Assumption 5:
- is closed and nonempty;
- ;
- for every there is a measurable with such that as , uniformly over .
Let be the kNN weights (12) with
and let as in (3). Then is asymptotically optimal and consistent: with probability 1, for -almost every ,
This is the unbounded-feasible-set half of Theorem 5 (e.g. the newsvendor with ); the bounded half (case 1 of Assumption 5) follows from the Walk (2010) step and Lemma 6, so Theorem 5 is the conjunction of the two cases.
Formalization Note Identical to PrescAnalytics.KNN.theorem_5_knn_asymptotically_optimal, with the hypothesis Assumption5 replaced by its second disjunct written out (IsClosed Z, Z.Nonempty, CostBoundedBelowAtInfinity c Z Ys, and the per- coercivity sets read in the version μ.condKernel x). The conclusion is Definition 1 for every selection from the argmin, inside the almost-sure quantifiers, exactly as in the parent theorem.
import Mathlib import Definitions.Def_PrescAnalytics_KNN_Basic open MeasureTheory ProbabilityTheory Filter Topology
namespace PrescAnalytics.KNN
/-- **Theorem 5 (kNN) under case 2 of Assumption 5** (= Theorem 15, iid case, arXiv:1402.5481v4,
pp. 19, 43, 47). Under Assumptions 3 and 4, with `𝒵` closed and nonempty,
`liminf_{‖z‖→∞} inf_{y ∈ 𝒴} c(z; y) > -∞`, and for every `x ∈ 𝒳` a measurable `D_x ⊆ 𝒴` with
`μ_{Y|x}(D_x) > 0` on which `c(z; y) → ∞` as `‖z‖ → ∞` uniformly (case 2 of Assumption 5), and iid
data `(x^i, y^i) ~ μ`, the kNN predictive prescription with `k = min {⌈C N^δ⌉, N - 1}`, `C > 0`,
`0 < δ < 1`, is asymptotically optimal and consistent (Definition 1), for every selection from its
argmin. -/
theorem theorem_5_knn_unbounded_case
{Ω : Type*} [MeasurableSpace Ω] {P : Measure Ω} [IsProbabilityMeasure P]
{dx dy dz : ℕ}
(μ : Measure (EuclideanSpace ℝ (Fin dx) × EuclideanSpace ℝ (Fin dy))) [IsProbabilityMeasure μ]
(S : ℕ → Ω → EuclideanSpace ℝ (Fin dx) × EuclideanSpace ℝ (Fin dy))
(hS_meas : ∀ i, Measurable (S i)) (hS_indep : iIndepFun S P)
(hS_law : ∀ i, P.map (S i) = μ)
(c : EuclideanSpace ℝ (Fin dz) → EuclideanSpace ℝ (Fin dy) → ℝ)
(Z : Set (EuclideanSpace ℝ (Fin dz)))
(Xs : Set (EuclideanSpace ℝ (Fin dx))) (Ys : Set (EuclideanSpace ℝ (Fin dy)))
(hXs : ∀ᵐ p ∂μ, p.1 ∈ Xs) (hYs : ∀ᵐ p ∂μ, p.2 ∈ Ys)
(h3 : Assumption3 μ c Z) (h4 : Assumption4 c Z Ys)
(hZ_closed : IsClosed Z) (hZ_ne : Z.Nonempty)
(h5_below : CostBoundedBelowAtInfinity c Z Ys)
(h5_coercive : ∀ x ∈ Xs, ∃ D ⊆ Ys, MeasurableSet D ∧ 0 < μ.condKernel x D ∧
CoerciveUniformlyOn c Z D)
(C δ : ℝ) (hC : 0 < C) (hδ0 : 0 < δ) (hδ1 : δ < 1) :
IsAsymptoticallyOptimal P μ c Z (knnArgmin C δ c Z S) ∧
IsConsistent P μ c Z (knnArgmin C δ c Z S) := by sorry
end PrescAnalytics.KNN