Information lower program , , , ,
DefinitionFairReplay_Supplement_TwoClassFamily_QLBfairness-testinginformation-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1sequential-testing
With , define
and . Let if group contains and no other high vertex (a boundary-only group), and otherwise. The information lower program is
and are the KL divergences of one query of a control group and of a boundary-only group containing the changed candidate.
Formalization Note The minimum over real is an infimum in , equal to when infeasible. .
Definition code
import Mathlib
import Definitions.Def_bernoulliRelativeEntropy
import Definitions.Def_FairReplay_Supplement_TwoClassFamily
import Definitions.Def_FairReplay_Supplement_TwoClassFamily_coverLP
namespace FairReplay.Supplement
/-- `K_ctrl(d) = r log(r/(r − d))`, `r = 1 − p − s − τ` (Theorem 10.9, proof of (i), p.21): the KL of
one query of a control group containing the changed candidate. -/
noncomputable def Kctrl (p s τ d : ℝ) : ℝ :=
(1 - p - s - τ) * Real.log ((1 - p - s - τ) / ((1 - p - s - τ) - d))
/-- `K_bnd(τ, d) = τ log(τ/(τ + d)) + r log(r/(r − d))`, `r = 1 − p − s − τ` (Theorem 10.9, proof of
(i), p.21): the KL of one query of a boundary-only group containing the changed candidate. -/
noncomputable def Kbnd (p s τ d : ℝ) : ℝ :=
τ * Real.log (τ / (τ + d)) + (1 - p - s - τ) * Real.log ((1 - p - s - τ) / ((1 - p - s - τ) - d))
/-- `b2 = (τ⁻¹ + r⁻¹)/2` (Theorem 10.9(iv), eq. (69), p.19), `r = 1 − p − s − τ`. -/
noncomputable def b2 (p s τ : ℝ) : ℝ :=
(τ⁻¹ + (1 - p - s - τ)⁻¹) / 2
/-- `b3 = (r⁻² − τ⁻²)/3` (Theorem 10.9(iv), eq. (69), p.19), `r = 1 − p − s − τ`. -/
noncomputable def b3 (p s τ : ℝ) : ℝ :=
(((1 - p - s - τ) ^ 2)⁻¹ - (τ ^ 2)⁻¹) / 3
namespace TwoClassFamily
/-- `R_{x,i} = 1`: group `i` is a **boundary-only** group for `x` — it contains `x` and no other high
vertex (Theorem 10.9, proof of (i), p.21: "If the group contains x but no other high vertex"). -/
def IsBoundary (F : TwoClassFamily) (x : Fin F.n) (i : Fin F.k) : Prop :=
x ∈ F.S i ∧ ∀ y ∈ F.S i, y ≠ x → F.high y = false
/-- The boundary matrix `R` as a `0/1` real matrix. -/
noncomputable def bnd (F : TwoClassFamily) (x : Fin F.n) (i : Fin F.k) : ℝ := by
classical exact if F.IsBoundary x i then 1 else 0
/-- **The information lower program** `QLB(d)` (Sah, Zhang, Lian, *Testing Fairness of Evolving
Software under Uncertainty*, STOC 2027 submission, manuscript of 2026-11-03, sha256 e23940a0…,
Theorem 10.9(i), eq. (65), and (iv), p.19 (PDF p.21)):
`min_{n ≥ 0} { c⊤n : (K_ctrl C + K_bnd R) n ≥ kl(1 − δ, δ) 1 }`, rows indexed by the candidates
`x ∈ A`.
**Formalization Note** The infimum over real `n ≥ 0` is taken in `[0, ∞]`; it is `∞` when the
program is infeasible (some candidate lies in no group). `kl` is
`BanditAlgorithm.bernoulliRelativeEntropy`. -/
noncomputable def QLB (F : TwoClassFamily) (p s τ d δ : ℝ) : ENNReal :=
⨅ (nv : Fin F.k → ℝ) (_ : ∀ i, 0 ≤ nv i)
(_ : ∀ x ∈ F.A, BanditAlgorithm.bernoulliRelativeEntropy (1 - δ) δ ≤
∑ i, (Kctrl p s τ d * F.ctrl x i + Kbnd p s τ d * F.bnd x i) * nv i),
ENNReal.ofReal (∑ i, F.c i * nv i)
end TwoClassFamily
end FairReplay.Supplement
Source
Sah, Zhang, Lian, Testing Fairness of Evolving Software under Uncertainty, STOC 2027 submission (manuscript of 2026-11-03, sha256 e23940a0a0f5960aedaf6aba60adc41e966efc604b6379b3180b06590610d025), Theorem 10.9(i), eq. (65), (iv), eq. (69), p.19 and proof of (i), p.21 (PDF pp.21, 23)