Proof of Theorem 4.1, p. 14 — KKT: g(p*) = Σ wᵢ g(pᵢ) + λ1ₙ + µ with µ ≥ 0 and µⱼ = 0 where p*ⱼ > 0
ProvedQAPooling.MaxMin.kkt_displayconvex-optimizationkkt-conditionsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quasi-arithmetic-pooling
Let be a regular proper scoring rule with exposure function , such that is continuous on for every and the expected reward is continuous on . Let with non-negative weights adding to , and let be their QA pool. Then there are and with
such that for every and whenever .
These are the Karush–Kuhn–Tucker conditions for minimizing over the simplex at its minimizer , valid even when lies on the boundary of . They are the step of the proof of Theorem 4.1 that ties the pool's own exposure to the experts' exposures.
Formalization Note is meaningful because (Claim 3.10). The continuity hypotheses are the paper's standing assumptions of p. 10.
Preamble
import Mathlib import Definitions.Def_QAPooling_MaxMin_Model
Formal statement
namespace QAPooling.MaxMin
/-- KKT display in the proof of Theorem 4.1 (p. 14): `g(p*) = Σ_i w_i g(p_i) + λ 1_n + μ` for some
`λ ∈ ℝ` and `μ ∈ ℝⁿ` with `μ_j ≥ 0` and `μ_j = 0` whenever `p*_j > 0`. -/
theorem kkt_display {n m : ℕ} (s : ScoringRule n) (g : (Fin n → ℝ) → Fin n → ℝ)
(hreg : IsRegular s) (hprop : IsProper s)
(hcont : ∀ j, ContinuousOn (fun p => s p j) (stdSimplex ℝ (Fin n)))
(hGcont : ContinuousOn (expectedReward s) (stdSimplex ℝ (Fin n)))
(hg : IsExposure s g)
(p : Fin m → Fin n → ℝ) (hp : ∀ i, p i ∈ forecastDomain s)
(w : Fin m → ℝ) (hw0 : ∀ i, 0 ≤ w i) (hw1 : ∑ i, w i = 1)
(pstar : Fin n → ℝ) (hpstar : IsQAPool s g p w pstar) :
∃ (lam : ℝ) (mu : Fin n → ℝ),
(∀ j, g pstar j = ∑ i, w i * g (p i) j + lam + mu j) ∧
(∀ j, 0 ≤ mu j) ∧ (∀ j, 0 < pstar j → mu j = 0) := by sorry
end QAPooling.MaxMin
Source
Neyman & Roughgarden, From Proper Scoring Rules to Max-Min Optimal Forecast Aggregation, arXiv:2102.07081v2, p. 14, proof of Theorem 4.1 (KKT display, footnote 14)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.