TR-LALM Theory

Section 2 — Deterministic method and convergence

Algorithm 2.1

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Selected defining clause 1 of 2; not the complete item.

The quadratic model minimized by one fixed-penalty NR-LALM step.

open scoped InnerProductSpace namespace LALM variable {n m : ℕ} @[expose] noncomputable def stepModel (f : EuclideanSpace ℝ (Fin n) → ℝ) (c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)) (ρ β : ℝ) (x : EuclideanSpace ℝ (Fin n)) (multiplier : EuclideanSpace ℝ (Fin m)) (p : EuclideanSpace ℝ (Fin n)) : ℝ := ⟪gradient f x, p⟫_ℝ + ⟪multiplier, c x + fderiv ℝ c x p⟫_ℝ + (ρ / 2) * ‖c x + fderiv ℝ c x p‖ ^ 2 + (β / 2) * ‖p‖ ^ 2

Algorithm 2.1

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Selected defining clause 2 of 2; not the complete item.

A fixed-penalty NR-LALM run, storing its generated points, multipliers, and steps together with the model-minimization and update laws.

open scoped InnerProductSpace NNReal namespace LALM variable {n m : ℕ} structure Run (f : EuclideanSpace ℝ (Fin n) → ℝ) (c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)) (ρ β : ℝ) (x₀ : EuclideanSpace ℝ (Fin n)) (multiplier₀ : EuclideanSpace ℝ (Fin m)) where /-- The penalty parameter is positive. -/ rho_pos : 0 < ρ /-- The proximal parameter is positive. -/ beta_pos : 0 < β /-- The generated primal points. -/ point : ℕ → EuclideanSpace ℝ (Fin n) /-- The generated multipliers. -/ multiplier : ℕ → EuclideanSpace ℝ (Fin m) /-- The generated primal steps. -/ step : ℕ → EuclideanSpace ℝ (Fin n) /-- The point sequence starts at the specified initial point. -/ point_zero : point 0 = x₀ /-- The multiplier sequence starts at the specified initial multiplier. -/ multiplier_zero : multiplier 0 = multiplier₀ /-- Each stored step globally minimizes the corresponding quadratic model. -/ minimizes_step (k : ℕ) : IsMinOn (stepModel f c ρ β (point k) (multiplier k)) Set.univ (step k) /-- The next point is obtained by adding the current step. -/ point_succ (k : ℕ) : point (k + 1) = point k + step k /-- The next multiplier uses the constraint value at the updated point. -/ multiplier_succ (k : ℕ) : multiplier (k + 1) = multiplier k + ρ • c (point (k + 1))

Assumption 2.1

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

A regularity certificate exposes the nonempty open region, local differentiability, strictly positive constants, and uniform estimates of Assumption 2.1.

open scoped ContDiff Gradient NNReal namespace EqualityConstrained variable {n m : ℕ} namespace Regularity variable {f : EuclideanSpace ℝ (Fin n) → ℝ} variable {c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)} theorem spec (h : Regularity f c) : h.region.Nonempty ∧ IsOpen h.region ∧ (DifferentiableOn ℝ f h.region ∧ DifferentiableOn ℝ c h.region) ∧ ((0 : ℝ) < h.gradientBound ∧ (0 : ℝ) < h.gradientLipschitz ∧ (0 : ℝ) < h.constraintGradientBound ∧ (0 : ℝ) < h.constraintGradientLipschitz ∧ 0 < h.licqModulus.val) ∧ ((∀ x ∈ h.region, h.objectiveLower ≤ f x) ∧ (∀ x ∈ h.region, ‖∇ f x‖ ≤ h.gradientBound) ∧ LipschitzOnWith h.gradientLipschitz (∇ f) h.region ∧ (∀ x ∈ h.region, ‖constraintGradient c x‖ ≤ h.constraintGradientBound) ∧ LipschitzOnWith h.constraintGradientLipschitz (constraintGradient c) h.region ∧ ∀ x ∈ h.region, ∀ u : EuclideanSpace ℝ (Fin m), h.licqModulus * ‖u‖ ≤ ‖constraintGradient c x u‖)

Definition 2.2

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Selected defining clause 1 of 5; not the complete item.

A point is approximately KKT when some multiplier certifies an approximate KKT pair.

open scoped NNReal namespace KKT variable {n m : ℕ} def IsApproximatePoint (f : EuclideanSpace ℝ (Fin n) → ℝ) (c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)) (ε : ℝ≥0) (x : EuclideanSpace ℝ (Fin n)) : Prop := ∃ multiplier : EuclideanSpace ℝ (Fin m), IsApproximatePair f c ε x multiplier

Definition 2.2

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Selected defining clause 2 of 5; not the complete item.

The two componentwise bounds certifying an approximate KKT pair.

