Samplinglib
Lean gate not recorded for this source state main · 9bb7a7394ab0

SourceQuadratureWork: 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 source quadrature and full phase work
Samplinglib mathematical lesson

Actual source quadrature and full phase work

AutoSamplingTheory.ExampleCases.SmoothedPicardHMC.SourceQuadratureWork.source_quadrature_phase_work · theorem · Teaching coverage

Read this first

Mathematical statement

Using exactly the source t,ell,Lambda,omega,b arrays above, set positionWeight_j=omega_{J-1,j} (the final node is h), momentumWeight_j=b_j and S=h^2 Lambda/2. Under mu=nu product ((Gaussian product Gaussian) product (Gaussian Fin-J array product Gaussian Fin-J array)), set d=finrank(E), a=exp(-h/2), sigma=sqrt(1-exp(-h)), MR=M+(1-exp(-h))*d, B=6MR+3eps^2+3eta*d, C=2+(1+log((1-c)^(-1)))/(-log c), L0=C[1+log(1+sqrt(2MR)/eps)], L1=C[1+log(1+sqrt(4MR+2S^2B)/eps)]. There exist measurable p,q,N with exact proximal equation, ||q(y)-p(y)||≤eps and successful proximalQuery from y with fuel N(y)+1 returning (q(y),N(y)+1) for every y. P0=aP+sigma zeta0, Y0_i=X+t_i P0, Z0_j=grad V(q(Y0_j)+sqrt(eta)G0_j), Y1_i=Y0_i-sum_j omega_ij Z0_j, Z1_j=grad V(q(Y1_j)+sqrt(eta)G1_j), Phi=(X+hP0-sum_j positionWeight_j Z1_j, a(P0-sum_j momentumWeight_j Z1_j)+sigma zeta1). The same Phi is measurable and defines the Gaussian pushforward Markov kernel. The count T=2*J+sum_i[(N(Y0_i)+1)+(N(Y1_i)+1)] is measurable. For every driving input w, phaseQuery with fuel(y)=N(y)+1 returns exactly some(Phi(w),T(w)); the real cast of T is integrable under mu and E_mu T≤J*(2+L0+L1). The node range and row budget needed by the compiled producer are derived from the coefficient certificate; the Fin J cardinal count is exactly J.

\[S=\frac{h^2}2\Lambda_J,\quad T=2J+\sum_{i=0}^{J-1}[N(Y_i^0)+1+N(Y_i^1)+1],\quad\mathbb E_\mu T\le J(2+L_0+L_1).\]
Lean statement · source_quadrature_phase_work

Exact source Fin J nodes, Mathlib Lagrange basis, actual compact supremum and coefficient integrals are explicit. Consumer retains all Gaussian factors and actual output/count.

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 source_quadrature_phase_work {J : ℕ} (hJ : 2 ≤ J) {V : E → ℝ} {κ : ℝ≥0}
    (hκ : 1 ≤ κ) (hV : ContDiff ℝ 2 V)
    (hH : ∀ x v : E, (κ : ℝ)⁻¹ * ‖v‖^2 ≤ (fderiv ℝ (fderiv ℝ V) x v) v ∧
      (fderiv ℝ (fderiv ℝ V) x v) v ≤ ‖v‖^2)
    {eta c eps : ℝ} (heta : 0 < eta) (hec : eta ≤ c) (hc : c < 1) (heps : 0 < eps)
    (ν : Measure (E × E)) [IsProbabilityMeasure ν]
    (xstar : E) (hstar : gradient V xstar = 0)
    {h M : ℝ} (hh : 0 < h) (hh1 : h ≤ 1) (hM : 0 ≤ M)
    (hstateI : Integrable (fun s : E × E => ‖s.1-xstar‖^2 + ‖s.2‖^2) ν)
    (hstate : (∫ s : E × E, ‖s.1-xstar‖^2 + ‖s.2‖^2 ∂ν) ≤ M)
