Si Tareq

Salem

Giovanni Neglia
email: giovanni.neglia@inria.fr

Damiano Carra
email: damiano.carra@univr.it

Ascent Similarity Caching with Approximate Indexes

Similarity search is a key operation in multimedia retrieval systems and recommender systems, and it will play an important role also for future machine learning and augmented reality applications. When these systems need to serve large objects with tight delay constraints, edge servers close to the enduser can operate as similarity caches to speed up the retrieval. In this paper we present AC ¸AI, a new similarity caching policy which improves on the state of the art by using (i) an (approximate) index for the whole catalog to decide which objects to serve locally and which to retrieve from the remote server, and (ii) a mirror ascent algorithm to update the set of local objects with strong guarantees even when the request process does not exhibit any statistical regularity.

I. INTRODUCTION

Mobile devices can enable rich interaction with the environment people are in. Applications such as object recognition or, in general, augmented reality, require to process and retrieve in real time information related to the content visualized by the camera. The logic behind such applications is very complex: although mobile devices' computational power and memory constantly increase, they may not be sufficient to run these sophisticated logics, especially considering the associated energy consumption. On the other hand, sending the data to the cloud to be processed introduces additional delays that may be undesirable or simply intolerable [START_REF] -H. Chen | Glimpse: Continuous, Real-Time Object Recognition on Mobile Devices[END_REF]. Edge Computing [START_REF] Zhou | Edge Intelligence: Paving the Last Mile of Artificial Intelligence With Edge Computing[END_REF], [START_REF] Venugopal | Shadow Puppets: Cloud-level Accurate AI Inference at the Speed and Economy of Edge[END_REF] solves this dichotomy by providing distributed computational and memory resources close to the users. Mobile devices may pre-process locally the data and send the requests to the closest edge server, which runs the application logic and provides quickly the answers.

Augmented reality applications often require to identify similar objects: for example, an image (or an opportune encoding of it) can be sent as a query, and the application logic finds similar objects to be returned to the user [START_REF] Venugopal | Shadow Puppets: Cloud-level Accurate AI Inference at the Speed and Economy of Edge[END_REF]- [START_REF] Guo | FoggyCache: Cross-Device Approximate Computation Reuse[END_REF]. For instance, a recommendation system may suggest similar products to a user browsing shop windows in a mall, or similar artists to a user enjoying street art. The search for similar objects is based on a k-nearest neighbor (kNN) search in an opportune metric space [START_REF] Bellet | Metric Learning[END_REF]. The flexibility of kNN search comes at the cost of (i) high computational complexity in case of high dimensional spaces, and (ii) large memory required to store the instances. The first issue has been solved in recent years with a set of techniques used to index the collection of objects that provide approximate answers to kNN searches, i.e., they trade accuracy for speed. Searches over large catalogs (billions of entries) in high dimensional spaces may be executed now in less than a millisecond [START_REF] Johnson | Billion-Scale Similarity Search with GPUs[END_REF]. Still, the issue of the memory required to store the objects persists, especially in a distributed edge computing scenario, as edge servers have limited memory resources compared to the cloud.

Due to memory constraints, edge servers can be forced to store a subset of the objects in the catalog, but object selection is not an easy task. Requests coming from the users often exhibit spatial and temporal correlation-e.g., the same augmented reality application will recover different information in different areas, and this information can change over time as the environment changes and users' interests evolve. This observation suggests that we may use the request pattern to drive the object selection. In other words, the edge server can be viewed as a cache that contains the set of objects needed to adequately respond to local requests while avoiding forwarding them to the cloud.

In this paper, we study how to optimize the memory usage of the edge server for similarity searches. To this aim, we consider the costs associated with the replies, which capture both the quality of the reply (that is how similar/dissimilar to the request the objects provided are), as well as system costs like the delay experienced, the load on the server or the network. Our study aims to design an online algorithm to minimize such costs. We provide the following contributions:

• We formulate the problem of kNN optimal caching taking into account both dissimilarity costs and system costs.

• We propose a new similarity caching policy, AC ¸AI (Ascent Similarity Caching with Approximate Indexes), that (i) relies on fast, approximate similarity search indexes to decide which objects to serve from the local datastore and which ones from the remote repository and (ii) uses an online mirror ascent algorithm to update the cached content to minimize the total service cost. AC ¸AI offers strong theoretical guarantees without any assumption on the traffic arrival pattern.

• We compare our solution with state-of-the-art algorithms for similarity caching and show that AC ¸AI consistently improves over all of them under realistic traces.

The remainder of the paper is organized as follows: we present similarity caches in Sec. II and other relevant background in Sec. III. We introduce AC ¸AI in Sec. IV and our experimental results in Sec. V. The notation used across the paper is summarized in Table I. The proofs and other technical details can be found in the Supplementary material. This work is an extension of our previous work [START_REF] Salem | AC ¸AI: Ascent Similarity Caching with Approximate Indexes[END_REF]. In particular, we provide (i)

the regret bound when the state of the system is only updated every M requests, (ii) a new rounding mechanism, and (iii) the complete proofs.

II. SIMILARITY CACHES

Consider a remote server that stores a catalog of objects N {1, 2, . . . , N }. A similarity search request r aims at finding the k objects o 1 , o 2 , . . . , o k ∈ N that are most similar to r given an application-specific definition of similarity. To this purpose, similarity search systems rely on a function c d (r, o) ∈ R ≥0 , which quantifies the dissimilarity of a request r and an object o. We call such a function the dissimilarity cost.

In practice, objects and requests are mapped to vectors in R d (called embeddings), so that the dissimilarity cost can be represented as (a function of) a selected distance between the corresponding embeddings. For instance, in the case of images, the embeddings could be a set of descriptors like SIFT [START_REF] Lowe | Object Recognition from Local Scale-Invariant Features[END_REF], ORB [START_REF] Rublee | ORB: An efficient alternative to SIFT or SURF[END_REF], or the set of activation values at an intermediate layer of a neural network [START_REF] Hinton | Reducing the Dimensionality of Data with Neural Networks[END_REF], [START_REF] Lin | Learning Compact Binary Descriptors With Unsupervised Deep Neural Networks[END_REF]. Examples of commonly employed distances are the p-norm, Mahalanobis, and cosine distances.

The server replies to each request r with the k most similar objects in the catalog N . As the dissimilarity is captured by the distance in the specific metric space, these objects are also the k closest objects (neighbors) in the catalog to the request r (kNN(r, N )). 1 The mapping translates the similarity search problem into a kNN problem [START_REF] Yianilos | Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces[END_REF], [START_REF] Navarro | Searching in Metric Spaces by Spatial Approximation[END_REF].

We can also associate a dissimilarity cost to the reply provided by a server (e.g., by summing the dissimilarity costs for all objects in kNN(r, N )). This cost depends on the catalog N and we do not have control over it. In addition, there is a fetching cost to retrieve those objects. The fetching cost captures, for instance, the extra load experienced by the server or the network to provide the objects to the user, the delay experienced by the user, or a mixture of those costs.

In the Edge Computing scenario we consider, we can reduce the fetching cost by storing at the edge server a subset of the catalog N , i.e., the edge server works as a cache. When answering to a request, the cache could provide just some of the k closest objects (those stored locally) and retrieve the others from the server. The seminal papers [START_REF] Falchi | A Metric Cache for Similarity Search[END_REF], [START_REF] Pandey | Nearest-Neighbor Caching for Content-Match Applications[END_REF] proposed a different use of the cache: the cache may reply to a request using a local subset of objects that are potentially farther than the closest neighbors to reduce the fetching cost while increasing-hopefully only slightly-the dissimilarity cost. They named such cache a similarity cache. The envisaged applications were content-based image retrieval [START_REF] Falchi | A Metric Cache for Similarity Search[END_REF] and contextual advertising [START_REF] Pandey | Nearest-Neighbor Caching for Content-Match Applications[END_REF]. But, as recognized in [START_REF] Neglia | Similarity Caching: Theory and Algorithms[END_REF], the idea has been rediscovered several times under different names for different applications: semantic caches for object recognition [START_REF] Venugopal | Shadow Puppets: Cloud-level Accurate AI Inference at the Speed and Economy of Edge[END_REF]- [START_REF] Guo | FoggyCache: Cross-Device Approximate Computation Reuse[END_REF], soft caches for recommender systems [START_REF] Sermpezis | Soft Cache Hits: Improving Performance Through Recommendation and Delivery of Related Content[END_REF], [START_REF] Costantini | Impact of Popular Content Relational Structure on Joint Caching and Recommendation Policies[END_REF], approximate caches for fast machine learning inference [START_REF] Crankshaw | Clipper: A Low-Latency Online Prediction Serving System[END_REF]. 1 More precisely, these are the k objects whose embeddings are closer to the embedding of r. From now on we identify objects with their embeddings.

A common assumption in the existing literature is that the cache can only store h objects and the index needed to manage them has essentially negligible size. We also maintain this assumption, which is justified in practice when objects have sizes of a few tens of kilobytes (see the quantitative examples in Sec. III). Caching policies. The performance of the cache depends heavily on which objects the cache stores. Among the papers mentioned above, many (e.g., [START_REF] Sermpezis | Soft Cache Hits: Improving Performance Through Recommendation and Delivery of Related Content[END_REF], [START_REF] Costantini | Impact of Popular Content Relational Structure on Joint Caching and Recommendation Policies[END_REF]) consider the offline object placement problem: a set of objects is selected based on historical information about object popularity and prefetched in the cache. But object popularity can be difficult to estimate and can change over time, especially at the level of small geographical areas (as in the case of areas served by an edge server) [START_REF] Paschos | Wireless Caching: Technical Misconceptions and Business Barriers[END_REF]. Other papers [START_REF] Venugopal | Shadow Puppets: Cloud-level Accurate AI Inference at the Speed and Economy of Edge[END_REF]- [START_REF] Guo | FoggyCache: Cross-Device Approximate Computation Reuse[END_REF], [START_REF] Crankshaw | Clipper: A Low-Latency Online Prediction Serving System[END_REF], [START_REF] Guo | Potluck: Cross-Application Approximate Deduplication for Computation-Intensive Mobile Applications[END_REF] present more a high-level view of the different components of the application system, without specific contributions in terms of cache management policies (e.g., they apply minor changes to exact caching policies like LRU or LFU). Some recent papers [START_REF] Neglia | Similarity Caching: Theory and Algorithms[END_REF], [START_REF] Zhou | Adaptive Offline and Online Similarity-Based Caching[END_REF], [START_REF] Sabnis | GRADES: Gradient Descent for Similarity Caching[END_REF] propose online caching policies that try to minimize the total cost of the system (the sum of the dissimilarity cost and the fetching cost), also in a networked context [START_REF] Zhou | Adaptive Offline and Online Similarity-Based Caching[END_REF], [START_REF] Garetto | Content placement in networks of similarity caches[END_REF], but their schemes apply only to the case k = 1, which is of limited practical interest.

To the best of our knowledge, the only dynamic caching policies conceived to manage the retrieval of k > 1 similar objects are SIM-LRU, CLS-LRU, and RND-LRU proposed in [START_REF] Pandey | Nearest-Neighbor Caching for Content-Match Applications[END_REF] and QCACHE proposed in [START_REF] Falchi | Similarity Caching in Large-scale Image Retrieval[END_REF]. Next, we describe in detail these policies to highlight AC ¸AI's differences and novelty.

