Stochastic gradient model, moment assumptions, and numerical quantities
DefinitionBCN_SG_ModelThis definition bundle specifies the objective, stochastic process, moment assumptions, and numerical quantities. Its definitions establish none of the five target estimates.
Notation and probability model
Let and have an actual gradient at every point, with for all , where . On a probability space , let be an increasing family of sub--algebras of . The initial vector is deterministic. The iterate is strongly -measurable, and the sampled direction is strongly -measurable with . For deterministic real step sizes , the algorithm is
An open set contains every iterate almost surely, and a real number satisfies for all . Put . Fix real constants , , , and . The source's first- and second-moment assumptions are, almost surely for every ,
Write ,
,
, and
; empty sums are zero.
Define using the actual objective's range
(Lean's real-valued sInf), and
when stating the strongly convex targets.
Those targets require , positive strong-convexity modulus, and
. The other targets permit and use the trajectory-region
lower bound , without assuming a global minimizer.
Formalization note: these are source assumptions with explicit filtration, measurability, and finite-second-moment conventions for genuine Bochner and conditional expectations. The deterministic initialization and square-integrable directions imply finite iterate second moments; objective and gradient moments must be justified from smoothness in the proofs. The model assumes no expected descent inequality, no gradient-gap inequality, and no convergence conclusion. Local index is paper index throughout. Full-history conditioning follows Algorithm 4.1, PDF p. 22, footnote 4; the model assumptions are Assumptions 4.1 and 4.3, PDF p. 23 and PDF p. 24, equations (4.6)–(4.9), in Section 4 of Bottou–Curtis–Nocedal, Optimization Methods for Large-Scale Machine Learning: https://arxiv.org/abs/1606.04838v3.
import Mathlib.Analysis.Calculus.Gradient.Basic
import Mathlib.Analysis.Convex.Strong
import Mathlib.Analysis.InnerProductSpace.PiL2
import Mathlib.Analysis.Normed.Lp.MeasurableSpace
import Mathlib.MeasureTheory.Function.L2Space
import Mathlib.Probability.ConditionalExpectation
import Mathlib.Probability.Process.Filtration
/-!
Bottou, Curtis, Nocedal, arXiv:1606.04838v3, Section 4, PDF pp. 21–34.
Algorithm 4.1 and its conditional-process convention: PDF p. 22, footnote 4.
Assumptions 4.1/4.3: PDF pp. 23–24, equations (4.6)–(4.9).
The local index 0 is the paper's index 1. Finite second moments are explicit.
The model contains no descent inequality or convergence conclusion.
-/
noncomputable section
open MeasureTheory ProbabilityTheory Filter
open scoped BigOperators Topology InnerProductSpace
namespace BCN
abbrev Space (d : ℕ) := EuclideanSpace ℝ (Fin d)
structure Objective (d : ℕ) where
F : Space d → ℝ
L : ℝ
L_pos : 0 < L
hasGradient : ∀ x, HasGradientAt F (gradient F x) x
smooth : ∀ x y, ‖gradient F x - gradient F y‖ ≤ L * ‖x - y‖
structure MomentConstants where
μ : ℝ
μG : ℝ
M : ℝ
MV : ℝ
μ_pos : 0 < μ
μ_le_μG : μ ≤ μG
M_nonneg : 0 ≤ M
MV_nonneg : 0 ≤ MV
def MomentConstants.MG (C : MomentConstants) : ℝ := C.MV + C.μG ^ 2
variable {d : ℕ} {Ω : Type*} [mΩ : MeasurableSpace Ω]
structure Run (P : Objective d) (C : MomentConstants)
(prob : Measure Ω) [IsProbabilityMeasure prob] (α : ℕ → ℝ) where
history : Filtration ℕ mΩ
w : ℕ → Ω → Space d
g : ℕ → Ω → Space d
w0 : Space d
initial : ∀ ω, w 0 ω = w0
w_adapted : ∀ k, StronglyMeasurable[history k] (w k)
g_adapted : ∀ k, StronglyMeasurable[history (k + 1)] (g k)
g_squareIntegrable : ∀ k, MemLp (g k) 2 prob
step_pos : ∀ k, 0 < α k
update : ∀ k, w (k + 1) =ᵐ[prob] fun ω ↦ w k ω - α k • g k ω
region : Set (Space d)
region_open : IsOpen region
in_region : ∀ k, ∀ᵐ ω ∂prob, w k ω ∈ region
lower : ℝ
lower_bound : ∀ x ∈ region, lower ≤ P.F x
angle : ∀ k, ∀ᵐ ω ∂prob,
C.μ * ‖gradient P.F (w k ω)‖ ^ 2 ≤
⟪gradient P.F (w k ω), prob[g k | history k] ω⟫_ℝ
mean_norm : ∀ k, ∀ᵐ ω ∂prob,
‖prob[g k | history k] ω‖ ≤ C.μG * ‖gradient P.F (w k ω)‖
variance : ∀ k, ∀ᵐ ω ∂prob,
prob[(fun ω ↦ ‖g k ω‖ ^ 2) | history k] ω - ‖prob[g k | history k] ω‖ ^ 2 ≤
C.M + C.MV * ‖gradient P.F (w k ω)‖ ^ 2
variable {P : Objective d} {C : MomentConstants} {prob : Measure Ω}
[IsProbabilityMeasure prob] {α : ℕ → ℝ}
def loss (R : Run P C prob α) (k : ℕ) (ω : Ω) : ℝ := P.F (R.w k ω)
def gradSq (R : Run P C prob α) (k : ℕ) (ω : Ω) : ℝ :=
‖gradient P.F (R.w k ω)‖ ^ 2
def expectedGradSq (R : Run P C prob α) (k : ℕ) : ℝ :=
∫ ω, gradSq R k ω ∂prob
def optimalValue (P : Objective d) : ℝ := sInf (Set.range P.F)
def expectedGap (R : Run P C prob α) (k : ℕ) : ℝ :=
∫ ω, P.F (R.w k ω) - optimalValue P ∂prob
def stepSum (α : ℕ → ℝ) (K : ℕ) : ℝ := ∑ k ∈ Finset.range K, α k
def weightedGradientSum (R : Run P C prob α) (K : ℕ) : ℝ :=
∫ ω, ∑ k ∈ Finset.range K, α k * gradSq R k ω ∂prob
def gradientSum (R : Run P C prob α) (K : ℕ) : ℝ :=
∫ ω, ∑ k ∈ Finset.range K, gradSq R k ω ∂prob
def fixedGapBound (P : Objective d) (C : MomentConstants)
(w0 : Space d) (a c : ℝ) (k : ℕ) : ℝ :=
a * P.L * C.M / (2 * c * C.μ) + (1 - a * c * C.μ) ^ k *
(P.F w0 - optimalValue P - a * P.L * C.M / (2 * c * C.μ))
def diminishingGapConstant (P : Objective d) (C : MomentConstants)
(w0 : Space d) (c β γ : ℝ) : ℝ :=
max (β ^ 2 * P.L * C.M / (2 * (β * c * C.μ - 1)))
((γ + 1) * (P.F w0 - optimalValue P))
end BCN
Read-back
What the Lean code literally says, in plain math · gpt-6
This bundle defines data structures and expressions; it does not assert that a run exists or prove an estimate. For every natural number , its space is the Euclidean space . An objective consists of , a real , the existence of its designated gradient at every , and for all . Moment constants are real with , , and ; the derived constant is . For any such objective and constants, any sample type with a measurable-space structure, any probability measure , and any deterministic real sequence , a run consists of an increasing filtration of sub--algebras of the ambient measurable space, functions , a vector , an open set , and a real . It requires for every and, for every natural , strong -measurability of , strong -measurability of , membership , positivity , the almost-sure update , and almost-sure membership . It requires for every . With , , and , it requires, for every , the almost-sure inequalities , , and . Almost-sure requirements are imposed separately at each index; the initial equality holds everywhere. The loss and squared-gradient functions are and , and the expected squared gradient is . For every objective it defines using the total real infimum; the expected gap is . For natural , the step sum is , the weighted gradient sum is , and the gradient sum is . For every objective, moment constants, vector , real , and natural , the fixed-gap expression is . For every such objective, constants, and vector , and arbitrary real , the diminishing-gap constant is . These last two definitions impose no sign restrictions on their additional real arguments. Indices start at zero, and at all the finite sums and their integrals are zero. The dimension is allowed and gives a one-point vector space; and are allowed, while are positive. The range of is nonempty even when ; if it is unbounded below, its total real infimum is zero. An objective is not required to have a global lower bound or an attained minimum. The run's bound applies only on and need not equal . An empty region cannot contain almost surely on a probability space; an empty sample type admits no probability measure; and a step sequence with a nonpositive entry admits no run. All expectations use the total Bochner integral, which is zero for a nonintegrable integrand; conditional expectations use their total mathematical-library definitions, including zero when the required integrability fails. There are no separate run fields requiring integrability of the loss or squared gradient. Real division has , and natural-number powers have zeroth power one, including .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.