Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.3 — Predictive Marker is 2min⁡(1+2Sℓ(ϵ),2Hk)2\min(1 + 2S_\ell(\epsilon), 2H_k)2min(1+2Sℓ​(ϵ),2Hk​)-competitive

Proved
CachingML.PredMarker.predictiveMarker_competitive

by mikedeng1 · Sep 28, 2026 · Mathlib 0df444a (Lean v4.33.1)

cachingcompetitive-analysislearning-augmented-algorithmsonline-algorithmsp2o-batch-p200bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider caching with cache size k≥1k \ge 1k≥1 and next-arrival predictions. Let ℓ≥0\ell \ge 0ℓ≥0 be a loss function whose spread is bounded by a concave function: SSS is concave on [0,∞)[0, \infty)[0,∞), continuous at 000 from the right, and for every m≥0m \ge 0m≥0 the spread Sℓ(m)S_\ell(m)Sℓ​(m) is finite with Sℓ(m)≤S(m)S_\ell(m) \le S(m)Sℓ​(m)≤S(m). Let ϵ≥0\epsilon \ge 0ϵ≥0. Then for every admissible tie-breaking rule of Predictive Marker, every request sequence σ\sigmaσ and every prediction sequence hhh whose error satisfies ηℓ(h,σ)≤ϵ⋅Opt(σ)\eta_\ell(h, \sigma) \le \epsilon \cdot \mathrm{Opt}(\sigma)ηℓ​(h,σ)≤ϵ⋅Opt(σ),

E[costPM(σ)]≤2⋅min⁡(1+2S(ϵ), 2Hk)⋅Opt(σ),\mathbb E\bigl[\mathrm{cost}_{PM}(\sigma)\bigr] \le 2 \cdot \min\bigl(1 + 2S(\epsilon),\ 2H_k\bigr) \cdot \mathrm{Opt}(\sigma),E[costPM​(σ)]≤2⋅min(1+2S(ϵ), 2Hk​)⋅Opt(σ),

where costPM(σ)\mathrm{cost}_{PM}(\sigma)costPM​(σ) is the number of misses of Predictive Marker, the expectation is over its random evictions, Opt(σ)\mathrm{Opt}(\sigma)Opt(σ) is the offline optimum from the empty cache, and Hk=1+12+⋯+1kH_k = 1 + \tfrac12 + \dots + \tfrac1kHk​=1+21​+⋯+k1​. In the paper's notation, crPM,ℓ(ϵ)≤2⋅min⁡(1+2Sℓ(ϵ),2Hk)\mathrm{cr}_{PM,\ell}(\epsilon) \le 2 \cdot \min(1 + 2S_\ell(\epsilon), 2H_k)crPM,ℓ​(ϵ)≤2⋅min(1+2Sℓ​(ϵ),2Hk​).

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 4Hk4H_k4Hk​, within a constant factor of the best possible for randomized caching.

Formalization Note The paper's competitive ratio is a maximum over sequences σ\sigmaσ and ϵ\epsilonϵ-accurate predictors hhh; the hypothesis here is the pointwise condition ηℓ(h,σ)≤ϵ Opt(σ)\eta_\ell(h,\sigma) \le \epsilon\,\mathrm{Opt}(\sigma)ηℓ​(h,σ)≤ϵOpt(σ) on the given pair, which every ϵ\epsilonϵ-accurate predictor satisfies on every σ\sigmaσ, and which is what the proof uses. The ratio is written as a product, so Opt(σ)=0\mathrm{Opt}(\sigma) = 0Opt(σ)=0 (the empty sequence) needs no special case. Predictions are arbitrary reals, one per request (the features of the paper's predictor h:X→Yh : X \to Yh:X→Y 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 SSS is applied at real arguments and is assumed continuous at 000, which the paper does not state; without it Lemma 3.3 fails for losses whose minimal reversed-order loss stays 000 for several lengths (see Lemma 3.3), and the paper's argument does not cover the case ϵ=0\epsilon = 0ϵ=0 for such losses. A concave function on [0,∞)[0,\infty)[0,∞) that is at least 111 is nondecreasing, so no monotonicity is assumed. The expected cost is a sum over the final-state distribution in [0,∞][0,\infty][0,∞], compared with the real bound through ENNReal.ofReal.

Preamble
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
Formal statement
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
Source
Lykouris, Vassilvitskii, Competitive Caching with Machine Learned Advice, arXiv:1802.05399v4, p. 14, Theorem 3.3 (proof p. 16); competitive ratio p. 5, §2.1; Definitions 2–3, pp. 7–8
Human review
  • Endorsed by Shuze Chen · Oct 1, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 1, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me