Lemma C.1 (saddle points and balancing) for
ProvedPrivBayesTest.lemma_C_1differential-privacyerror-exponentshypothesis-testinginformation-theoryp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Fix and let be either or . Let be a nonempty convex subset of a real vector space with a topology, let be nonnegative, convex and lower semicontinuous functions on , and set
Suppose that every sublevel set is compact. Then:
- has a saddle point : minimizes over and maximizes over ;
- for every saddle point , its value equals , and if there is with
where moreover if and , and if .
The lemma gives the balancing value used in the converse (Lemma 3.2) through Corollary C.2.
Differences from the source:
- encoding: z ranging over a convex set Z → Z a nonempty convex subset of a real vector space E with an arbitrary topology; reason: the topology is needed for lower semicontinuity and compactness; Z = ∅ is the degenerate case in which no saddle point exists and the statement has no content
- encoding: z ↦ max_{α∈[0,1]} Φ(α, z) has compact sublevel sets → {z ∈ Z | ∀ α ∈ [0,1], Φ(α, z) ≤ t} is compact for every real t; reason: same sets
- generalization: the value and τ clauses for the saddle point the lemma produces → the value and τ clauses for every saddle point; reason: contains the printed claim
- encoding: sup_α inf_z Φ(α, z) → extended-real supremum over α ∈ [0,1] of the infimum over z ∈ Z; reason: Lean convention; α ranges over [0,1] as in the lemma's max
Preamble
import Mathlib import Definitions.Def_PrivBayesTest_saddleObj import Definitions.Def_PrivBayesTest_klTvValue
Formal statement
namespace PrivBayesTest
/-- **Lemma C.1 (Saddle Points and Balancing)** of Jacobsen, *Optimal Error Exponents for Private Bayesian Hypothesis Testing*, STOC 2027 submission (manuscript sha256 abff2fdd…124ef), p.28. Fix `ε > 0` and let `ω` be either
`α̃ = min{α, 1 − α}` or `α`. For nonnegative functions `A, B, W` on a convex set `Z` let
`Φ(α, z) = α A(z) + (1 − α) B(z) + ω(α) ε W(z)` (eq. (7)). Suppose `A, B, W` are convex and lower
semicontinuous and `z ↦ max_{α∈[0,1]} Φ(α, z)` has compact sublevel sets. Then `Φ` has a saddle point
`(α*, z*)` (`z*` minimizes `Φ(α*, ·)` over `Z` and `α*` maximizes `Φ(·, z*)` over `[0,1]`), and its
value `V = Φ(α*, z*)` equals `sup_α inf_z Φ(α, z)`. If `α* ∈ (0,1)`, there is `τ ∈ [0,1]` with
`V = A(z*) + τ ε W(z*) = B(z*) + (1 − τ) ε W(z*)`; moreover `τ ∈ {0,1}` if `ω = α̃` and `α* ≠ 1/2`, and
`τ = 1` if `ω(α) = α`.
**Formalization Note** `Z` is a convex subset of a real vector space `E` carrying an arbitrary
topology (used for lower semicontinuity and compactness only). `Z` is assumed nonempty. The
sublevel set `{z ∈ Z | max_α Φ(α, z) ≤ t}` is written `{z ∈ Z | ∀ α ∈ [0,1], Φ(α, z) ≤ t}`. The value
and the balancing clauses are stated for **every** saddle point, which contains the printed statement
about the saddle point it produces. `sup_α inf_z` is computed in `EReal` with `α ∈ [0,1]`. -/
theorem lemma_C_1 {E : Type*} [AddCommGroup E] [Module ℝ E] [TopologicalSpace E] (ε : ℝ)
(hε : 0 < ε) (ω : ℝ → ℝ) (hω : ω = alphaTilde ∨ ω = id) (Z : Set E) (hZ : Convex ℝ Z)
(hZne : Z.Nonempty) (A B W : E → ℝ) (hA0 : ∀ z ∈ Z, 0 ≤ A z) (hB0 : ∀ z ∈ Z, 0 ≤ B z)
(hW0 : ∀ z ∈ Z, 0 ≤ W z) (hAc : ConvexOn ℝ Z A) (hBc : ConvexOn ℝ Z B) (hWc : ConvexOn ℝ Z W)
(hAl : LowerSemicontinuousOn A Z) (hBl : LowerSemicontinuousOn B Z)
(hWl : LowerSemicontinuousOn W Z)
(hcpt : ∀ t : ℝ, IsCompact {z ∈ Z | ∀ α ∈ Set.Icc (0 : ℝ) 1, saddleObj ω ε A B W α z ≤ t}) :
(∃ α₀ ∈ Set.Icc (0 : ℝ) 1, ∃ z₀ ∈ Z,
(∀ z ∈ Z, saddleObj ω ε A B W α₀ z₀ ≤ saddleObj ω ε A B W α₀ z) ∧
(∀ α ∈ Set.Icc (0 : ℝ) 1, saddleObj ω ε A B W α z₀ ≤ saddleObj ω ε A B W α₀ z₀)) ∧
∀ α₀ ∈ Set.Icc (0 : ℝ) 1, ∀ z₀ ∈ Z,
(∀ z ∈ Z, saddleObj ω ε A B W α₀ z₀ ≤ saddleObj ω ε A B W α₀ z) →
(∀ α ∈ Set.Icc (0 : ℝ) 1, saddleObj ω ε A B W α z₀ ≤ saddleObj ω ε A B W α₀ z₀) →
((saddleObj ω ε A B W α₀ z₀ : ℝ) : EReal) =
⨆ α ∈ Set.Icc (0 : ℝ) 1, ⨅ z ∈ Z, ((saddleObj ω ε A B W α z : ℝ) : EReal) ∧
(α₀ ∈ Set.Ioo (0 : ℝ) 1 → ∃ τ ∈ Set.Icc (0 : ℝ) 1,
saddleObj ω ε A B W α₀ z₀ = A z₀ + τ * ε * W z₀ ∧
saddleObj ω ε A B W α₀ z₀ = B z₀ + (1 - τ) * ε * W z₀ ∧
(ω = alphaTilde → α₀ ≠ 1 / 2 → τ = 0 ∨ τ = 1) ∧
(ω = id → τ = 1)) := by sorry
end PrivBayesTest
Source
Jacobsen, Optimal Error Exponents for Private Bayesian Hypothesis Testing, STOC 2027 submission (manuscript sha256 abff2fdd66827f43…124ef), Lemma C.1 and eq. (7), p.28
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.