OnlineLearning.convex_compact_minimax_of_finite_sublevel_intersections
Minimax equality from finite sublevel intersections. Let $X, Y \subseteq \bbr$ with $X$ and $Y$ nonempty, $X$ compact and convex, and $Y$ convex, and let $f : \bbr \times \bbr \to \bbr$ be bounded above and below on $X \times Y$, with $f(\cdot, y)$ continuous and convex on $X$ for every $y \in Y$ and $f(x, \cdot)$ concave on $Y$ for every $x \in X$. Write $v = \sup_{y \in Y} \inf_{x \in X} f(x,y)$ for the lower value, and suppose that for every $\varepsilon > 0$ and every finite set $u$ of column points from $Y$, the set \[ \{x \in X : f(x,y) \leq v + \varepsilon \text{ for all } y \in u\} \] is nonempty. Then the minimax equality \[ \inf_{x \in X}\,\sup_{y \in Y}\,f(x,y) \;=\; \sup_{y \in Y}\,\inf_{x \in X}\,f(x,y) \] holds.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open Real Finset BigOperators in theorem OnlineLearning.convex_compact_minimax_of_finite_sublevel_intersections {X Y : Set ℝ} {f : ℝ → ℝ → ℝ} (h : ConvexCompactMinimaxHypotheses X Y f) (hfin : ∀ ε > 0, ∀ u : Finset Y, (X ∩ ⋂ y ∈ u, minimaxSublevel X f y ((⨆ y : Y, ⨅ x : X, f x y) + ε)).Nonempty) : ConvexCompactMinimaxStatement X Y f
- Source
- TCSlib, `OnlineLearning.convex_compact_minimax_of_finite_sublevel_intersections`
- Lean proof
- By Karim Abdel Sadek, Mark Bedaywi, from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 Karim Abdel Sadek and Mark Bedaywi. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.OnlineLearning.convex_compact_minimax_of_finite_sublevel_intersections← OnlineLearning.convex_compact_minimax_of_finite_sublevel_intersections (TCSlib/LearningTheory/Minimax/ConvexMinimaxSeparation.lean:435): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- OnlineLearning.minimaxSublevelFor a set $X \subseteq \bbr$, a payoff function $f$, a column point $y$, and a threshold $c \in \bbr$, the minimax sublevel set is…
- OnlineLearning.weak_convex_compact_minimaxWeak minimax inequality for convex-compact games. Let $X, Y \subseteq \bbr$ be nonempty convex sets with $X$ also compact, and let…
- OnlineLearning.ConvexCompactMinimaxStatementFor sets $X, Y \subseteq \bbr$ and a payoff function $f : \bbr \to \bbr \to \bbr$,
OnlineLearning.ConvexCompactMinimaxStatement… - OnlineLearning.exists_forall_le_of_finite_sublevel_intersectionsFrom finite feasibility to a uniform row point. Let $X, Y \subseteq \bbr$ together with a payoff function $f : \bbr \to \bbr \to \bbr$…
- OnlineLearning.ConvexCompactMinimaxHypothesesA structure bundling the assumptions of Cesa-Bianchi--Lugosi Theorem~7.1 for $f : \bbr \to \bbr \to \bbr$ on sets $X, Y \subseteq \bbr$:…
- Used by 1
- OnlineLearning.convex_compact_minimax_by_separationA convex–concave minimax equality. Let $X, Y \subseteq \bbr$ be nonempty sets with $X$ compact and both $X$ and $Y$ convex, and let…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option relaxedAutoImplicit false inset_option autoImplicit false inopen Real Finset BigOperators in/-- The minimax identity from the finite sublevel intersection property: under `ConvexCompactMinimaxHypotheses`, if for every `ε > 0` and every finite set `u` of column points some row `x ∈ X` has `f x y ≤ v + ε` for all `y ∈ u` (with `v` the lower value), then the upper and lower values coincide (`ConvexCompactMinimaxStatement`). [CBL06, Thm 7.1]. This packages the compactness argument of the source's proof. **Proof sketch.** By `le_antisymm`. Step 1 (hard direction, `upper ≤ lower`): it suffices to show `upper ≤ v + ε` for every `ε > 0`. Compactness of `X` (`exists_forall_le_of_finite_sublevel_intersections`) turns the finite-sample hypothesis into a single row `x ∈ X` with `f x y ≤ v + ε` for every `y ∈ Y`; then `sup_y f x y ≤ v + ε` (`hsup_le`) and `upper ≤ sup_y f x y` since the upper value is an infimum over rows (`hleft_le`). Step 2 (easy direction): `weak_convex_compact_minimax`. -/theorem OnlineLearning.convex_compact_minimax_of_finite_sublevel_intersections {X Y : Set ℝ} {f : ℝ → ℝ → ℝ} (h : ConvexCompactMinimaxHypotheses X Y f) (hfin : ∀ ε > 0, ∀ u : Finset Y, (X ∩ ⋂ y ∈ u, minimaxSublevel X f y ((⨆ y : Y, ⨅ x : X, f x y) + ε)).Nonempty) : ConvexCompactMinimaxStatement X Y f := by haveI : Nonempty X := h.X_nonempty.to_subtype haveI : Nonempty Y := h.Y_nonempty.to_subtype unfold ConvexCompactMinimaxStatement apply le_antisymm -- Step 1: the hard direction, by compactness and letting `ε → 0`. · apply le_of_forall_pos_le_add intro ε hε obtain ⟨x, hx, hx_le⟩ := exists_forall_le_of_finite_sublevel_intersections h ((⨆ y : Y, ⨅ x : X, f x y) + ε) (hfin ε hε) let xX : X := ⟨x, hx⟩ -- The compactness point works for all columns, so the supremum over columns -- at this row is at most the lower value plus `ε`. have hsup_le : (⨆ y : Y, f xX y) ≤ (⨆ y : Y, ⨅ x : X, f x y) + ε := by exact ciSup_le fun y => hx_le y have hleft_le : (⨅ x : X, ⨆ y : Y, f x y) ≤ ⨆ y : Y, f xX y := by have hbdd : BddBelow (Set.range fun x' : X => ⨆ y : Y, f x' y) := by rcases h.bounded_below with ⟨a, ha⟩ refine ⟨a, ?_⟩ rintro _ ⟨x', rfl⟩ let y₀ : Y := Classical.choice ‹Nonempty Y› have habove : BddAbove (Set.range fun y : Y => f x' y) := by rcases h.bounded_above with ⟨b, hb⟩ refine ⟨b, ?_⟩ rintro _ ⟨y, rfl⟩ exact hb ⟨(x', y), rfl⟩ exact (ha ⟨(x', y₀), rfl⟩).trans (le_ciSup habove y₀) exact ciInf_le hbdd xX exact hleft_le.trans hsup_le -- Step 2: the reverse inequality is the standard weak minimax inequality from -- the core file. · exact weak_convex_compact_minimax h