Anisotropic box instances, gates (55) and the gated oracle (57)
DefinitionParallelDiffusionLB_NearIsotropic_Supplement_BoxFix a dimension , a query budget and a score accuracy . The public parameters (53) are
and for each label the candidate interval (54) is with center . A label vector selects the axis-aligned box , and the target is , where for a measurable set of positive finite volume .
For an interval and , is the posterior mean of given with :
defined at every . For the gate (55) is when and otherwise
The gated oracle (57) answers a query , , coordinatewise by
the empty product being , and for the truncated oracle (61) keeps for and answers for .
These objects are the hard instance family of §4 and Appendix B and its oracle; all of them are public except the labels .
Formalization Note Coordinates and labels are 0-indexed (Fin d, Fin M), so the paper's and are i.val + 1 and k.val + 1. Because and are integers, . The gate is only defined by the paper for ; for the last coordinate the Lean function returns the placeholder , which no statement uses (the product in (57) only involves ). The truncated oracle takes the paper's index as a natural number.
import Definitions.Def_ParallelDiffusionLB_NearIsotropic_Gaussian
open MeasureTheory ProbabilityTheory
open scoped ENNReal
noncomputable section
namespace ParallelDiffusionLB.NearIsotropic.Supplement
/-- Uniform law `Unif(S)` of a measurable set of positive finite volume (§Notation, p. 5):
`volume(S)⁻¹ • volume|_S`. Used only for such sets, where it is a probability measure. -/
def unifSet {α : Type*} [MeasureSpace α] (S : Set α) : Measure α :=
(volume S)⁻¹ • volume.restrict S
/-! ### Public parameters (53)–(54), p. 30.
Paper indices `i ∈ [d]`, `k ∈ [M]` are 1-indexed; here `i : Fin d`, `k : Fin M` are 0-indexed,
so the paper's `i` is `i.val + 1` and the paper's `k` is `k.val + 1`. -/
/-- `M = ⌈100(dP+1)⌉`, an integer already, so the ceiling is the identity. -/
def numIntervals (d P : ℕ) : ℕ := 100 * (d * P + 1)
/-- Ratio of consecutive spatial scales, `q = 100 M d / ε_score`. -/
def ratio (d P : ℕ) (ε : ℝ) : ℝ := 100 * (numIntervals d P : ℝ) * d / ε
/-- Location scale `a_i = q^{-(i-1)}/4` (paper index `i = j.val + 1`). -/
def scale (d P : ℕ) (ε : ℝ) (j : Fin d) : ℝ := (ratio d P ε)⁻¹ ^ j.val / 4
/-- Interval half-length `h_i = a_i/(100 M)`. -/
def halfLen (d P : ℕ) (ε : ℝ) (j : Fin d) : ℝ := scale d P ε j / (100 * numIntervals d P)
/-- Noise cutoff `t_i = 4 a_i / ε_score`. -/
def cutoff (d P : ℕ) (ε : ℝ) (j : Fin d) : ℝ := 4 * scale d P ε j / ε
/-- Center `c_i(k) = a_i + (k - 1/2) a_i / M` (paper label `k = k.val + 1`). -/
def center (d P : ℕ) (ε : ℝ) (j : Fin d) (k : Fin (numIntervals d P)) : ℝ :=
scale d P ε j + ((k.val : ℝ) + 1 / 2) * scale d P ε j / numIntervals d P
/-- Candidate interval `I_i(k) = [c_i(k) - h_i, c_i(k) + h_i]` (54). -/
def interval (d P : ℕ) (ε : ℝ) (j : Fin d) (k : Fin (numIntervals d P)) : Set ℝ :=
Set.Icc (center d P ε j k - halfLen d P ε j) (center d P ε j k + halfLen d P ε j)
/-- The box `K^θ = ∏_i I_i(θ_i)` in `E d` (7). -/
def box (d P : ℕ) (ε : ℝ) (θ : Fin d → Fin (numIntervals d P)) : Set (E d) :=
{x | ∀ j, x j ∈ interval d P ε j (θ j)}
/-- Scalar posterior mean of `U ~ Unif(I)` given `U + σZ = z`, `Z ~ N(0,1)` (p. 31):
the uniform interval measure weighted by its Gaussian likelihood at `z`, defined at every `z`.
The Gaussian normalizing constant cancels. -/
def postMeanUnif (I : Set ℝ) (σ z : ℝ) : ℝ :=
(∫ u in I, u * Real.exp (-(z - u) ^ 2 / (2 * σ ^ 2))) /
∫ u in I, Real.exp (-(z - u) ^ 2 / (2 * σ ^ 2))
/-- Gate `g^k_{i,σ}` (55), p. 31: `≡ 1` when `σ > t_{i+1}`, otherwise
`min{1, max{0, 2 - dist(z, I_i(k))/(10 h_i)}}`. The paper defines it only for `i < d`
(here `i.val + 1 < d`); for the last coordinate the value `1` is a placeholder never used. -/
def gate (d P : ℕ) (ε : ℝ) (i : Fin d) (k : Fin (numIntervals d P)) (σ z : ℝ) : ℝ :=
if h : i.val + 1 < d then
if cutoff d P ε ⟨i.val + 1, h⟩ < σ then 1
else min 1 (max 0 (2 - Metric.infDist z (interval d P ε i k) / (10 * halfLen d P ε i)))
else 1
/-- Coordinate `j` of the gated oracle (57): `-x_j/σ² + 1{σ ≤ t_j} (∏_{i<j} g^{θ_i}_{i,σ}(x_i))
m^{θ_j}_{j,σ}(x_j)/σ²`, the empty product being `1`. -/
def gatedCoord (d P : ℕ) (ε : ℝ) (θ : Fin d → Fin (numIntervals d P)) (x : E d) (σ : ℝ)
(j : Fin d) : ℝ :=
-x j / σ ^ 2 +
(if σ ≤ cutoff d P ε j then
(∏ i ∈ Finset.univ.filter (fun i : Fin d => i < j), gate d P ε i (θ i) σ (x i)) *
postMeanUnif (interval d P ε j (θ j)) σ (x j) / σ ^ 2
else 0)
/-- The gated oracle `ŝ^θ` (57)/(9) as a map on queries `(x, σ)` with `σ > 0`. -/
def gatedOracle (d P : ℕ) (ε : ℝ) (θ : Fin d → Fin (numIntervals d P)) : Query d → E d :=
fun q => WithLp.toLp 2 (fun j => gatedCoord d P ε θ q.1 q.2.1 j)
/-- Truncated oracle `ŝ^{θ,[r]}` (61), p. 32, with the paper's `r` (coordinates `j ≤ r`, i.e.
`j.val < r`, keep the gated answer; later ones get the null score `-x_j/σ²`). -/
def truncOracle (d P : ℕ) (ε : ℝ) (r : ℕ) (θ : Fin d → Fin (numIntervals d P)) :
Query d → E d :=
fun q => WithLp.toLp 2 (fun j =>
if j.val < r then gatedCoord d P ε θ q.1 q.2.1 j else -q.1 j / q.2.1 ^ 2)
end ParallelDiffusionLB.NearIsotropic.Supplement