Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 6 (case 1: 𝒡 bounded) β€” minima and minimizers of Ĉ_N(Β·|x) converge to v*(x) and 𝒡*(x)

Proved
PrescAnalytics.KNN.lemma_6_bounded_case

by mikedeng1 Β· Oct 6, 2026 Β· Mathlib 0df444a (Lean v4.33.1)

consistencyp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1stability-of-minimizers

Fix a covariate value xxx and one sample path of data: weights wN,iw_{N,i}wN,i​ that are nonnegative and sum to 111 for all large NNN, and observations yi∈Yy^i\in\mathcal Yyi∈Y. Let ZβŠ†Rdz\mathcal Z\subseteq\mathbb R^{d_z}ZβŠ†Rdz​ be closed, bounded and nonempty. Suppose c(z;β‹…)c(z;\cdot)c(z;β‹…) is ΞΌY∣x\mu_{Y|x}ΞΌY∣x​-integrable for every z∈Zz\in\mathcal Zz∈Z, ccc is equicontinuous in zzz (Assumption 4), ΞΌY∣x(Y)=1\mu_{Y|x}(\mathcal Y)=1ΞΌY∣x​(Y)=1, and C^N(z∣x)β†’C(z∣x)\widehat C_N(z\mid x)\to C(z\mid x)CN​(z∣x)β†’C(z∣x) for every z∈Zz\in\mathcal Zz∈Z. Then Zβˆ—(x)β‰ βˆ…\mathcal Z^*(x)\ne\emptysetZβˆ—(x)ξ€ =βˆ…, arg⁑min⁑z∈ZC^N(z∣x)β‰ βˆ…\arg\min_{z\in\mathcal Z}\widehat C_N(z\mid x)\ne\emptysetargminz∈Z​CN​(z∣x)ξ€ =βˆ… for all large NNN, and every sequence zN∈arg⁑min⁑z∈ZC^N(z∣x)z_N\in\arg\min_{z\in\mathcal Z}\widehat C_N(z\mid x)zNβ€‹βˆˆargminz∈Z​CN​(z∣x) (for all large NNN) satisfies

lim⁑Nβ†’βˆžmin⁑z∈ZC^N(z∣x)=vβˆ—(x),lim⁑Nβ†’βˆžC(zN∣x)=vβˆ—(x),lim⁑Nβ†’βˆžΒ inf⁑z∈Zβˆ—(x)βˆ₯zβˆ’zNβˆ₯=0.\lim_{N\to\infty}\min_{z\in\mathcal Z}\widehat C_N(z\mid x)=v^*(x),\qquad \lim_{N\to\infty}C(z_N\mid x)=v^*(x),\qquad \lim_{N\to\infty}\ \inf_{z\in\mathcal Z^*(x)}\|z-z_N\|=0 .Nβ†’βˆžlim​z∈Zmin​CN​(z∣x)=vβˆ—(x),Nβ†’βˆžlim​C(zNβ€‹βˆ£x)=vβˆ—(x),Nβ†’βˆžlim​ z∈Zβˆ—(x)inf​βˆ₯zβˆ’zN​βˆ₯=0.

This is the deterministic optimization step of the paper's argument: once the sample objective converges to the true conditional objective at xxx, the optimal values and the optimal decisions converge as well.

Formalization Note The paper states Lemma 6 under Assumption 5 in both cases, with the extra hypothesis ΞΌ^Y∣x,Nβ†’ΞΌY∣x\hat\mu_{Y|x,N}\to\mu_{Y|x}ΞΌ^​Y∣x,N​→μY∣x​ weakly. As printed it is false in case 2 (Z\mathcal ZZ unbounded): with Y=Z=R\mathcal Y=\mathcal Z=\mathbb RY=Z=R, ΞΌY∣x=Ξ΄0\mu_{Y|x}=\delta_0ΞΌY∣x​=Ξ΄0​, Dx={0}D_x=\{0\}Dx​={0}, c(z;y)=min⁑(1+∣z∣,β€‰βˆ£βˆ£zβˆ£βˆ’2/∣y∣∣)c(z;y)=\min(1+|z|,\,||z|-2/|y||)c(z;y)=min(1+∣z∣,∣∣zβˆ£βˆ’2/∣y∣∣) for yβ‰ 0y\neq0yξ€ =0, c(z;0)=1+∣z∣c(z;0)=1+|z|c(z;0)=1+∣z∣ and ΞΌ^Y∣x,N=Ξ΄1/N\hat\mu_{Y|x,N}=\delta_{1/N}ΞΌ^​Y∣x,N​=Ξ΄1/N​, every hypothesis holds but min⁑zC^N(z∣x)=0\min_z\widehat C_N(z\mid x)=0minz​CN​(z∣x)=0 while vβˆ—(x)=1v^*(x)=1vβˆ—(x)=1. The Lean therefore states case 1 only; the weak-convergence hypothesis is used only in case 2 and is dropped. vβˆ—(x)v^*(x)vβˆ—(x) is read as C(zβ‹†βˆ£x)C(z^\star\mid x)C(zβ‹†βˆ£x) for each zβ‹†βˆˆZβˆ—(x)z^\star\in\mathcal Z^*(x)zβ‹†βˆˆZβˆ—(x), and min⁑zC^N(z∣x)\min_{z}\widehat C_N(z\mid x)minz​CN​(z∣x) as C^N(zN∣x)\widehat C_N(z_N\mid x)CN​(zNβ€‹βˆ£x) at a minimizer; the attainment of both minima is part of the conclusion. Integrability at xxx, ΞΌY∣x(Y)=1\mu_{Y|x}(\mathcal Y)=1ΞΌY∣x​(Y)=1, yi∈Yy^i\in\mathcal Yyi∈Y and the normalization of the weights are read as in Lemma 5. Metric.infDist is the distance to Zβˆ—(x)\mathcal Z^*(x)Zβˆ—(x), which is nonempty by the first conclusion.

