Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 11 — projected stochastic gradient descent with biased gradients on an interval

Proved
AdaptiveBaseStock.Regret.biased_projected_sgd

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

online-convex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-approximation

Let S=[m,M]\mathcal S = [m, M]S=[m,M] with m≤Mm \le Mm≤M, and let Φ\PhiΦ be convex on S\mathcal SS with derivative Φ′\Phi'Φ′ (one-sided at the endpoints) and a minimizer z∗∈Sz^* \in \mathcal Sz∗∈S. On a filtered probability space (Ft)t≥1(\mathcal F_t)_{t\ge1}(Ft​)t≥1​, let Z1∈SZ_1 \in \mathcal SZ1​∈S and

Zt+1=PS(Zt−ϵtHt),ϵt=ζ diam(S)B‾⋅1tα,Z_{t+1} = P_{\mathcal S}\big(Z_t - \epsilon_t H_t\big), \qquad \epsilon_t = \frac{\zeta\, \mathrm{diam}(\mathcal S)}{\overline B}\cdot \frac1{t^\alpha},Zt+1​=PS​(Zt​−ϵt​Ht​),ϵt​=Bζdiam(S)​⋅tα1​,

where ζ>0\zeta > 0ζ>0, α∈(0,1)\alpha \in (0,1)α∈(0,1), B‾>0\overline B > 0B>0, ZtZ_tZt​ is Ft\mathcal F_tFt​-measurable, the estimate HtH_tHt​ is Ft+1\mathcal F_{t+1}Ft+1​-measurable with E[Ht2]≤B‾2E[H_t^2] \le \overline B^2E[Ht2​]≤B2, and PS(z)=max⁡{m,min⁡{z,M}}P_{\mathcal S}(z) = \max\{m, \min\{z, M\}\}PS​(z)=max{m,min{z,M}}. Let ηt=E[Ht∣Ft]−Φ′(Zt)\eta_t = E[H_t \mid \mathcal F_t] - \Phi'(Z_t)ηt​=E[Ht​∣Ft​]−Φ′(Zt​) be the bias of the estimate. Then for all T≥1T \ge 1T≥1,

∑t=1TE[Φ(Zt)−Φ(z∗)]≤diam(S){B‾[Tα2ζ+ζ T1−α2(1−α)]+∑t=1TE∣ηt∣}.\sum_{t=1}^T E\big[\Phi(Z_t) - \Phi(z^*)\big] \le \mathrm{diam}(\mathcal S)\Big\{\overline B\Big[\frac{T^\alpha}{2\zeta} + \frac{\zeta\, T^{1-\alpha}}{2(1-\alpha)}\Big] + \sum_{t=1}^T E|\eta_t|\Big\}.t=1∑T​E[Φ(Zt​)−Φ(z∗)]≤diam(S){B[2ζTα​+2(1−α)ζT1−α​]+t=1∑T​E∣ηt​∣}.

This is the online convex optimization bound that the base-stock levels SkS_kSk​ of the algorithm obey; the bias terms are where the Markov chain enters.

Formalization Note The paper states the result for a compact set in Rn\mathbb R^nRn and writes the bias as E[Ht(z)∣z]−∇Φ(z)E[H_t(z)\mid z] - \nabla\Phi(z)E[Ht​(z)∣z]−∇Φ(z); here S\mathcal SS is an interval (the paper's only use is [M‾,M‾][\underline M, \overline M][M​,M]) and the bias is the conditional expectation given the history Ft\mathcal F_tFt​, which is how the paper applies it when the estimate depends on the past inventory. The second-moment bound is required unconditionally. Lean index ttt is the paper's t+1t+1t+1.

Preamble
import Mathlib
Formal statement
namespace AdaptiveBaseStock.Regret

open MeasureTheory ProbabilityTheory

/-- Theorem 11, pp. 24–25 (one-dimensional, filtration form): projected stochastic gradient
descent on `𝒮 = [m, M]` with step `ϵ_t = ζ diam(𝒮) / (B̄ t^α)` and gradient estimates of second
moment at most `B̄²` satisfies
`Σ_{t=1}^T E[Φ(Z_t) - Φ(z*)] ≤ diam(𝒮) {B̄ [T^α/(2ζ) + ζ T^{1-α}/(2(1-α))] + Σ_{t=1}^T E|η_t|}`,
where `η_t = E[H_t | 𝓕_t] - Φ'(Z_t)` is the bias of the estimate. Lean index `t` is the paper's
`t + 1`. -/
theorem biased_projected_sgd {Ω : Type*} [mΩ : MeasurableSpace Ω] (P : Measure Ω)
    [IsProbabilityMeasure P] (ℱ : Filtration ℕ mΩ)
    (m M : ℝ) (hmM : m ≤ M) (Φ Φ' : ℝ → ℝ)
    (hconv : ConvexOn ℝ (Set.Icc m M) Φ)
    (hderiv : ∀ z ∈ Set.Icc m M, HasDerivWithinAt Φ (Φ' z) (Set.Icc m M) z)
    (zstar : ℝ) (hzstar : zstar ∈ Set.Icc m M) (hmin : IsMinOn Φ (Set.Icc m M) zstar)
    (Bbar ζ α : ℝ) (hB : 0 < Bbar) (hζ : 0 < ζ) (hα0 : 0 < α) (hα1 : α < 1)
    (Z H : ℕ → Ω → ℝ)
    (hZ0 : ∀ ω, Z 0 ω ∈ Set.Icc m M)
    (hZadapt : ∀ t, StronglyMeasurable[ℱ t] (Z t))
    (hHmeas : ∀ t, StronglyMeasurable[ℱ (t + 1)] (H t))
    (hH2 : ∀ t, MemLp (H t) 2 P)
    (hHbound : ∀ t, ∫ ω, H t ω ^ 2 ∂P ≤ Bbar ^ 2)
    (hrec : ∀ t ω, Z (t + 1) ω =
      max m (min (Z t ω - ζ * (M - m) / (Bbar * ((t : ℝ) + 1) ^ α) * H t ω) M))
    (T : ℕ) (hT : 1 ≤ T) :
    ∑ t ∈ Finset.range T, ∫ ω, (Φ (Z t ω) - Φ zstar) ∂P
      ≤ (M - m) * (Bbar * ((T : ℝ) ^ α / (2 * ζ) + ζ * (T : ℝ) ^ (1 - α) / (2 * (1 - α)))
          + ∑ t ∈ Finset.range T, ∫ ω, |P[H t | ℱ t] ω - Φ' (Z t ω)| ∂P) := by sorry

end AdaptiveBaseStock.Regret
Source
Huh, Janakiraman, Muckstadt, Rusmevichientong, An Adaptive Algorithm for Finding the Optimal Base-Stock Policy in Lost Sales Inventory Systems with Censored Demand, working paper, February 8, 2007 (published version: Math. Oper. Res., 2009, DOI 10.1287/moor.1080.0367), Theorem 11, pp. 24–25 (citing Huh and Rusmevichientong 2006a)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me