Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5 (kNN), case 2 of Assumption 5 — asymptotic optimality and consistency for unbounded feasible sets

Open
PrescAnalytics.KNN.theorem_5_knn_unbounded_case

by tianyipeng · Nov 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

asymptotic-optimalityconditional-stochastic-optimizationconsistencynearest-neighbors

Let (x1,y1),(x2,y2),…(x^1,y^1),(x^2,y^2),\dots(x1,y1),(x2,y2),… be independent and identically distributed with law μ\muμ of (X,Y)(X,Y)(X,Y) on Rdx×Rdy\mathbb R^{d_x}\times\mathbb R^{d_y}Rdx​×Rdy​, with X∈XX\in\mathcal XX∈X and Y∈YY\in\mathcal YY∈Y almost surely. Let c:Rdz×Rdy→Rc:\mathbb R^{d_z}\times\mathbb R^{d_y}\to\mathbb Rc:Rdz​×Rdy​→R be a cost and Z⊆Rdz\mathcal Z\subseteq\mathbb R^{d_z}Z⊆Rdz​ a feasible set satisfying Assumption 3 (existence) and Assumption 4 (equicontinuity of c(z;y)c(z;y)c(z;y) in zzz, uniformly over y∈Yy\in\mathcal Yy∈Y), and case 2 of Assumption 5:

  1. Z\mathcal ZZ is closed and nonempty;
  2. lim inf⁡∥z∥→∞inf⁡y∈Yc(z;y)>−∞\liminf_{\|z\|\to\infty}\inf_{y\in\mathcal Y} c(z;y)>-\inftyliminf∥z∥→∞​infy∈Y​c(z;y)>−∞;
  3. for every x∈Xx\in\mathcal Xx∈X there is a measurable Dx⊆YD_x\subseteq\mathcal YDx​⊆Y with μY∣x(Dx)>0\mu_{Y|x}(D_x)>0μY∣x​(Dx​)>0 such that c(z;y)→∞c(z;y)\to\inftyc(z;y)→∞ as ∥z∥→∞\|z\|\to\infty∥z∥→∞, uniformly over y∈Dxy\in D_xy∈Dx​.

Let wN,i(x)w_{N,i}(x)wN,i​(x) be the kNN weights (12) with

k=min⁡{⌈CNδ⌉, N−1},C>0, 0<δ<1,k=\min\big\{\lceil CN^\delta\rceil,\ N-1\big\},\qquad C>0,\ 0<\delta<1,k=min{⌈CNδ⌉, N−1},C>0, 0<δ<1,

and let z^N(x)∈arg⁡min⁡z∈Z∑i=1NwN,i(x) c(z;yi)\hat z_N(x)\in\arg\min_{z\in\mathcal Z}\sum_{i=1}^N w_{N,i}(x)\,c(z;y^i)z^N​(x)∈argminz∈Z​∑i=1N​wN,i​(x)c(z;yi) as in (3). Then z^N(x)\hat z_N(x)z^N​(x) is asymptotically optimal and consistent: with probability 1, for μX\mu_XμX​-almost every xxx,

lim⁡N→∞E[c(z^N(x);Y)∣X=x]=v∗(x)andlim⁡N→∞ inf⁡z∈Z∗(x)∥z^N(x)−z∥=0.\lim_{N\to\infty}\mathbb E\big[c(\hat z_N(x);Y)\mid X=x\big]=v^*(x)\qquad\text{and}\qquad \lim_{N\to\infty}\ \inf_{z\in\mathcal Z^*(x)}\|\hat z_N(x)-z\|=0 .N→∞lim​E[c(z^N​(x);Y)∣X=x]=v∗(x)andN→∞lim​ z∈Z∗(x)inf​∥z^N​(x)−z∥=0.

This is the unbounded-feasible-set half of Theorem 5 (e.g. the newsvendor with Z=[0,∞)\mathcal Z=[0,\infty)Z=[0,∞)); 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-xxx 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.

Preamble
import Mathlib
import Definitions.Def_PrescAnalytics_KNN_Basic

open MeasureTheory ProbabilityTheory Filter Topology
Formal statement
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
Source
Bertsimas, Kallus, From Predictive to Prescriptive Analytics, arXiv:1402.5481v4, p. 19, Theorem 5 with Assumption 5 case 2 (pp. 18-19); restated with iid sampling as Theorem 15, p. 43; proof p. 47 (via Lemmas 5-7, pp. 45-47)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me