  Commonly used caching policies, such as LRU (Least Recently Used) or LFU
(Least Frequently Used), exhibit optimal performance only under specific
traffic patterns. Even advanced machine learning-based methods, which detect
patterns in historical request data, struggle when future requests deviate from
past trends. Recently, a new class of policies has emerged that are robust to
varying traffic patterns. These algorithms address an online optimization
problem, enabling continuous adaptation to the context. They offer theoretical
guarantees on the regret metric, which measures the performance gap between the
online policy and the optimal static cache allocation in hindsight. However,
the high computational complexity of these solutions hinders their practical
adoption.
  In this study, we introduce a new variant of the gradient-based online
caching policy that achieves groundbreaking logarithmic computational
complexity relative to catalog size, while also providing regret guarantees.
This advancement allows us to test the policy on large-scale, real-world traces
featuring millions of requests and items - a significant achievement, as such
scales have been beyond the reach of existing policies with regret guarantees.
To the best of our knowledge, our experimental results demonstrate for the
first time that the regret guarantees of gradient-based caching policies offer
substantial benefits in practical scenarios.