All these policies maintain an ordered list of key-value pairs where the key is a previous request and the value is the set of k closest objects to the request in the catalog (in general k ≥ k). The cache, whose size is h, maintains a set of h/k past requests. This approach allows to decompose the potentially expensive search for close objects in the cache (see Sec. III) in two separate less expensive searches on smaller sets. Upon the arrival of a request r, the cache identifies the l closest requests to r among the h/k in the cache. Then, it merges their corresponding values and looks for the k closest objects to r in this set including at most l × k objects. As the cache has no knowledge about the catalog at the server, it cannot compare the quality (i.e., the dissimilarity cost) of the local answer with the quality of the answer the server can provide. It relies then on heuristics (detailed below) to decide if the local answer is good enough. If this is the case, then an approximate hit occurs and the answer is provided to the user, otherwise the request r is forwarded to the server that needs to provide all k closest objects.

The cache state is updated following an LRU-like approach: upon an approximate hit, all key-value pairs that contributed to the answer are moved to the front of the list; upon a miss, the new key-value pair provided by the server is stored at the front of the list, and the pair at the end of the list is evicted.

This operation is common to SIM-LRU, CLS-LRU, RND-LRU, and QCACHE. They differ in the choice of the parameters k and l and in the way to decide between an approximate hit and a miss. We emphasize that the parameters k and l are only required by the LRU-like policies and do not play any role in AC ¸AI's workflow.

SIM-LRU considers k ≥ k and l = 1. Upon a request for r, SIM-LRU selects the closest request in the cache and decides for an approximate hit (resp. a miss) if their dissimilarity is smaller (resp. larger) than a given threshold C θ ∈ R ≥0 . Every stored key r covers then a hypersphere in the request space with radius C θ . SIM-LRU has the property that no two keys in the cache have a dissimilarity cost lower than C θ , but the corresponding hyperspheres may still intersect.

CLS-LRU [START_REF] Pandey | Nearest-Neighbor Caching for Content-Match Applications[END_REF] is a variant of SIM-LRU, that can update the stored keys (the centers of the hyperspheres) and push away intersecting hyperspheres to cover the largest possible area of the request space. To this purpose, CLS-LRU maintains the history of requests served at each hypersphere and, upon an approximate hit, moves the center to the object that minimizes the distance to every object within the hypersphere's history. When two hyperspheres overlap, this mechanism drives their centers apart, which in turn reduces the overlapping region.

RND-LRU [START_REF] Pandey | Nearest-Neighbor Caching for Content-Match Applications[END_REF] is a random variant of SIM-LRU that determines the request r to be a miss with a probability that is increasing with the dissimilarity between r and the closest request in the cache.

Finally, QCACHE [START_REF] Falchi | Similarity Caching in Large-scale Image Retrieval[END_REF] considers k = k and l > 1. The policy decides if the k objects selected from the cache are an approximate hit if (i) at least two of them would have been provided also by the server-a sufficient condition can be obtained from geometric considerations-or (ii) the distribution of distances of the k objects from the request looks similar to the distribution of objects around the corresponding request for other stored key-value pairs. These policies share potential inefficiencies: (i) the sets of closest objects to previous queries are not necessarily disjoint (but CLS-LRU tries to reduce their overlap) and then the cache may store less than h distinct objects; (ii) the two-level search may miss some objects in the cache that are close to r, but are indexed by requests that are not among the l closest requests to r; (iii) the policy takes into account the dissimilarity costs at the caches but not at the server; (iv) objects are served in bulk, all from the cache or all from the server, without the flexibility of a per-object choice. As we are going to see, AC ¸AI design prevents such inefficiencies by exploiting new advances in efficient approximate kNN search algorithms, which allows us to abandon the key-value pair indexing and to estimate the dissimilarity costs at the server. Also AC ¸AI departs from the LRU-like cache updates, considering gradient update schemes inspired by online learning algorithms [START_REF] Paschos | Learning to Cache With No Regrets[END_REF].

III. OTHER RELEVANT BACKGROUND

Indexes for approximate kNN search. Indexes are used to efficiently search objects in a large catalog. In the case of kNN, one of the approaches is to use tree-based data structures. Unfortunately, in high dimensional spaces, e.g., R d with d > 10, the computational cost of such a search is comparable to a full scan of the collection [START_REF] Weber | A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces[END_REF]. Approximate Nearest Neighbor search techniques trade accuracy for speed and provide k points close to the query, but not necessarily the closest, sometimes with a guaranteed bounded error. Prominent examples are the solutions based on locality-sensitive hashing [START_REF] Andoni | Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions[END_REF], product quantization [START_REF] Johnson | Billion-Scale Similarity Search with GPUs[END_REF], [START_REF] Babenko | The Inverted Multi-Index[END_REF], and graphs [START_REF] Malkov | Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs[END_REF]. Despite being approximate, these indexes are in practice very accurate, as shown over different benchmarks in [START_REF] Aumüller | ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms[END_REF].

As we are going to describe, AC ¸AI employs two approximate indexes (both stored at the edge server): one for the content stored in the cache, and one for the whole catalog N stored in the remote server. For the former, since cache content varies over time, we rely on a graph-based solution, such as HNSW [START_REF] Malkov | Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs[END_REF], that supports dynamic (re-)indexing with no speed loss. On various benchmarks [START_REF] Aumüller | ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms[END_REF], HNSW is the fastest index, and it is able to answer a 100NN query over a dataset with 1 million objects in a 128-dimensional space in less than 0.5 ms with a recall greater than 97%. As for the memory footprint, a typical configuration of the HNSW index requires O(d) bytes per object, where d is the number of dimensions. For instance, in the case of d = 128 dimensional vectors, the memory required to index 10 million objects is approximately 5 GB. As the server catalog changes less frequently (e.g., contextual advertising applications [START_REF] Pandey | Nearest-Neighbor Caching for Content-Match Applications[END_REF], and image retrieval applications [START_REF] Falchi | Similarity Caching in Large-scale Image Retrieval[END_REF]), AC ¸AI can index it using approaches with a more compact object representation like FAISS [START_REF] Johnson | Billion-Scale Similarity Search with GPUs[END_REF]. FAISS is slightly slower than HNSW and does not support fast reindexing if the catalog changes, but it can manage a much larger set of objects. With a dataset of 1 billion objects, FAISS provides an answer in less than 0.7 ms per query, using a GPU [START_REF] Johnson | Billion-Scale Similarity Search with GPUs[END_REF]. Practically, the global catalog index can be fully reconstructed whenever a given percentage of the catalog changes. This operation can be done in parallel to the normal cache operation. Once the catalog index is modified, the cache can remove the objects that do not appear anymore in the catalog and allocate the corresponding space to other objects. As for the memory footprint, for a typical configuration (IVFPQ), FAISS is able to represent an object with 30 bytes (independently of d): only 3 GB for a dataset with 100 million objects! Summing up our numerical example, if each object has size 20 KB, an edge server with AC ¸AI storing locally 10 million objects from a catalog with 100 million objects, needs 200 GB for the objects and only 8 GB for the two indexes. The larger the objects, the smaller the indexes' footprint: for example, when the server has a few Terabytes of disk space to store large multimedia objects, the indexes' size can be ignored.

Gradient descent approaches. Online caching policies based on gradient methods have been studied in the stochastic request setting for exact caching, with provable performance guarantees, [START_REF] Ioannidis | Distributed Caching over Heterogeneous Mobile Networks[END_REF], [START_REF] Ioannidis | Adaptive Caching Networks with Optimality Guarantees[END_REF]. More recently, the authors of [START_REF] Sabnis | GRADES: Gradient Descent for Similarity Caching[END_REF] have proposed a gradient method to refine the allocation of objects stored by traditional similarity caching policies like SIM-LRU. Similarly, the reference [START_REF] Zhou | Adaptive Offline and Online Similarity-Based Caching[END_REF] considers a heuristic based on the gradient descent/ascent algorithm to allocate objects in a network of similarity caches. In both papers, the system provides a single similar object (k = 1). A closely related recent work [START_REF] Salem | Towards Inference Delivery Networks: Distributing Machine Learning with Optimality Guarantees[END_REF] considers the problem of allocating different inference models that can satisfy users' queries at different quality levels. The authors propose a policy based on mirror descent, and provide guarantees under a general request process, but their policy does not scale to a large catalog size.

We deviate from these works by considering k > 1, large catalog size, and the more general family of online mirror ascent algorithms (of which the usual gradient ascent method is a particular instance). Also our policy provides strong performance guarantees under a general request process, where requests can even be selected by an adversary. Our analysis relies on results from online convex optimization [START_REF] Shalev-Shwartz | Online Learning and Online Convex Optimization[END_REF] and is similar in spirit to what was done for exact caching using the classic gradient method in [START_REF] Paschos | Learning to Cache With No Regrets[END_REF] and mirror descent in [START_REF] Salem | No-Regret Caching via Online Mirror Descent[END_REF]. Two recent papers [START_REF] Salem | No-Regret Caching via Online Mirror Descent[END_REF], [START_REF] Mukhopadhyay | Online Caching with Optimal Switching Regret[END_REF] pursued this line of work taking into account update costs for a single exact cache.

IV. AC ¸AI DESIGN

AC ¸AI design is summarized in Fig. 1.

A. Cost Assumptions

Many of the similarity caching policies proposed in the literature (including SIM-LRU, CLS-LRU, RND-LRU, and QCACHE) have not been designed with a clear quantitative objective, but with the qualitative goal of significantly reducing the fetching cost without increasing too much the dissimilarity cost. Because of such vagueness, the corresponding papers do not make clear assumptions about the dissimilarity costs and the fetching costs. On the contrary, AC ¸AI has been designed to minimize the total cost of the similarity search system and we make explicit the corresponding hypotheses.

Our main assumption is that all costs are additive. 2 The function c d (r, o) introduced in Sec. II quantifies the dissimilarity of the object o and the request r. Let A be the set of objects in the answer to request r. It is natural to consider as dissimilarity cost of the answer o∈A c d (r, o).

In addition, if fetching a single object from the server incurs a cost c f ∈ R >0 , the fetching cost to retrieve m objects is m × c f . This is an obvious choice when c f captures server or network cost. When c f captures the delay experienced by the user, then summing the costs is equivalent to consider the round trip time negligible in comparison to the transmission time, which is justified for large multimedia objects. It is easy to modify AC ¸AI to consider the alternative case when the fetching cost does not depend on how many objects are retrieved. Finally, as common in other works [START_REF] Neglia | Similarity Caching: Theory and Algorithms[END_REF], [START_REF] Sabnis | GRADES: Gradient Descent for Similarity Caching[END_REF], we assume that both the dissimilarity cost and the fetching cost can be directly compared (e.g., they can both be converted into dollars). Under these assumptions, when, for example, the k nearest neighbors in N to the query r (kNN(r, N )) are retrieved from the remote server, the total cost experienced by the system is o∈kNN(r,N ) c d (r, o) + kc f .

B. Cache Indexes

AC ¸AI departs from the key-value indexes of most of the similarity caching policies. As discussed in Sec. II, such an approach was essentially motivated by the need to simplify kNN searches by performing two searches on smaller datasets (the set of keys first, and then the union of the values for l keys), and may lead to potential inefficiencies including subutilization of the available caching space.

The two-level search implemented by existing similarity caching policies can be seen as a naïve way to implement an approximate kNN search on the set of objects stored locally (the local catalog C). Thanks to the recent advances in approximate kNN searches (Sec. III), we have now better approaches to search through large catalogs with limited memory and computation requirements. We assume then that the cache maintains two indexes supporting kNN searches: one for the local catalog (the objects stored locally) and one for the remote catalog (the objects stored at the server). A discussion about which approximate index is more appropriate for each catalog is in Sec. III.

