Theorem 1.1(b), p. 294 ā for š, š® ā āāæā, E[cost of FPL*(ε/2A)] ⤠(1 + ε)min-cost_T + 4AD(1 + ln n)/ε
ProvedKalaiVempala.Multiplicative.theorem_1_1_bSetting. Decisions are chosen from a set and states from a set ; the cost of decision in state is . The decision set is accessed only through an offline oracle . The instance is measured by
For a state sequence write and .
The algorithm. FPL*(Ī·) on period draws from the density and plays .
Theorem 1.1(b). Suppose decisions and states are nonnegative, , and . For every , every measurable argmin oracle , and every state sequence ,
This is the multiplicative ("competitive") guarantee of Follow the Perturbed Leader: with exponentially distributed perturbations, the online cost is within a factor of the best fixed decision in hindsight, up to an additive term that does not grow with .
Formalization Note Vectors are Fin n ā ā, is ā¬įµ„, is written as ; the decision set is Dset and the diameter Ddiam. The expected cost is fplStarExpectedCost M s (ε / (2 * A)) T, defined with the normalised law . Four hypotheses are added and disclosed: measurability of (the expectations presuppose it); ; (the parameter presupposes it); and , which Theorem 1.1(b) does not state but its proof uses ("using the fact that gives the theorem", p. 303). The bound of the paper is not used by part (b) and is not a hypothesis. No hypothesis on is needed: is Real.log n, and for the statement is still the paper's with .
import Mathlib import Definitions.Def_OracleRO_ApproxFPL_FPL import Definitions.Def_KalaiVempala_Multiplicative_Setting open MeasureTheory OracleRO.ApproxFPL
namespace KalaiVempala.Multiplicative
theorem theorem_1_1_b {n : ā} (Dset S : Set (Fin n ā ā))
(M : (Fin n ā ā) ā (Fin n ā ā)) (hM : KalaiVempala.Additive.IsArgminOracle Dset M) (hMmeas : Measurable M)
(Ddiam : ā) (hD : ā d ā Dset, ā d' ā Dset, ā i, |d i - d' i| ⤠Ddiam)
(A : ā) (hA : ā x ā S, ā i, |x i| ⤠A)
(s : ā ā Fin n ā ā) (T : ā) (hs : ā t ā Finset.Icc 1 T, s t ā S)
(hDnn : ā d ā Dset, ā i, 0 ⤠d i) (hSnn : ā x ā S, ā i, 0 ⤠x i)
(hA0 : 0 < A) (ε : ā) (hε0 : 0 < ε) (hε1 : ε ⤠1) :
fplStarExpectedCost M s (ε / (2 * A)) T ā¤
(1 + ε) * (M (prefixSum s T) ā¬įµ„ prefixSum s T) + 4 * A * Ddiam * (1 + Real.log n) / ε := by sorry
end KalaiVempala.Multiplicative
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.