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

QuadraticRegularization: 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. Quadratic regularization shifts actual curvature and gradient smoothness
ASTIS mathematical exposition

Quadratic regularization shifts actual curvature and gradient smoothness

AutoSamplingTheory.TechnicalLemmas.Analysis.QuadraticRegularization.strongConvexOn_and_lipschitzWith_gradient_add_quadratic · theorem · Teaching coverage

Statement

Let E be a complete real inner-product space and U:E→R be everywhere twice continuously Fréchet differentiable. Let m,L,r be nonnegative real constants. Suppose m‖v‖²≤D²U(x)[v,v]≤L‖v‖² for every x,v∈E. For every centre u∈E, the actual potential W(x)=U(x)+r‖x−u‖²/2 is (m+r)-strongly convex on E and its actual gradient is (L+r)-Lipschitz on E. The constants are exact, including r=0. No gradient field, Hessian field or operator-norm bound is supplied as an assumption.

\[W(x)=U(x)+\frac r2\|x-u\|^2,\qquad W(ax+by)\le aW(x)+bW(y)-\frac{m+r}{2}ab\|x-y\|^2,\qquad\|\nabla W(x)-\nabla W(y)\|\le(L+r)\|x-y\|,\quad a,b\ge0,\ a+b=1.\]

All objects and hypotheses

  • E is any complete real inner-product space, including zero dimension; no finite-dimensional or nontrivial-space assumption occurs in the theorem.
  • ContDiff ℝ 2 U witnesses genuine C² regularity. D²U(x)[v,v] is (fderiv ℝ (fderiv ℝ U) x v) v. Totalized derivative notation alone would not establish that these are actual derivatives.
  • The lower and upper inequalities hold at every point and in every direction on the whole space. The nonnegative types m,L,r:ℝ≥0 encode their signs. In particular, nonnegative lower curvature is used to control the absolute Rayleigh quotient.
  • In SPHMC Lemma 6.4 use m=κ⁻¹, L=1 and r=A⁻¹. A=∞ is represented by r=0, not by declaring a zero finite variance admissible. PBPS uses the same regularized potential with m=α, L=β and r=η⁻¹, under its source-positive parameters.
  • No measure, normalizer, measurability or integrability is needed for the production conclusion. Focused probability consumers separately add finite dimension, a Borel measurable structure, canonical volume and positive source curvature.

Mathematical proof

1. Differentiate the actual quadratic potential

The squared norm is smooth on a real inner-product space. Differentiate the shifted quadratic twice: its first derivative evaluates r⟨x−u,v⟩, and its second derivative evaluates r⟨v,w⟩. Thus W is genuinely C² and its diagonal Hessian is the diagonal Hessian of U plus r‖v‖². The original sandwich shifts by exactly r on both sides.

\[DW(x)[v]=DU(x)[v]+r\langle x-u,v\rangle,\qquad D^2W(x)[v,w]=D^2U(x)[v,w]+r\langle v,w\rangle,\qquad(m+r)\|v\|^2\le D^2W(x)[v,v]\le(L+r)\|v\|^2.\]
Corresponding Lean step

ContDiff.norm_sq proves hW. HasFDerivAt.norm_sq and the sum/chain rules give hq, hWfd and hWdd; hbounds evaluates the derivative on the diagonal. The local J packages v↦innerSL ℝ v as a continuous real-linear map, proving additivity and scalar compatibility because the generic innerSL API is conjugate-linear. This is an implementation adapter, not an assumed Hessian.

2. Turn the shifted lower bound into the exact chord inequality

Apply the shared Hessian-to-strong-convexity theorem to W and the shifted lower bound. Its scalar-line argument yields the chord correction (m+r)ab‖x−y‖²/2 without losing a factor. This is the first public conclusion.

\[D^2W(x)[v,v]\ge(m+r)\|v\|^2\quad\Longrightarrow\quad W(ax+by)\le aW(x)+bW(y)-\frac{m+r}{2}ab\|x-y\|^2.\]
Corresponding Lean step

HessianStrongConvexity.strongConvexOn_univ_of_fderiv2_lower receives hW and the lower half of hbounds, returning StrongConvexOn Set.univ with precisely the coerced NNReal sum m+r.

3. Identify the genuine derivative of the gradient and its symmetry