Preamble
import Mathlib
import Definitions.Def_PrescAnalytics_KNN_Basic

open MeasureTheory ProbabilityTheory Filter Topology
Formal statement
namespace PrescAnalytics.KNN

/-- **Lemma 6, case 1 of Assumption 5 (`𝒡` bounded)** (arXiv:1402.5481v4, pp. 45–47). Fix `x` and one
sample path: weights `w N i` that are eventually nonnegative and sum to 1, observations `ys i ∈ 𝒴`.
Let `𝒡` be closed, bounded and nonempty, `c(z; Β·)` integrable under `ΞΌ_{Y|x}` for every `z ∈ 𝒡`,
`c` equicontinuous in `z` on `𝒴` with `ΞΌ_{Y|x}(𝒴) = 1`, and `Ĉ_N(z|x) β†’ C(z|x)` for every `z ∈ 𝒡`.
Then `𝒡*(x) β‰  βˆ…`, the argmin of `Ĉ_N(Β·|x)` over `𝒡` is eventually nonempty, and every sequence
`z_N` of eventual minimizers of `Ĉ_N(Β·|x)` over `𝒡` satisfies, for every `z⋆ ∈ 𝒡*(x)`,
`min_{z ∈ 𝒡} Ĉ_N(z|x) = Ĉ_N(z_N|x) β†’ v*(x) = C(z⋆|x)` and `C(z_N|x) β†’ v*(x)`, and
`inf_{z ∈ 𝒡*(x)} β€–z - z_Nβ€– β†’ 0`. The printed hypothesis `ΞΌΜ‚_{Y|x,N} β†’ ΞΌ_{Y|x}` weakly is used only in
case 2 and is dropped. -/
theorem lemma_6_bounded_case
    {dx dy dz : β„•}
    (ΞΌ : Measure (EuclideanSpace ℝ (Fin dx) Γ— EuclideanSpace ℝ (Fin dy))) [IsProbabilityMeasure ΞΌ]
    (c : EuclideanSpace ℝ (Fin dz) β†’ EuclideanSpace ℝ (Fin dy) β†’ ℝ)
    (Z : Set (EuclideanSpace ℝ (Fin dz))) (Ys : Set (EuclideanSpace ℝ (Fin dy)))
    (hZ_closed : IsClosed Z) (hZ_bdd : Bornology.IsBounded Z) (hZ_ne : Z.Nonempty)
    (x : EuclideanSpace ℝ (Fin dx))
    (w : β„• β†’ β„• β†’ ℝ) (ys : β„• β†’ EuclideanSpace ℝ (Fin dy))
    (hys : βˆ€ i, ys i ∈ Ys) (hYx : βˆ€α΅ y βˆ‚(ΞΌ.condKernel x), y ∈ Ys)
    (hw : βˆ€αΆ  N in atTop, (βˆ€ i < N, 0 ≀ w N i) ∧ βˆ‘ i ∈ Finset.range N, w N i = 1)
    (h3x : βˆ€ z ∈ Z, Integrable (c z) (ΞΌ.condKernel x))
    (h4 : Assumption4 c Z Ys)
    (hconv : βˆ€ z ∈ Z, Tendsto (fun N => weightedCost c w ys N z) atTop (𝓝 (condCost ΞΌ c z x))) :
    (optSet μ c Z x).Nonempty ∧
      (βˆ€αΆ  N in atTop, (weightedArgmin c w ys Z N).Nonempty) ∧
      βˆ€ zN : β„• β†’ EuclideanSpace ℝ (Fin dz), (βˆ€αΆ  N in atTop, zN N ∈ weightedArgmin c w ys Z N) β†’
        (βˆ€ zstar ∈ optSet ΞΌ c Z x,
          Tendsto (fun N => weightedCost c w ys N (zN N)) atTop (𝓝 (condCost ΞΌ c zstar x)) ∧
          Tendsto (fun N => condCost ΞΌ c (zN N) x) atTop (𝓝 (condCost ΞΌ c zstar x))) ∧
        Tendsto (fun N => Metric.infDist (zN N) (optSet ΞΌ c Z x)) atTop (𝓝 0) := by sorry

end PrescAnalytics.KNN
Source
Bertsimas, Kallus, From Predictive to Prescriptive Analytics, arXiv:1402.5481v4, pp. 45–47, Lemma 6 (case 1 of Assumption 5)
Human review
  • Endorsed by Shuze Chen Β· Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 Β· Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

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