Theorem 3.3 — Predictive Marker is -competitive
ProvedCachingML.PredMarker.predictiveMarker_competitiveConsider caching with cache size and next-arrival predictions. Let be a loss function whose spread is bounded by a concave function: is concave on , continuous at from the right, and for every the spread is finite with . Let . Then for every admissible tie-breaking rule of Predictive Marker, every request sequence and every prediction sequence whose error satisfies ,
where is the number of misses of Predictive Marker, the expectation is over its random evictions, is the offline optimum from the empty cache, and . In the paper's notation, .
The bound interpolates between consistency and robustness: with an accurate predictor the ratio is a constant depending only on the error, and with an arbitrarily bad one it is still , within a constant factor of the best possible for randomized caching.
Formalization Note The paper's competitive ratio is a maximum over sequences and -accurate predictors ; the hypothesis here is the pointwise condition on the given pair, which every -accurate predictor satisfies on every , and which is what the proof uses. The ratio is written as a product, so (the empty sequence) needs no special case. Predictions are arbitrary reals, one per request (the features of the paper's predictor are arbitrary). The tie-breaking of the arg max in Algorithm 1 is left open by the paper; the theorem holds for every admissible rule. Algorithm 1 is implemented with its eviction performed after the clean branch as well (a printed slip; see the definition). The spread majorant is applied at real arguments and is assumed continuous at , which the paper does not state; without it Lemma 3.3 fails for losses whose minimal reversed-order loss stays for several lengths (see Lemma 3.3), and the paper's argument does not cover the case for such losses. A concave function on that is at least is nondecreasing, so no monotonicity is assumed. The expected cost is a sum over the final-state distribution in , compared with the real bound through ENNReal.ofReal.
import Mathlib import Definitions.Def_CachingML_PredMarker_predError import Definitions.Def_CachingML_PredMarker_opt import Definitions.Def_CachingML_PredMarker_spread import Definitions.Def_CachingML_PredMarker_predictiveMarker open scoped ENNReal
namespace CachingML.PredMarker
/-- Theorem 3.3 of Lykouris–Vassilvitskii (arXiv:1802.05399v4, p. 14): for cache size `k ≥ 1`, a
nonnegative loss `ℓ` whose spread is bounded by a concave function `S` (continuous at `0`), and any
`ε ≥ 0`, Predictive Marker (with any tie-breaking of its `arg max`) satisfies, on every request sequence
`σ` and prediction sequence `h` with error `η_ℓ(h, σ) ≤ ε · Opt(σ)`,
`E[cost_PM(σ)] ≤ 2 · min(1 + 2 S(ε), 2 H_k) · Opt(σ)`. -/
theorem predictiveMarker_competitive {α : Type*} [DecidableEq α] (k : ℕ) (hk : 1 ≤ k)
(ℓ : ℝ → ℝ → ℝ) (hℓ : ∀ a b, 0 ≤ ℓ a b)
(S : ℝ → ℝ) (hSconc : ConcaveOn ℝ (Set.Ici 0) S)
(hScont : ContinuousWithinAt S (Set.Ici 0) 0)
(hspread : ∀ m : ℝ, 0 ≤ m → ∃ t : ℕ, spread ℓ m = t ∧ (t : ℝ) ≤ S m)
(ε : ℝ) (hε : 0 ≤ ε)
(tb : PMState α → α) (htb : IsMaxTieBreak tb)
(σ : List α) (h : Fin σ.length → ℝ)
(hacc : predError ℓ σ h ≤ ε * (opt k σ : ℝ)) :
expCost k tb σ h ≤
ENNReal.ofReal (2 * min (1 + 2 * S ε) (2 * (harmonic k : ℝ)) * (opt k σ : ℝ)) := by sorry
end CachingML.PredMarker
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.