Completeness supplies inverse Riesz representation. Apply it to the first derivative of W to obtain Mathlib's actual gradient, then differentiate this fixed continuous linear transformation. The resulting operator Tₓ=D(∇W)(x) represents the genuine Hessian: ⟨Tₓv,w⟩=D²W(x)[v,w]. The C² symmetry theorem makes Tₓ symmetric; no matrix representation or finite-dimensional eigenbasis is introduced.

\[T_x=D(\nabla W)(x),\qquad\langle T_xv,w\rangle=D^2W(x)[v,w]=D^2W(x)[w,v]=\langle v,T_xw\rangle.\]
Corresponding Lean step

R packages (InnerProductSpace.toDual ℝ E).symm as a continuous real-linear map. T is R.comp applied to fderiv ℝ (fderiv ℝ W) x. hTd is a HasFDerivAt witness for gradient W, hinner uses InnerProductSpace.toDual_symm_apply, and hsym uses ContDiffAt.isSymmSndFDerivAt.

4. Bound the operator norm from the diagonal sandwich

For a symmetric operator the operator norm equals the supremum of the absolute Rayleigh quotient. The shifted lower bound and m+r≥0 make the Hessian diagonal nonnegative. For v≠0 the shifted upper bound therefore gives quotient at most L+r. At v=0 the totalized quotient is zero, so this case also satisfies the bound and does not require E to contain a nonzero vector.

\[\|T_x\|=\sup_v\left|\frac{\langle T_xv,v\rangle}{\|v\|^2}\right|\le L+r.\]
Corresponding Lean step

ContinuousLinearMap.norm_eq_iSup_rayleighQuotient and ciSup_le reduce hnorm to each quotient. hbounds supplies nonnegativity and the upper estimate. The proof handles v=0 explicitly; otherwise norm_pos_iff and div_le_iff₀ justify division.

5. Use the whole-space mean-value bound

The actual gradient is differentiable everywhere and its derivative has norm at most L+r at every point. The whole-space mean-value theorem gives global (L+r)-Lipschitz continuity, which is the precise smoothness sense returned here.

\[\|D(\nabla W)(x)\|\le L+r\quad(\forall x)\quad\Longrightarrow\quad\|\nabla W(x)-\nabla W(y)\|\le(L+r)\|x-y\|\quad(\forall x,y).\]
Corresponding Lean step

lipschitzWith_of_nnnorm_fderiv_le uses differentiability from hTd and rewrites the derivative by (hTd x).fderiv before applying hnorm. The public LipschitzWith conclusion is about gradient W itself, not a separately declared gradient or Hessian norm.

Lean statement · strongConvexOn_and_lipschitzWith_gradient_add_quadratic