open scoped NNReal namespace KKT variable {n m : ℕ} structure IsApproximatePair (f : EuclideanSpace ℝ (Fin n) → ℝ) (c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)) (ε : ℝ≥0) (x : EuclideanSpace ℝ (Fin n)) (multiplier : EuclideanSpace ℝ (Fin m)) : Prop where /-- The stationarity residual is at most `ε`. -/ stationarity_le : ‖stationarity f c x multiplier‖ ≤ ε /-- The feasibility residual is at most `ε`. -/ feasibility_le : ‖c x‖ ≤ ε

Definition 2.2

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Selected defining clause 3 of 5; not the complete item.

An exact KKT point is an approximate KKT point with zero tolerance.

open scoped NNReal namespace KKT variable {n m : ℕ} def IsPoint (f : EuclideanSpace ℝ (Fin n) → ℝ) (c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)) (x : EuclideanSpace ℝ (Fin n)) : Prop := IsApproximatePoint f c 0 x

Definition 2.2

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Selected defining clause 4 of 5; not the complete item.

An exact KKT pair is an approximate KKT pair with zero tolerance.

open scoped NNReal namespace KKT variable {n m : ℕ} def IsPair (f : EuclideanSpace ℝ (Fin n) → ℝ) (c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)) (x : EuclideanSpace ℝ (Fin n)) (multiplier : EuclideanSpace ℝ (Fin m)) : Prop := IsApproximatePair f c 0 x multiplier

Definition 2.2

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Selected defining clause 5 of 5; not the complete item.

The aggregate Euclidean residual of stationarity and feasibility.

open scoped NNReal namespace KKT variable {n m : ℕ} @[expose] noncomputable def residual (f : EuclideanSpace ℝ (Fin n) → ℝ) (c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)) (x : EuclideanSpace ℝ (Fin n)) (multiplier : EuclideanSpace ℝ (Fin m)) : ℝ := Real.sqrt (‖stationarity f c x multiplier‖ ^ 2 + ‖c x‖ ^ 2)

Assumption 2.3

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Assumption 2.3: an admissible scalar-parameter certificate exposes positivity and the four initialization-independent inequalities.

open scoped NNReal namespace LALM variable {n m : ℕ} variable {f : EuclideanSpace ℝ (Fin n) → ℝ} variable {c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)} namespace AdmissibleParameters theorem spec (params : AdmissibleParameters h) : ((0 : ℝ) < params.delta ∧ (0 : ℝ) < params.beta ∧ (0 : ℝ) < params.rho ∧ (0 : ℝ) < params.multiplierBound) ∧ (((h.gradientBound + params.beta * params.delta + params.rho * h.constraintGradientBound * linearizationConstant h * params.delta ^ 2) / h.licqModulus : ℝ) ≤ params.multiplierBound ∧ (h.gradientBound / params.beta + 3 * h.constraintGradientBound * params.multiplierBound / (params.beta + params.rho * h.licqModulus ^ 2) : ℝ) ≤ params.delta ∧ modelConstant h params.delta params.rho params.multiplierBound ≤ 3 * params.beta / 8 ∧ 8 * multiplierPrimalConstant h params.delta params.beta params.rho params.multiplierBound / params.beta ≤ params.rho)

Proposition 2.4

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 2.4: fixed regularity data admit accuracy-independent scalar NR-LALM parameters with a fixed penalty ratio and multiplier bound of order beta * delta.

open Filter Asymptotics namespace LALM variable {n m : ℕ} variable {f : EuclideanSpace ℝ (Fin n) → ℝ} variable {c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)} theorem existsParametersOfLargeBeta (h : EqualityConstrained.Regularity f c) : ∃ delta tauRho beta₀ : ℝ, 0 < delta ∧ 0 < tauRho ∧ 0 < beta₀ ∧ ∃ multiplierBound : ℝ → ℝ, multiplierBound =Θ[atTop] (fun beta ↦ beta * delta) ∧ ∀ beta ≥ beta₀, ∃ params : AdmissibleParameters h, params.values = (delta, beta, tauRho * beta, multiplierBound beta)

Assumption 2.5

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Selected defining clause 1 of 4; not the complete item.

The exact-gradient deterministic sublevel, enlarged by the chosen step radius, lies inside the regularity region.

namespace LALM variable {n m : ℕ} variable {f : EuclideanSpace ℝ (Fin n) → ℝ} variable {c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)} @[expose] def DeterministicRegionCondition (h : EqualityConstrained.Regularity f c) {x₀ : EuclideanSpace ℝ (Fin n)} {multiplier₀ : EuclideanSpace ℝ (Fin m)} (params : Parameters h x₀ multiplier₀) : Prop := Metric.cthickening params.delta (deterministicSublevel h params) ⊆ h.region

Assumption 2.5

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Selected defining clause 2 of 4; not the complete item.

