TR-LALM Theory
Section 2 — Deterministic method and convergence
Algorithm 2.1
Lean contributors (project-level attribution): Zichen Wang.
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‖ ^ 2Algorithm 2.1
Lean contributors (project-level attribution): Zichen Wang.
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.
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.
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 multiplierDefinition 2.2
Lean contributors (project-level attribution): Zichen Wang.
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.
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 xDefinition 2.2
Lean contributors (project-level attribution): Zichen Wang.
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 multiplierDefinition 2.2
Lean contributors (project-level attribution): Zichen Wang.
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.
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.
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.
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.regionAssumption 2.5
Lean contributors (project-level attribution): Zichen Wang.
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.
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.
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 ^ 2Lemma 2.6
Lean contributors (project-level attribution): Zichen Wang.
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.deltaLemma 2.7
Lean contributors (project-level attribution): Zichen Wang.
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‖ ^ 2Lemma 2.8
Lean contributors (project-level attribution): Zichen Wang.
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.
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‖ ^ 2Theorem 2.10
Lean contributors (project-level attribution): Zichen Wang.
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.
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.
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.
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.
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‖ ^ 2Definition 3.2
Lean contributors (project-level attribution): Zichen Wang.
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 multiplierDefinition 3.2
Lean contributors (project-level attribution): Zichen Wang.
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 ≤ ε ^ 2Lemma 3.3
Lean contributors (project-level attribution): Zichen Wang.
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 kLemma 3.4
Lean contributors (project-level attribution): Zichen Wang.
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 ω‖ ^ 2Lemma 3.5
Lean contributors (project-level attribution): Zichen Wang.
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.
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.
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 confidenceCorollary 3.8
Lean contributors (project-level attribution): Zichen Wang.
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.
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.initialMultiplierCorollary 4.2
Lean contributors (project-level attribution): Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Zichen Wang.
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)