Proof of Theorem 8, implication display — a suboptimal plug-in decision with estimation error ≤ ε forces 0 < Δ(x) ≤ 2Bε
ProvedFastCLO.ETO.implication_displayLet be a polytope with norm bound and extreme points , let be the regression function of an instance, and let be a plug--in policy for some , so minimizes over . Fix and . If
- the decision is strictly suboptimal for the true cost: , and
- the estimation error is small: ,
then the gap satisfies
This is the step of the proof of Theorem 8 that converts a decision error into a statement about the gap: because plug-in decisions are extreme points, a wrong decision can only occur at points where the gap is positive and at most a multiple of the estimation error. The noise condition then controls how likely such points are. In the paper .
Formalization Note Suboptimality is measured against the optimal value, which equals . That is finite, which the positivity of relies on, is a fact about polytopes to be proved, not a hypothesis.
import Mathlib import Definitions.Def_FastCLO_ETO_Model open MeasureTheory ProbabilityTheory open scoped InnerProductSpace ENNReal
namespace FastCLO.ETO
/-- **Proof of Theorem 8, the implication display** (Hu, Kallus, Mao, *Fast Rates for Contextual
Linear Optimization*, arXiv:2011.03030v3, Appendix A.5, p. 30): "`f*(X)ᵀ(π_f̂(X) − π_f*(X)) > 0,
‖f*(X) − f̂(X)‖ ≤ 2^r δ ⟹ 0 < f*(X)ᵀ(π_f̂(X) − π_f*(X)) ≤ 2^{r+1}Bδ ⟹ 0 < Δ(X) ≤ 2^{r+1}Bδ, since
π_f(x) ∈ Z∠ is always an extreme point, for any f and x."
For a plug-in policy `π` for an estimate `f` and a point `x`: if the decision `π(x)` is strictly
suboptimal for the true cost `f*(x)` and `‖f*(x) − f(x)‖ ≤ ε`, then `0 < Δ(x) ≤ 2Bε`.
Formalization Note: `ε` stands for the page's `2^r δ`. Suboptimality is measured against the
optimal value `optVal` (equal to `f*(x)ᵀπ_f*(x)`, since `π_f*(x) ∈ Z*(x)`). The gap `Δ` uses real
`sInf` over `Z∠ \ Z*(x)`, a nonempty finite set whenever `Z*(x) ≠ Z`; finiteness of `Z∠` is a
fact to prove, not a hypothesis. -/
theorem implication_display {p d : ℕ} (P : Polytope d) (I : Instance p d) (f π : FastCLO.ERM.Vec p → FastCLO.ERM.Vec d)
(hπ : IsPlugIn P f π) (x : FastCLO.ERM.Vec p) (ε : ℝ)
(hsub : 0 < ⟪I.fstar x, π x⟫_ℝ - optVal P I x) (herr : ‖I.fstar x - f x‖ ≤ ε) :
0 < gap P I x ∧ gap P I x ≤ 2 * P.B * ε := by sorry
end FastCLO.ETO
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.