Proof of Theorem 3.3 —
ProvedCachingML.PredMarker.opt_le_cleanCountcachingcompetitive-analysisonline-algorithmsp2o-batch-p200bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be the cache size, a request sequence, the number of clean elements of its Marker phases, and the least number of misses of any eviction schedule starting from the empty cache. Then
The paper uses this inequality, without a separate statement, in the last sentence of the proof of Theorem 3.3, to pass from the accuracy condition to the per-chain average . Together with Claim 1 it pins between and .
Preamble
import Mathlib import Definitions.Def_CachingML_PredMarker_opt import Definitions.Def_CachingML_PredMarker_cleanCount
Formal statement
namespace CachingML.PredMarker
/-- The step `Opt(σ) ≤ Q` of the proof of Theorem 3.3 (Lykouris–Vassilvitskii, arXiv:1802.05399v4,
p. 16, last sentence of the proof): the offline optimum suffers at most as many cache misses as there
are clean elements. -/
theorem opt_le_cleanCount {α : Type*} [DecidableEq α] (k : ℕ) (hk : 1 ≤ k) (σ : List α) :
opt k σ ≤ cleanCount k σ := by sorry
end CachingML.PredMarker
Source
Lykouris, Vassilvitskii, Competitive Caching with Machine Learned Advice, arXiv:1802.05399v4, p. 16, proof of Theorem 3.3, last sentence ("since Opt(σ) ≤ Q")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.