OnlineLearning.convex_compact_minimax_by_separation
theoremverifiedimported Lean
A convex–concave minimax equality. Let $X, Y \subseteq \bbr$ be nonempty sets with $X$ compact and both $X$ and $Y$ convex, 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 section $x \mapsto f(x,y)$ is continuous and convex on $X$, while for every $x \in X$ the section $y \mapsto f(x,y)$ is concave on $Y$. 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_by_separation {X Y : Set ℝ} {f : ℝ → ℝ → ℝ} (h : ConvexCompactMinimaxHypotheses X Y f) : ConvexCompactMinimaxStatement X Y f
- Source
- TCSlib, `OnlineLearning.convex_compact_minimax_by_separation`
- 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_by_separation← OnlineLearning.convex_compact_minimax_by_separation (TCSlib/LearningTheory/Minimax/ConvexMinimaxSeparation.lean:484): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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$:…
- OnlineLearning.convex_compact_minimax_of_finite_sublevel_intersectionsMinimax equality from finite sublevel intersections. Let $X, Y \subseteq \bbr$ with $X$ and $Y$ nonempty, $X$ compact and convex, and $Y$…
- OnlineLearning.finite_sublevel_intersections_by_separationNonempty finite intersection of minimax sublevel sets. Let $X, Y \subseteq \bbr$ and $f : \bbr \times \bbr \to \bbr$ satisfy the…
- OnlineLearning.ConvexCompactMinimaxStatementFor sets $X, Y \subseteq \bbr$ and a payoff function $f : \bbr \to \bbr \to \bbr$,
- Used by 1
- OnlineLearning.convex_compact_minimaxConvex-compact minimax theorem on the line. Let $X, Y \subseteq \bbr$ be nonempty convex sets with $X$ compact, 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 convex-compact minimax theorem via the separation route: under `ConvexCompactMinimaxHypotheses` (nonempty compact convex `X ⊆ ℝ`, nonempty convex `Y ⊆ ℝ`, bounded `f` continuous and convex in the row variable, concave in the column variable), the upper value `inf_x sup_y f x y` equals the lower value `sup_y inf_x f x y`. [CBL06, Thm 7.1]. Deviation: specialized to `ℝ`, and proved by Hahn–Banach separation on finite column samples plus compactness rather than by the source's regret-based route (whose last step is isolated, and proved under strengthened hypotheses, in `ConvexMinimaxNoRegret`); [Kom88] is a different route to a more general result, and this file does not follow Komiya's argument either. -/theorem OnlineLearning.convex_compact_minimax_by_separation {X Y : Set ℝ} {f : ℝ → ℝ → ℝ} (h : ConvexCompactMinimaxHypotheses X Y f) : ConvexCompactMinimaxStatement X Y f := by exact convex_compact_minimax_of_finite_sublevel_intersections h (finite_sublevel_intersections_by_separation h)