Theorem 1.3, p. 3 — proportional volume sampling with an α-approximate (d−1, d)-wise independent measure is an α-approximation for A-optimal design
ProvedPropVolSampling.Reduction.theorem_1_3Let be integers and a real matrix. The A-optimal design problem asks for , , minimising ; let be its optimal value.
Let be an optimal solution of the convex relaxation (1)–(3),
with finite value , and let be a probability measure on or that is -approximate -wise independent with respect to . Run Algorithm 1: sample by proportional volume sampling, , and output padded by arbitrary further indices to a set of size . Then
- the algorithm is an -approximation in expectation: for every -set ,
hence the expected objective is at most ; 2. the integrality gap of the relaxation is at most : some -set has .
This reduces approximating A-optimal design to constructing approximately independent distributions; the paper's Theorems 1.4 and 1.5 instantiate it with hard-core distributions.
Formalization Note The page assumes such a for every feasible ; as the remark after Theorem 1.3 says, only the optimal is used, so the Lean statement takes one optimal and one , which implies the page's form. Approximate independence is cross-multiplied (Definition 1.2 wherever its ratio is defined). The following are added: the normaliser is positive (Definition 1.1 presupposes it; otherwise is undefined); is positive definite (part of optimality with finite ); (for ). is expressed by quantifying over -sets with positive definite Gram matrix, because Lean's inverse is a junk on singular matrices; those sets have value on the page. The padding is an arbitrary map with and on the support of (for on , take ).
import Mathlib import Definitions.Def_PropVolSampling_Reduction_Model
namespace PropVolSampling.Reduction
open Matrix Finset
theorem theorem_1_3 {d n : ℕ} (V : Matrix (Fin d) (Fin n) ℝ) (k : ℕ) (hd : 1 ≤ d) (hdk : d ≤ k)
(hkn : k ≤ n) (x : Fin n → ℝ) (hx : IsRelaxOptimal V k x)
(μ : Finset (Fin n) → ℝ) (hμ : IsSetDist k μ) (α : ℝ) (hα : IsApproxIndep d α x μ)
(hZ : 0 < pvsNormalizer V μ) (pad : Finset (Fin n) → Finset (Fin n))
(hpad : ∀ S, μ S ≠ 0 → S ⊆ pad S ∧ (pad S).card = k) :
(∀ Sopt : Finset (Fin n), Sopt.card = k → (gram V Sopt).PosDef →
pvsExpect V μ (fun S => aObj (gram V (pad S))) ≤ α * aObj (gram V Sopt)) ∧
∃ S : Finset (Fin n), S.card = k ∧ (gram V S).PosDef ∧
aObj (gram V S) ≤ α * aObj (weightedGram V x) := by sorry
end PropVolSampling.Reduction
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.