Theorem 4.1 — Linear parallel lower bound for anisotropic boxes
OpenParallelDiffusionLB.NearIsotropic.Supplement.theorem_4_1Let . For all sufficiently large , every query budget and every score accuracy , there are finitely many instances with a probability law on them, and for each instance an axis-aligned box
which is full-dimensional and contained in the open unit ball , together with a fixed legal score oracle for at accuracy (a jointly measurable map of with for every ), such that the following holds. For every number of rounds and every randomized adaptive parallel algorithm with rounds of at most queries each and a seed of arbitrary law , whose output law against instance is ,
The instance law, the boxes and the oracles are chosen before the algorithm. Compared with the goal (Theorem 3.1), the round lower bound here is linear in , but the targets are strongly anisotropic rather than near-isotropic.
Differences from the source:
- encoding: for sufficiently large d, with a polynomial budget P = poly(d) and an inverse-polynomial accuracy ε_score = poly(d)^{-1} fixed beforehand → ∀ a b : ℕ, ∃ d₀, ∀ d ≥ d₀, ∀ P with 1 ≤ P ≤ d^a, ∀ ε > 0 with d^{-b} ≤ ε; reason: every polynomial budget is eventually at most d^a and every inverse polynomial eventually at least d^{-b}, for some a, b; this is the shape of the published theorem_3_1
- encoding: coordinates i ∈ [d] and labels k ∈ [M], 1-indexed → i : Fin d and k : Fin M, 0-indexed (paper i = i.val + 1, paper k = k.val + 1); reason: Lean convention; same objects
- encoding: a distribution over boxes K^θ → a probability measure μ on Fin K indexing finitely many boxes; reason: the paper's distribution (θ uniform on [M]^d) is finitely supported; an existential over finitely supported laws specializes to it
- encoding: full-dimensional axis-aligned boxes K^θ ⊂ B_2(0,1) → K_i = {x | ∀ j, l_i j ≤ x_j ≤ u_i j} with l_i j < u_i j for all j, and K_i ⊆ Metric.ball 0 1; reason: closed axis-aligned boxes with positive side lengths; the open ball is the stronger reading of B_2(0,1)
- encoding: π^θ = Unif(K^θ) → unifSet K_i = vol(K_i)⁻¹ • vol|_{K_i}; reason: the paper's uniform law of a set of positive finite volume
- encoding: every randomized sampler using fewer than d rounds → ∀ R < d, every probability law ν on an arbitrary seed space Ω and every ParallelAlgorithm with exactly P slots per round; reason: at most P queries are encoded by repeating queries; the published model of §2.2
- encoding: a fixed legal approximate oracle satisfying (1); Pr_θ[d_TV(Q^θ,π^θ) ≥ 0.9] ≥ 0.9 → LegalOracle (unifSet K_i) ε (o i), and 9/10 ≤ μ.real {i | 9/10 ≤ PolySampIso.tvDist (A.outputLaw ν (o i)) (unifSet K_i)}; reason: the published legality predicate, output law and total variation, as in theorem_3_1
import Definitions.Def_ParallelDiffusionLB_NearIsotropic_Supplement_Box import Definitions.Def_ParallelDiffusionLB_NearIsotropic_Algorithm import Definitions.Def_PolySampIso_Divergences open MeasureTheory ProbabilityTheory open scoped ENNReal noncomputable section
namespace ParallelDiffusionLB.NearIsotropic.Supplement
/-- Theorem 4.1 (Linear parallel lower bound), p. 14, with the polynomial budgets of §2.2 made
explicit, in the quantifier shape of the published `theorem_3_1`. The finite instance law, the
full-dimensional axis-aligned boxes `K_i = ∏_j [l_i j, u_i j] ⊂ B₂(0,1)` and their legal oracles
are chosen before quantifying over every round count `R < d` and every measurable randomized
algorithm with `P` query slots per round. -/
theorem theorem_4_1 (a b : ℕ) :
∃ d₀ : ℕ, ∀ d : ℕ, d₀ ≤ d → ∀ P : ℕ, 1 ≤ P → P ≤ d ^ a →
∀ ε : ℝ, 0 < ε → (d : ℝ) ^ (-(b : ℤ)) ≤ ε →
∃ K : ℕ, 0 < K ∧ ∃ μ : Measure (Fin K), IsProbabilityMeasure μ ∧
∃ l u : Fin K → Fin d → ℝ, ∃ o : Fin K → Query d → E d,
(∀ i, (∀ j, l i j < u i j) ∧
{x : E d | ∀ j, l i j ≤ x j ∧ x j ≤ u i j} ⊆ Metric.ball (0 : E d) 1 ∧
LegalOracle (unifSet {x : E d | ∀ j, l i j ≤ x j ∧ x j ≤ u i j}) ε (o i)) ∧
∀ R : ℕ, R < d →
∀ (Ω : Type*) [MeasurableSpace Ω] (ν : Measure Ω) [IsProbabilityMeasure ν]
(A : ParallelAlgorithm (Query d) (E d) (E d) Ω P R),
(9 / 10 : ℝ) ≤ μ.real {i | (9 / 10 : ℝ) ≤
PolySampIso.tvDist (A.outputLaw ν (o i))
(unifSet {x : E d | ∀ j, l i j ≤ x j ∧ x j ≤ u i j})} := by sorry
end ParallelDiffusionLB.NearIsotropic.Supplement