:
    let t := fun i : Fin J => h/2*(1-Real.cos ((i : ℝ)/(J-1 : ℝ)*Real.pi))
    let ell := fun j : Fin J => Lagrange.basis Finset.univ t j
    let Lambda := sSup ((fun s : ℝ => ∑ j : Fin J, |(ell j).eval s|) '' Set.Icc 0 h)
    let omega := fun i j : Fin J => ∫ s in 0..t i, (t i-s)*(ell j).eval s
    let positionWeight := omega ⟨J-1,by omega⟩
    let momentumWeight := fun j : Fin J => ∫ s in 0..h, (ell j).eval s
    let S := h^2/2*Lambda
    let a := Real.exp (-h/2)
    let sigma := Real.sqrt (1-Real.exp (-h))
    let gi := Measure.pi (fun _ : Fin J => stdGaussian E)
    let γ := ((stdGaussian E).prod (stdGaussian E)).prod (gi.prod gi)
    let μ := ν.prod γ
    let MR := M + (1-Real.exp (-h)) * (Module.finrank ℝ E : ℝ)
    let B := 6*MR + 3*eps^2 + 3*eta*(Module.finrank ℝ E : ℝ)
    let C := 2 + (1+Real.log ((1-c)⁻¹))/(-Real.log c)
    let L0 := C*(1+Real.log (1+Real.sqrt (2*MR)/eps))
    let L1 := C*(1+Real.log (1+Real.sqrt (4*MR+2*S^2*B)/eps))
    ∃ p q : E → E, ∃ N : E → ℕ,
      Measurable p ∧ Measurable q ∧ Measurable N ∧
      (∀ y, p y + eta • gradient V (p y) = y ∧ ‖q y-p y‖ ≤ eps ∧
        ApproximateProximalExecution.proximalQuery (gradient V) eta eps y (N y+1) y =
          some (q y,N y+1)) ∧
      let P0 := fun w : (E × E) × ((E × E) × ((Fin J → E) × (Fin J → E))) =>
        a • w.1.2 + sigma • w.2.1.1
      let Y0 := fun i w => w.1.1 + t i • P0 w
      let Z0 := fun j w => gradient V (q (Y0 j w) + Real.sqrt eta • w.2.2.1 j)
      let Y1 := fun i w => Y0 i w - ∑ j, omega i j • Z0 j w
      let Z1 := fun j w => gradient V (q (Y1 j w) + Real.sqrt eta • w.2.2.2 j)
      let Φ := fun w => (w.1.1 + h • P0 w - ∑ j, positionWeight j • Z1 j w,
        a • (P0 w - ∑ j, momentumWeight j • Z1 j w) + sigma • w.2.1.2)
      let T := fun w => 2*J+∑ i, ((N (Y0 i w)+1)+(N (Y1 i w)+1))
      Measurable Φ ∧ Measurable T ∧
      (∃ K : Kernel (E × E) (E × E), IsMarkovKernel K ∧
        ∀ s, K s = γ.map (fun z => Φ (s,z))) ∧
      (∀ w, CountedPhaseProgram.phaseQuery (gradient V) eta eps h t omega positionWeight momentumWeight
        (fun y => N y+1) w = some (Φ w,T w)) ∧
      Integrable (fun w => (T w : ℝ)) μ ∧
      (∫ w, (T w : ℝ) ∂μ) ≤ (J : ℝ)*(2+L0+L1)

Exact module and namespace context

Proof roadmap

  1. 1Instantiate the source node and coefficient certificate

    Apply the independently reviewable coefficient leaf to the actual zero-based Chebyshev-Lobatto nodes. Set both stochastic-gradient-array indices to Fin J, the position weights to the final coefficient row and the momentum weights to the actual ell_j integrals. The final node equals h, so that row has exactly the source endpoint integration limit.

  2. 2Derive the moment-producer inputs

    From 0≤t_i≤h≤1 obtain |t_i|≤1. Lambda≥1 gives S=h^2 Lambda/2≥0, and each actual integrated row has l1 norm≤S. These were formerly supplied interface assumptions; here they follow from the true source arrays, with the factor1/2 retained. The h≤1 restriction is explicit and belongs to the existing moment interface, not a hidden theorem assumption.

  3. 3Execute and bound the same actual Gaussian phase

    Apply the existing actual counted-phase theorem with these derived inputs. It supplies measurable exact/approximate stopped proximal witnesses and the same full pushforward Markov kernel. The actual interpreter executes the first array, uses its returned gradients in the second centers, executes the second array and returns the exact complete update and count. The count includes every terminal residual test and precisely2J direct gradients. Its full-law integrability and expected-work bound are derived from incoming-state moments; there is no count or center-moment assumption.

  4. 4Keep all accuracy and source complexity boundaries explicit

    The input law is nu times all four independent Gaussian innovation factors; arithmetic is exact real arithmetic. The query certificate is not a runtime computation of N. The numerical L0/L1 coefficients use the actual Lambda and S; replacing Lambda by its classical logarithmic estimate and proving uniform state history/parameter complexity still require separate proofs. No target-law cost transfer or full theorem claim is made.