The deterministic objective--feasibility localization set.

namespace LALM variable {n m : ℕ} variable {f : EuclideanSpace ℝ (Fin n) → ℝ} variable {c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)} @[expose] def deterministicSublevel (h : EqualityConstrained.Regularity f c) {x₀ : EuclideanSpace ℝ (Fin n)} {multiplier₀ : EuclideanSpace ℝ (Fin m)} (params : Parameters h x₀ multiplier₀) : Set (EuclideanSpace ℝ (Fin n)) := {x | f x ≤ deterministicObjectiveBound h params ∧ ‖c x‖ ≤ 2 * params.multiplierBound / params.rho}

Assumption 2.5

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Selected defining clause 3 of 4; not the complete item.

The deterministic objective threshold Hdet obtained from the initial-potential bound and the multiplier correction.

namespace LALM variable {n m : ℕ} variable {f : EuclideanSpace ℝ (Fin n) → ℝ} variable {c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)} @[expose] noncomputable def deterministicObjectiveBound (h : EqualityConstrained.Regularity f c) {x₀ : EuclideanSpace ℝ (Fin n)} {multiplier₀ : EuclideanSpace ℝ (Fin m)} (params : Parameters h x₀ multiplier₀) : ℝ := initialPotentialBound h params + params.multiplierBound ^ 2 / (2 * params.rho)

Assumption 2.5

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Selected defining clause 4 of 4; not the complete item.

The deterministic initial-potential bound determined by the regularity data and chosen NR-LALM parameters.

namespace LALM variable {n m : ℕ} variable {f : EuclideanSpace ℝ (Fin n) → ℝ} variable {c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)} @[expose] noncomputable def initialPotentialBound (h : EqualityConstrained.Regularity f c) {x₀ : EuclideanSpace ℝ (Fin n)} {multiplier₀ : EuclideanSpace ℝ (Fin m)} (params : Parameters h x₀ multiplier₀) : ℝ := f x₀ + h.gradientBound * params.delta + 4 * params.multiplierBound ^ 2 / params.rho + (multiplierPrimalConstant h params.delta params.beta params.rho params.multiplierBound / params.rho) * params.delta ^ 2

Lemma 2.6

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Lemma 2.6 (1): every primal step among the first N completed iterations of an admissible prefix has norm at most the chosen step-radius parameter Δ.

open scoped InnerProductSpace NNReal namespace LALM.Run variable {n m : ℕ} variable {f : EuclideanSpace ℝ (Fin n) → ℝ} variable {c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)} variable {x₀ : EuclideanSpace ℝ (Fin n)} variable {multiplier₀ : EuclideanSpace ℝ (Fin m)} theorem norm_step_le (h : EqualityConstrained.Regularity f c) (params : Parameters h x₀ multiplier₀) (run : Run f c params.rho params.beta x₀ multiplier₀) {N k : ℕ} (h_admissible : run.IsAdmissiblePrefix h N) (hk : k < N) : ‖run.step k‖ ≤ params.delta

Lemma 2.7

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Lemma 2.7: every iteration in an admissible prefix decreases the fixed-penalty augmented Lagrangian by at least (params.beta / 2) * ‖run.step k‖ ^ 2.

open scoped InnerProductSpace LALM NNReal namespace LALM.Run variable {n m : ℕ} variable {f : EuclideanSpace ℝ (Fin n) → ℝ} variable {c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)} variable {x₀ : EuclideanSpace ℝ (Fin n)} variable {multiplier₀ : EuclideanSpace ℝ (Fin m)} theorem augmentedLagrangianDescent (h : EqualityConstrained.Regularity f c) (params : Parameters h x₀ multiplier₀) (run : Run f c params.rho params.beta x₀ multiplier₀) {N k : ℕ} (h_admissible : run.IsAdmissiblePrefix h N) (hk : k < N) : ℒ[f, c; params.rho](run.point (k + 1), run.multiplier k) ≤ ℒ[f, c; params.rho](run.point k, run.multiplier k) - (params.beta / 2) * ‖run.step k‖ ^ 2

Lemma 2.8

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Lemma 2.8: for every positive iteration index in an admissible prefix, the squared successive-multiplier difference is bounded by the multiplier-primal constant times the sum of the current and preceding squared step norms.

namespace LALM.Run variable {n m : ℕ} variable {f : EuclideanSpace ℝ (Fin n) → ℝ} variable {c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)} variable {x₀ : EuclideanSpace ℝ (Fin n)} variable {multiplier₀ : EuclideanSpace ℝ (Fin m)} theorem norm_multiplier_succ_sub_sq_le (h : EqualityConstrained.Regularity f c) (params : Parameters h x₀ multiplier₀) (run : Run f c params.rho params.beta x₀ multiplier₀) {N k : ℕ} (h_admissible : run.IsAdmissiblePrefix h N) (hk_pos : 1 ≤ k) (hk : k < N) : ‖run.multiplier (k + 1) - run.multiplier k‖ ^ 2 ≤ multiplierPrimalConstant h params.delta params.beta params.rho params.multiplierBound * (‖run.step k‖ ^ 2 + ‖run.step (k - 1)‖ ^ 2)

