Training a machine-learning model often means choosing a vector of parameters to minimize an average loss. Evaluating the full gradient can require processing an entire dataset. A stochastic-gradient method instead updates the parameters using a random direction obtained from a smaller amount of information. Its computational appeal raises a mathematical question: which assumptions on those directions and the stepsizes guarantee progress, and what kind of convergence follows?
This mission formalizes the core convergence theory in Section 4 of Bottou, Curtis, and Nocedal, Optimization Methods for Large-Scale Machine Learning. The results distinguish strongly convex objectives, where expected objective error can be controlled, from general smooth objectives, where the guarantee concerns gradients. They also distinguish constant stepsizes, which leave a noise-dependent error bound, from diminishing stepsizes.
The mathematics targeted here is already proved in the literature; the task is its Lean formalization, not a claim that these convergence results are unresolved research conjectures.
Let be differentiable with an -Lipschitz gradient, where . On a probability space , let contain the history before step . Starting from a deterministic vector , the algorithm uses positive deterministic stepsizes and random directions to update
The state is measurable with respect to ; the direction is measurable with respect to and has a finite second moment. Conditional assertions hold almost surely. This uses the adapted-process formulation expressly permitted in footnote 4, PDF p. 22, rather than requiring independent sample seeds. The local index corresponds to the paper's . Algorithm 4.1 and footnote 4.
Write for conditioning on . The moment conditions use constants and :
Define . The iterates lie almost surely in an open region on which for a real lower bound . These are Assumptions 4.1 and 4.3, PDF pp. 23–24, equations (4.6)–(4.9). Source.
The goal is Theorem 4.10, Section 4.3, PDF p. 33, equations (4.30a)–(4.30b). Suppose
For , establish both
There is no convexity assumption and no restriction that the initial stepsizes already satisfy a small-step bound. Theorem 4.10.
Four milestones capture the surrounding theory. Lemma 4.4 gives the two successive conditional expected-descent inequalities (4.10a)–(4.10b), PDF pp. 24–25. It is a common input to the convergence results. Theorem 4.6 gives a geometric upper bound for strongly convex objectives with a constant stepsize. Theorem 4.7 gives the corresponding bound for . These are parallel strongly convex targets, not prerequisites for the nonconvex goal. Theorem 4.8 gives finite-horizon sum and average squared-gradient bounds for general objectives with a constant stepsize. Section 4.
For example, if is the strong-convexity constant, , and , Theorem 4.6 states, with and ,
The upper bound tends to ; this does not assert that the actual expected error tends to . Every milestone retains the paper's constants and all displayed conclusions. Equations (4.13)–(4.14), PDF p. 26.
The result explains precisely how noise and stepsize interact. The general-objective goal guarantees that the stepsize-weighted expected squared gradients average to zero even when . The strongly convex milestones quantify objective error and the effect of initialization. These results concern the stated quantities; they do not assert convergence of iterates, global optimality for a nonconvex objective, or almost-sure convergence. Sections 4.2–4.3.
A completed development would provide reusable Lean results for smooth objective functions, conditional moment bounds, stochastic updates, and expected convergence. The proposed statements are open proof obligations. Compilation establishes that the definitions and statements are well formed, not that their convergence claims have already been proved.
Finite conditional expectations must be connected to unconditional integrals without relying on total-function defaults. The infinite-horizon result also requires careful handling of a finite initial segment: square summability gives eventually small steps, not a bound at every step. Strong convexity must justify the objective-gap estimates and the properties of the optimum. Treating a descent recurrence as a hypothesis would omit the analytic content that this mission is intended to formalize.
The model uses real finite-dimensional Euclidean space, Mathlib gradients, filtrations, Bochner conditional expectations, and ordinary real integrals. The probability space is arbitrary; no finite-support or standard-Borel restriction is imposed. Directions have explicit finite second moments, making the finite-expectation convention in the paper visible. Square integrability of iterates and integrability of losses are consequences to establish, not extra model fields.
Strong convexity uses Mathlib's StrongConvexOn, equivalent here to Assumption 4.5's first-order inequality. The optimum is defined as the infimum of the range of , with its finiteness to be derived in the strongly convex branch. That branch requires : the paper's deduction implicitly uses a nontrivial space. The nonconvex statements allow . Zero noise is allowed. Finite-horizon averages require ; the value assigned at does not affect an asymptotic limit.
Contributions to the conditional-descent infrastructure and any of the four milestones are welcome. Variance reduction, Newton-type methods, and the remainder of the survey are outside this initial mission.
namespace BCN
theorem NonconvexDiminishingStep :
∀ (d : ℕ) (P : Objective d) (C : MomentConstants)
(Ω : Type u) [MeasurableSpace Ω] (prob : Measure Ω) [IsProbabilityMeasure prob]
(α : ℕ → ℝ) (R : Run P C prob α),
Tendsto (stepSum α) atTop atTop → Summable (fun k ↦ α k ^ 2) →
(∃ S : ℝ, Tendsto (weightedGradientSum R) atTop (𝓝 S)) ∧
Tendsto (fun K ↦ weightedGradientSum R K / stepSum α K) atTop (𝓝 0) := by sorry
end BCNNo convexity assumption is made. Let the deterministic positive step sizes satisfy
Then the expected weighted partial sums converge to a finite real number, and their step-weighted averages vanish:
Formalization note: direct source theorem, both conclusions (4.30a)–(4.30b). The existence of a finite limit formalizes the finite expectation limit in (4.30a). It is stronger than merely asserting that each finite partial sum is finite. There is no additional uniform upper bound on all step sizes, no monotonicity requirement, and no assertion that every individual gradient tends to zero. The objective lower bound is required on the open trajectory region.
Source: Léon Bottou, Frank E. Curtis, Jorge Nocedal, Optimization Methods for Large-Scale Machine Learning, arXiv:1606.04838v3, https://arxiv.org/abs/1606.04838v3; Section 4, PDF p. 33 and PDF p. 34, Theorem 4.10, equations (4.30a)–(4.30b); PDF p. 28, step-size condition (4.19).
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.
No open leaves. Every sub-goal is proved or awaiting decomposition.