Full assumptions and notation

All objects and hypotheses

  • E is a complete finite-dimensional real inner-product space with Borel sigma-algebra; the source node count is natural J≥2 and index Fin J.
  • V is C2, kappa≥1, and kappa^(-1)||v||^2 ≤ D2V(x)[v,v] ≤ ||v||^2 for all x,v. Its actual gradient vanishes at the supplied xstar.
  • 0<eta≤c<1, eps>0, 0<h≤1 and M≥0. The incoming probability law nu on(X,P) has integrable ||X-xstar||^2+||P||^2 with mean≤M. No source node, coefficient, Lambda or row-budget hypothesis.

Mathematical proof

1. Instantiate the source node and coefficient certificate

Apply the independently reviewable coefficient leaf to the actual zero-based Chebyshev-Lobatto nodes. Set both stochastic-gradient-array indices to Fin J, the position weights to the final coefficient row and the momentum weights to the actual ell_j integrals. The final node equals h, so that row has exactly the source endpoint integration limit.

\[t_i=\frac h2\{1-\cos(i\pi/(J-1))\},\quad\Lambda_J=\sup_{s\in[0,h]}\sum_j|\ell_j(s)|,\quad\sum_j|\omega_{ij}|\le\frac{t_i^2}2\Lambda_J\le\frac{h^2}2\Lambda_J,\quad\sum_j b_j=h.\]
Corresponding Lean step

ChebyshevLobattoQuadrature.chebyshev_lobatto_coefficients

2. Derive the moment-producer inputs

From 0≤t_i≤h≤1 obtain |t_i|≤1. Lambda≥1 gives S=h^2 Lambda/2≥0, and each actual integrated row has l1 norm≤S. These were formerly supplied interface assumptions; here they follow from the true source arrays, with the factor1/2 retained. The h≤1 restriction is explicit and belongs to the existing moment interface, not a hidden theorem assumption.

\[|t_i|\le1,\quad S\ge0,\quad\sum_j|\omega_{ij}|\le S.\]
Corresponding Lean step

abs_le; node range; mul_nonneg; coefficient row bound

3. Execute and bound the same actual Gaussian phase

Apply the existing actual counted-phase theorem with these derived inputs. It supplies measurable exact/approximate stopped proximal witnesses and the same full pushforward Markov kernel. The actual interpreter executes the first array, uses its returned gradients in the second centers, executes the second array and returns the exact complete update and count. The count includes every terminal residual test and precisely2J direct gradients. Its full-law integrability and expected-work bound are derived from incoming-state moments; there is no count or center-moment assumption.

\[S=\frac{h^2}2\Lambda_J,\quad T=2J+\sum_{i=0}^{J-1}[N(Y_i^0)+1+N(Y_i^1)+1],\quad\mathbb E_\mu T\le J(2+L_0+L_1).\]
Corresponding Lean step

CountedPhaseProgram.implemented_phase_expected_query_work; CountedPhaseProgram.phaseQuery

4. Keep all accuracy and source complexity boundaries explicit

The input law is nu times all four independent Gaussian innovation factors; arithmetic is exact real arithmetic. The query certificate is not a runtime computation of N. The numerical L0/L1 coefficients use the actual Lambda and S; replacing Lambda by its classical logarithmic estimate and proving uniform state history/parameter complexity still require separate proofs. No target-law cost transfer or full theorem claim is made.

