Samplinglib
Lean gate not recorded for this source state main · 0e31a3cda412

ReferenceCarryingCost: mathematical reading route

Read the statements and derivations in source order. Every result has its own optional Lean statement and proof. Source assumptions, library reuse and unproved boundaries are kept explicit.

  1. Actual reference count under the recursive state law
ASTIS mathematical exposition

Actual reference count under the recursive state law

AutoSamplingTheory.ExampleCases.SmoothedPicardHMC.ReferenceCarryingCost.reference_carrying_cost · theorem · Teaching coverage

Statement

The actual reference count C is jointly measurable and nonnegative. Measurability of epsilon implies measurability of B. For every state, C(s,.) is integrable under K(s) and its integral is at most B(s). For every SFinite state measure mu, the extended nonnegative integral of ofReal(C) under mu compProd K is at most the extended integral of ofReal(B) under mu. If B is mu-integrable, C is integrable under mu compProd K and its real integral is at most the real integral of B. Absorbed states have exactly zero count; the active count is the same actual N+1 used in the enhanced reference update.

\[C(s,x,z)=\begin{cases}0,&\theta\le b,\\N(s,x,z)+1,&b<\theta,\end{cases}\quad \int C(s,z)\,K(s,dz)\le B(s).\]

All objects and hypotheses

  • E is a finite-dimensional real inner-product Borel space with d=dim(E)>0. V is C2 and its genuine Hessian satisfies alpha*norm(w)^2<=D2V(x)[w,w]<=beta*norm(w)^2, with 0<alpha<=beta.
  • The retained state s=(b,u,xref,k,h) belongs to NNReal x E x E x Nat x (Nat->E). eta,tau are measurable strictly positive functions of the full state. epsilon is any real-valued function; no sign or measurability is assumed globally. M is an actual Markov kernel to original-coordinate points. theta is a supplied nonnegative precision cutoff.
  • Set beta_s=beta+b, a_s=alpha+b, kappa_s=beta_s/a_s, v=(eta+tau)/beta_s and V_s(w)=V(w)+b/2*norm(w-u)^2. Only at active states b<theta assume W2(M(s),H_(eta/beta_s) pi_(V_s))^2<=ofReal(kappa_s*epsilon(s)^2/beta_s), where pi_(V_s) is the volume tilt by -V_s and H_t adds independent Gaussian variance t. This is the current-call accuracy input, not a supplied moment or cost bound.
  • For p=(s,(x,z)), set y=x+sqrt(tau/beta_s)*z, bplus=b+toNNReal(1/v), uplus=(bplus)^(-1)*(b*u+v^(-1)*y), F_p(w)=V(w)+bplus/2*norm(w-uplus)^2 and T_p(w)=w-(beta+bplus)^(-1)*grad F_p(w). N(p) is the least n with norm(grad F_p(T_p^n(x)))^2<=(alpha+bplus)*d, or zero if no such n exists. The reused parent proves finite attainment; this is its same actual program from the pre-noise x.
  • Define C(p)=0 if theta<=b, otherwise N(p)+1. Set kappa_plus=(beta+bplus)/(alpha+bplus) and B(s)=0 if theta<=b, otherwise 2+kappa_plus*log(1+4*(eta+tau)*(1+eta)+2*(eta+tau)*kappa_s*epsilon(s)^2/d+tau/(eta+tau)). K(s)=M(s) product G, with G the standard Gaussian probability.
  • For integration, mu is any SFinite measure on the full state and mu compProd K is the actual kernel composition-product integration measure. The real global bound additionally assumes Integrable B mu. A probability state law gives an expectation interpretation; the theorem does not establish that an arbitrary mu was generated by the recursive algorithm.

Mathematical proof

1. Derive the true current curvature

Differentiate the actual quadratic regularizer twice. Its first derivative is b times the inner-product functional of w-u, and its second derivative adds b*norm(v)^2. Thus V_s is C2 with genuine Hessian interval [alpha+b,beta+b], supplying the exact hypotheses of the existing joint-reference theorem.