The local catalog index allows AC ¸AI to (i) fully exploit the available space (the cache stores at any time h objects and can perform a kNN search on all of them), (ii) potentially find closer objects in comparison to the non-optimized keyvalue search. Instead, the remote catalog index allows AC ¸AI to evaluate what objects the server would provide as an answer to the request, and then to correctly evaluate which objects should be served locally and which one should be served from the server/ as we are going to describe next.

C. Request Serving

Differently from existing policies, AC ¸AI has the possibility to compose the answer using both local objects and remote ones. Upon a request r, AC ¸AI uses the two indexes to find the closest objects from the local catalog C and the remote catalog N . We denote the set of objects identified by these indexes as kNN(r, C) and kNN(r, N ), respectively. AC ¸AI composes the answer A by combining the objects with the smallest costs in the two sets. For an object o stored locally (o ∈ C), the system only pays c d (r, o); for an object o fetched from the remote server (o ∈ N \ C), the system pays c d (r, o) + c f . The total cost experienced is

C(r, A) o∈A∩kNN(r,C) c d (r, o) + o∈A\kNN(r,C) (c d (r, o) + c f ) . (1)
The answer A is determined by selecting k objects that minimize the total cost, that is

A = arg min B⊂(kNN(r,C)∪kNN(r,N )) |B|=k C(r, B). (2)

D. Cache State and Service Cost/Gain

In order to succinctly present how AC ¸AI updates the local catalog and its theoretical guarantee, it is convenient to express the cost in (1) as a function of the current cache state and replace the set notation with a vectorial one.

First, we define the augmented catalog U N ∪ {N + 1, N + 2, . . . , 2N } and define the new costs

c(r, i) = c d (r, i), if i ∈ N , c d (r, i -N ) + c f , if i ∈ U \ N . (3)
Essentially, i and i + N (for i ∈ {1, . . . , N }) correspond to the same object, with i capturing the cost when the object is stored at the cache and i + N capturing the cost when it is stored at the server. From now on, when we talk about the closest objects to a request, we are considering c(•, •) as the distance.

Note that AC ¸AI can easily be modified to account for heterogeneous retrieval costs by modifying Eq. ( 3) and replacing c f by an object-dependent retrieval cost c f,i for every object i ∈ N . Moreover, we assume that the fetching cost and dissimilarity cost are added together linearly in the objective, however our model can capture the scenario where the cost is not necessarily additive in c d and c f by a redefinition of the second line in Eq. (3). In particular, the algorithm only requires the existence of an arbitrary function c(r, i) and the theoretical guarantees in Sec. IV-H also hold under such modifications. We consider a simplified model to streamline the presentation.

It is also convenient to represent the state of the cache (the set of objects stored locally) as a vector x ∈ {0, 1} 2N , where, for i ∈ N , x i = 1 (resp., x i = 0), if i is stored (resp., is not stored) in the cache, and we set x i+N = 1x i . 3 The set of valid cache configurations is given by:

X x ∈ {0, 1} 2N : i∈N x i = h, x j+N = 1 -x j , ∀j ∈ N . (4)
For every request r ∈ R we define the sequence π r as the permutation of the elements of U, where π r i is the i-th closest object to r in U according to the costs c(r, o), ∀o ∈ U. The answer A provided by AC ¸AI (Eq. ( 2)) coincides with the first k elements of π r for which the corresponding index in x is equal to 1. The total cost to serve r can then be expressed directly as a function of the cache state x:

C(r, x) = 2N i=1 c(r, π r i )x π r i 1 i-1 j=1 x π r j <k , ∀x ∈ X , (5)
where 1 {χ} = 1 when the condition χ is true, and 1 {χ} = 0 otherwise. Instead of working with the cost C(r, x), we can equivalently consider the caching gain defined as the cost reduction due to the presence of the cache (as in [START_REF] Ioannidis | Adaptive Caching Networks with Optimality Guarantees[END_REF], [START_REF] Shanmugam | FemtoCaching: Wireless Content Delivery Through Distributed Caching Helpers[END_REF], [START_REF] Neglia | A Swiss Army Knife for Dynamic Caching in Small Cell Networks[END_REF]):

G(r, x) C(r, (0, 0, . . . , 0 N , 1, 1, . . . , 1 N )) -C(r, x), (6)
where the first term corresponds to the cost when the cache is empty (and then requests are entirely satisfied by the server).

The theoretical guarantees of AC ¸AI are simpler to express in terms of the caching gain (Sec. IV-H). Observe that the caching gain is zero for any cache state when the retrieval cost is null (c f = 0), e.g., the cache and the server are co-located. In this case, the cache would not provide any advantage.

The caching gain has the following compact expression (Supplementary material, Sec. I, Lemma 3):

G(r, x) = K r -1 i=1 α r i min    k -σ r i , i j=1 x π r j -σ r i    , (7)
where

σ r i i j=1 1 {π r j ∈U \N } , ∀(i, r) ∈ U × R, (8)
K r is the value of the minimum index i ∈ U such that σ r i = k, and α r i c(r, π r i+1 )c(r, π r i ) ≥ 0. Let conv(X ) denote the convex hull of the set of valid cache configurations X . We observe that G(r, y) is a concave function of variable y ∈ conv(X ). Indeed, from Eq. ( 7), G(r, y) is a linear combination, with positive coefficients, of concave functions (the minimum of affine functions in y).

E. Cache Updates

We denote by r t ∈ R the t-th request. The cache is allowed to change its state x t ∈ X to x t+1 ∈ X in a reactive manner, after receiving the request r t and incurring the gain G(r t , x t ). AC ¸AI updates its state x t to greedily maximize the gain. The update of the state x t is driven from a continuous fractional state y t ∈ conv(X ), where y t,i can be interpreted as the probability to store object i in the cache. At each request r t , AC ¸AI increases the components of y t corresponding to the objects that are used to answer to r t , and decreases the other components. This could be achieved by a classic gradient method, e.g., y t+1 = y t + ηg t , where g t is a subgradient of G(r t , y t ) and η ∈ R + is the learning rate (or stepsize), but in AC ¸AI we consider a more general online mirror ascent update OMA [START_REF] Bubeck | Convex Optimization: Algorithms and Complexity[END_REF]Ch. 4] that is described in Algorithm 1. 4 OMA is parameterized by the function Φ( • ), that is called 4 Properly speaking OMA, only refers to the update of y t and does not include the randomized rounding schemes in lines 8-14.

Algorithm 1 Online Mirror Ascent (OMA)

Input: η ∈ R + , ROUNDINGSCHEME 1: procedure ONLINEMIRRORASCENT 2: y 1 ← arg min y∈conv(X )∩D Φ(y); x 1 ← DEPROUND(y 1 ) 3: for t ← 1, 2, . .

. , T do

Incur a gain G(rt, y t ), and compute a subgradient g t of G at point y t (Supplementary material, Sec. V, Eq. ( 52))

4:

ŷt ← ∇Φ(y t )

Map primal point to dual point 5: ẑt+1 ← ŷt + ηg t Take gradient step in the dual 6:

z t+1 ← (∇Φ) -1 (ẑ t+1 )
Map dual point to a primal point 7: end for 16: end procedure the mirror map (see Supplementary material, Sec. VI). If the mirror map is the squared Euclidean norm, OMA coincides with the usual gradient ascent method, but other mirror maps can be selected. In particular, our experiments in Sec. V show that the negative entropy map Φ(y) = i∈N y i log y i with domain D = R N >0 achieves better performance.

y t+1 ← Φ conv(X )∩D (z t+1 ) Proj.

F. Rounding the Cache Auxiliary State

At every time slot t ∈ [T ], AC ¸AI can use the randomized rounding scheme DEPROUND [START_REF] Byrka | An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization[END_REF] to generate a cache allocation x t+1 ∈ X from y t+1 ∈ conv(X ), while still satisfying the capacity constraint at any time slot t. The cache can fetch from the server the objects that are in x t+1 but not in x t .

As cache updates introduce extra costs for the network operator, DEPROUND could potentially cause extra update costs that grow linearly in time. To mitigate incurring large update costs, we may avoid updating the cache state at every time slot t ∈ [T ] by freezing the cache physical state for M ∈ [T ] time steps. In particular, we assume the update cost of the system to be proportional to the number of fetched files, which can be upper bounded by the l 1 norm of the state update: i∈N max{0, x t+1,ix t,i } ≤ x t+1x t 1 . Hence, if we denote by C UC,T the total update cost of the system over the time horizon T , then we have

C UC,T = O T -1 t=1 x t+1 -x t 1 . (9)
When the cache state is refreshed after a call to the rounding scheme DEPROUND, the incurred update cost is in the order of O (2h), and

C UC,T T = O 2h M . Moreover, when M = Θ T β for β ∈ (0, 1) it holds C UC,T T = O T -β
, and for any > 0 and T large enough

C UC,T T ≤ . (10)
The average update cost of the system is then negligible for large T . The parameter M reduces cache updates at the expense of reducing the cache reactivity (see Theorem IV.3).

In some applications, it is possible to slightly violate the capacity constraint with small deviations, as long as this is satisfied on average [START_REF] Lorido-Botran | A Review of Auto-scaling Techniques for Elastic Applications in Cloud Environments[END_REF]- [START_REF] Carra | Elastic Provisioning of Cloud Caches: A Cost-Aware TTL Approach[END_REF]. For example, there could be a monetary value associated to the storage reserved by the cache, and a total budget available over a target time horizon T . In this setting, the cache may violate momentarily the capacity constraint, as far as the total payment does not exceed the budget.

COUPLEDROUNDING (Algorithm 2) is a rounding approach which works under this relaxed capacity constraint and does not require freezing the cache state for M time slots. At time slot t ∈ [T ], the cache decides which files to cache through N coin tosses, where the file i ∈ N is cached with probability y t,i , and the random state obtained is x t . By definition, the expected value of the integral state is E[x t ] = y t . The probability that the cache exceeds its target storage capacity by δh is given by the Chernoff bound [START_REF] Mitzenmacher | Probability and Computing: Randomized Algorithms and Probabilistic Analysis[END_REF] as:

P ( x t 1 > (1 + δ)h) < e -δ 2 h 2 , δ ∈ (0, 1], (11)
where the l 1 norm is restricted to the first N components of the vector, i.e., x 1 i∈N |x i |. In the regime of large cache sizes h 1, we observe from the Chernoff bound that the cache stores less than (1 + δ) of its target capacity h with high probability.

Theorem IV.1 (proof in Supplementary material, Sec. VIII-A) shows that the expected movement of COUPLEDROUND-ING is equal to the movement of the fractional auxiliary states {y t } T t=1 . Theorem IV.1. If the input to Algorithm 2 is sampled from a random variable x t ∈ {0, 1} N with E[x t ] = y t , then we obtain as output an integral cache configuration

x t+1 ∈ {0, 1} N satisfying E[x t+1 ] = y t+1 and E [ x t+1 -x t 1 ] = y t+1 -y t 1 .
Moreover, the movement of the fractional states is negligible for large T : Theorem IV.2. Algorithm 1, configured with the negative entropy mirror map and learning rate η = O 1 √ T , selects fractional cache states satisfying

T -1 t=1 y t+1 -y t 1 = O( √ T ). ( 12
)
The proof is in Supplementary material, Sec. VIII-B.

Combining the two theorems and ( 9), we also conclude that the expected average update cost of the system E C UC,T T is negligible for large T .

G. Time Complexity