\[\mu=\nu\otimes[(\gamma_E\otimes\gamma_E)\otimes(\gamma_E^{\operatorname{Fin}J}\otimes\gamma_E^{\operatorname{Fin}J})].\]
Corresponding Lean step

SourceQuadratureWork.source_quadrature_phase_work

Lean verification

The exact proof begins folded immediately after the mathematical argument; the statement is folded beside the claim above.

Lean proof · source_quadrature_phase_work

The formula proof covers the entire current module including private node-range/injectivity/endpoint helpers for the coefficient leaf.

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.

Download module (.lean)
theorem source_quadrature_phase_work {J : ℕ} (hJ : 2 ≤ J) {V : E → ℝ} {κ : ℝ≥0}
    (hκ : 1 ≤ κ) (hV : ContDiff ℝ 2 V)
    (hH : ∀ x v : E, (κ : ℝ)⁻¹ * ‖v‖^2 ≤ (fderiv ℝ (fderiv ℝ V) x v) v ∧
      (fderiv ℝ (fderiv ℝ V) x v) v ≤ ‖v‖^2)
    {eta c eps : ℝ} (heta : 0 < eta) (hec : eta ≤ c) (hc : c < 1) (heps : 0 < eps)
    (ν : Measure (E × E)) [IsProbabilityMeasure ν]
    (xstar : E) (hstar : gradient V xstar = 0)
    {h M : ℝ} (hh : 0 < h) (hh1 : h ≤ 1) (hM : 0 ≤ M)
    (hstateI : Integrable (fun s : E × E => ‖s.1-xstar‖^2 + ‖s.2‖^2) ν)
    (hstate : (∫ s : E × E, ‖s.1-xstar‖^2 + ‖s.2‖^2 ∂ν) ≤ M)