\[D^2V_s(w)[v,v]=D^2V(w)[v,v]+b\|v\|^2.\]
Corresponding Lean step

regularized_hessian; statewise_cost: hreg,hHs

2. Put the source precision into original coordinates

At an active state use smoothing eta/beta_s and fresh-noise variance tau/beta_s. The radius r=sqrt(kappa_s*epsilon^2/beta_s) is real and nonnegative. Its square is exactly the source squared precision budget, including epsilon=0. The parent derives the initial gradient moment and logarithmic count integrability from this W2 input; those are not extra assumptions.

\[r_s^2=\frac{\kappa_s\varepsilon_s^2}{\beta_s},\qquad \mathbb E\|\nabla V_s(X)\|^2\le\beta_s(4d+4\eta_s d+2\kappa_s\varepsilon_s^2).\]
Corresponding Lean step

statewise_cost: hb,ha,hn,H; JointReferenceGradientDescent.joint_reference_gradient_descent

3. Simplify the derived logarithmic bound

The joint-reference result integrates the actual first-hit count under M(s) product G. Its initial random-center gradient moment includes tau*d/(beta_s*v^2). Substituting v=(eta+tau)/beta_s into the complete moment expression produces the displayed explicit logarithm. No independence between the stopping index and initial gradient is assumed.

\[\mathbb E[N_s+1]\le2+\kappa_s^+\log\!\left(1+4(\eta_s+\tau_s)(1+\eta_s)+\frac{2(\eta_s+\tau_s)\kappa_s\varepsilon_s^2}{d}+\frac{\tau_s}{\eta_s+\tau_s}\right).\]
Corresponding Lean step

statewise_cost: hi,he,heq; firstIndex

4. Identify the same first hit in the enhanced state

The source potential W=V_s+norm(.-y)^2/(2v) and completed-square F differ by a spatial constant. The parent proves equality of genuine gradients and every iterate from x. Together with bplus=b+1/v this makes the threshold predicates identical for every n. Unfold the actual least-hit definition to identify Ns=N, including the definition of its fallback; the finite-hit parent ensures the fallback is not hiding failure.

\[\nabla W=\nabla F,\quad T_W^n(x)=T_F^n(x),\quad q_n^{W}=q_n^{F},\quad N_W=N_F.\]
Corresponding Lean step

reference_carrying_cost: R,hbp,hc,ha,hq,hN; ReferenceCarryingKernel.reference_carrying_kernel

5. Charge only the active branch

The existing N is jointly measurable in full state, output and noise. The measurable cutoff partitions the domain. Its absorbed branch has count zero, while the active branch charges N+1. Cast the natural count to reals and combine the two branches. Transfer the statewise bound through the proved equality of indices; the zero branch is directly integrable.

\[C=\mathbf1_{\{b<\theta\}}(N+1)\ge0,\qquad C(s,\cdot)\in L^1(K(s)).\]
Corresponding Lean step

reference_carrying_cost: hNm,hCm,hC0,K,hK,hKs,hp

6. Separate measurable budgets from integrable budgets

If epsilon is measurable, every term in B is measurable: projections, positive scales, scalar arithmetic, square, logarithm and the cutoff partition. This proves the conditional measurable-budget conclusion. It does not bound the size of B along a state law and cannot imply global L1 by itself.

\[\varepsilon\text{ measurable}\Longrightarrow B\text{ measurable}.\]
Corresponding Lean step

reference_carrying_cost: hBm; Measurable.ite

7. Integrate the actual nonnegative cost first

For each state, nonnegative count integrability identifies its nonnegative extended integral with ofReal of its real integral. Apply the actual compProd iterated-integral formula and monotonicity to the proved statewise bound. This remains a general nonnegative integral inequality if B has not been shown measurable.

\[\int^-\!\operatorname{ofReal}(C)\,d(\mu\otimes_K)\le\int^-\!\operatorname{ofReal}(B)\,d\mu.\]
Corresponding Lean step

