Actual joint inner reference stopping and expected count
AutoSamplingTheory.ExampleCases.SmoothedPicardHMC.JointReferenceGradientDescent.joint_reference_gradient_descent · theorem · Teaching coverage
Statement
The actual inner stopping index N and output out are jointly measurable in the pair. For every pair the output satisfies gradient-square<=a*d, residual norm= A*norm(grad F_p(out))<=A*sqrt(a*d), every earlier index strictly fails the threshold, and N+1<=2+k*log(1+A*norm(grad F_p(y))^2/d). Under the actual nu.prod(stdGaussian(E)), N+1 is integrable and its expectation is at most 2+k*log(1+A*(M+tau*d/A^2)/d).
All objects and hypotheses
- E is a complete finite-dimensional real inner-product space with its Borel measurable structure and canonical volume. Its real dimension d is strictly positive. U:E->R is C2.
- alpha,beta are nonnegative reals with 0<alpha<=beta. The genuine Hessian obeys alpha*norm(v)^2<=D2U(x)[v,v]<=beta*norm(v)^2 for every x,v.
- eta>=0,tau>0,r>=0. The actual probability nu satisfies W2(nu,rho_eta)^2<=ofReal(r^2), where pi=volume.tilted(-U) and rho_eta is the law of X+sqrt(eta)*Z for independent X~pi,Z~stdGaussian(E). W2 is the actual infimum of quadratic coupling costs.
- Set A=eta+tau,a=alpha+1/A,c=beta+1/A,k=c/a,M=4*beta*d+4*beta^2*eta*d+2*beta^2*r^2. For p=(y,z), set u(p)=y+sqrt(tau)*z and F_p(x)=U(x)+norm(x-u(p))^2/(2*A).
- Use T_p(x)=x-c^(-1)*grad F_p(x), start at y, and define N(p) as the least n with norm(grad F_p(T_p^n(y)))^2<=a*d if one exists, otherwise zero. Define out(p)=T_p^N(p)(y). The finite-hit proof makes the default branch unreachable for every pair.
Mathematical proof
1. Identify the actual regularized gradient and positive parameters
A=eta+tau is positive. The inherited genuine quadratic differentiation gives grad F_p(x)=grad U(x)+(x-u(p))/A. Thus c and a are positive and the gradient descent step is well defined. F is the actual regularized potential, not an abstract gradient field with an assumed moment.
Corresponding Lean step
actual_joint_program: H,hg; joint_reference_gradient_descent: hA,ha,hc,hgrad; TerminalReferenceGradientDescent.terminal_reference_gradient_descent
2. Prove joint continuity of each actual finite iterate
The center map p=(y,z) maps continuously to y+sqrt(tau)*z. Starting from the first projection, induct on the number of actual updates. Continuity of grad U and the algebraic update prove continuity of the whole pair-to-iterate map. Fixed-center continuity alone would not justify this conclusion.
Corresponding Lean step
joint_iterates; actual_joint_program: hu,hgU,hTeq,hi; Function.iterate_succ_apply'
3. Use the strict terminal index only as a finite witness
The public terminal theorem gives a finite index hitting d/A and its pointwise count bound. Since d/A<=a*d, that point also witnesses existence for the actual inner predicate. jointIndex takes the least index of this inner predicate; Nat.find minimality makes it no larger than the witness and proves strict failure at every earlier index. The two stopping indices and outputs are not identified.
Corresponding Lean step
jointIndex; joint_stop: ht,hn,hle; actual_joint_program: hs,hw; Nat.find_spec; Nat.find_min; Nat.find_min'
4. Obtain measurability of the first index and stopped output
For each n, the actual gradient formula and joint iterate continuity make the inner stopping event measurable. The finite witness eliminates the default no-hit branch everywhere. Apply measurable_find to the index and Measurable.find to the stopped family of iterates. This proves measurability for the same pair that sets both center and starting point.
Corresponding Lean step
actual_joint_program: hp; joint_stop: hNm,hOm; measurable_find; Measurable.find
5. Derive the actual inner residual bound
Rearrange the genuine gradient identity to express u-A*grad U(x)-x as -A*grad F_p(x). Taking norms gives the exact residual identity. At the actual stopped point, the inner threshold bounds the gradient norm by sqrt(a*d), hence the residual by A*sqrt(a*d). The terminal bound sqrt(d*A) is not asserted for this different output.
Corresponding Lean step
joint_reference_gradient_descent: hres,hP; Real.le_sqrt_of_sq_le
6. Consume the moment of the same random potential and initial state
An explicit function equality identifies F_p with the potential used by ApproximateInitialGradientMoment. That theorem derives joint gradient-square integrability and the displayed moment from the actual W2 input. Its pair law is exactly nu.prod(G), with y both the initial point and part of u(p). No unconditional fixed-center expected-cost clause is used and no target moment is assumed.
Corresponding Lean step
joint_reference_gradient_descent: hMom,hFeq,hgi,hM,hgm; ApproximateInitialGradientMoment.approximate_initial_gradient_moment
7. Establish logarithm and count integrability before expectation
For nonnegative g and s=d/A>0, log(1+g/s) lies between zero and g/s, so it is integrable. At the upper mean m=M+tau*d/A^2, the logarithmic tangent bounds it by log(1+m/s)+(g-m)/(s+m). Integrate this inequality using the proved moment bound. The pointwise count estimate then gives N+1 integrability and the stated expected bound. N=0 still costs one gradient check; random histories and cumulative sampler costs require further proofs.
Corresponding Lean step
expected_count: hli,htangent,hlog,hci; joint_reference_gradient_descent: hE,ratio
Lean statement · joint_reference_gradient_descent
Actual same-pair first-hit index and output, measurability, inner residual and first-hit/count properties, actual count L1 and expected bound.
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 joint_reference_gradient_descent [FiniteDimensional ℝ E]
[MeasurableSpace E] [BorelSpace E] {U : E → ℝ} {α β : ℝ≥0}
(hα : 0 < α) (hαβ : α ≤ β) (hU : ContDiff ℝ 2 U)
(hH : ∀ x v : E, (α:ℝ)*‖v‖^2 ≤ fderiv ℝ (fderiv ℝ U) x v v ∧
fderiv ℝ (fderiv ℝ U) x v v ≤ (β:ℝ)*‖v‖^2)
{η τ r : ℝ} (hη : 0 ≤ η) (hτ : 0 < τ) (hr : 0 ≤ r)
(hd : 0 < (Module.finrank ℝ E : ℝ))
(ν : Measure E) [IsProbabilityMeasure ν]
(hw : TechnicalLemmas.Measure.WassersteinSpace.wassersteinDistance ν
(TechnicalLemmas.Measure.GaussianSmoothing.gaussianSmoothing
((volume : Measure E).tilted (fun x => -U x)) (Real.sqrt η)) ^ 2 ≤ ENNReal.ofReal (r^2)) :
let d : ℝ := Module.finrank ℝ E
let A := η+τ
let a := (α:ℝ)+A⁻¹
let c := (β:ℝ)+A⁻¹
let k := c/a
let M := 4*(β:ℝ)*d+4*(β:ℝ)^2*η*d+2*(β:ℝ)^2*r^2
let u := fun p : E × E => p.1+Real.sqrt τ • p.2
let F := fun p x => U x+A⁻¹/2*‖x-u p‖^2
let T := fun p x => x-c⁻¹ • gradient (F p) x
let N := jointIndex T (fun p x => ‖gradient (F p) x‖^2) (a*d)
let out := fun p => (T p)^[N p] p.1
Measurable N ∧ Measurable out ∧
(∀ p, ‖gradient (F p) (out p)‖^2 ≤ a*d ∧
‖u p-A • gradient U (out p)-out p‖ = A*‖gradient (F p) (out p)‖ ∧
‖u p-A • gradient U (out p)-out p‖ ≤ A*Real.sqrt (a*d) ∧
(∀ j < N p, a*d < ‖gradient (F p) ((T p)^[j] p.1)‖^2) ∧
(N p:ℝ)+1 ≤ k*Real.log (1+A*‖gradient (F p) p.1‖^2/d)+2) ∧
Integrable (fun p => (N p:ℝ)+1) (ν.prod (stdGaussian E)) ∧
(∫ p, (N p:ℝ)+1 ∂ν.prod (stdGaussian E)) ≤
2+k*Real.log (1+A*(M+τ*d/A^2)/d)Lean proof · joint_reference_gradient_descent
Joint iteration continuity, strict terminal witness for actual inner first hitting, measurable choice, genuine residual identity, same-potential moment consumption and integrable logarithmic tangent.
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 joint_reference_gradient_descent [FiniteDimensional ℝ E]
[MeasurableSpace E] [BorelSpace E] {U : E → ℝ} {α β : ℝ≥0}
(hα : 0 < α) (hαβ : α ≤ β) (hU : ContDiff ℝ 2 U)
(hH : ∀ x v : E, (α:ℝ)*‖v‖^2 ≤ fderiv ℝ (fderiv ℝ U) x v v ∧
fderiv ℝ (fderiv ℝ U) x v v ≤ (β:ℝ)*‖v‖^2)
{η τ r : ℝ} (hη : 0 ≤ η) (hτ : 0 < τ) (hr : 0 ≤ r)
(hd : 0 < (Module.finrank ℝ E : ℝ))
(ν : Measure E) [IsProbabilityMeasure ν]
(hw : TechnicalLemmas.Measure.WassersteinSpace.wassersteinDistance ν
(TechnicalLemmas.Measure.GaussianSmoothing.gaussianSmoothing
((volume : Measure E).tilted (fun x => -U x)) (Real.sqrt η)) ^ 2 ≤ ENNReal.ofReal (r^2)) :
let d : ℝ := Module.finrank ℝ E
let A := η+τ
let a := (α:ℝ)+A⁻¹
let c := (β:ℝ)+A⁻¹
let k := c/a
let M := 4*(β:ℝ)*d+4*(β:ℝ)^2*η*d+2*(β:ℝ)^2*r^2
let u := fun p : E × E => p.1+Real.sqrt τ • p.2
let F := fun p x => U x+A⁻¹/2*‖x-u p‖^2
let T := fun p x => x-c⁻¹ • gradient (F p) x
let N := jointIndex T (fun p x => ‖gradient (F p) x‖^2) (a*d)
let out := fun p => (T p)^[N p] p.1
Measurable N ∧ Measurable out ∧
(∀ p, ‖gradient (F p) (out p)‖^2 ≤ a*d ∧
‖u p-A • gradient U (out p)-out p‖ = A*‖gradient (F p) (out p)‖ ∧
‖u p-A • gradient U (out p)-out p‖ ≤ A*Real.sqrt (a*d) ∧
(∀ j < N p, a*d < ‖gradient (F p) ((T p)^[j] p.1)‖^2) ∧
(N p:ℝ)+1 ≤ k*Real.log (1+A*‖gradient (F p) p.1‖^2/d)+2) ∧
Integrable (fun p => (N p:ℝ)+1) (ν.prod (stdGaussian E)) ∧
(∫ p, (N p:ℝ)+1 ∂ν.prod (stdGaussian E)) ≤
2+k*Real.log (1+A*(M+τ*d/A^2)/d) := by
let d : ℝ := Module.finrank ℝ E
let A := η+τ
let a := (α:ℝ)+A⁻¹
let c := (β:ℝ)+A⁻¹
let k := c/a
let M := 4*(β:ℝ)*d+4*(β:ℝ)^2*η*d+2*(β:ℝ)^2*r^2
let u := fun p : E × E => p.1+Real.sqrt τ • p.2
let F := fun p x => U x+A⁻¹/2*‖x-u p‖^2
let T := fun p x => x-c⁻¹ • gradient (F p) x
let N := jointIndex T (fun p x => ‖gradient (F p) x‖^2) (a*d)
let out := fun p => (T p)^[N p] p.1
have hA : 0 < A := add_pos_of_nonneg_of_pos hη hτ
have ha : 0 < a := add_pos_of_nonneg_of_pos α.coe_nonneg (inv_pos.mpr hA)
have hc : 0 < c := add_pos_of_nonneg_of_pos β.coe_nonneg (inv_pos.mpr hA)
have hP := actual_joint_program (τ:=τ) hU hH hαβ hA hd rfl
have hgrad (p : E × E) (x : E) :
gradient (F p) x=gradient U x+A⁻¹ • (x-u p) :=
(TerminalReferenceGradientDescent.terminal_reference_gradient_descent
hU hH hαβ hA hd rfl (u p)).2.2.2.1 x
have hres (p : E × E) (x : E) :
‖u p-A • gradient U x-x‖=A*‖gradient (F p) x‖ := by
have he : u p-A • gradient U x-x=-(A • gradient (F p) x) := by
rw [hgrad,smul_add,smul_smul,mul_inv_cancel₀ hA.ne',one_smul]
abel
rw [he,norm_neg,norm_smul,Real.norm_eq_abs,abs_of_pos hA]
have hMom := ApproximateInitialGradientMoment.approximate_initial_gradient_moment
hα hαβ hU hH hη hτ hr ν hw
have hFeq (y z : E) :
(fun x => U x+‖x-(y+Real.sqrt τ • z)‖^2/(2*(η+τ)))=F (y,z) := by
funext x
dsimp [F,u,A]
simp only [div_eq_mul_inv,mul_inv_rev]
ring
have hgi : Integrable (fun p : E × E => ‖gradient (F p) p.1‖^2)
(ν.prod (stdGaussian E)) := by
simpa only [hFeq] using hMom.2.2.2.1
have hM : (∫ p : E × E, ‖gradient (F p) p.1‖^2 ∂ν.prod (stdGaussian E)) ≤
M+τ*d/A^2 := by
simpa only [hFeq] using hMom.2.2.2.2.2.1
have hgm : Measurable (fun p : E × E => ‖gradient (F p) p.1‖^2) := by
simp_rw [hgrad]
have hgU := TechnicalLemmas.Analysis.Calculus.Gradient.continuous_gradient_of_contDiff_one
(hU.of_le (by norm_num))
exact ((hgU.comp continuous_fst).add
((continuous_fst.sub (continuous_fst.add (continuous_snd.const_smul _))).const_smul _)).norm.pow 2 |>.measurable
have ratio (z : ℝ) : z/(d/A)=A*z/d := by field_simp
have hE := expected_count (ν.prod (stdGaussian E))
(fun p => ‖gradient (F p) p.1‖^2) N (k:=k) (s:=d/A)
(div_pos hc ha) (div_pos hd hA)
hgm hgi (fun p => sq_nonneg _) hP.1 hM (fun p => by
simpa only [ratio] using (hP.2.2 p).2.2)
refine ⟨hP.1,hP.2.1,fun p => ?_,hE.1,?_⟩
· have hp := hP.2.2 p
refine ⟨hp.1,hres p _,?_,hp.2.1,hp.2.2⟩
rw [hres]
exact mul_le_mul_of_nonneg_left (Real.le_sqrt_of_sq_le hp.1) hA.le
· simpa only [ratio] using hE.2
end AutoSamplingTheory.ExampleCases.SmoothedPicardHMC.JointReferenceGradientDescentScope and omitted-condition boundaries
- Actual inner threshold a*d is preserved; terminal d/A supplies only a finite witness and upper count, never an identical stopping time or output. The logarithmic formula is a derived sufficient bound. General beta, coordinate-free finite dimension and eta=0 extend the source; this theorem requires d>0,tau>0,0<alpha<=beta and allows r=0. The input W2 guarantee remains supplied. N+1 counts one base-gradient evaluation per visited point including the initial/final check, reused for the update; no evaluator trace or cross-sampler cache saving is proved. The theorem proves joint measurability in (Y,Z) at fixed parameters, not a kernel jointly in all parameters, conditional-history propagation, a stage sum or either complete main result.
Source and reuse
ASTIS parents called
AutoSamplingTheory.ExampleCases.SmoothedPicardHMC.TerminalReferenceGradientDescent.terminal_reference_gradient_descentAutoSamplingTheory.ExampleCases.SmoothedPicardHMC.ApproximateInitialGradientMoment.approximate_initial_gradient_momentAutoSamplingTheory.TechnicalLemmas.Analysis.Calculus.Gradient.continuous_gradient_of_contDiff_one
Mathlib API called (external library)
- Function.iterate_succ_apply'
- measurable_find
- Measurable.find
- Nat.find_spec
- Nat.find_min
- Nat.find_min'
- Real.le_sqrt_of_sq_le
- Real.log_le_sub_one_of_pos
- MeasureTheory.integral_mono
Mathematical sources
- SPHMC Section6.3 inner reference-point construction — Actual fixed-call inner rule and sufficient expected count; history and total sampler cost remain separate.
ASTIS prose is not a quotation or a source-equivalence certificate. Definitions and aliases are explained as constructions, not counted as new mathematical proofs.