:
    let t := fun i : Fin J => h/2*(1-Real.cos ((i : ℝ)/(J-1 : ℝ)*Real.pi))
    let ell := fun j : Fin J => Lagrange.basis Finset.univ t j
    let Lambda := sSup ((fun s : ℝ => ∑ j : Fin J, |(ell j).eval s|) '' Set.Icc 0 h)
    let omega := fun i j : Fin J => ∫ s in 0..t i, (t i-s)*(ell j).eval s
    let positionWeight := omega ⟨J-1,by omega⟩
    let momentumWeight := fun j : Fin J => ∫ s in 0..h, (ell j).eval s
    let S := h^2/2*Lambda
    let a := Real.exp (-h/2)
    let sigma := Real.sqrt (1-Real.exp (-h))
    let gi := Measure.pi (fun _ : Fin J => stdGaussian E)
    let γ := ((stdGaussian E).prod (stdGaussian E)).prod (gi.prod gi)
    let μ := ν.prod γ
    let MR := M + (1-Real.exp (-h)) * (Module.finrank ℝ E : ℝ)
    let B := 6*MR + 3*eps^2 + 3*eta*(Module.finrank ℝ E : ℝ)
    let C := 2 + (1+Real.log ((1-c)⁻¹))/(-Real.log c)
    let L0 := C*(1+Real.log (1+Real.sqrt (2*MR)/eps))
    let L1 := C*(1+Real.log (1+Real.sqrt (4*MR+2*S^2*B)/eps))
    ∃ p q : E → E, ∃ N : E → ℕ,
      Measurable p ∧ Measurable q ∧ Measurable N ∧
      (∀ y, p y + eta • gradient V (p y) = y ∧ ‖q y-p y‖ ≤ eps ∧
        ApproximateProximalExecution.proximalQuery (gradient V) eta eps y (N y+1) y =
          some (q y,N y+1)) ∧
      let P0 := fun w : (E × E) × ((E × E) × ((Fin J → E) × (Fin J → E))) =>
        a • w.1.2 + sigma • w.2.1.1
      let Y0 := fun i w => w.1.1 + t i • P0 w
      let Z0 := fun j w => gradient V (q (Y0 j w) + Real.sqrt eta • w.2.2.1 j)
      let Y1 := fun i w => Y0 i w - ∑ j, omega i j • Z0 j w
      let Z1 := fun j w => gradient V (q (Y1 j w) + Real.sqrt eta • w.2.2.2 j)
      let Φ := fun w => (w.1.1 + h • P0 w - ∑ j, positionWeight j • Z1 j w,
        a • (P0 w - ∑ j, momentumWeight j • Z1 j w) + sigma • w.2.1.2)
      let T := fun w => 2*J+∑ i, ((N (Y0 i w)+1)+(N (Y1 i w)+1))
      Measurable Φ ∧ Measurable T ∧
      (∃ K : Kernel (E × E) (E × E), IsMarkovKernel K ∧
        ∀ s, K s = γ.map (fun z => Φ (s,z))) ∧
      (∀ w, CountedPhaseProgram.phaseQuery (gradient V) eta eps h t omega positionWeight momentumWeight
        (fun y => N y+1) w = some (Φ w,T w)) ∧
      Integrable (fun w => (T w : ℝ)) μ ∧
      (∫ w, (T w : ℝ) ∂μ) ≤ (J : ℝ)*(2+L0+L1) := by
  classical
  dsimp only
  let t := fun i : Fin J => h/2*(1-Real.cos ((i : ℝ)/(J-1 : ℝ)*Real.pi))
  let ell := fun j : Fin J => Lagrange.basis Finset.univ t j
  let Lambda := sSup ((fun s : ℝ => ∑ j : Fin J, |(ell j).eval s|) '' Set.Icc 0 h)
  let omega := fun i j : Fin J => ∫ s in 0..t i, (t i-s)*(ell j).eval s
  let S := h^2/2*Lambda
  obtain ⟨ht,hinj,hlast,hcard,hpart,hLambda,hrow,hmom⟩ :=
    AutoSamplingTheory.TechnicalLemmas.Analysis.ChebyshevLobattoQuadrature.chebyshev_lobatto_coefficients hJ hh
  have ht' (i : Fin J) : |t i| ≤ 1 := by
    apply abs_le.mpr
    have hti : 0 ≤ t i := (ht i).1
    exact ⟨(by norm_num : (-1 : ℝ) ≤ 0).trans hti,(ht i).2.trans hh1⟩
  have hS : 0 ≤ S := by
    dsimp [S]
    exact mul_nonneg (by positivity) (by linarith : 0 ≤ Lambda)
  exact CountedPhaseProgram.implemented_phase_expected_query_work hκ hV hH heta hec hc heps
    ν xstar hstar hh.le hM hS hstateI hstate t ht' omega (fun i => (hrow i).2)
    (omega ⟨J-1,by omega⟩) (fun j => ∫ s in 0..h, (ell j).eval s)

end AutoSamplingTheory.ExampleCases.SmoothedPicardHMC.SourceQuadratureWork

Exact module and namespace context

Scope and omitted-condition boundaries
  • Actual Algorithm3.1 source quadrature arrays in one gradient-only full Gaussian phase, with a supplied incoming state L2 budget and explicit0<h≤1. All successful counts and the bound use the same actual driving law. Finite fuel is a noncomputable execution certificate, not runtime N-precomputation or a cost premise; no failed-path cost claim. Logarithmic Lebesgue bound/nonnegative weights/B2/globalD7/numericalD8/Wq/proxy-warmness/initialization/PBPS/composition and both main results remain open. No TV-to-unbounded-cost transfer.
Sources, dependencies, and reuse

Source and reuse

Samplinglib parents called

Mathlib API called (external library)

  • abs_le
  • mul_nonneg

Mathematical sources

  • SPHMC3.6 and B1 coefficient proof — Actual Algorithm3.1 source quadrature arrays in one gradient-only full Gaussian phase, with a supplied incoming state L2 budget and explicit0<h<=1. All successful counts and the bound use the same actual driving law. Finite fuel is a noncomputable execution certificate, not runtime N-precomputation or a cost premise; no failed-path cost claim. Logarithmic Lebesgue bound/nonnegative weights/B2/globalD7/numericalD8/Wq/proxy-warmness/initialization/PBPS/composition and both main results remain open. No TV-to-unbounded-cost transfer.

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