Theorem 2.9

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Theorem 2.9 (1): on an admissible prefix, each positive-index Lyapunov step decreases by at least (params.beta / 4) * ‖run.step k‖ ^ 2.

open scoped InnerProductSpace LALM NNReal namespace LALM.Run variable {n m : ℕ} variable {f : EuclideanSpace ℝ (Fin n) → ℝ} variable {c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)} variable {x₀ : EuclideanSpace ℝ (Fin n)} variable {multiplier₀ : EuclideanSpace ℝ (Fin m)} theorem lyapunovDescent (h : EqualityConstrained.Regularity f c) (params : Parameters h x₀ multiplier₀) (run : Run f c params.rho params.beta x₀ multiplier₀) {N k : ℕ} (h_admissible : run.IsAdmissiblePrefix h N) (hk_pos : 1 ≤ k) (hk : k < N) : run.lyapunov h params (k + 1) ≤ run.lyapunov h params k - (params.beta / 4) * ‖run.step k‖ ^ 2

Theorem 2.10

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Theorem 2.10 (1), existence: admissible positive parameters determine at least one infinite deterministic NR-LALM run from the prescribed initial data.

open scoped InnerProductSpace LALM NNReal namespace LALM.Run variable {n m : ℕ} variable {f : EuclideanSpace ℝ (Fin n) → ℝ} variable {c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)} variable {ρ β : ℝ} variable {x₀ : EuclideanSpace ℝ (Fin n)} variable {multiplier₀ : EuclideanSpace ℝ (Fin m)} theorem nonempty_of_parameters (h : EqualityConstrained.Regularity f c) (params : Parameters h x₀ multiplier₀) : Nonempty (Run f c params.rho params.beta x₀ multiplier₀)

Lemma 2.11

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Lemma 2.11: on every deterministic admissible prefix, the squared aggregate KKT residual after iteration k is controlled by the current and preceding squared step norms.

namespace LALM variable {n m : ℕ} variable {f : EuclideanSpace ℝ (Fin n) → ℝ} variable {c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)} namespace Run variable {x₀ : EuclideanSpace ℝ (Fin n)} variable {multiplier₀ : EuclideanSpace ℝ (Fin m)} theorem residual_sq_le (h : EqualityConstrained.Regularity f c) (params : Parameters h x₀ multiplier₀) (run : Run f c params.rho params.beta x₀ multiplier₀) {N k : ℕ} (h_admissible : run.IsAdmissiblePrefix h N) (hk_pos : 1 ≤ k) (hk : k < N) : KKT.residual f c (run.point (k + 1)) (run.multiplier (k + 1)) ^ 2 ≤ residualComparisonConstant h params.delta params.beta params.rho params.multiplierBound * (‖run.step k‖ ^ 2 + ‖run.step (k - 1)‖ ^ 2)

Theorem 2.12

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Theorem 2.12: under the deterministic assumptions, the uniform expected squared residual decays as C_det / (K - 1).

open scoped BigOperators NNReal namespace LALM variable {n m : ℕ} variable {f : EuclideanSpace ℝ (Fin n) → ℝ} variable {c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)} variable {ρ β : ℝ} variable {x₀ : EuclideanSpace ℝ (Fin n)} variable {multiplier₀ : EuclideanSpace ℝ (Fin m)} namespace Run theorem expect_residual_sq_le (h : EqualityConstrained.Regularity f c) (params : Parameters h x₀ multiplier₀) (h_region : DeterministicRegionCondition h params) (run : Run f c params.rho params.beta x₀ multiplier₀) (K : ℕ) (hK : 2 ≤ K) : (𝔼 k ∈ Finset.Icc 1 (K - 1), KKT.residual f c (run.point (k + 1)) (run.multiplier (k + 1)) ^ 2) ≤ deterministicComplexityConstant h params run / ((K : ℝ) - 1)

Theorem 2.13

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Theorem 2.13 (1): compactness of the deterministic sublevel and the Kurdyka--Łojasiewicz property at every lifted cluster point imply summability of the primal-step and multiplier-increment lengths.

