Tight Results for Online Convex Paging

Online convex paging (Menache and Singh, 2015; Chiplunkar, Henzinger, Kale, and Vötsch, 2023) models a broad class of cost functions for the classical paging problem. In particular, it naturally captures fairness constraints: e.g., that no specific page (or groups of pages) suffers an “unfairly” high number of evictions by considering ℓp norms of eviction vectors for p>1. The case of the ℓ∞ norm has also been of special interest, and is called min-max paging. We give tight upper and lower bounds for the convex paging problem for a broad class of convex functions. Prior to our work, only fractional algorithms were known for this general setting. Moreover, our general result also improves on prior works for special cases of the problem. For example, it implies that the randomized competitive ratio of the min-max paging problem is Θ(logklogn); this improves both the upper bound and the lower bound given in prior work. It also shows that the randomized and deterministic competitive ratios for ℓp-norm paging are Θ(plogk) and Θ(pk) respectively; the randomized results are completely new, as is the deterministic lower bound. All previous algorithms we know for paging with non-linear costs used fractional relaxations. We show a fundamental limitation of this approach — we give integrality gap instances for the natural relaxation used in these works. This shows that a generic relax-and-round framework—solving the relaxation and then rounding it—is insufficient for obtaining tight bounds for this problem. To bypass this bottleneck, we work with the integer versions of the problems directly. Somewhat surprisingly, we show how to take an arbitrary online algorithm for the weighted paging problem (with linear costs), and convert it in a black-box way to an online algorithm for convex paging, losing just an optimal factor in this reduction. This reduction proves especially challenging in the randomized case, where the underlying weighted paging algorithm is randomized, and the analysis needs to proceed via a delicate martingale argument. We believe this approach of lifting arbitrary (weighted linear) online algorithms to convex objectives may be of broader interest.