Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3, p. 22 — generic wait-and-judge bound by γ*

Proved
WaitJudge.Generic.theorem_3

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

p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1scenario-optimizationsupport-constraintswait-and-judge

Let S be an arbitrary decision set with real cost f, domain X, and scenario constraints X_δ indexed by a probability space (Δ,ℱ,P). For N≥1 independent samples, let x_N be the unique tie-broken solution, s_N its number of support constraints, and V(x*_N) the probability that a new constraint rejects it. Assume existence and uniqueness for every finite sample (Assumption 1), and that almost surely the support constraints alone select the same solution (Assumption 2). For any ε(k)∈[0,1], 0≤k≤N,

PN{V(xN∗)>ε(sN∗)}≤γ∗,\mathbb P^N\{V(x^*_N)>\varepsilon(s^*_N)\}\le\gamma^*,PN{V(xN∗​)>ε(sN∗​)}≤γ∗,

where γ* is the infimum of q(1) over degree-at-most-N polynomials satisfying the derivative inequalities (31). The bound adapts to the observed number of support constraints without an a priori dimension bound.

Formalization Note The source prints k=0,…,d in Theorem 3, although its generic section has no d; (31) and the preceding paragraph use k=0,…,N, which is the range formalized here. The finite tie-break list pins down the page's tie-break rule. Joint constraint measurability, solution-map measurability, and support-event measurability make explicit the convention of footnote 1. A Nonempty S instance is redundant with Assumption 1 and supplies the selector's unused fallback. The probability is compared in extended nonnegative reals with ENNReal.ofReal γ*.

Preamble
import Mathlib
import Definitions.Def_WaitJudge_Generic_Setting
Formal statement
namespace WaitJudge.Generic

open MeasureTheory

theorem theorem_3
    {S Δ : Type*} [Nonempty S] [MeasurableSpace S] [MeasurableSpace Δ]
    (P : Measure Δ) [IsProbabilityMeasure P]
    (f : S → ℝ) (X : Set S) (Xδ : Δ → Set S)
    {p : ℕ} (tb : Fin p → S → ℝ)
    (hA1 : Assumption1 f X Xδ tb)
    (hA2 : Assumption2 f X Xδ tb P)
    (hmeas : MeasurabilityPins f X Xδ tb)
    (N : ℕ) (hN : 0 < N) (ε : ℕ → ℝ)
    (hε : ∀ k ≤ N, 0 ≤ ε k ∧ ε k ≤ 1) :
    (Measure.pi fun _ : Fin N => P)
      {ω : Fin N → Δ | ε (sstar f X Xδ tb ω) <
        ScenarioApproach.Nonconvex.violation P Xδ (xstar f X Xδ tb ω)} ≤
      ENNReal.ofReal (gammaStar31 N ε) := by sorry

end WaitJudge.Generic
Source
Campi & Garatti, Wait-and-judge scenario optimization, Math. Program. (2018), doi:10.1007/s10107-016-1056-9 (accepted manuscript), PDF p. 22, Theorem 3 and (31)
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