Lykouris and Vassilvitskii (ICML 2018) introduce a model of online caching
with machine-learned advice, where each page request additionally comes with a
prediction of when that page will next be requested. In this model, a natural
goal is to design algorithms that (1) perform well when the advice is accurate
and (2) remain robust in the worst case a la traditional competitive analysis.
Lykouris and Vassilvitskii give such an algorithm by adapting the Marker
algorithm to the learning-augmented setting. In a recent work, Rohatgi (SODA
2020) improves on their result with an approach also inspired by randomized
marking. We continue the study of this problem, but with a somewhat different
approach: We consider combining the BlindOracle algorithm, which just na\"ively
follows the predictions, with an optimal competitive algorithm for online
caching in a black-box manner. The resulting algorithm outperforms all existing
approaches while being significantly simpler. Moreover, we show that combining
BlindOracle with LRU is in fact optimal among deterministic algorithms for this
problem.

采用盲算法和最优竞争算法相结合的混合算法在在线缓存中表现优于所有现有方法，而且结构更简单。此外，我们证明了对于这个问题，将 BlindOracle 与 LRU 相结合实际上是确定性算法中的最优解。

更好和更简单的学习增强在线缓存

Better and Simpler Learning-Augmented Online Caching

In the model of online caching with machine learned advice, introduced by
Lykouris and Vassilvitskii, the goal is to solve the caching problem with an
online algorithm that has access to next-arrival predictions: when each input
element arrives, the algorithm is given a prediction of the next time when the
element will reappear. The traditional model for online caching suffers from an
$\Omega(\log k)$ competitive ratio lower bound (on a cache of size $k$). In
contrast, the augmented model admits algorithms which beat this lower bound
when the predictions have low error, and asymptotically match the lower bound
when the predictions have high error, even if the algorithms are oblivious to
the prediction error. In particular, Lykouris and Vassilvitskii showed that
there is a prediction-augmented caching algorithm with a competitive ratio of
$O(1+\min(\sqrt{\eta/OPT}, \log k))$ when the overall $\ell_1$ prediction error
is bounded by $\eta$, and $OPT$ is the cost of the optimal offline algorithm.
The dependence on $k$ in the competitive ratio is optimal, but the dependence
on $\eta/OPT$ may be far from optimal. In this work, we make progress towards
closing this gap. Our contributions are twofold. First, we provide an improved
algorithm with a competitive ratio of $O(1 + \min((\eta/OPT)/k, 1) \log k)$.
Second, we provide a lower bound of $\Omega(\log \min((\eta/OPT)/(k \log k),
k))$.

该论文研究了基于机器学习建议的在线缓存模型，提出了一种新的算法来解决缓存问题，该算法适用于低误差情况下的预测，具有低的竞争比率；通过改进算法和提供下限，有望进一步提高算法性能。

机器学习建议在线缓存的近最优界限

Near-Optimal Bounds for Online Caching with Machine Learned Advice

In the worst-case analysis of algorithms, the overall performance of an
algorithm is summarized by its worst performance on any input. This approach
has countless success stories, but there are also important computational
problems --- like linear programming, clustering, online caching, and neural
network training --- where the worst-case analysis framework does not provide
any helpful advice on how to solve the problem. This article covers a number of
modeling methods for going beyond worst-case analysis and articulating which
inputs are the most relevant.

该论文介绍了超越最坏情况分析的建模方法，以及对线性规划，聚类，在线缓存和神经网络训练等计算问题提供帮助的输入优化技术。