integrate_actual_cost: hE,hE0,first branch; Measure.lintegral_compProd; ofReal_integral_eq_lintegral_ofReal

8. Obtain the real global bound only after L1

Now assume B is mu-integrable. The measurable nonnegative conditional count integral is bounded by B, so it is integrable. Nonnegativity identifies the conditional norm integral with that count integral. The compProd integrability criterion proves global C integrability, after which the real iterated-integral formula and integral monotonicity yield the bound. For a probability mu this is an expected reference cost; for arbitrary SFinite mu it is an integral bound.

\[B\in L^1(\mu)\Longrightarrow C\in L^1(\mu\otimes_K),\qquad \int C\,d(\mu\otimes_K)\le\int B\,d\mu.\]
Corresponding Lean step

integrate_actual_cost: hEi,heq,hCi; Measure.integrable_compProd_iff; Measure.integral_compProd

Lean statement · reference_carrying_cost

Actual absorbed/active reference count, conditional budget measurability, statewise L1 and explicit cost, and compProd extended/conditional real integral bounds.

Braces mark parameters Lean can infer; square brackets request structures such as a measurable space or probability measure. Named hypotheses are mathematical premises, not facts established by this declaration. Section parameters are described in the mathematical hypotheses above; the module link retains their exact source context.

theorem reference_carrying_cost [FiniteDimensional ℝ E] [MeasurableSpace E] [BorelSpace E]
    {V : E → ℝ} {α β : ℝ≥0} (hα : 0 < α) (hαβ : α ≤ β)
    (hV : ContDiff ℝ 2 V)
    (hH : ∀ x w : E, (α:ℝ)*‖w‖^2 ≤ fderiv ℝ (fderiv ℝ V) x w w ∧
      fderiv ℝ (fderiv ℝ V) x w w ≤ (β:ℝ)*‖w‖^2)
    (hd : 0 < (Module.finrank ℝ E : ℝ))
    (η τ ε : RefState E → ℝ) (hη : Measurable η) (hτ : Measurable τ)
    (hη0 : ∀ s, 0 < η s) (hτ0 : ∀ s, 0 < τ s)
    (M : Kernel (RefState E) E) [IsMarkovKernel M] (threshold : ℝ≥0)
    (hw : ∀ s : RefState E, s.1 < threshold →
      AutoSamplingTheory.TechnicalLemmas.Measure.WassersteinSpace.wassersteinDistance (M s)
        (AutoSamplingTheory.TechnicalLemmas.Measure.GaussianSmoothing.gaussianSmoothing
          ((volume : Measure E).tilted (fun x => -(V x+(s.1:ℝ)/2*‖x-s.2.1‖^2)))
          (Real.sqrt (η s/((β:ℝ)+s.1)))) ^ 2 ≤
        ENNReal.ofReal ((((β:ℝ)+s.1)/((α:ℝ)+s.1))*(ε s)^2/((β:ℝ)+s.1))) :
    let d : ℝ := Module.finrank ℝ E
    let bs := fun s : RefState E => (β:ℝ)+s.1
    let a := fun s : RefState E => (α:ℝ)+s.1
    let v := fun s => (η s+τ s)/bs s
    let bp := fun s : RefState E => s.1+Real.toNNReal (v s)⁻¹
    let obs := fun p : RefState E × (E × E) => p.2.1+Real.sqrt (τ p.1/bs p.1) • p.2.2
    let center := fun p : RefState E × (E × E) => (bp p.1:ℝ)⁻¹ •
      ((p.1.1:ℝ) • p.1.2.1+(v p.1)⁻¹ • obs p)
    let F := fun p x => V x+(bp p.1:ℝ)/2*‖x-center p‖^2
    let T := fun p x => x-((β:ℝ)+bp p.1)⁻¹ • gradient (F p) x
    let q := fun n p => ‖gradient (F p) ((T p)^[n] p.2.1)‖^2
    let N := firstIndex q (fun p => ((α:ℝ)+bp p.1)*d)
    let C := fun p : RefState E × (E × E) => if threshold ≤ p.1.1 then 0 else (N p:ℝ)+1
    let B := fun s : RefState E => if threshold ≤ s.1 then 0 else
      2+(((β:ℝ)+bp s)/((α:ℝ)+bp s))*Real.log
        (1+4*(η s+τ s)*(1+η s)+2*(η s+τ s)*(bs s/a s)*(ε s)^2/d+τ s/(η s+τ s))
    let K := M ×ₖ Kernel.const (RefState E) (stdGaussian E)
    Measurable C ∧ (Measurable ε → Measurable B) ∧ (∀ p, 0 ≤ C p) ∧
      (∀ s, Integrable (fun z => C (s,z)) (K s) ∧ (∫ z, C (s,z) ∂K s) ≤ B s) ∧
      (∀ (μ : Measure (RefState E)) [SFinite μ],
        (∫⁻ p, ENNReal.ofReal (C p) ∂μ.compProd K) ≤ ∫⁻ s, ENNReal.ofReal (B s) ∂μ ∧
          (Integrable B μ → Integrable C (μ.compProd K) ∧
            (∫ p, C p ∂μ.compProd K) ≤ ∫ s, B s ∂μ))