AC ¸AI uses OMA in Algorithm 1 coupled with a rounding procedure DEPROUND or COUPLEDROUNDING. The rounding step may take O (N ) operations (amortized every M requests when DEPROUND is used). In practice, AC ¸AI quickly sets irrelevant objects in the fractional allocation vector y t very close to 0. Therefore, we can keep track only of objects with a fractional value above a threshold > 0, and the size of this subset is practically of the order of h.

Algorithm 2 Coupled Rounding

Input: xt, y t , y t+1 xt satisfies E[xt] = y t 1: procedure COUPLEDROUNDING 2: δ ← y t+1 -y t
Compute the change in distribution 3:

for i ∈ N do 4: if (x t,i = 1) ∧ (δ i < 0) then 5: x t+1,i ← 0 w.p. -δ i y t,i
, and x t+1,i ← 1 w.p.

y t,i +δ i y t,i 6: else if (x t,i = 0) ∧ (δ i > 0) then 7:
x t+1,i ← 0 w.p. Similarly, subgradient computation (see Supplementary material, Sec. V, Eq. ( 52)) may require O (N ) operations per each component and then have O N 2 complexity, but in practice, as the vector y t is sparse, calculations require only a constant number of operations and complexity reduces to O (N ).

Finally, we use the negative entropy Bregman projection in [START_REF] Salem | No-Regret Caching via Online Mirror Descent[END_REF] (line 6 of Algorithm 1) that has O (N + h log(h)) time complexity. The O (N + h log(h)) is due to a partial sorting operation while the actual projection takes O (h). Again, most of the components of y t are equal to 0, so that, in practice, we need to sort much fewer points.

H. Theoretical Guarantees

The best static cache allocation in hindsight is the cache state x * that maximizes the time-averaged caching gain in Eq. ( 6) over the time horizon T , i.e.,

x * ∈ arg max x∈X G T (x) 1 T T t=1 G(r t , x) . ( 13
)
We observe that solving (13) is NP-hard in general even for k = 1 under a stationary request process [START_REF] Neglia | Similarity Caching: Theory and Algorithms[END_REF]. Nevertheless, AC ¸AI operates in the online setting and provides guarantees in terms of the ψ-regret [START_REF] Krause | Submodular Function Maximization[END_REF]. In this scenario, the regret is defined as a gain loss in comparison to the best static cache allocation x * in [START_REF] Lin | Learning Compact Binary Descriptors With Unsupervised Deep Neural Networks[END_REF]. The ψ-regret discounts the best static gain by a factor ψ ∈ (0, 1]. Formally,

ψ-Regret T,X (OMA Φ ) = sup {r1,r2,...,r T }∈R T ψ T t=1 G(r t , x * ) -E T t=1 G(r t , x t ) , (14)
where the expectation is over the randomized choices of DEPROUND. Note that the supremum in ( 14) is over all possible request sequences. This definition corresponds to the so-called adversarial analysis, imagining that an adversary selects requests in R to jeopardize cache performance. The definition of the regret in Eq. ( 14), which compares the gain of the policy to a static offline solution, is classic. Several bandit settings, e.g., simple multi-armed bandits [50]- [START_REF] Audibert | Exploration-Exploitation Tradeoff Using Bariance Estimates in Multi-Armed Bandits[END_REF], contextual bandits [START_REF] Chu | Contextual Bandits with Linear Payoff Functions[END_REF]- [START_REF] Dudik | Efficient Optimal Learning for Contextual Bandits[END_REF], and, of course, their applications to caching problems under the full-information setting [START_REF] Paschos | Learning to Cache With No Regrets[END_REF], [START_REF] Salem | No-Regret Caching via Online Mirror Descent[END_REF], [START_REF] Mukhopadhyay | Online Caching with Optimal Switching Regret[END_REF], [START_REF] Bhattacharjee | Fundamental Limits on the Regret of Online Network-Caching[END_REF], [START_REF] Li | Online Caching Networks with Adversarial Guarantees[END_REF], adopt this definition. In all these cases, the dynamic, adaptive algorithm is compared to a static policy that has full hindsight of the entire trace of actions. Moreover, as is customary when the offline problem is NP-hard [START_REF] Chen | Online Continuous Submodular Maximization[END_REF], the regret is not w.r.t. the optimal caching gain, but w.r.t. the gain obtained by an offline approximation algorithm. Regret bounds in the adversarial setting provide strong robustness guarantees in practical scenarios. AC ¸AI has the following regret guarantee:

(1 -1/e)-Regret T,X (OMA Φ ) ≤ 1 - 1 e (c k d + c f )h 2 log N h ((M -1)(T + M ) + T ),
where the constant c k d is an upper bound on the dissimilarity cost of the k-th closest object for any request in R.

Proof. (sketch) We first prove that the expected gain of the randomly sampled allocations x t is a (1-1/e)-approximation of the fractional gain. Then, we use online learning results [START_REF] Bubeck | Convex Optimization: Algorithms and Complexity[END_REF] to bound the regret of OMA schemes operating on a convex decision space against concave gain functions picked by an adversary. The two results are combined to obtain an upper bound on the (1-1/e)-regret. The full proof is available in Supplementary material, Sec. IX.

The (1 -1/e)-regret of AC ¸AI under COUPLEDROUNDING scheme has order-optimal regret O √ T [START_REF] Hazan | Introduction to online convex optimization[END_REF]. Under the rounding scheme DEPROUND with freezing period M = Θ T β , the reduced reactivity of AC ¸AI is reflected by the additional T β 2 factor in the order of the regret. Nonetheless, the expected time-average (1 -1/e)-regret of AC ¸AI can get arbitrarily close to zero for a large time horizon. Hence, AC ¸AI performs on average as well as a (1 -1/e)-approximation of the optimal configuration x * . This observation also suggests that our algorithm can be used as an iterative method to solve the NP-hard static allocation problem with the best approximation bound achievable for these kinds of problems [START_REF] Nemhauser | Best Algorithms for Approximating the Maximum of a Submodular Set Function[END_REF].

Corollary IV.3.1. (offline solution) Let ȳ be the average fractional allocation ȳ = 1 T T i=1 y i of AC ¸AI, and x the random state sampled from ȳ through COUPLEDROUNDING or DEPROUND. If Algorithm 1 is configured with the negative entropy mirror map, and, at each iteration t ∈ [ T ], operates with subgradients of the time-averaged caching gain (13), then ∀ > 0 and over a sufficiently large number of iterations T , x satisfies

E [G T (x)] ≥ 1 - 1 e - G T (x * ).
where The proof can be found in Supplementary material, Sec. X.

x * = arg max x∈X G T (x).

V. EXPERIMENTS

We start evaluating AC ¸AI in a simple scenario with a synthetic request process, for which we can compute the optimal fractional static cache allocation. We then consider real-world catalogs and traces and compare our solution with state-of-the-art online policies proposed for kNN caching, i.e., SIM-LRU [START_REF] Pandey | Nearest-Neighbor Caching for Content-Match Applications[END_REF], CLS-LRU [START_REF] Pandey | Nearest-Neighbor Caching for Content-Match Applications[END_REF], and QCACHE [START_REF] Falchi | Similarity Caching in Large-scale Image Retrieval[END_REF] described in Sec. II.

A. Simple Scenario

As in [START_REF] Sabnis | GRADES: Gradient Descent for Similarity Caching[END_REF], we consider a synthetic catalog of N = 900 objects positioned on a 30 × 30 grid. The request process is generated according to the Independent Reference Model [START_REF] Coffman | Operating Systems Theory[END_REF]. The objects' popularity is represented by a Gaussian distribution. In particular, an object o ∈ N with l 1 distance d o from the center of the grid [START_REF] Navarro | Searching in Metric Spaces by Spatial Approximation[END_REF][START_REF] Navarro | Searching in Metric Spaces by Spatial Approximation[END_REF] . The synthetic catalog is depicted in Fig. 2.

We consider the dissimilarity cost to be the l 1 distance. We take different values for the retrieval cost c f ∈ {1, 2, 3, 4} and the number of neighbors k ∈ {1, 2, 3, 4, 5}. We take the cache capacity to be h = 15. We configure AC ¸AI with DEPROUND rounding scheme.