open Filter Topology open scoped LALM namespace LALM variable {n m : ℕ} namespace Run variable {f : EuclideanSpace ℝ (Fin n) → ℝ} variable {c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)} variable {x₀ : EuclideanSpace ℝ (Fin n)} variable {multiplier₀ : EuclideanSpace ℝ (Fin m)} variable {ρ β : ℝ} theorem summableStepAndMultiplierIncrement (h : EqualityConstrained.Regularity f c) (params : Parameters h x₀ multiplier₀) (h_region : DeterministicRegionCondition h params) (run : Run f c params.rho params.beta x₀ multiplier₀) (h_compact : IsCompact (deterministicSublevel h params)) (h_KL : KurdykaLojasiewicz.HasAtClusterPoints (liftedEnergy f c params.rho params.beta) atTop run.liftedIterate) : Summable (fun k ↦ ‖run.step k‖ + ‖run.multiplier (k + 1) - run.multiplier k‖)

Section 3 — Stochastic method

Assumption 3.1

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

A stochastic oracle exposes the joint measurability, differentiability, expectation, unbiasedness, noise, and mean-square Lipschitz conditions of Assumption 3.1.

open MeasureTheory open scoped Gradient NNReal namespace EqualityConstrained universe u namespace StochasticOracle variable {n : ℕ} {f : EuclideanSpace ℝ (Fin n) → ℝ} variable {region : Set (EuclideanSpace ℝ (Fin n))} variable {Ω : Type u} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] theorem spec (oracle : StochasticOracle f region μ) : Measurable (fun z : EuclideanSpace ℝ (Fin n) × Ω ↦ oracle.sampleGradient z.1 z.2) ∧ (∀ᵐ ω ∂μ, DifferentiableOn ℝ (fun x ↦ oracle.sample x ω) region) ∧ (∀ x ∈ region, Integrable (fun ω ↦ oracle.sample x ω) μ ∧ (∫ ω, oracle.sample x ω ∂μ) = f x) ∧ (∀ x ∈ region, Integrable (fun ω ↦ oracle.sampleGradient x ω) μ ∧ (∫ ω, oracle.sampleGradient x ω ∂μ) = ∇ f x) ∧ (∀ x ∈ region, Integrable (fun ω ↦ ‖oracle.sampleGradient x ω - ∇ f x‖ ^ 2) μ ∧ (∫ ω, ‖oracle.sampleGradient x ω - ∇ f x‖ ^ 2 ∂μ) ≤ oracle.noiseLevel ^ 2) ∧ ∀ x ∈ region, ∀ y ∈ region, Integrable (fun ω ↦ ‖oracle.sampleGradient x ω - oracle.sampleGradient y ω‖ ^ 2) μ ∧ (∫ ω, ‖oracle.sampleGradient x ω - oracle.sampleGradient y ω‖ ^ 2 ∂μ) ≤ oracle.meanSquareLipschitz ^ 2 * ‖x - y‖ ^ 2

Definition 3.2

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Selected defining clause 1 of 2; not the complete item.

A stochastic approximate KKT point has a random multiplier on the same probability space.

open MeasureTheory open scoped ENNReal NNReal namespace KKT.Stochastic universe u variable {n m : ℕ} {Ω : Type u} [MeasurableSpace Ω] def IsApproximatePoint (ℙ : Measure Ω) [IsProbabilityMeasure ℙ] (f : EuclideanSpace ℝ (Fin n) → ℝ) (c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)) (ε : ℝ≥0) (x : Ω → EuclideanSpace ℝ (Fin n)) : Prop := ∃ multiplier : Ω → EuclideanSpace ℝ (Fin m), IsApproximatePair ℙ f c ε x multiplier

Definition 3.2

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Selected defining clause 2 of 2; not the complete item.

A stochastic approximate KKT pair on a fixed probability space.

open MeasureTheory open scoped ENNReal NNReal namespace KKT.Stochastic universe u variable {n m : ℕ} {Ω : Type u} [MeasurableSpace Ω] structure IsApproximatePair (ℙ : Measure Ω) [IsProbabilityMeasure ℙ] (f : EuclideanSpace ℝ (Fin n) → ℝ) (c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)) (ε : ℝ≥0) (x : Ω → EuclideanSpace ℝ (Fin n)) (multiplier : Ω → EuclideanSpace ℝ (Fin m)) : Prop where /-- The stochastic point is a random variable up to `ℙ`-null sets. -/ aemeasurable_point : AEMeasurable x ℙ /-- The stochastic multiplier is a random variable up to `ℙ`-null sets. -/ aemeasurable_multiplier : AEMeasurable multiplier ℙ /-- The stationarity mean square is at most `ε ^ 2`. -/ stationarityMeanSquare_le : stationarityMeanSquare ℙ f c x multiplier ≤ ε ^ 2 /-- The feasibility mean square is at most `ε ^ 2`. -/ feasibilityMeanSquare_le : feasibilityMeanSquare ℙ c x ≤ ε ^ 2

Lemma 3.3

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Lemma 3.3: On an almost-surely admissible length-K prefix whose squared steps are integrable, the independent-batch stochastic NR-LALM run satisfies the accumulated expected squared projected SPIDER gradient-error bound.

