Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1.3, p. 3 — proportional volume sampling with an α-approximate (d−1, d)-wise independent measure is an α-approximation for A-optimal design

Proved
PropVolSampling.Reduction.theorem_1_3

by mikedeng1 · Oct 20, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximation-algorithmsoptimal-designp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1volume-sampling

Let 1≤d≤k≤n1\le d\le k\le n1≤d≤k≤n be integers and V=[v1,…,vn]V=[v_1,\dots,v_n]V=[v1​,…,vn​] a real d×nd\times nd×n matrix. The A-optimal design problem asks for S⊆[n]S\subseteq[n]S⊆[n], ∣S∣=k|S|=k∣S∣=k, minimising tr⁡(VSVS⊤)−1=tr⁡(∑i∈Svivi⊤)−1\operatorname{tr}(V_SV_S^\top)^{-1}=\operatorname{tr}(\sum_{i\in S}v_iv_i^\top)^{-1}tr(VS​VS⊤​)−1=tr(∑i∈S​vi​vi⊤​)−1; let OPT\mathrm{OPT}OPT be its optimal value.

Let xxx be an optimal solution of the convex relaxation (1)–(3),

min⁡ tr⁡(∑i=1nxivivi⊤)−1s.t.∑ixi=k, 0≤xi≤1,\min\ \operatorname{tr}\Big(\sum_{i=1}^nx_iv_iv_i^\top\Big)^{-1}\quad\text{s.t.}\quad\sum_ix_i=k,\ 0\le x_i\le1,min tr(i=1∑n​xi​vi​vi⊤​)−1s.t.i∑​xi​=k, 0≤xi​≤1,

with finite value CP\mathrm{CP}CP, and let μ\muμ be a probability measure on Uk\mathcal U_kUk​ or U≤k\mathcal U_{\le k}U≤k​ that is α\alphaα-approximate (d−1,d)(d-1,d)(d−1,d)-wise independent with respect to xxx. Run Algorithm 1: sample S\mathcal SS by proportional volume sampling, Pr⁡[S=S]∝μ(S)det⁡(VSVS⊤)\Pr[\mathcal S=S]\propto\mu(S)\det(V_SV_S^\top)Pr[S=S]∝μ(S)det(VS​VS⊤​), and output S\mathcal SS padded by arbitrary further indices to a set pad⁡(S)⊇S\operatorname{pad}(\mathcal S)\supseteq\mathcal Spad(S)⊇S of size kkk. Then

  1. the algorithm is an α\alphaα-approximation in expectation: for every kkk-set SoptS^{\mathrm{opt}}Sopt,
E[tr⁡(Vpad⁡(S)Vpad⁡(S)⊤)−1]≤α tr⁡(VSoptVSopt⊤)−1,\mathbb E\Big[\operatorname{tr}\big(V_{\operatorname{pad}(\mathcal S)}V_{\operatorname{pad}(\mathcal S)}^\top\big)^{-1}\Big]\le\alpha\,\operatorname{tr}\big(V_{S^{\mathrm{opt}}}V_{S^{\mathrm{opt}}}^\top\big)^{-1},E[tr(Vpad(S)​Vpad(S)⊤​)−1]≤αtr(VSopt​VSopt⊤​)−1,

hence the expected objective is at most α OPT\alpha\,\mathrm{OPT}αOPT; 2. the integrality gap of the relaxation is at most α\alphaα: some kkk-set SSS has tr⁡(VSVS⊤)−1≤α CP\operatorname{tr}(V_SV_S^\top)^{-1}\le\alpha\,\mathrm{CP}tr(VS​VS⊤​)−1≤αCP.

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 μ\muμ for every feasible xxx; as the remark after Theorem 1.3 says, only the optimal xxx is used, so the Lean statement takes one optimal xxx and one μ\muμ, 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 ∑Sμ(S)det⁡(VSVS⊤)\sum_S\mu(S)\det(V_SV_S^\top)∑S​μ(S)det(VS​VS⊤​) is positive (Definition 1.1 presupposes it; otherwise μ′\mu'μ′ is undefined); ∑ixivivi⊤\sum_ix_iv_iv_i^\top∑i​xi​vi​vi⊤​ is positive definite (part of optimality with finite CP\mathrm{CP}CP); 1≤d1\le d1≤d (for d−1d-1d−1). OPT\mathrm{OPT}OPT is expressed by quantifying over kkk-sets with positive definite Gram matrix, because Lean's inverse is a junk 000 on singular matrices; those sets have value +∞+\infty+∞ on the page. The padding is an arbitrary map pad⁡\operatorname{pad}pad with S⊆pad⁡(S)S\subseteq\operatorname{pad}(S)S⊆pad(S) and ∣pad⁡(S)∣=k|\operatorname{pad}(S)|=k∣pad(S)∣=k on the support of μ\muμ (for μ\muμ on Uk\mathcal U_kUk​, take pad⁡=id\operatorname{pad}=\mathrm{id}pad=id).

Preamble
import Mathlib
import Definitions.Def_PropVolSampling_Reduction_Model
Formal statement
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
Source
Nikolov, Singh, Tantipongpipat, Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design, arXiv:1802.08318v5, p. 3, Theorem 1.3 and the remark after it (proof §2, pp. 7–10; Algorithm 1, p. 8)
Human review
  • Endorsed by Shuze Chen · Oct 20, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 20, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me