We use CVXPY [START_REF] Diamond | CVXPY: A Python-Embedded Modeling Language for Convex Optimization[END_REF] to find the optimal fractional static cache allocation, and AC ¸AI to compute its approximation according to Corollary IV.3.1. In particular, AC ¸AI runs for T = 10 000 iterations with a diminishing learning rate η t = 2.0 c f (1 + cos( πt T )). Results. Figure 3 shows the optimal fractional static cache allocations and the AC ¸AI's fractional static cache allocations (see Corollary IV.3.1) under different retrieval costs and the number of neighbors k. We observe that the optimal fractional static cache allocations in Fig. 3 (a) are symmetric, while AC ¸AI's fractional static cache allocations in Fig. 3 (b) partially lose this symmetry for values of k ∈ {2, 3, 4} primarily due to the different ways a kNN query can be satisfied over the physical catalog for such values. In fact, there are multiple objects in the catalog with the same distance from a request r, and AC ¸AI only selects a single permutation π r for a request r. We observe that, when the retrieval cost is higher, the allocations are more spread to cover a larger part of the popular region. In Fig. 4, we compare the gain obtained by the optimal fractional static cache allocations, its (1 -1 e )-approximation, and the gain obtained by AC ¸AI's fractional static cache allocations and the static integral cache allocations (see Corollary IV.3.1). While Fig. 3 shows that AC ¸AI's fractional static cache allocations may differ from the optimal ones, their costs are practically indistinguishable (the two corresponding surfaces overlap in Fig. 4). We also observe that rounding comes at a cost, as there is a clear gap between the gain of AC ¸AI's fractional cache allocations and of AC ¸AI's integral ones. Still, the average gain of the integral cache allocations remains close to the fractional optimum and well above the (1 -

c f = 1, k = 1 c f = 1, k = 2 c f = 1, k = 3 c f = 1, k = 4 c f = 1, k = 5 10 20 c f = 2, k = 1 c f = 2, k = 2 c f = 2, k = 3 c f = 2, k = 4 c f = 2, k = 5 10 20
c f = 3, k = 1 c f = 3, k = 2 c f = 3, k = 3 c f = 3, k = 4 c f = 3, k = 5
c f = 1, k = 1 c f = 1, k = 2 c f = 1, k = 3 c f = 1, k = 4 c f = 1, k = 5 10 20
c f = 2, k = 1 c f = 2, k = 2 c f = 2, k = 3 c f = 2, k = 4 c f = 2, k = 5 10 20
c f = 3, k = 1 c f = 3, k = 2 c f = 3, k = 3 c f = 3, k = 4 c f = 3, k = 5

B. Real-world Datasets

SIFT1M trace. SIFT1M is a classic benchmark dataset to evaluate approximate kNN algorithms [START_REF] Jégou | Product Quantization for Nearest Neighbor Search[END_REF]. It contains 1 million objects embedded as points in a 128-dimensional space. SIFT1M does not provide a request trace so we generated a synthetic one according to the Independent Reference Model [START_REF] Coffman | Operating Systems Theory[END_REF] (similar to what is done in other papers like [START_REF] Falchi | A Metric Cache for Similarity Search[END_REF], [START_REF] Guo | Potluck: Cross-Application Approximate Deduplication for Computation-Intensive Mobile Applications[END_REF]). Request r t is for object i with a probability λ i independently of previous requests. We spatially correlated objects' popularities by letting λ i depend on the position of the embeddings in the space. In particular, we considered the barycenter of the whole dataset and set λ i proportional to d -β i , where d i is the distance of i from the barycenter. The parameter β was chosen such that the tail of the ranked objects' popularity distribution is similar to a Zipf with parameter 0.9, as observed in some image retrieval systems [START_REF] Falchi | Similarity Caching in Large-scale Image Retrieval[END_REF]. We generated a trace with 10 5 requests. The number of distinct objects requested in the trace is approximately 2 × 10 4 . Amazon trace. The authors of [START_REF] Mcauley | Image-Based Recommendations on Styles and Substitutes[END_REF] crawled the Amazon web-store and collected a dataset to model relationships among products and provide user recommendations. They took as input the visual features of product images obtained from a machine learning model pre-trained on 1.2 million images from ImageNet. The visual features are augmented with the relationships between the items, and these relationships are collected based on the cosine similarity of the sets of users who purchased or viewed the items. The objects' dissimilarity is modeled as a distance d(•, •), such that P(item i is related to item j) increases monotonically with d(x i , x j ), where x i and x j are the visual features of the items i and j. The authors of [START_REF] Mcauley | Image-Based Recommendations on Styles and Substitutes[END_REF] show that the relationship 'users who viewed i also viewed j' can successfully be used to provide accurate recommendations. The authors of [START_REF] Sabnis | GRADES: Gradient Descent for Similarity Caching[END_REF] built a request trace from the timestamped user reviews for objects in the category Baby embedded in a 100-dimensional space. Two products o and o are considered similar if they have been viewed by the same users. We use the request trace from [START_REF] Sabnis | GRADES: Gradient Descent for Similarity Caching[END_REF] and in particular the interval [2×105 , 3×10 5 ]. 5 The number of distinct objects requested in this trace is approximately 2×10 4 .

C. Settings and Performance Metrics

For AC ¸AI, unless otherwise said, we choose the negative entropy Φ(y) = i∈N y i log(y i ) as mirror map (see Fig. 10 and the corresponding discussion for other choices) and the rounding scheme DEPROUND with M = 1. The learning rate is set to the best value found exploring the range [10 -6 , 10 -4 ].

As for the state-of-the-art caching policies, SIM-LRU and CLS-LRU have two parameters, C θ and k , that we set in each experiment to the best values we found exploring the ranges [c f , 2c f ] for C θ and [1, h] for k . For QCACHE we consider l = h/k: the cache can then perform the kNN search over all local objects.

We also consider a simple similarity caching policy that stores previous requests and the corresponding set of k closest objects as key-value pairs, and manages the set of keys according to LRU. The cache then serves locally the request if it coincides with one of the previous requests in its memory, it forwards it to the server, otherwise. The ordered list of keys is updated as in LRU. We refer to this policy simply as LRU.

We compare the policies in terms of their normalized average caching gain per request, where the normalization factor corresponds to the caching gain of a cache with a size equal to the whole catalog. In such a case, the cache could store the entire catalog locally and would achieve the same dissimilarity cost of the server without paying any fetching cost. The maximum possible caching gain is then kc f . The normalized average gain of a policy P with cache states {x t } T t=1 over T requests can then be defined as:

NAG(P) = 1 kc f T T t=1 G(r t , x t ). (15)

D. Results

We consider a dissimilarity cost proportional to the squared Euclidean distance. This is the usual metric considered for SIFT1M benchmark and also the one considered to learn the embeddings for the Amazon trace in [START_REF] Mcauley | Image-Based Recommendations on Styles and Substitutes[END_REF].

The numerical value of the fetching cost depends on its interpretation (delay experienced by the user, load on the server or on the network) as well as on the application, because it needs to be converted into the same unit of the approximation cost. In our evaluation, we let it depend on the topological characteristics of the dataset in order to be able to compare the results for the two different traces. Unless otherwise said, we set c f equal to the average distance of the 50-th closest neighbor in the catalog N . Figure 5 shows how the normalized average gain changes as requests arrive and the different caching policies update the local set of objects (starting from an empty configuration). The cache size is h = 1000 and the cache provides k = 10 similar objects for each request. All policies reach an almost stationary gain after at most a few thousand requests. Unsurprisingly, the naïve LRU has the lowest gain (it can only satisfy locally requests that match exactly a previous request) and similarity caching policies perform better. AC ¸AI has a significant improvement in comparison to the second best policy (SIM-LRU for SIFT1M and CLS-LRU for Amazon).

This advantage of AC ¸AI is constantly confirmed for dif- (e) CLS-LRU, h = 50 ferent cache sizes (Fig. 6), different values of the fetching cost c f (Fig. 7), and different values of k (Fig. 8). The relative improvement of AC ¸AI, in comparison to the second best policy, is larger for small values of the cache size (+30% for SIFT1M and +25% for Amazon when h = 50), and small values of the fetching cost (+35% for SIFT1M and +100% for c f equal to the average distance from the second closest object). Note how these are the settings where caching choices are more difficult (and indeed all policies have lower gains): when cache storage can accommodate only a few objects, it is critical to carefully select which ones to store; when the server is close, the costs of serving requests from the cache or the server are similar and it is difficult to correctly decide how to satisfy the request. The performance of caching policies is in general less dependent on the number k of similar objects to retrieve and AC ¸AI achieves about 10% improvement for k between 10 and 100 when h = 1000 (Fig. 8).

Sensitivity analysis. We now evaluate the robustness of AC ¸AI to the configuration of its single parameter (the learning rate η). Figure 9 shows indeed that, for learning rates that are two orders of magnitude apart, we can achieve almost the same normalized average gain both for h = 50 and for Euclidean: η = 10 -6 Fig. 10: Caching gain for AC ¸AI configured with negative entropy and Euclidean maps (SIFT1M trace). The cache size is h = 100 and k = 10. h = 1000. 6 In contrast, the performance of the second best policies (SIM-LRU and CLS-LRU) are more sensitive to the choice of their two configuration parameters k and C θ . For example, the optimal configuration of SIM-LRU is k = 10 and C θ = 1.5 × c f for a small cache (h = 50) but k = 200 and C θ = 2 × c f for a large one (h = 1000). Moreover, in both cases a misconfiguration of these parameters would lead to significant performance degradation.

Choice of the mirror map. If the mirror map is selected equal to the squared Euclidean norm, the OMA update coincides with a standard gradient update. Figure 10 shows the superiority of the negative entropy map: it allows one to achieve a higher gain than the Euclidean norm map or the same gain but in a shorter time. To the best of our knowledge, ours is the first paper that shows the advantage of using non-Euclidean mirror maps for similarity caching problems. We observe how our finding is in apparent contrast with what observed for exact caches in [START_REF] Salem | No-Regret Caching via Online Mirror Descent[END_REF], i.e., that the Euclidean mirror map should always be preferred when requests are not batched. The difference can be explained as follows: under exact caching only the requested object can satisfy the request and then the gradient has a single non-null component, but, under similarity caching, multiple objects in the vicinity of a request can contribute to reduce the cost of serving it and the gradient is then less sparse. It is known that denser gradients may lead to prefer the negative entropy map [START_REF] Bubeck | Convex Optimization: Algorithms and Complexity[END_REF]Sec. 4.3] and our results in Supplementary material, Sec. VII-A provide a theoretical justification for our specific problem.

Dissecting AC ¸AI performance. In comparison to state-ofthe-art similarity caching policies, AC ¸AI introduces two key ingredients: (i) the use of fast, approximate indexes to decide what to serve from the local catalog and what from the remote one, and (ii) the OMA algorithm to update the cache state. It is useful to understand how much each ingredient contributes to AC ¸AI improvement with respect to the other policies.

To this aim, we integrated the same indexes in the other policies allowing them to serve requests as AC ¸AI does, combining both local objects and remote ones based on their costs (see Sec. IV-C), while leaving their cache updating mechanism unchanged. We then compute, in the same setting of Fig. 8, how much the gain of the second best policy (SIM-LRU for SIFT1M and CLS-LRU for Amazon) increases because of AC ¸AI request service mechanism. This is the part of AC ¸AI improvement attributed to the use of the two indexes, the rest is attributed to the cache update mechanism through OMA. We observe from Fig. 11 that most of AC ¸AI gain improvement over the second best caching policy is due to the use of approximate indexes, but OMA updates are still responsible for 15-20% of AC ¸AI performance improvement under SIFT1M trace and 20-35% for the Amazon trace.

Update cost. In this part, we evaluate the update cost of the different rounding schemes. We set the cache size h = 1000 and k = 10. We run AC ¸AI over the Amazon trace with a learning rate η = 10 -5 .

Figure 12 (a) gives the time-averaged number of files fetched and Figure 12 (b) gives the caching gain of the different rounding schemes. We observe that, by increasing the cache state freezing parameter M , the system fetches fewer files per iteration at the expense of losing reactivity and then incurring a smaller gain at the start. The coupled rounding scheme achieves the best performance as it fetches fewer files without losing reactivity.

Figure 13 shows the instantaneous and time-averaged cache occupancy of the cache using the COUPLEDROUND- ING scheme with the relaxed capacity constraint. We observe that the time-averaged cache occupancy rapidly converges to the cache capacity h, while the instantaneous occupancy is kept within 5% of the cache capacity.

VI. CONCLUSION Edge computing provides computing and storage resources that may enable complex applications with tight delay guarantees like augmented-reality ones, but these strategically positioned resources need to be used efficiently. To this aim, we designed AC ¸AI, a content cache management policy that determines dynamically the best content to store on the edge server. Our solution adapts to the user requests, without any assumption on the traffic arrival pattern. AC ¸AI leverages two key components: (i) new efficient content indexing methods to keep track of both local and remote content, and (ii) mirror ascending techniques to optimally select the content to store. The results show that AC ¸AI is able to outperform the stateof-the-art policies and does not need careful parameter tuning.

As future work, we plan to evaluate AC ¸AI in the context of machine learning classification tasks [START_REF] Khandelwal | Generalization through Memorization: Nearest Neighbor Language Models[END_REF], in which the size of the objects in the catalog is comparable to their ddimensional representation in the index, and, as a consequence, the index size cannot be neglected in comparison to the local catalog size. Another important future research direction is to consider dynamic regret, whereby the performance of a policy is compared to a dynamic optimum. Also, since the employed online algorithm OMA is greedy (i.e., does not keep track of the history of the requests), with careful selection of the mirror map, it may have an adaptive regret guarantee, e.g., such guarantee holds for OGD [START_REF] Zinkevich | Online Convex Programming and Generalized Infinitesimal Gradient Ascent[END_REF].

x π r j    -min    c, i-1 j=1 x π r j    = x π r i 1 i-1 j=1 x π r j <c . (16)
Proof. We distinguish two cases:

(i) When i-1 j=1 x π r j ≥ c this implies that i j=1 x π r j = x π r j + i-1 j=1 x π r j ≥ c + x π r i ≥ c since x π r i ≥ 0. Therefore, i-1 j=1 x π r j ≥ c implies that min c, i-1 j=1 x π r j = min c, i j=1 x π r j
= c, and we have:

min    c, i j=1 x π r j    -min    c, i-1 j=1 x π r j    = 0. ( 17
) (ii) When i-1 j=1 x π r j < c, we have i j=1 x π r j = x π r j + i-1 j=1 x π r j < c + x π r i ≤ c since x π r i ≤ 1, this implies that min c, i j=1 x π r j = i j=1 x π r j and min c, i-1 j=1 x π r j = i-1 j=1
x π r j , and we have min

   c, i j=1 x π r j    -min    c, i-1 j=1 x π r j    = x π r i . (18)
Combining Eqs. ( 17) and (18) yields Eq. ( 16).

Lemma 2. The cost function C(r, x) given by the expression in Eq. (5), can be equivalently expressed as:

C(r, x) = - K r -1 i=1 α r i min    k -σ r i , i j=1 x π r j -σ r i    + K r i=1 c(r, π r i )1 {π r i ∈U \N } , (19)
where

σ r i = i j=1 1 {π r j ∈U \N } , α r i = c(r, π r i+1 ) -c(r, π r i ) and K r = min{i ∈ U : σ r i = k} for every (r, i) ∈ R × U. Proof. Let c(r, o), ∀(r, o) ∈ R × U be a cost defined as c(r, π r i ) = c(r, π r i ), ∀i ∈ [K r
] and 0 otherwise, and we also define

αr i as αr i c(r, π r i+1 ) -c(r, π r i ). When i = 1 and for any r ∈ R, we have c(r, π r i ) min    k, i-1 j=1 x π r j    = 0. (20)
Note that σ r 1 = 0 by definition, since π r 1 ∈ N for any r ∈ R. We have

- K r i=1 αr i σ r i = K r i=1 c(r, π r i )σ r i - K r i=1 c(r, π r i+1 )σ r i = K r i=1 c(r, π r i )σ r i - K r i=2 c(r, π r i )σ r i-1 (21)
= K r i=1 c(r, π r i )σ r i - K r i=1 c(r, π r i )σ r i-1 = K r i=1 c(r, π r i )1 {π r i ∈U \N } = K r i=1 c(r, π r i )1 {π r i ∈U \N } . (22)
Observe that the indicator function 1 i-1 j=1 x π r j <k is 0 for every i ≥ K r + 1; therefore, the summation in Eq. ( 5) can be limited to K r instead of 2N . Using Lemma 1 we expand the expression of C(r, x) as follows:

C(r, x) = K r i=1 c(r, π r i )x π r i 1 i-1 j=1 x π r j <k = K r i=1 c(r, π r i )x π r i 1 i-1 j=1 x π r j <k (23) (16)
= K r i=1 c(r, π r i )   min    k, i j=1 x π r j    -min    k, i-1 j=1 x π r j      ( 24
) (20) = K r i=1 c(r, π r i ) min    k, i j=1 x π r j    - K r -1 i=1 c(r, π r i+1 ) min    k, i j=1 x π r j    (25) = K r i=1 c(r, π r i ) min    k, i j=1 x π r j    - K r i=1 c(r, π r i+1 ) min    k, i j=1 x π r j    (26) = - K r i=1 αr i min    k, i j=1 x π r j    = - K r i=1 αr i min    k -σ r i , i j=1 x π r j -σ r i    - K r i=1 αr i σ r i ( 27
) (22) = - K r i=1 αr i min    k -σ r i , i j=1 x π r j -σ r i    + K r i=1 c(r, π r i )1 {π r i ∈U \N } (28) = - K r -1 i=1 α r i min    k -σ r i , i j=1 x π r j -σ r i    + K r i=1 c(r, π r i )1 {π r i ∈U \N } (since k -σ r K r = 0). (29)
This gives the cost function expression in Eq. ( 19).

Lemma 3. For any request r ∈ R the caching gain function G(r, x) in Eq. ( 6) has the following expression

G(r, x) = K r -1 i=1 α r i min    k -σ r i , i j=1 x π r j -σ r i    , (30)
where σ r i = i j=1 1 {π r j ∈U \N } , α r i = c(r, π r i+1 )c(r, π r i ) and K r = min{i ∈ U : σ r i = k} for every (r, i) ∈ R × U. Proof. From Lemma 2, the cost function C(r, x) can be equivalently expressed as:

C(r, x) = - K r -1 i=1 α r i min    k -σ r i , i j=1 x π r j -σ r i    + K r i=1 c(r, π r i )1 {π r i ∈U \N } . (31)
Without caching the system incurs the cost kc f + k o∈kNN(r) c(r, o) when r ∈ R is requested. This is the retrieval cost of fetching k objects and the sum of the approximation costs of the k closest objects in N . From the definition of π r , this cost can equivalently be expressed as K r i=1 c(r, π r i )1 {π r i ∈U \N } . Therefore, we recover the gain expression in Eq. ( 3) as the cost reduction due to having a similarity cache. Thus, we have

G(r, x) = kc f + k o∈kNN(r) c(r, o) -C(r, x) (32)
= K r i=1 c(r, π r i )1 {π r i ∈U \N } - K r i=1 c(r, π r i )1 {π r i ∈U \N } + K r -1 i=1 α r i min    k -σ r i , i j=1 x π r j -σ r i    (33) = K r -1 i=1 α r i min    k -σ r i , i j=1 x π r j -σ r i    . ( 34
)
This concludes the proof.

II. SUPPORTING LEMMAS FOR PROOF OF PROPOSITION IV.1

Lemma 4. For every request r ∈ R, index i ∈ U, and fractional cache state y ∈ conv(X ) the index set defined as

I r i j ∈ [i] : π r j ∈ N ∧ π r j + N / ∈ {π r l : l ∈ [i]} (35)
satisfies the following

j∈[i] y π r j -σ r i = j∈I r i y π r j , (36)
where σ r i = i j=1 1 {π r j ∈U \N } (defined in Eq. ( 8)). Proof.

j∈[i] y π r j -σ r i (8) = j∈[i] y π r j - j∈[i] 1 {π r j ∈U \N } = j∈[i] π r j ∈N y π r j + j∈[i] π r j ∈U \N y π r j -1 = j∈[i] π r j ∈N y π r j - l∈[i] π r l ∈U \N y (π r l -N ) (37)
Remark that if l ∈ [i] and π r l ∈ U \N , then the object π r l -N has a strictly smaller cost and it appears earlier in the permutation π r , that is there exists j < l such that π r j = π r l -N . In this case, the variable y (π r l -N ) cancels out y π r j in the RHS of [START_REF] Shalev-Shwartz | Online Learning and Online Convex Optimization[END_REF]. Then, we have

j∈[i] π r j ∈N y π r j - l∈[i] π r l ∈U \N y (π r l -N ) = j∈[i] π r j ∈N π r j +N / ∈{π r l :(l∈[i])∧(π r l ∈U \N )} y π r j . (38)
Note that if π r l / ∈ U \ N (i.e., π r l ∈ N ), then π r j + N = π r l . Then the sets {π r l : (l ∈ [i]) ∧ (π r l ∈ U \ N )} and {π r l : l ∈ [i]} coincide. Therefore, the above equation can be simplified as follows

j∈[i] π r j ∈N y π r j - l∈[i] π r l ∈U \N y (π r l -N ) = j∈[i] π r j ∈N π r j +N / ∈{π r l :l∈[i]} y π r j = j∈I r i y π r j . (39)
Eq. ( 37) and Eq. ( 39) are combined to get

j∈[i] y π r j -σ r i = j∈I r i y π r j , (40)
and this concludes the proof.

III. BOUNDS ON THE AUXILIARY FUNCTION

We define Λ : R × conv(X ) → R + , an auxiliary function, that will be utilized in bounding the value of the gain function

Λ(r, y) K r -1 i=1 α r i (k -σ r i )   1 - j∈I r i 1 - y π r j k -σ r i   , ∀r ∈ R, y ∈ conv(X ). (41)
The DEPROUND [START_REF] Byrka | An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization[END_REF] subroutine outputs a rounded variable x ∈ X from a fractional input y ∈ conv(X ), by iteratively modifying the fractional input y. At each iteration the subroutine SIMPLIFY that is part of DEPROUND is executed on two yet unrounded variables y i , y j ∈ (0, 1) with i, j ∈ N , until all the variables are rounded in O(N ) steps. Note that only y i , ∀i ∈ N is rounded, since x i ∈ U \ N is determined directly from x i-N . The random output of DEPROUND [START_REF] Byrka | An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization[END_REF] subroutine x ∈ X given the input y ∈ conv(X ) has the following properties:

P1 E[x i ] = y i , ∀i ∈ N . P2 i∈N x i = k. P3 ∀S ⊂ N , E i∈S (1 -x i ) ≤ i∈S (1 -y i ) . Lemma 5.
The random output x ∈ X of DEPROUND given the fractional cache state input y ∈ conv(X ), or the random output x ∈ {0, 1} U of COUPLEDROUNDING given an integral cache state x , and fractional cache states y, y ∈ conv(X ) with E[x ] = y , satisfy the following for any request r ∈ R

E [Λ(r, x)] ≥ Λ(r, y). ( 42
)
Proof.

E [Λ(r, x)] (41) = E   K r -1 i=1 α r i (k -σ r i )   1 - j∈I r i 1 - x π r j k -σ r i     = K r -1 i=1 α r i (k -σ r i )   1 -E   j∈I r i 1 - x π r j k -σ r i     (43)
≤ K r -1 i=1 α r i (k -σ r i )   1 - j∈I r i 1 - y π r j k -σ r i   = Λ(r, y). (44)
The second equality is obtained using the linearity of the expectation operator. The inequality is obtained using [68, Lemma E.10] with S = I r i , c m = 1 k-σ r i , as σ r i < k for i < K r in the case when x is the output of DEPROUND, and in the case when x is an output of COUPLEDROUNDING, the inequality holds with equality since every x i for i ∈ N is an independent random variable.

IV. BOUNDS ON THE GAIN FUNCTION

Proposition IV.1. The caching gain function G(r, x) defined in Eq. ( 6) has the following lower and upper bound for any request r ∈ R and fractional cache state y ∈ conv(X ):

Λ(r, y) ≤ G(r, y) ≤ 1 - 1 e -1 Λ(r, y). (45)
Proof. We have the following

G(r, y) = K r -1 i=1 α r i min    k -σ r i , j∈[i] y π r j -σ r i    (36) = K r -1 i=1 α r i min    k -σ r i , i j∈I r i y π r j    (46)
≥ K r -1 i=1 α r i (k -σ r i )   1 - j∈I r i 1 - y π r j k -σ r i   (47)
= Λ(r, y),

and

G(r, y) = K r -1 i=1 α r i min    k -σ r i , j∈I r i y π r j    (49) ≤ 1 - 1 e -1 K r -1 i=1 α r i (k -σ r i )   1 - j∈I r i 1 - y π r j k -σ r i   (50)
= Λ(r, y).

The inequalities in Eq. ( 47) and Eq. ( 50) are obtained through [START_REF] Salem | Towards Inference Delivery Networks: Distributing Machine Learning with Optimality Guarantees[END_REF]Lemma E.7], and [68, Lemma E.8], respectively, by setting c = kσ r i , and q i = 1 for every i ∈ [K r -1].

V. SUBGRADIENTS COMPUTATION Theorem V.1. For any time slot t ∈ [T ], the vectors g t given by Eq. ( 52) are subgradients of the caching gain function G(r, y) for request r t ∈ R at fractional cache state y t ∈ conv(X ).

g t = c r t , π rt i r t * +1 -c (r t , l) 1 {l r t * ≤i r t * } l∈N , ( 52
)
where i rt * max i ∈ [K rt -1] : i j=1 y t,π r j ≤ k ∧ (l + N / ∈ {π rt v : v ∈ [i]}) , l rt * (π rt ) -1 (l), ∀l ∈ N , and (π rt ) -1 is the inverse permutation of π rt . (y) = 0, if i j=1 y π r j ≥ k, ∂ ∂y l i j=1 y π r j otherwise. (58)
= 1 i j=1 y π r j <k ∧ l r * ≤i ∧ (l+N ∈{π r v :v∈[n]}) . (59)
For any non-negative factor α r i , we have ∂ α r i f (r,i) (y) = α r i ∂ f (r,i) (y) (multiply both sides of the subgradient inequality by a non-negative constant [43, Definition 1.2]), and using [START_REF] Rockafellar | Convex Analysis[END_REF]Theorem 23.6] we get