open MeasureTheory namespace LALM.StochasticRun universe u v w x variable {n m : ℕ} variable {Ξ : Type u} [MeasurableSpace Ξ] {ν : Measure Ξ} [IsProbabilityMeasure ν] variable {Ω : Type v} [MeasurableSpace Ω] {ℙ : Measure Ω} [IsProbabilityMeasure ℙ] variable {f : EuclideanSpace ℝ (Fin n) → ℝ} variable {c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)} variable {x₀ : EuclideanSpace ℝ (Fin n)} variable {multiplier₀ : EuclideanSpace ℝ (Fin m)} variable {h : EqualityConstrained.Regularity f c} variable {oracle : EqualityConstrained.StochasticOracle f h.region ν} variable {Param : Type*} [PositivePenaltyParameters Param] variable {params : Param} {Q B b : ℕ+} theorem accumulatedGradientErrorMeanSquare_le (run : StochasticRun h oracle ℙ x₀ multiplier₀ params Q B b) (K : ℕ) (h_admissible : run.IsAEAdmissiblePrefix K) (h_step_integrable : run.HasIntegrableStepSquares K) : ∑ k ∈ Finset.range K, run.gradientErrorMeanSquare k ≤ K * oracle.noiseLevel ^ 2 / B + (Q * oracle.meanSquareLipschitz ^ 2 / b) * ∑ k ∈ Finset.range K, run.stepMeanSquare k

Lemma 3.4

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Lemma 3.4 (1): on an admissible stochastic prefix, one step decreases the augmented Lagrangian up to the current projected-gradient error.

open MeasureTheory open scoped InnerProductSpace LALM NNReal namespace LALM.StochasticRun universe u v variable {n m : ℕ} variable {Ξ : Type u} [MeasurableSpace Ξ] {ν : Measure Ξ} [IsProbabilityMeasure ν] variable {Ω : Type v} [MeasurableSpace Ω] {ℙ : Measure Ω} [IsProbabilityMeasure ℙ] variable {f : EuclideanSpace ℝ (Fin n) → ℝ} variable {c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)} variable {x₀ : EuclideanSpace ℝ (Fin n)} variable {multiplier₀ : EuclideanSpace ℝ (Fin m)} variable {h : EqualityConstrained.Regularity f c} variable {oracle : EqualityConstrained.StochasticOracle f h.region ν} variable {params : LALM.Parameters h x₀ multiplier₀} {Q B b : ℕ+} variable (run : StochasticRun h oracle ℙ x₀ multiplier₀ params Q B b) theorem augmentedLagrangianDescent {N k : ℕ} (h_admissible : run.IsAdmissiblePrefix N) (hk : k < N) (ω : Ω) : ℒ[f, c; params.rho](run.point (k + 1) ω, run.multiplier k ω) ≤ ℒ[f, c; params.rho](run.point k ω, run.multiplier k ω) - (params.beta / 2) * ‖run.step k ω‖ ^ 2 + (2 / params.beta) * ‖run.gradientError k ω‖ ^ 2

Lemma 3.5

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Lemma 3.5: on an almost-surely admissible stochastic prefix, the squared KKT residual at iteration k + 1 obeys the stated pathwise bound almost surely.

open MeasureTheory open scoped InnerProductSpace NNReal namespace LALM.StochasticRun universe u v variable {n m : ℕ} variable {Ξ : Type u} [MeasurableSpace Ξ] {ν : Measure Ξ} [IsProbabilityMeasure ν] variable {Ω : Type v} [MeasurableSpace Ω] {ℙ : Measure Ω} [IsProbabilityMeasure ℙ] variable {f : EuclideanSpace ℝ (Fin n) → ℝ} variable {c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)} variable {x₀ : EuclideanSpace ℝ (Fin n)} variable {multiplier₀ : EuclideanSpace ℝ (Fin m)} variable {h : EqualityConstrained.Regularity f c} variable {oracle : EqualityConstrained.StochasticOracle f h.region ν} variable {params : Parameters h x₀ multiplier₀} {Q B b : ℕ+} theorem residual_sq_le (run : StochasticRun h oracle ℙ x₀ multiplier₀ params Q B b) {N k : ℕ} (h_admissible : run.IsAEAdmissiblePrefix N) (hk_pos : 1 ≤ k) (hk : k < N) : ∀ᵐ ω ∂ℙ, KKT.residual f c (run.point (k + 1) ω) (run.multiplier (k + 1) ω) ^ 2 ≤ stochasticResidualConstant h params.delta params.beta params.rho params.multiplierBound * (‖run.step k ω‖ ^ 2 + ‖run.step (k - 1) ω‖ ^ 2 + ‖run.gradientError k ω‖ ^ 2 + ‖run.gradientError (k - 1) ω‖ ^ 2)

