(28), p. 21 β π(π΄) β€ (Tβ/Ξ³β)(1 + (3/2)(2^{(πβ1)/2} β 1)β»ΒΉ) if π > 1, Tβ(1 + (3/2)R)/Ξ³β if π = 1
ProvedMLLangevin.General.display_28complexitymultilevel-monte-carlop2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , , and , and set and . Then the complexity satisfies
When the cost of all correcting levels together is of the order of the cost of level ; when it grows linearly in .
Formalization Note. The complexity is the formula of p. 6, used for all horizons (the page gives it for horizons that are multiples of the steps). The statement is arithmetic about that formula.
Preamble
import Mathlib import Definitions.Def_MLLangevin_General_Setting
Formal statement
namespace MLLangevin.General
theorem display_28 (π Ξ³β Tβ : β) (R : β) (hπ : 1 β€ π β§ π β€ 2) (hΞ³β : 0 < Ξ³β) (hTβ : 0 < Tβ) :
cost R Ξ³β (geomHorizon Tβ π)
β€ if 1 < π then Tβ / Ξ³β * (1 + 3 / 2 * ((2 : β) ^ ((π - 1) / 2) - 1)β»ΒΉ)
else Tβ * (1 + 3 / 2 * (R : β)) / Ξ³β := by sorry
end MLLangevin.General
Source
EgΓ©aβPanloup, arXiv:2109.07753v2, (28), p. 21, in Proposition 3.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.