B.3, p. 27 — the Nadaraya–Watson estimate is the maximum of an (s, P) program with a single feasible point
ProvedBootRobust.NWDual.nw_eq_programlinear-programmingnadaraya-watsonp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1prescriptive-analytics
Let be a distribution on the finite support , let be positive weights and arbitrary losses. Then the Nadaraya–Watson estimate
is the maximum of the program
The maximum is attained; in fact the only feasible point is , .
This rewrites the ratio estimator as a linear objective over a cone, the first step towards the perspective program of Corollary 1.
Preamble
import Mathlib import Definitions.Def_BootRobust_NWDual_Setting
Formal statement
namespace BootRobust.NWDual
/-- B.3, p. 27: the Nadaraya–Watson estimate (19) at `D ∈ Dₙ` is the maximum of the linear
program over `s > 0` and `P` with `P = s · D`, `∑ P = s` and `∑ w P = 1`. -/
theorem nw_eq_program {ι : Type*} [Fintype ι] [DecidableEq ι]
(D : ι → ℝ) (hD : D ∈ stdSimplex ℝ ι) (w : ι → ℝ) (hw : ∀ i, 0 < w i) (ℓ : ι → ℝ) :
IsGreatest {x : ℝ | ∃ (s : ℝ) (P : ι → ℝ), 0 < s ∧ (∀ i, P i = D i * s) ∧
∑ i, P i = s ∧ ∑ i, w i * P i = 1 ∧ x = ∑ i, w i * ℓ i * P i}
(BootRobust.Perf.nwEst w ℓ D) := by sorry
end BootRobust.NWDual
Source
Bertsimas and Van Parys, Bootstrap robust prescriptive analytics, arXiv:1711.09974v2, B.3 (proof of Corollary 1), p. 27, first display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.