Exact module and namespace context

Lean proof · reference_carrying_cost

Genuine current Hessian, original-coordinate W2 input, existing actual first-hit count, source/completed-square index identity, measurable zero-cost branch and actual kernel integral calculus.

Braces mark parameters Lean can infer; square brackets request structures such as a measurable space or probability measure. Named hypotheses are mathematical premises, not facts established by this declaration. Section parameters are described in the mathematical hypotheses above; the module link retains their exact source context.

theorem reference_carrying_cost [FiniteDimensional ℝ E] [MeasurableSpace E] [BorelSpace E]
    {V : E → ℝ} {α β : ℝ≥0} (hα : 0 < α) (hαβ : α ≤ β)
    (hV : ContDiff ℝ 2 V)
    (hH : ∀ x w : E, (α:ℝ)*‖w‖^2 ≤ fderiv ℝ (fderiv ℝ V) x w w ∧
      fderiv ℝ (fderiv ℝ V) x w w ≤ (β:ℝ)*‖w‖^2)
    (hd : 0 < (Module.finrank ℝ E : ℝ))
    (η τ ε : RefState E → ℝ) (hη : Measurable η) (hτ : Measurable τ)
    (hη0 : ∀ s, 0 < η s) (hτ0 : ∀ s, 0 < τ s)
    (M : Kernel (RefState E) E) [IsMarkovKernel M] (threshold : ℝ≥0)
    (hw : ∀ s : RefState E, s.1 < threshold →
      AutoSamplingTheory.TechnicalLemmas.Measure.WassersteinSpace.wassersteinDistance (M s)
        (AutoSamplingTheory.TechnicalLemmas.Measure.GaussianSmoothing.gaussianSmoothing
          ((volume : Measure E).tilted (fun x => -(V x+(s.1:ℝ)/2*‖x-s.2.1‖^2)))
          (Real.sqrt (η s/((β:ℝ)+s.1)))) ^ 2 ≤
        ENNReal.ofReal ((((β:ℝ)+s.1)/((α:ℝ)+s.1))*(ε s)^2/((β:ℝ)+s.1))) :
    let d : ℝ := Module.finrank ℝ E
    let bs := fun s : RefState E => (β:ℝ)+s.1
    let a := fun s : RefState E => (α:ℝ)+s.1
    let v := fun s => (η s+τ s)/bs s
    let bp := fun s : RefState E => s.1+Real.toNNReal (v s)⁻¹
    let obs := fun p : RefState E × (E × E) => p.2.1+Real.sqrt (τ p.1/bs p.1) • p.2.2
    let center := fun p : RefState E × (E × E) => (bp p.1:ℝ)⁻¹ •
      ((p.1.1:ℝ) • p.1.2.1+(v p.1)⁻¹ • obs p)
    let F := fun p x => V x+(bp p.1:ℝ)/2*‖x-center p‖^2
    let T := fun p x => x-((β:ℝ)+bp p.1)⁻¹ • gradient (F p) x
    let q := fun n p => ‖gradient (F p) ((T p)^[n] p.2.1)‖^2
    let N := firstIndex q (fun p => ((α:ℝ)+bp p.1)*d)
    let C := fun p : RefState E × (E × E) => if threshold ≤ p.1.1 then 0 else (N p:ℝ)+1
    let B := fun s : RefState E => if threshold ≤ s.1 then 0 else
      2+(((β:ℝ)+bp s)/((α:ℝ)+bp s))*Real.log
        (1+4*(η s+τ s)*(1+η s)+2*(η s+τ s)*(bs s/a s)*(ε s)^2/d+τ s/(η s+τ s))
    let K := M ×ₖ Kernel.const (RefState E) (stdGaussian E)
    Measurable C ∧ (Measurable ε → Measurable B) ∧ (∀ p, 0 ≤ C p) ∧
      (∀ s, Integrable (fun z => C (s,z)) (K s) ∧ (∫ z, C (s,z) ∂K s) ≤ B s) ∧
      (∀ (μ : Measure (RefState E)) [SFinite μ],
        (∫⁻ p, ENNReal.ofReal (C p) ∂μ.compProd K) ≤ ∫⁻ s, ENNReal.ofReal (B s) ∂μ ∧
          (Integrable B μ → Integrable C (μ.compProd K) ∧
            (∫ p, C p ∂μ.compProd K) ≤ ∫ s, B s ∂μ)) := by
  classical
  intro d bs a v bp obs center F T q N C B K
  have R := AutoSamplingTheory.ExampleCases.SmoothedPicardHMC.ReferenceCarryingKernel.reference_carrying_kernel
    hα hαβ hV hH hd η τ hη hτ hη0 hτ0 M threshold
  have hbp (s : RefState E) : (bp s:ℝ)=(s.1:ℝ)+(v s)⁻¹ := (R.1 s).2
  have hNm : Measurable N := R.2.1
  have hCm : Measurable C := by
    apply Measurable.ite (measurableSet_le measurable_const (by fun_prop)) measurable_const
    exact (measurable_from_nat.comp hNm).add measurable_const
  have hC0 (p : RefState E × (E × E)) : 0 ≤ C p := by dsimp [C]; split_ifs <;> positivity
  have hBm (hε : Measurable ε) : Measurable B := by
    dsimp [B,bp,v,bs,a]
    apply Measurable.ite (measurableSet_le measurable_const (by fun_prop)) measurable_const
    fun_prop
  have hK : IsMarkovKernel K := by dsimp [K]; infer_instance
  have hKs (s : RefState E) : K s=(M s).prod (stdGaussian E) := by
    simp only [K,Kernel.prod_apply,Kernel.const_apply]
  have hp (s : RefState E) : Integrable (fun z => C (s,z)) (K s) ∧
      (∫ z, C (s,z) ∂K s) ≤ B s := by
    by_cases hs : threshold ≤ s.1
    · simp only [C,B,if_pos hs,integrable_const,integral_const,smul_zero,le_refl,and_self]
    · have Hs := statewise_cost hα hαβ hV hH hd s.1 s.2.1 (η s) (τ s) (ε s)
        (hη0 s) (hτ0 s) (M s) (hw s (lt_of_not_ge hs))
      let W := fun z : E × E => fun x => V x+(s.1:ℝ)/2*‖x-s.2.1‖^2+
        (v s)⁻¹/2*‖x-(z.1+Real.sqrt (τ s/bs s) • z.2)‖^2
      let Ts := fun z x => x-(bs s+(v s)⁻¹)⁻¹ • gradient (W z) x
      let qs := fun n z => ‖gradient (W z) ((Ts z)^[n] z.1)‖^2
      let Ns := firstIndex qs (fun _ => (a s+(v s)⁻¹)*d)
      have hc : bs s+(v s)⁻¹=(β:ℝ)+bp s := by rw [hbp]; dsimp [bs]; ring
      have ha : a s+(v s)⁻¹=(α:ℝ)+bp s := by rw [hbp]; dsimp [a]; ring
      have hq (n : ℕ) (z : E × E) : qs n z=q n (s,z) := by
        have hz := R.2.2.2.2.1 (s,z)
        have ht := hz.2.2.2.2.2.1 n
        have hg := hz.2.2.2.2.1
        change (fun x => x-((β:ℝ)+bp s)⁻¹ • gradient (W z) x)^[n] z.1 =
          (T (s,z))^[n] z.1 at ht
        dsimp only [qs,Ts]
        rw [hc,ht]
        exact congrArg (fun w : E => ‖w‖^2) (hg _)
      have hN (z : E × E) : Ns z=N (s,z) := by
        dsimp only [Ns,N,firstIndex]
        simp only [hq,ha]
      change Integrable (fun z => (Ns z:ℝ)+1) ((M s).prod (stdGaussian E)) ∧
        (∫ z, (Ns z:ℝ)+1 ∂(M s).prod (stdGaussian E)) ≤
          2+((bs s+(v s)⁻¹)/(a s+(v s)⁻¹))*Real.log _ at Hs
      simp_rw [hN] at Hs
      simpa only [C,B,if_neg hs,hKs,hc,ha] using Hs
  exact ⟨hCm,hBm,hC0,hp,fun μ => integrate_actual_cost K C B hCm hC0
    (fun s => (hp s).1) (fun s => (hp s).2) μ⟩

