Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 8, implication display — a suboptimal plug-in decision with estimation error ≤ ε forces 0 < Δ(x) ≤ 2Bε

Proved
FastCLO.ETO.implication_display

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

contextual-optimizationlinear-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let Z\mathcal ZZ be a polytope with norm bound BBB and extreme points Z∠\mathcal Z^\angleZ∠, let f∗f^*f∗ be the regression function of an instance, and let π\piπ be a plug-fff-in policy for some f:Rp→Rdf : \mathbb R^p \to \mathbb R^df:Rp→Rd, so π(x)∈Z∠\pi(x) \in \mathcal Z^\angleπ(x)∈Z∠ minimizes f(x)⊤zf(x)^\top zf(x)⊤z over Z\mathcal ZZ. Fix xxx and ε∈R\varepsilon \in \mathbb Rε∈R. If

  1. the decision π(x)\pi(x)π(x) is strictly suboptimal for the true cost: f∗(x)⊤π(x)>min⁡z∈Zf∗(x)⊤zf^*(x)^\top \pi(x) > \min_{z \in \mathcal Z} f^*(x)^\top zf∗(x)⊤π(x)>minz∈Z​f∗(x)⊤z, and
  2. the estimation error is small: ∥f∗(x)−f(x)∥≤ε\|f^*(x) - f(x)\| \le \varepsilon∥f∗(x)−f(x)∥≤ε,

then the gap Δ(x)\Delta(x)Δ(x) satisfies

0<Δ(x)≤2Bε.0 < \Delta(x) \le 2B\varepsilon.0<Δ(x)≤2Bε.

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 ε=2rδ\varepsilon = 2^r\deltaε=2rδ.

Formalization Note Suboptimality is measured against the optimal value, which equals f∗(x)⊤πf∗(x)f^*(x)^\top\pi_{f^*}(x)f∗(x)⊤πf∗​(x). That Z∠\mathcal Z^\angleZ∠ is finite, which the positivity of Δ(x)\Delta(x)Δ(x) relies on, is a fact about polytopes to be proved, not a hypothesis.

Preamble
import Mathlib
import Definitions.Def_FastCLO_ETO_Model
open MeasureTheory ProbabilityTheory
open scoped InnerProductSpace ENNReal
Formal statement
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
Source
Hu, Kallus, Mao, Fast Rates for Contextual Linear Optimization, arXiv:2011.03030v3, proof of Theorem 8 (Appendix A.5), the implication display, p. 30
Human review
  • Endorsed by Shuze Chen · Oct 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 9, 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