∂G(r, y) = ∂ K r -1 i=1 α rt i f (r,i) (y) = K r -1 i=1 α rt i ∂f (r,i) (y). ( 60
) Let i r * max{i ∈ [K r -1] : i j=1 y π r j ≤ k ∧ (l + N / ∈ {π r v : v ∈ [i]
)}}. Now we can define a subgradient g t of the function G(r, y) at point y t ∈ conv(X ) and request r t ∈ R for any t ∈ [T ], where every component l ∈ N of g t is given by

g t,l = K r t -1 i=1 α rt i g (rt,i) l (y t ) = K r t -1 i=1 α rt i 1 i j=1 y π r t j <k ∧ (l r t * ≤i) ∧ (l+N ∈{π r t v :v∈[n]}) (61)
= K r t -1 i=l r t * α rt i 1 i j=1 y π r t j <k ∧ (l+N ∈{π r t v :v∈[n]}) = i r t * i=l r t * α rt i = i r t * i=l r t * c(r t , π rt i+1 ) -c(r t , π rt i ) (62) = c(r t , π rt i r t * +1 ) -c(r t , l) 1 {l r t * ≤i r t * } , ∀l ∈ N . (63)
Note that in the last equality we used the definition of l rt * to obtain c(r t , l) = c(r t , π r l r t *

). This concludes the proof.

VI. MIRROR MAPS

Let D ⊂ R N be a convex open set, and Y be a convex set such that Y ⊂ cl(D) where cl( • ) is the closure; moreover, D ∩ Y = ∅. The map Φ : D → R is called a mirror map if the following is satisfied [START_REF] Bubeck | Convex Optimization: Algorithms and Complexity[END_REF]:

1) The map Φ is strictly convex and differentiable.

2) The gradient of Φ takes all the possible values of R N , i.e., {∇Φ(x) : x ∈ D} = R N .

3) The gradient of Φ diverges at the boundary of D, i.e., lim x→∂D ∇Φ(x) = +∞.

It is easy to check the above properties are satisfied for the Euclidean mirror map Φ(x) = 1 2 x 2 over the domain D = R N , and the negative entropy mirror map Φ(x) = i∈N x i log(x i ) over the domain D = R N >0 .

Second part. For any i ∈ N , we can have two types of movements: If δ i < 0, then given that x t,i = 1, we evict with probability -δi yt,i . If δ i > 0, then given that x t,i = 0, we retrieve a file with probability δi 1-yt,i . Thus the expected movement is given by:

E [ x t+1 -x t 1 ] = i∈N E[|x t+1,i -x t+1,i |] (75) = i∈N E |x t+1,i -x t,i | x t,i = 0 P(x t,i = 0) + E |x t+1,i -x t,i | x t,i = 1 P(x t,i = 1) (76) = i∈N δ i 1 -y t,i 1 {δi>0} • (1 -y t,i ) + -δ i y t,i 1 {δi<0} • y t,i (77)
= i∈N |δ i | = i∈N |y t+1,i -y t,i | = y t+1 -y t 1 . (78)
D Φ (y t , z t+1 ) = Φ(y t ) -Φ(z t+1 ) -∇Φ(z t+1 ) T (y t -z t+1 ) = Φ(y t ) -Φ(z t+1 ) + ∇Φ(y t ) T (z t+1 -y t ) + (∇Φ(y t ) -∇Φ(z t+1 )) T (y t -z t+1 ) ≤ - ρ 2 y t -z t+1 2 1 + ηg T t (y t -z t+1 ) (79) ≤ - ρ 2 y t -z t+1 2 + ηL y t -z t+1 2 1
(80)

≤ η 2 L 2 2ρ . (81)
Eqs. ( 79)-(81) are obtained using the strong convexity of Φ and the update rule, Cauchy-Schwarz inequality, and the inequality axbx 2 ≤ max x axbx 2 = a 2 /4b as in the last step in the proof of [43, Theorem 4.2], respectively. Moreover, for any

t ∈ [T -1] it holds y t+1 -y t 1 ≤ 2 ρ D Φ (y t , y t+1 ) ≤ 2 ρ D Φ (y t , z t+1 ) - 2 ρ D Φ (y t+1 , z t+1 ) ≤ 2 ρ D Φ (y t , z t+1 ) ≤ 2η 2 L 2 2ρ 2 ≤ Lη ρ . (82)
The above chain of inequalities is obtained through: the strong convexity of Φ, the generalized Pythagorean inequality [43, Lemma 4.1], non-negativity of the Bregman divergence of a convex function, and Eq. (81), in respective order. The learning rate is η = O 1 √ T ; therefore, we finally get

T -1 t=1 y t+1 -y t 1 (82) ≤ LηT ρ = O( √ T ). (83)

IX. PROOF OF THEOREM IV.3

Proof. To prove the ψ-regret guarantee: (i) we first establish an upper bound on the regret of the AC ¸AI policy over its fractional cache states domain conv(X ) against a fractional optimum, then (ii) the guarantee is transformed in a ψ-regret guarantee over the integral cache states domain X in expectation.

Fractional domain guarantee. We establish first the regret of running Algorithm 1 with decisions taken over the fractional domain conv(X ). The following properties are satisfied: (i) The caching gain function G(r, y) is concave over its fractional domain conv(X ) for any r ∈ R (see Sec. IV-D).

(ii) The negative entropy mirror map Φ : D → R is With the above properties satisfied, the regret of Algorithm 1 with the gains evaluated over the fractional cache states {y G(r t , y) over the domain y ∈ conv(X ). We can only obtain a lower gain by restricting the maximization to a subset of the domain X ⊂ conv(X ). Therefore, we obtain:

t } T t=1 ∈ conv(X ) T is [43, Theorem 4.2] Regret T,conv(X ) (OMA Φ ) = sup {rt} T t=1 ∈R T T t=1 G(r t , y * ) - T t=1 G(r t , y t ) (84) ≤ D Φ (y * , y 1 ) η + ηh 2 T t=1 g t 2 ∞ ≤ D η + ηL 2 hT 2 . ( 85
T t=1 G(r t , y * ) ≥ T t=1 G(r t , x * ). (86)
Note that the components for x and y in U \ N are completely determined by the components in N . Take ψ = 1 -1/e. For every t ∈ {1, M, 2M, . . . , M T /M } and r ∈ R it holds

E [G(r, x t )] (45)
≥

E [Λ(r, x t )] (42)
≥ Λ(r, y t )

≥ ψG(r, y t ).

Moreover, consider the following decomposition of the time slots {1, 2, . . . , T

} = T 1 ∪ T 2 ∪ • • • ∪ T T /M +1
, where each T i represents the i-th freezing period, i.e., x t = x min(Ti) for t ∈ T i . Note that |T i | ≤ M for i ∈ {1, 2, . . . , T /M + 1}. Now we can decompose the total expected gain of the policy as

ψ T t=1 G(r t , x * ) - T t=1 E [G(r t , x t )] (86)
≤ ψ T t=1 G(r t , y * ) - T t=1 E [G(r t , x t )] = ψ T t=1 G(r t , y * ) - T /M +1 i=1 t∈Ti E [G(r t , x t )] (87)
≤ ψ T t=1 G(r t , y * ) -ψ T /M +1 i=1 t∈Ti G(r t , y min(Ti) ) = ψ T t=1 G(r t , y * ) -ψ T t=1 G(r t , y t ) + ψ T t=1 G(r t , y t ) -ψ T /M +1 i=1 t∈Ti G(r t , y min(Ti) ) (85) ≤ ψ • Regret T,conv(X ) (OMA Φ ) + ψ   T t=1 G(r t , y t ) - T /M +1 i=1 t∈Ti G(r t , y min(Ti) )   . (88)
The first equality is obtained through a decomposition of the time slots to T i for i ∈ {1, 2, . . . , T /M + 1}. It remains to bound the r.h.s of Eq. (88), i.e.,

This concludes the proof.

X. PROOF OF COROLLARY IV.3.1

We have the following

E [G T (x)] (45)
≥ E 1 T T t=1 Λ(r t , x t )

(42) ≥ 1 T T t=1 Λ(r t , x t ) (45)
≥ ψG T (ȳ).

We apply Jensen's inequality to obtain

G T (ȳ) ≥ 1 T T i=1 G T (y i ). (95)
It is easy to verify that G T (13) is concave, and has bounded subgradients under the l ∞ norm over the fractional caching domain conv(X ); moreover, the remaining properties are satisfied for the same mirror map and decision set. The regret of Algorithm 1 with the gains evaluated over the fractional cache states {y i } T i=1 ∈ conv(X ) T is [43, Theorem 4.2] is given by

where y * = arg max y∈conv(X )

G T (y).

We combine Eq. (94), Eq. (95), and Eq. (97) to obtain

E [G T (x)] ≥ G T (y * ) -(c k d + c f )h 2 log N h T , (98)
and G T (y * ) can only be larger than G T (x * ); thus, we also obtain

E [G T (x)] ≥ G T (x * ) -(c k d + c f )h 2 log N h T . ( 99
)
We conclude ∀ > 0 for a sufficiently large number of iterations T , x satisfies

E [G T (x)] ≥ 1 - 1 e - G T (x * ). (100)

XI. ADDITIONAL EXPERIMENTS

A. Redundancy

We quantify the redundancy present in the caches in Figure 14 (a), as the percentage of added objects to fill the physical cache. We also show the contribution of the dangling objects to the gain in Figure 14 (b), that does not exceed 2.0% under both traces.

B. Approximate Index Augmentation

We repeat the sensitivity analysis and show the caching gain when the different policies are augmented with an approximate index, and are allowed to mix the best object that can be served locally and from the server. Figure 15 shows the caching gain for the different caching policies and different values of the cache size h ∈ {50, 100, 200, 500, 1000} and k = 10. Figure 16 shows the caching gain for the different caching policies and different values of the retrieval cost c f , that is taken as the average distance to the i-th neighbor, i ∈ {2, 50, 100, 500, 1000}. The cache size is h = 1000 and k = 10.

C. Computation Time

We provide a comparison of the computation time of the different algorithms in Fig. 18. When the different LRU-like policies are not augmented with a global catalog index in Fig. 18

Fig. 1 :

 1 Fig.1: Subfigure (a) illustrates AC ¸AI's state adaptation. A time slot is initiated when a request r t is received. A virtual (fictitious) gain G(r t , y t ) and a physical gain G(r t , x t ) are incurred. The virtual cache adapts its fractional state by calling Online Mirror Ascent to obtain a new state y t+1 ∈ conv(X ) employing the subgradient of the virtual gain ∂ y G(r t , y t ), and the new state is randomly rounded to a valid cache state x t+1 ∈ X . Subfigure (b) depicts how AC ¸AI employs the two indexes (local catalog index and global catalog index). Approximate kNN queries are performed on each index, and the contents with the least overall costs are selected.

  M -1)(M +T ) , and rounding scheme COUPLEDROUNDING or DEPROUND with a freezing period M = Θ T β for β ∈ [0, 1), has a sublinear (1 -1/e)-regret in the number of requests, i.e.,

Fig. 2 :

 2 Fig. 2: Synthetic catalog of objects located on a 30 × 30 grid. The heatmap depicts the popularity distribution of objects in the grid.

  Optimal fractional static cache allocations 10 20