end AutoSamplingTheory.ExampleCases.SmoothedPicardHMC.ReferenceCarryingCost

Exact module and namespace context

Scope and omitted-condition boundaries

  • One-step actual reference GD cost, excluding M sampling queries, terminal FORS, cross-call cache discounts and evaluator traces. N+1 counts visited gradient checks under one evaluation per point with check/update reuse. Only active states require the supplied original-coordinate A1 W2 guarantee; no sampler achieving it is constructed. General beta, coordinate-free positive dimension, arbitrary retained states, arbitrary real epsilon and SFinite state measures are disclosed extensions. Without measurable epsilon the upper extended integral uses Mathlib general nonnegative-integral conventions, not automatically a measurable random budget. Measurable B is distinct from integrable B; global L1 requires the latter. At absorbed states the auxiliary product integration representation has zero cost and does not assert actual random draws. compProd is not the next-state marginal, and this theorem does not publicly return P. Valid execution state laws, source parameter schedule, stopping depth, accumulated costs, history invariants, full composition and both main results remain open.

Source and reuse

ASTIS parents called

Mathlib API called (external library)

  • Measurable.ite
  • MeasureTheory.Measure.lintegral_compProd
  • MeasureTheory.Measure.integrable_compProd_iff
  • MeasureTheory.Measure.integral_compProd
  • MeasureTheory.ofReal_integral_eq_lintegral_ofReal

Mathematical sources

  • SPHMC Algorithm3.3 and Section6.3 reference query cost — One-step actual reference GD cost, excluding M sampling queries, terminal FORS, cross-call cache discounts and evaluator traces. N+1 counts visited gradient checks under one evaluation per point with check/update reuse. Only active states require the supplied original-coordinate A1 W2 guarantee; no sampler achieving it is constructed. General beta, coordinate-free positive dimension, arbitrary retained states, arbitrary real epsilon and SFinite state measures are disclosed extensions. Without measurable epsilon the upper extended integral uses Mathlib general nonnegative-integral conventions, not automatically a measurable random budget. Measurable B is distinct from integrable B; global L1 requires the latter. At absorbed states the auxiliary product integration representation has zero cost and does not assert actual random draws. compProd is not the next-state marginal, and this theorem does not publicly return P. Valid execution state laws, source parameter schedule, stopping depth, accumulated costs, history invariants, full composition and both main results remain open.

ASTIS prose is not a quotation or a source-equivalence certificate. Definitions and aliases are explained as constructions, not counted as new mathematical proofs.