OnlineLearning.convex_compact_minimax
theoremverifiedformalizationimported Lean
Convex-compact minimax theorem on the line. Let $X, Y \subseteq \bbr$ be nonempty convex sets with $X$ compact, and let $f : \bbr \times \bbr \to \bbr$ be a payoff function that is bounded above and below on $X \times Y$. Suppose that for every $y \in Y$ the map $x \mapsto f(x,y)$ is continuous and convex on $X$, and that for every $x \in X$ the map $y \mapsto f(x,y)$ is concave on $Y$. Then the minimax identity holds: \[ \inf_{x \in X}\,\sup_{y \in Y}\, f(x,y) \;=\; \sup_{y \in Y}\,\inf_{x \in X}\, f(x,y). \]
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in theorem OnlineLearning.convex_compact_minimax {X Y : Set ℝ} {f : ℝ → ℝ → ℝ} (h : ConvexCompactMinimaxHypotheses X Y f) : ConvexCompactMinimaxStatement X Y f
- Formalizes
- Convex-compact minimax theorem on the line, as formalized in TCSlib (`OnlineLearning.convex_compact_minimax`)
- 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← OnlineLearning.convex_compact_minimax (TCSlib/LearningTheory/Minimax/ConvexMinimax.lean:49): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- OnlineLearning.ConvexCompactMinimaxStatementFor sets $X, Y \subseteq \bbr$ and a payoff function $f : \bbr \to \bbr \to \bbr$,
OnlineLearning.ConvexCompactMinimaxStatement… - 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$:…
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 in/-- The convex-compact minimax theorem: for a nonempty compact convex `X ⊆ ℝ`, a nonempty convex `Y ⊆ ℝ`, and a bounded payoff `f` that is convex and continuous in the row variable `x` for each `y ∈ Y` and concave in the column variable `y` for each `x ∈ X` (the hypotheses bundled in `ConvexCompactMinimaxHypotheses`), the upper value `inf_{x ∈ X} sup_{y ∈ Y} f x y` equals the lower value `sup_{y ∈ Y} inf_{x ∈ X} f x y` (the conclusion `ConvexCompactMinimaxStatement`). [CBL06, Thm 7.1]. Deviation: specialized to subsets of `ℝ`, and proved via the Hahn–Banach separation route of `ConvexMinimaxSeparation` rather than the source's no-regret argument, whose last step needs an extra uniformity hypothesis (see `ConvexMinimaxNoRegret`). This theorem is intentionally a thin wrapper. It hides the proof-route choice from downstream files and currently delegates to the completed separation proof. -/theorem OnlineLearning.convex_compact_minimax {X Y : Set ℝ} {f : ℝ → ℝ → ℝ} (h : ConvexCompactMinimaxHypotheses X Y f) : ConvexCompactMinimaxStatement X Y f := by -- Keep the public theorem independent of proof-route details. At present, -- the separation proof is the strongest completed route. exact convex_compact_minimax_by_separation h