Fig. 3 :

 3 Fig. 3: The optimal fractional static cache allocations, and AC ¸AI's fractional static cache allocations under different values of the retrieval costs c f ∈ {1, 2, 3, 4} and of the number of neighbors k ∈ {1, 2, 3, 4, 5}.

Fig. 4 :

 4 Fig. 4: The gain of the optimal fractional static cache allocations (Gain(OPT Y )), its (1 -1 e )-approximation, and the gain obtained by AC ¸AI's fractional static cache allocations (Gain(AC ¸AI Y )) and static integral cache allocations (Gain(AC ¸AI X )) under different values of the retrieval cost c f ∈ {1, 2, 3, 4} and of the number of neighbors k ∈ {1, 2, 3, 4, 5}. For AC ¸AI's static integral cache allocations, we report 95% confidence intervals computed over 50 different runs. The gain of the fractional static cache allocations obtained by AC ¸AI overlaps with the gain of the optimal fractional static cache allocations.

Fig. 5 :Fig. 6 :Fig. 7 :

 567 Fig. 5: Caching gain for the different policies. The cache size is h = 1000 and k = 10.

Fig. 8 :

 8 Fig. 8: Caching gain for the different policies. The cache size is h = 1000, and k ∈ {10, 20, 30, 50, 100}.

3 Fig. 9 :

 39 Fig. 9: Caching gain for AC ¸AI for different values of η (top). Caching gain for SIM-LRU(middle) and CLS-LRU (bottom) for different values of the parameters (k , C θ ). SIFT1M trace.

  : η = 10 -5 Neg-entropy: η = 10 -4 Euclidean: η = 5 × 10 -7

Fig. 11 :

 11 Fig. 11: AC ¸AI caching gain improvement in comparison to the second best state-of-the-art similarity caching policy: contribution of approximate indexes and gradient updates. The cache size is h = 1000, and k ∈ {10, 20, 30, 50, 100}.

Fig. 13 :

 13 Fig. 13: Time-averaged and instantaneous cache occupancy under COUPLEDROUNDING. AC ¸AI is run with the learning rate η = 10 -5 over the Amazon trace. The cache size is h = 1000 and k = 10.

Giovanni

  Neglia is a researcher at Inria, France, since 2008, and holds a chair on Pervasive Sustainable Learning Systems at the 3IA Côte d'Azur (one of the French Interdisciplinary Institutes on Artificial Intelligence), since 2021. He received his Habilitation in 2017 from the Université Côte d'Azur, France, his PhD and electronic engineering degree from University of Palermo, Italy, respectively in 2005 and in 2001. Before joining Inria as a permanent researcher, he was a research scholar at the University Massachusetts Amherst, (2005) and a postdoc at Inria (2006-2007). His research activity focuses on modelling and performance evaluation of networked systems and proposals of new mechanisms to improve their performance. Currently, his main interests are networks of caches and distributed optimization for machine learning. Damiano Carra received the Laurea degree in telecommunication engineering from the Politecnico di Milano and the Ph.D. degree in Computer Science from the University of Trento. He is currently an Associate Professor with the Computer Science Department, University of Verona. His research interests include modeling and performance evaluation of large scale distributed systems. Ascent Similarity Caching with Approximate Indexes I. EQUIVALENT EXPRESSION OF THE COST FUNCTION Lemma 1. Let us fix the threshold c ∈ N ∪ {0}, r ∈ R and i ∈ U. The following equality holds min

  (iv) The Bregman divergence D Φ (y * , y 1 ) is bounded by a constant D where y * = arg max y∈conv(X ) T t=1 G(r, y) and y 1 = arg min y∈conv(X )∩D Φ(y) is the initial fractional cache state (Lemma 7).

)

  Integral domain guarantee. Let x * = arg max x∈X T t=1 G(r t , x) and y * = arg max y∈conv(X ) T t=1 G(r t , y). The fractional cache state y * ∈ conv(X ) is obtained by maximizing T t=1

∂t

  t , y min(Ti) ) = T /M +1 i=1 t∈Ti G(r t , y t ) -G(r t , y min(Ti) ) y G(r t , y min(Ti) ) • y ty min(Ti) concavity of G(r t , •) ≤ T /M +1 i=1 t∈Ti ∂ y G(r t , y min(Ti) ) =min(Ti)y t+1y t 1 triangle inequality and definition of L M (M -1) 2 update cost upper bound in Eq. (82)= L 2 η 2ρ (M -1) (T + M ) = hL 2 η 2 (M -1) (T + M ) we have ρ = 1/h.(90)Thus, by bounding r.h.s of Eq. (88) in Eq. (90) we getψ T t=1 G(r t , x * ) -T t=1 E [G(r t , x t )] (M -1)(M +T ))giving the tightest upper bound we obtainψ T t=1 G(r t , x * ) -T t=1E [G(r t , x t )] ≤ ψL 2Dh(T + (M -1)(T + M )) (M -1)(T + M )).

G

  T (y i ) = T G T (y * )of the equality by T , and move the gain attained by AC ¸AI to the l.h.s to get1 T T i=1 G T (y i ) ≥ G T (y * ) -(c k d + c f )h 2 log N h T ,

  Storage redundancy of the LRU-based policies under SIFT1M trace.

  Storage redundancy of the LRU-based policies under Amazon trace.

  The average gain of the dangling objects under SIFT1M trace.

  The average gain contribution of the dangling objects under Amazon trace.

Fig. 14 :

 14 Fig. 14: Storage redundancy percentage and gain contribution for the different policies. The cache size h = 1000, and k ∈ {10, 20, 30, 50, 100}.

15 :

 15 Figure 17 shows the caching gain for the different caching policies and different values of k ∈ {10, 20, 30, 50, 100} and h = 1000. Caching gain of the different policies when augmented with the approximate index, for different cache sizes h ∈ {50, 100, 200, 500, 1000} and k = 10.

  (a), AC ¸AI experiences a higher computation time per iteration. When the different LRU-like policies are augmented with a global catalog index in Fig.18 (b), AC ¸AI has a similar computation time to the different policies except for the simple vanilla lru policy. Nonetheless, in both settings AC ¸AI computation time remains comparable and approximately within factor 4 w.r.t the computation time of the different policies. Due to space limitation we cannot add this figure to the main text.

Fig. 16 :

 16 Fig.16: Caching gain for the different policies and different retrieval cost when augmented with the approximate index. The retrieval cost c f is taken as the average distance to the i-th neighbor, i ∈ {2, 10, 50, 100, 500, 1000}. The cache size is h = 1000 and k = 10.

Fig. 17 :

 17 Fig. 17: Caching gain for the different policies when augmented with the approximate index. The cache size is h = 1000, and k ∈ {10, 20, 30, 50, 100}.

Fig

  Fig. Time-averaged computation time of AC ¸AI and the different policies LRU, SIM-LRU, CLS-LRU, and QCACHE(a) w/o an approximate global catalog index, and (b) w/ an approximate global catalog index. Experiment run over the Amazon trace, cache size h = 1000, parameter k = 10, η = 10 -4 , retrieval cost c f is set to be the distance to the 50-th closest neighbor in N .

TABLE I :

 I Notation Summary

		Notational Conventions
	1χ [n] conv(S) Convex hull of a set S Indicator function set to 1 when condition χ is true Set of integers {1, 2, . . . , n}
		System Model
	N U x i h r / R c f c d (r, o) c(r, o) π r α r i K r kNN(r, S) Set of k closest objects to r in S ⊂ N according to c(r, • ) Catalog of N objects Augmented catalog of 2N objects 0-1 indicator variable set to 1 when i ∈ N is cached, and x i = 1 -x i-N for i ∈ U \ N Cache capacity Request / Request set Retrieval cost Dissimilarity cost of serving object o to request r Overall cost of serving object o to request r Permutation of the elements of U , where π r i gives the i-th closest object to r Cost difference between the (i + 1)-th smallest cost and the i-th smallest cost when serving request r The order of the largest possible cost when r is requested. x / X Cache state vector / Set of valid cache states t / T Time slot / Time horizon C(r, x) Total cost to serve request r under cache allocation x G(r, x) Total caching gain to serve request r under cache allocation x C UC,T Update cost of the system over time horizon T G T (x) Time-averaged caching gain
		AC ¸AI
	Φ D y η g t M Φ S ( • )	Mirror map Domain of the mirror map Fractional cache state Learning rate Subgradient of G(rt, y) at point y t Negative entropy Bregman projection onto the set S Freezing period
	c k d ψ	Upper bound on the dissimilarity cost of the k-th closest object for any request Static optimum discount factor

  is requested at any time slot t with probability p o ∝ e

	-	d 2 o 2×6 2

  B. Proof of Theorem IV.2 Proof. The negative entropy mirror map Φ is ρ = 1 h strongly convex w.r.t the norm • 1 over D ∩ conv(X ) (see [37, Ex. 2.5]), and the subgradients are bounded under the dual norm • ∞ by L, i.e., for any r t ∈ R, y t ∈ conv(X ), and t ∈ [T ] we have g t ∞ ≤ L (Lemma 6). For any time slot t ∈ [T -1], it holds:

In Sec. IV-D, we discuss to which extent this assumption can be removed.

The vector x has redundant components, but such redundancy leads to more compact expressions in what follows.

We discard the initial part of the trace because it contains requests only for a small set of objects (likely the set of products to crawl was progressively extended during the measurement campaign in[START_REF] Mcauley | Image-Based Recommendations on Styles and Substitutes[END_REF]).

Under a stationary request process, a smaller learning rate would lead to converge slower but to a solution closer to the optimal one. Under a nonstationary process, a higher learning rate may allow faster adaptivity. In this trace, the two effects almost compensate, but see also Fig.10.

Supplementary Material for Paper:

Proof. For any request r ∈ R, the function f (r,i) (y) min kσ r i , i j=1 y π r jσ r i is a concave function, i.e., a minimum of two concave functions (a constant and an affine function). The subdifferential of the function at point y, using Theorem [START_REF] Mordukhovich | Geometric Approach to Subdifferential Calculus[END_REF]Theorem 8.2 ] is given as

where conv ( • ) is the convex hull of a set. Thus, a valid subgradient g (r,i) (y) of f (r,i) at point y can be picked as

Note that ∂ ∂y l i j=1 y π r j = 1 {y l appears in the sum and y l+N =1-y l does not} (55)

The l-th component of the subgradient g (r,i) (y) is given by

The constant c k d is an upper bound on the dissimilarity cost of the k-th closest object for any request in R, and c f is the retrieval cost.

Proof. For any time slot t ∈ [T ] we have

Note that L 2 ∂ y G(r, y) 2 can be as high as √ N L and N can be very large; moreover, the regret upper bound is proportional to L 2 instead of L when the Euclidean map is used as a mirror map (see [START_REF] Bubeck | Convex Optimization: Algorithms and Complexity[END_REF]Theorem 4.2]). This justifies why it is preferable to work with the negative entropy instantiation of OMA rather than the classical Euclidean setting.

B. Bregman Divergence Bound

Proof. It is easy to check that y 1,i = h N , ∀i ∈ N (y 1 has maximum entropy); moreover, we have Φ(y) ≤ 0, ∀y ∈ conv(X ). The first order optimality condition [START_REF] Bubeck | Convex Optimization: Algorithms and Complexity[END_REF]Proposition 1.3] gives -∇Φ(y 1 )

T (yy 1 ) ≤ 0, ∀y ∈ conv(X ). We have

VIII. UPDATE COSTS

A. Proof of Theorem IV.1

Proof.

First part. We show that E [x t+1 ] = y t+1 . Take δ y t+1y t . If δ i > 0 for i ∈ N , then:

If δ i < 0 for i ∈ N , then: