  We formulate and study non-linear paging - a broad model of online paging
where the size of subsets of pages is determined by a monotone non-linear set
function of the pages. This model captures the well-studied classic weighted
paging and generalized paging problems, and also submodular and supermodular
paging, studied here for the first time, that have a range of applications from
virtual memory to machine learning.
  Unlike classic paging, the cache threshold parameter $k$ does not yield good
competitive ratios for non-linear paging. Instead, we introduce a novel
parameter $\ell$ that generalizes the notion of cache size to the non-linear
setting. We obtain a tight deterministic $\ell$-competitive algorithm for
general non-linear paging and a $o\left(\log^2 (\ell)\right)$-competitive lower
bound for randomized algorithms. Our algorithm is based on a new generic LP for
the problem that captures both submodular and supermodular paging, in contrast
to LPs used for submodular cover settings. We finally focus on the supermodular
paging problem, which is a variant of online set cover and online submodular
cover, where sets are repeatedly requested to be removed from the cover. We
obtain polylogarithmic lower and upper bounds and an offline approximation
algorithm.
