Algorithms for Caching and MTS with reduced number of predictions

This paper studies online algorithms for caching (and more generally MTS) with predictions. The considered prediction is “action prediction”, which tells what (the ideally optimal) algorithm does. The goal here is not only to achieve a good prediction error vs competitive ratio tradeoff, but also to use fewer predictions, through queries to the action prediction.

The results look very general and strong. The main results are about caching with size k. It shows for a large class of functions f, the algorithm uses f(log k) * OPT predictions, achieves consistency 1, robustness O(log k) and smoothness O(f^{-1}(\eta / OPT)), where \eta is the number of wrongly predicted actions. Furthermore, these bounds are also justified by nearly matching lower bounds.

Technically, the caching algorithm first tries to follow the prediction, and if the prediction “looks bad”, it switches to a modified Marking algorithm to preserve the robustness. But to preserve consistency, this modified Marking is run for only O(k) distinct requests and will switch back to follow the prediction again. This algorithm is intuitive, but the analysis is very involved, especially to deal with the randomness of the Marking algorithm and to control the number of predictions used.

For the MTS problem, it does not make much sense to aim for a query complexity bound like f(\cdot) OPT, and the paper turns to put a constraint that the algorithm can only make a query every $a$ steps, where $a$ is some parameter. This also makes the techniques very different from the caching algorithm.

This paper considers online caching and metrical task systems (MTS) in the popular algorithms with predictions framework. Following recent related work due to Im et al. 2022, they consider reducing the number of predictions utilized by the algorithm. This paper differs from that one in two respects:

• This paper considers action predictions as introduced by Antoniadis et al. which are different from the usual notion of "next-arrival-time" predictions as used by Lykouris and Vassilvitskii 2021, Rohatgi 2020, and Im et al. 2022.
• In addition to considering bounded number of predictions as in Im et al. 2022, they also propose studying well-separated queries to the predictions. In this setting there is a lower bound on the number of time steps between queries to the predictions. This is motivated by settings where we may not be able to immediately query the prediction.

The main theoretical results are as follows:

• An algorithm for caching with robustness $O(\log k)$, smoothness $O(f^{-1}(\eta / OPT))$ and using at most $O(log k)OPT$ queries to predictions. $f$ is an increasing function with some restrictions. Examples of the relationship for different $f$'s are described.
• A lower bound of $f(\ln k) OPT$ queries to the predictor for any algorithm that is $f(\eta)$ smooth.
• For MTS, the authors study well-separated queries that arrive once every $a$ steps and give an algorithm with cost $O(a)(OPT + 2\eta)$ and give a nearly tight lower bound.

To complement these, several experiments using datasets that have been utilized in prior work are carried out, comparing the proposed algorithm to the algorithms proposed in several prior works.

This paper considers the problem of Metrical Task Systems (MTS) under the prediction setting. In the classical MTS problem, the algorithm starts from an initial state (or a point in a metrical space), and the adversary releases a cost function at each time step. After seeing the cost function, the algorithm needs to make a decision at each time: either stay in the same state or move to another state, which is possibly cheap, but some extra moving costs will be charged. In the prediction setting, the algorithm accesses a prediction on future information. In this paper, the prediction is considered the next stage of an optimal algorithm. Unlike other prediction papers, this work investigates how the number of predictions affects the algorithm.

The main contribution of this work is a learning-augmented framework achieves a good trade-off between the smoothness ratio and the number of predictions. For the Caching problem, this framework achieves a nearly optimal tradeoff. The authors also show that such a framework works for the general MTS problem. Besides this, this work also extends the framework for the setting where the prediction can also be obtained by at least a time step. Finally, the authors verify their algorithm in some datasets.

The paper studies the online caching problem and the metrical task system problem which admits online caching as a special case. In the online caching problem, we are given a cache of fixed capacity $k$ and a sequence of online arriving elements, and want to design an online algorithm that decides which elements to keep in the cache and which ones to evict when the cache becomes full. The goal is to minimize the number of cache misses, which occur when an arriving element is not present in the cache. In the metrical task system problem, we are given a metric space $M$ of states and an initial state $x_0\in M$. At each time step $t$, we receive a cost function $\ell_t: M \rightarrow R^+ \cup \set{0, \infty }$ and need to decide which state to move to. When moving to a state $x_t\in M$, we have to pay $\ell_t(x_t) + d(x_{t-1},x_t)$. The goal is to minimize the total payment. To see that online caching is its special case, we can view the elements kept in the cache as the state in a metric space.

The two problems are considered in the learning-augmented setting, where we can access imperfect predictions about the future. More precisely, the authors assume that at any time $t$, if they query a predictor, the predictor returns a prediction $\hat{s}_t$ of the state that the optimal solution (or a good approximation solution) moves to. Since the prediction is imperfect, they define the prediction error $\eta$ to be the moving distance between the predicted state and the real optimal state. The authors show that for online caching, there exists an algorithm that achieves $1$-consistency, $O(\log k)$-robustness, and $O(f^{-1}(\eta /OPT))$-smoothness within a query complexity at most $f(\log k)OPT$, where function $f( \cdot )$ is an increasing convex function with $f(0)=0$ and $f(i)\leq 2^i-1$ $\forall i\geq 0$. For metrical task system, the authors show that there exists an algorithm that achieves a cost at most $O(a) \cdot (OPT+2\eta)$ by making a query each $a$ time step. The smoothness lower bounds are further provided in the paper to show the optimality of their results. Finally, the proposed algorithms are evaluated empirically.

The paper studies the caching and metrical task system problems in the setting where the algorithm is given access to predictions. Similarly to previous work, the paper considers an action prediction model, and the main focus is on reducing the number of predictions used by the algorithm. The problems studied are classical online optimization problems and the specific setting considered in this work is well-motivated. The reviewers appreciated the contributions of this work, and there was clear consensus that this paper makes a strong theoretical contribution to this line of work.

Accept (poster)