Theorem 3.6

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Theorem 3.6 (1): with the prescribed SPIDER schedule and an almost-surely admissible length-K stochastic NR-LALM prefix, the independent uniform output has expected squared KKT residual at most C_st / (K - 1).

open MeasureTheory open scoped ENNReal NNReal namespace LALM.StochasticRun universe u v variable {n m : ℕ} variable {Ξ : Type u} [MeasurableSpace Ξ] {ν : Measure Ξ} [IsProbabilityMeasure ν] variable {Ω : Type v} [MeasurableSpace Ω] {ℙ : Measure Ω} [IsProbabilityMeasure ℙ] variable {f : EuclideanSpace ℝ (Fin n) → ℝ} variable {c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)} variable {x₀ : EuclideanSpace ℝ (Fin n)} variable {multiplier₀ : EuclideanSpace ℝ (Fin m)} variable {h : EqualityConstrained.Regularity f c} variable {oracle : EqualityConstrained.StochasticOracle f h.region ν} variable {params : LALM.Parameters h x₀ multiplier₀} variable {Q B b : ℕ+} namespace UniformOutput theorem residualMeanSquare_le (K : ℕ) (hK : 2 ≤ K) (run : SPIDER.ScheduledRun h oracle ℙ x₀ multiplier₀ params K) (h_admissible : run.IsAEAdmissiblePrefix K) : residualMeanSquare run K hK ≤ ENNReal.ofReal (complexityConstant h oracle params / ((K : ℝ) - 1))

Theorem 3.7

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Theorem 3.7 (1): under the prescribed SPIDER schedule and localization conditions, including the source's explicit hypothesis x₀ ∈ X, the probability of leaving X by iteration K is at most confidence.

open MeasureTheory open scoped ENNReal InnerProductSpace LALM NNReal namespace LALM.StochasticRun universe u v w x variable {n m : ℕ} variable {Ξ : Type u} [MeasurableSpace Ξ] {ν : Measure Ξ} [IsProbabilityMeasure ν] variable {Ω : Type v} [MeasurableSpace Ω] {ℙ : Measure Ω} [IsProbabilityMeasure ℙ] variable {f : EuclideanSpace ℝ (Fin n) → ℝ} variable {c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)} variable {x₀ : EuclideanSpace ℝ (Fin n)} variable {multiplier₀ : EuclideanSpace ℝ (Fin m)} variable {h : EqualityConstrained.Regularity f c} variable {oracle : EqualityConstrained.StochasticOracle f h.region ν} variable {params : LALM.Parameters h x₀ multiplier₀} variable {Q B b : ℕ+} variable {confidence : ℝ} -- Route correction: the unrestricted Lemmas 3.4 and 3.5 require admissibility -- on every sample path. Localization supplies the required bounds only on the -- chosen surviving path, so the deterministic core is exposed with explicit -- segment, step, and multiplier hypotheses below. namespace Localization theorem exitProbability_le (K : ℕ) (hK : 2 ≤ K) (confidence : ℝ) (confidence_pos : 0 < confidence) (X : Set (EuclideanSpace ℝ (Fin n))) (hX : MeasurableSet X) (initial_mem : x₀ ∈ X) (run : SPIDER.ScheduledRun h oracle ℙ x₀ multiplier₀ params K) (h_region : RegionCondition h oracle params confidence X) : ℙ {ω | exitTime run X ω ≤ K} ≤ ENNReal.ofReal confidence

Corollary 3.8

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Corollary 3.8 (1): independent safeguarded restarts terminate almost surely.

open MeasureTheory open LALM.StochasticRun.UniformOutput open scoped BigOperators ENNReal NNReal namespace LALM.SafeguardedRestart open StochasticRun.Localization universe u v variable {n m : ℕ} variable {Ξ : Type u} [MeasurableSpace Ξ] {ν : Measure Ξ} [IsProbabilityMeasure ν] variable {Ω : Type v} [MeasurableSpace Ω] {ℙ : Measure Ω} [IsProbabilityMeasure ℙ] variable {f : EuclideanSpace ℝ (Fin n) → ℝ} variable {c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)} variable {x₀ : EuclideanSpace ℝ (Fin n)} variable {multiplier₀ : EuclideanSpace ℝ (Fin m)} variable {h : EqualityConstrained.Regularity f c} variable {oracle : EqualityConstrained.StochasticOracle f h.region ν} variable {params : LALM.Parameters h x₀ multiplier₀} theorem terminatesAE (K : ℕ) (hK : 2 ≤ K) (confidence : ℝ) (confidence_pos : 0 < confidence) (confidence_lt_one : confidence < 1) (X : Set (EuclideanSpace ℝ (Fin n))) (hX : MeasurableSet X) (initial_mem : x₀ ∈ X) (restart : SafeguardedRestart h oracle ℙ x₀ multiplier₀ params K hK X) (h_region : RegionCondition h oracle params confidence X) : ∀ᵐ ω ∂ℙ, restart.firstAccepted ω ≠ ⊤