The theorem quantifies over E with NormedAddCommGroup, InnerProductSpace ℝ and CompleteSpace; U:E→ℝ; m,L,r:ℝ≥0; and u:E. Its only mathematical input hypotheses are ContDiff ℝ 2 U and the everywhere/every-direction nested-fderiv sandwich. Its let-bound W is the actual quadratic regularization. The two conclusions are StrongConvexOn Set.univ (↑(m+r)) W and LipschitzWith (L+r) (gradient W).

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 strongConvexOn_and_lipschitzWith_gradient_add_quadratic
    {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
    {U : E → ℝ} {m L r : ℝ≥0}
    (hU : ContDiff ℝ 2 U)
    (hH : ∀ x v : E,
      (m : ℝ) * ‖v‖ ^ 2 ≤ (fderiv ℝ (fderiv ℝ U) x v) v ∧
      (fderiv ℝ (fderiv ℝ U) x v) v ≤ (L : ℝ) * ‖v‖ ^ 2)
    (u : E) :
    let W := fun x => U x + (r : ℝ) / 2 * ‖x - u‖ ^ 2
    StrongConvexOn Set.univ ((m + r : ℝ≥0) : ℝ) W ∧
      LipschitzWith (L + r) (gradient W)

Exact module and namespace context

Lean proof · strongConvexOn_and_lipschitzWith_gradient_add_quadratic

One shared production theorem contains the quadratic-shift, Riesz and norm estimates as local proof terms, not public wrapper siblings. The focused tests instantiate the source constants κ⁻¹, 1, A⁻¹; separately retain r=0 and zero dimension. Under source-positive curvature and the finite-dimensional Borel canonical-volume assumptions, they use the derived strong convexity with StrongConvexGibbsIntegrability to return integrability, strictly positive Gibbs normalizer and actual probability. That derived probability feeds quadratic_tilt_tilt, with positive A⁻¹ used for the additional normalized Gaussian reweighting. Neither integrability nor probability is assumed.

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 strongConvexOn_and_lipschitzWith_gradient_add_quadratic
    {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
    {U : E → ℝ} {m L r : ℝ≥0}
    (hU : ContDiff ℝ 2 U)
    (hH : ∀ x v : E,
      (m : ℝ) * ‖v‖ ^ 2 ≤ (fderiv ℝ (fderiv ℝ U) x v) v ∧
      (fderiv ℝ (fderiv ℝ U) x v) v ≤ (L : ℝ) * ‖v‖ ^ 2)
    (u : E) :
    let W := fun x => U x + (r : ℝ) / 2 * ‖x - u‖ ^ 2
    StrongConvexOn Set.univ ((m + r : ℝ≥0) : ℝ) W ∧
      LipschitzWith (L + r) (gradient W) := by
  let W := fun x => U x + (r : ℝ) / 2 * ‖x - u‖ ^ 2
  have hUd : Differentiable ℝ U := hU.differentiable (by norm_num)
  have hUdd : Differentiable ℝ (fderiv ℝ U) :=
    (hU.fderiv_right (m := 1) (by norm_num)).differentiable_one
  have hn : ContDiff ℝ 2 (fun x : E => ‖x - u‖ ^ 2) :=
    (contDiff_id.sub contDiff_const).norm_sq (𝕜 := ℝ)
  have hW : ContDiff ℝ 2 W := hU.add (contDiff_const.mul hn)
  have hq (x : E) : HasFDerivAt (fun z => (r : ℝ) / 2 * ‖z - u‖ ^ 2)
      ((r : ℝ) • innerSL ℝ (x - u)) x := by
    convert (((hasFDerivAt_id x).sub_const u).norm_sq).const_mul ((r : ℝ) / 2)
      using 1 <;> first | rfl | (ext v; simp; ring)
  have hWfd (x : E) : fderiv ℝ W x =
      fderiv ℝ U x + (r : ℝ) • innerSL ℝ (x - u) :=
    ((hUd x).hasFDerivAt.add (hq x)).fderiv
  let J : E →L[ℝ] (E →L[ℝ] ℝ) :=
    { toFun := fun v => innerSL ℝ v
      map_add' := by intros; ext; simp
      map_smul' := by intros; ext; simp
      cont := (innerSL ℝ (E := E)).continuous }
  have hWdd (x : E) : HasFDerivAt (fderiv ℝ W)
      (fderiv ℝ (fderiv ℝ U) x + (r : ℝ) • J) x := by
    rw [show fderiv ℝ W = (fun z => fderiv ℝ U z +
      (r : ℝ) • innerSL ℝ (z - u)) from funext hWfd]
    convert (hUdd x).hasFDerivAt.add
      ((J.hasFDerivAt.comp x ((hasFDerivAt_id x).sub_const u)).const_smul
        (r : ℝ)) using 1 <;> rfl
  have hbounds (x v : E) :
      ((m + r : ℝ≥0) : ℝ) * ‖v‖ ^ 2 ≤ (fderiv ℝ (fderiv ℝ W) x v) v ∧
      (fderiv ℝ (fderiv ℝ W) x v) v ≤ ((L + r : ℝ≥0) : ℝ) * ‖v‖ ^ 2 := by
    rw [(hWdd x).fderiv]
    change ((m : ℝ) + r) * ‖v‖ ^ 2 ≤
        (fderiv ℝ (fderiv ℝ U) x v) v + (r : ℝ) * inner ℝ v v ∧
      (fderiv ℝ (fderiv ℝ U) x v) v + (r : ℝ) * inner ℝ v v ≤
        ((L : ℝ) + r) * ‖v‖ ^ 2
    rw [real_inner_self_eq_norm_sq]
    constructor <;> nlinarith [(hH x v).1, (hH x v).2]
  refine ⟨HessianStrongConvexity.strongConvexOn_univ_of_fderiv2_lower hW
    (fun x v => (hbounds x v).1), ?_⟩
  let R : (E →L[ℝ] ℝ) →L[ℝ] E :=
    { toFun := (toDual ℝ E).symm
      map_add' := (toDual ℝ E).symm.map_add
      map_smul' := by intros; simp
      cont := (toDual ℝ E).symm.continuous }
  let T (x : E) : E →L[ℝ] E := R.comp (fderiv ℝ (fderiv ℝ W) x)
  have hTd (x : E) : HasFDerivAt (gradient W) (T x) x := by
    exact R.hasFDerivAt.comp x
      (((hW.fderiv_right (m := 1) (by norm_num)).differentiable_one x).hasFDerivAt)
  have hinner (x v w : E) : inner ℝ (T x v) w =
      (fderiv ℝ (fderiv ℝ W) x v) w := by
    exact toDual_symm_apply
  have hsym (x : E) : (T x).IsSymmetric := by
    intro v w
    change inner ℝ (T x v) w = inner ℝ v (T x w)
    calc
      _ = (fderiv ℝ (fderiv ℝ W) x v) w := hinner x v w
      _ = (fderiv ℝ (fderiv ℝ W) x w) v :=
        hW.contDiffAt.isSymmSndFDerivAt (by norm_num) v w
      _ = inner ℝ (T x w) v := (hinner x w v).symm
      _ = inner ℝ v (T x w) := real_inner_comm _ _
  have hnorm (x : E) : ‖T x‖ ≤ ((L + r : ℝ≥0) : ℝ) := by
    rw [(T x).norm_eq_iSup_rayleighQuotient (hsym x)]
    apply ciSup_le
    intro v
    change |inner ℝ (T x v) v / ‖v‖ ^ 2| ≤ ((L + r : ℝ≥0) : ℝ)
    rw [hinner]
    have hnonneg : 0 ≤ (fderiv ℝ (fderiv ℝ W) x v) v :=
      (mul_nonneg (NNReal.coe_nonneg _) (sq_nonneg _)).trans (hbounds x v).1
    rw [abs_of_nonneg (div_nonneg hnonneg (sq_nonneg _))]
    by_cases hv : v = 0
    · simp [hv]
      positivity
    · exact (div_le_iff₀ (sq_pos_of_pos (norm_pos_iff.mpr hv))).2 (hbounds x v).2
  apply lipschitzWith_of_nnnorm_fderiv_le (fun x => (hTd x).differentiableAt)
  intro x
  rw [(hTd x).fderiv]
  exact hnorm x

end AutoSamplingTheory.TechnicalLemmas.Analysis.QuadraticRegularization

Exact module and namespace context

Scope and omitted-condition boundaries

  • Direct source coverage is SPHMC Lemma 6.4's strong-convexity and smoothness clause for the actual regularized potential. Its normalized-oracle closure and condition-number recurrence (6.1) are not proved by this declaration.
  • PBPS (2.9) supplies a second potential consumer and (2.10) supplies its Hessian sandwich. This theorem gives an analytic consequence useful downstream, including smoothness for that potential; it does not return the Hessian sandwich as a public conclusion and is not direct formalization of all of (2.10) or Proposition 2.1.
  • Conditional-law identification, Poincaré or covariance bounds, invariant kernels, sampler accuracy, condition-number algebra and query costs are not proved by this declaration.
  • The complete-inner-product-space and nonnegative-parameter extensions concern only deterministic curvature/smoothness. They do not establish infinite-dimensional Gibbs normalization or remove positive-curvature conditions from the source sampling results.

Source and reuse

ASTIS parents called

Mathlib API called (external library)

  • ContDiff.norm_sq
  • ContDiff.differentiable
  • ContDiff.fderiv_right
  • ContDiff.differentiable_one
  • HasFDerivAt.norm_sq
  • HasFDerivAt.comp
  • HasFDerivAt.const_mul
  • HasFDerivAt.const_smul
  • HasFDerivAt.add
  • HasFDerivAt.fderiv
  • InnerProductSpace.toDual_symm_apply
  • ContDiffAt.isSymmSndFDerivAt
  • ContinuousLinearMap.norm_eq_iSup_rayleighQuotient
  • lipschitzWith_of_nnnorm_fderiv_le

Mathematical sources

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