Theorem 11 — projected stochastic gradient descent with biased gradients on an interval
ProvedAdaptiveBaseStock.Regret.biased_projected_sgdLet with , and let be convex on with derivative (one-sided at the endpoints) and a minimizer . On a filtered probability space , let and
where , , , is -measurable, the estimate is -measurable with , and . Let be the bias of the estimate. Then for all ,
This is the online convex optimization bound that the base-stock levels 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 and writes the bias as ; here is an interval (the paper's only use is ) and the bias is the conditional expectation given the history , which is how the paper applies it when the estimate depends on the past inventory. The second-moment bound is required unconditionally. Lean index is the paper's .
import Mathlib
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.