Lemma 4.2, p. 18 — max{w₁², ¼Σwᵢ²} ≤ V^LB ≤ V^OPT ≤ Σwᵢ²
ProvedCorrClusterExp.IBR.lemma_4_2approximation-ratioexperimental-designp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1robust-optimization
Let , , and let be the sorted cluster sizes. Then
In particular the independent assignment, whose worst-case variance is , is a -approximation.
Formalization Note is w ⟨0, hn⟩ (0-based).
Differences from the source:
- encoding: →
w ⟨0, hn⟩with ; reason: 0-based indexing; needs a first cluster.
Preamble
import Mathlib import Definitions.Def_CorrClusterExp_IBR_Setting
Formal statement
namespace CorrClusterExp.IBR
theorem lemma_4_2 (q : ℝ) (hq0 : 0 < q) (hq : q ≤ 1 / 2) (n : ℕ) (hn : 0 < n)
(w : Fin n → ℝ) (hw0 : ∀ i, 0 ≤ w i) (hw : Antitone w) :
max (w ⟨0, hn⟩ ^ 2) (1 / 4 * ∑ i, w i ^ 2) ≤ VLB w ∧
VLB w ≤ VOPT q w ∧ VOPT q w ≤ ∑ i, w i ^ 2 := by sorry
end CorrClusterExp.IBR
Source
Candogan, Chen, Niazadeh, Correlated Cluster-Based Randomized Experiments: Robust Variance Minimization, SSRN 3852100 (version of March 22, 2023), p. 18, Lemma 4.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.