Section 4 — Second-order correction

Proposition 4.1

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 4.1: the source problem f(x) = sin x, c(x) = 2x - cos x with its unique feasible initialization realizes strict containment at Δ = 1 / 20, Λ = 4, β = 50, and ρ = 2200.

open scoped NNReal namespace LALM variable {n m : ℕ} variable {f : EuclideanSpace ℝ (Fin n) → ℝ} variable {c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)} namespace Correction theorem sourceStrictParameterRegion : SourceWitness.regularity.region = Set.univ ∧ (∃! x : EuclideanSpace ℝ (Fin 1), SourceWitness.constraint x = 0) ∧ SourceWitness.constraint SourceWitness.initialPoint = 0 ∧ ‖SourceWitness.initialMultiplier‖ = 4 ∧ (SourceWitness.sourceDelta : ℝ) = 1 / 20 ∧ (SourceWitness.sourceBeta : ℝ) = 50 ∧ (SourceWitness.sourceRho : ℝ) = 2200 ∧ (SourceWitness.sourceMultiplierBound : ℝ) = 4 ∧ LALM.initializedParameterRegion SourceWitness.regularity SourceWitness.sourceBeta SourceWitness.sourceRho SourceWitness.initialPoint SourceWitness.initialMultiplier = ∅ ∧ (SourceWitness.sourceDelta, SourceWitness.sourceMultiplierBound) ∈ initializedParameterRegion SourceWitness.regularity SourceWitness.sourceBeta SourceWitness.sourceRho SourceWitness.initialPoint SourceWitness.initialMultiplier

Corollary 4.2

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Corollary 4.2 (4): the corrected deterministic budget attains an ε-KKT pair.

open Filter MeasureTheory Topology open scoped BigOperators ENNReal InnerProductSpace LALM NNReal namespace LALM.Correction open LALM.StochasticRun.UniformOutput universe u v variable {n m : ℕ} variable {f : EuclideanSpace ℝ (Fin n) → ℝ} variable {c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)} variable {x₀ : EuclideanSpace ℝ (Fin n)} variable {multiplier₀ : EuclideanSpace ℝ (Fin m)} namespace Run theorem existsApproximatePair (h : EqualityConstrained.Regularity f c) (params : Parameters h x₀ multiplier₀) (h_region : DeterministicRegionCondition h params) (run : Run f c params.rho params.beta x₀ multiplier₀) (ε : ℝ≥0) (ε_pos : 0 < ε) : ∃ k ∈ Finset.Icc 1 (deterministicIterationBudget h params run ε - 1), KKT.IsApproximatePair f c ε (run.point (k + 1)) (run.multiplier (k + 1))

Appendix C — Remarks

Remark C.1

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

legacy appendix remark C.1 (2): in the explicit scalar example, applying the correction strictly increases true constraint infeasibility from the feasible trial point.

open scoped NNReal
namespace LALM.Correction
namespace ScalarExample
theorem mayIncreaseTrueInfeasibility :
    ‖constraint (trialPoint basePoint baseStep)‖ <
      ‖constraint (nextPoint constraint basePoint baseStep)‖

Remark C.2

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Under the full hypotheses of legacy appendix remark C.2, the first-order base-step estimate supplies the convergence assumption for the quadratic correction estimate.

open Filter
open scoped ContDiff InnerProductSpace NNReal
namespace LALM.Correction
variable {n m : ℕ}
variable {f : EuclideanSpace ℝ (Fin n) → ℝ}
variable {c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)}
variable {rho beta : NNRealˣ}
variable {xStar : EuclideanSpace ℝ (Fin n)}
variable {multiplierStar : EuclideanSpace ℝ (Fin m)}
variable {p : EuclideanSpace ℝ (Fin n) × EuclideanSpace ℝ (Fin m) →
  EuclideanSpace ℝ (Fin n)}
variable (hf : ContDiff ℝ 2 f) (hc : ContDiff ℝ 2 c)
variable (h_kkt : KKT.IsPair f c xStar multiplierStar)
variable (h_licq : ∀ᶠ x in nhds xStar,
  Function.Injective (EqualityConstrained.constraintGradient c x))
variable (h_minimizes : ∀ᶠ y in nhds (xStar, multiplierStar),
  IsMinOn (LALM.stepModel f c rho beta y.1 y.2) Set.univ (p y))
theorem step_isBigO_sq_of_minimizes :
    (fun y ↦ step c y.1 (p y)) =O[nhds (xStar, multiplierStar)]
      (fun y ↦ ‖p y‖ ^ 2)