Anirudh Sabnis
email: asabnis@cs.umass.edu

Si Tareq

Salem

Giovanni Neglia
email: giovanni.neglia@inria.fr

Michele Garetto
email: garetto@di.unito.it

Emilio Leonardi
email: leonardi@polito.it

Ramesh K Sitaraman
email: ramesh@cs.umass.edu

GRADES: Gradient Descent for Similarity Caching

A similarity cache can reply to a query for an object with similar objects stored locally. In some applications of similarity caches, queries and objects are naturally represented as points in a continuous space. This is for example the case of 360 • videos where user's head orientation-expressed in spherical coordinates-determines what part of the video needs to be retrieved, or of recommendation systems where a metric learning technique is used to embed the objects in a finite dimensional space with an opportune distance to capture content dissimilarity. Existing similarity caching policies are simple modifications of classic policies like LRU, LFU, and qLRU and ignore the continuous nature of the space where objects are embedded. In this paper, we propose GRADES, a new similarity caching policy that uses gradient descent to navigate the continuous space and find appropriate objects to store in the cache. We provide theoretical convergence guarantees and show GRADES increases the similarity of the objects served by the cache in both applications mentioned above.

I. INTRODUCTION

Similarity searching [START_REF] Chávez | Searching in metric spaces[END_REF] is a key building block for a large variety of applications including multimedia retrieval [START_REF] Berchtold | Fast parallel similarity search in multimedia databases[END_REF]- [START_REF] Falchi | Similarity caching in large-scale image retrieval[END_REF], recommender systems [START_REF] Pandey | Nearest-neighbor caching for content-match applications[END_REF]- [START_REF] Sermpezis | Soft cache hits: Improving performance through recommendation and delivery of related content[END_REF], genome study [START_REF] Yan | Genome-wide similarity search for transcription factors and their binding sites in a metal-reducing prokaryote geobacter sulfurreducens[END_REF], [START_REF] Auch | Standard operating procedure for calculating genome-to-genome distances based on high-scoring segment pairs[END_REF], machine learning training [START_REF] Weston | Memory networks[END_REF]- [START_REF] Santoro | Meta-learning with memory-augmented neural networks[END_REF], and serving [START_REF] Crankshaw | Scalable training and serving of personalized models[END_REF]- [START_REF] Salem | Towards inference delivery networks: Distributing machine learning with optimality guarantees[END_REF]. Given a query for an object, the goal is to retrieve one or more similar objects from a repository. In the traditional setting, a cache is used to speed up object retrieval: once similarity search has identified the set of similar objects in the global catalog, the system checks if some of these objects are stored in the cache memory. In this setting, the cache performs a local exact lookup for the objects. Similarity search over the catalog can be itself a time-consuming operation, equivalent to linearly scanning the whole catalog [START_REF] Weber | A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces[END_REF]. Moreover, if users generating the queries are located far from the repository, they may experience long delays.

In order to solve these problems, 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, almost at the same time, a different use of the cache: clients' requests are directly forwarded to the cache; then the cache performs a similarity search over the set of locally stored objects and possibly serves the requests without the need to forward the query to the (remote) repository. The cache thus reduces the overall serving time at the cost of providing objects less similar than those the repository would provide. This operation was named similarity caching, in contrast to the traditional exact caching. As recognized in [START_REF] Neglia | Similarity caching: Theory and algorithms[END_REF], the idea of similarity caching has been rediscovered a number of times under different names: recognition caches [START_REF] Drolia | Cachier: Edgecaching for recognition applications[END_REF], [START_REF] Drolia | Precog: Prefetching for image recognition applications at the edge[END_REF], approximate deduplication [START_REF] Guo | Potluck: Cross-application approximate deduplication for computation-intensive mobile applications[END_REF], semantic caches [START_REF] Venugopal | Shadow puppets: Cloud-level accurate AI inference at the speed and economy of edge[END_REF], prediction caches [START_REF] Crankshaw | Clipper: A low-latency online prediction serving system[END_REF], approximate caches [START_REF] Kumar | Accelerating deep learning inference via freezing[END_REF], and soft caches [START_REF] Sermpezis | Soft cache hits: Improving performance through recommendation and delivery of related content[END_REF], [START_REF] Spyropoulos | Soft cache hits and the impact of alternative content recommendations on mobile edge caching[END_REF].

In many applications similarity is quantified using supervised machine learning techniques that collectively go under the name of distance metric learning [START_REF] Bellet | Metric learning[END_REF]. These techniques learn how to map similar objects to vectors in R d (called embeddings) that are close according to p-norm distances, cosine similarity, or Mahalanobis distances. Requests and objects live then in a continuous space. For instance, in augmented reality applications we often require to identify similar objects: the image is coded into a query, i.e., an embedding in R d , and the application logic finds similar images to be returned to the user [START_REF] Drolia | Cachier: Edgecaching for recognition applications[END_REF]- [START_REF] Guo | Foggycache: Cross-device approximate computation reuse[END_REF], [START_REF] Venugopal | Shadow puppets: Cloud-level accurate AI inference at the speed and economy of edge[END_REF]. This is also the case for other potential applications of similarity caching like 360 • videos, where requests for parts of the video are implicitly dictated by the user's head orientation expressed in spherical coordinates.

Existing dynamic policies for similarity caches adapt and extend well-known exact caching policies, like LRU and LFU, to deal with the notion of a dissimilarity cost, i.e., how distant is a cached object from the request. As a consequence, they treat requests and objects as discrete entities and ignore the continuous representation space.

This paper proposes GRADES, the first similarity caching policy designed to exploit object embeddings in R d with a distance that captures dissimilarity costs. While previous policies update the cache state by replacing a cached object with (in general) a distant one-corresponding to "jumps" in the representation space-GRADES incrementally updates the (embedding of) each object using a gradient descent step to progressively reduce the dissimilarity cost. Qualitatively, as shown in Fig. 1, the objects in the cache smoothly move in the representation space to find their optimal position, i.e., where they can serve a large number of requests with small dissimilarity cost.

We prove that in a stationary setting, with an opportune choice of the gradient step sizes, GRADES converges to a cache configuration that corresponds to a critical point of the service cost (likely a local minimum). Our experiments based on realistic traces (made available online [START_REF]Similarity caching trace repository[END_REF]) shows that GRADES outperforms existing similarity caching policies both for 360 • videos and recommendation systems applications.

The paper is organized as follows. After an overview of the related work in Sec. II, we present the formal problem definition in Sec. III. We introduce GRADES and its theoret-

II. RELATED WORK

Most existing policies for similarity caches generalize wellknown exact caching policies, like LRU and LFU, to the new context, where besides the exact hits and misses, approximate hits are also possible. For example SIM-LRU [START_REF] Pandey | Nearest-neighbor caching for content-match applications[END_REF], [START_REF] Crankshaw | Scalable training and serving of personalized models[END_REF] maintains objects in an ordered queue and serves an object from the cache if its distance to the requested object is lesser than a given threshold (an approximate hit occurs). The object is then moved to the front of the queue. When no object in the cache is close enough to the request, there is a miss. The object is then retrieved from the server and inserted at the front of the queue, possibly evicting objects from the back. RND-LRU [START_REF] Pandey | Nearest-neighbor caching for content-match applications[END_REF] is a variant of SIM-LRU where the threshold is replaced by a random variable that is a function of the dissimilarity cost i.e., the cost associated to the distance between a cached object and the request. As with SIM-LRU and RND-LRU that are adaptations of LRU, qLRU-∆C [START_REF] Neglia | Similarity caching: Theory and algorithms[END_REF] modifies qLRU [START_REF] Garetto | A unified approach to the performance analysis of caching systems[END_REF] by introducing a refresh probability that depends on the similarity. Finally, DUEL [START_REF] Neglia | Similarity caching: Theory and algorithms[END_REF] is inspired by LFU, and decides which object to evict by tracking the dissimilarity cost i.e., the cost associated to the distance between a cached object and the request accumulated over a given time-window. In our experiments we compare GRADES with SIM-LRU, qLRU-∆C, and DUEL. Recently, there has been preliminary work that shows that coordinating decisions in a network of similarity caches is particularly challenging [START_REF] Garetto | Content placement in networks of similarity caches[END_REF], [START_REF] Zhou | Adaptive offline and online similarity-based caching[END_REF]. GRADES can be adapted to work with a network of similarity caches by tweaking the algorithm to use the cost to retrieve content from a parent/neighboring cache in place of the cost to retrieve content from a remote server. This change, however, does not ensure optimal coordination amongst the similarity caches in the network.

Our algorithm was inspired by the work from Jorge Cortés et al. on coordination algorithms for mobile agents [START_REF] Cortes | Coverage control for mobile sensing networks[END_REF]- [START_REF] Cortés | Spatially-distributed coverage optimization and control with limited-range interactions[END_REF]). In their setting mobile agents (e.g., drones) place themselves in the space to be able to detect the largest number of events in the environment. Similarly, the objects in the cache need to position themselves to optimally serve the requests appearing over the space. Despite similarities at a high-level, their work focuses on a two-dimensional space and needs to take into account agents' movement and communication constraints that do not hold in our context.

From another point of view, GRADES gradient update can be considered as a generalization of stochastic K-means algorithms, where the function we want to minimize is not necessarily the squared Euclidean distance (as it is the case for K-means). Our proofs rely on techniques for non-convex optimization originally proposed in [START_REF] Bottou | On-line learning and stochastic approximations[END_REF] also to study K-means.

Online caching policies based on gradient methods have been proposed in the stochastic request setting (see, e.g., [START_REF] Ioannidis | Distributed caching over heterogeneous mobile networks[END_REF], [START_REF] Ioannidis | Adaptive caching networks with optimality guarantees[END_REF]), and, more recently, in the adversarial setting [START_REF] Paschos | Learning to cache with no regrets[END_REF], [START_REF] Salem | No-Regret Caching via Online Mirror Descent[END_REF]. In these papers, the gradient step updates a vector of length equal to the catalog size, whose component i (in [0, 1]) represents which fraction of object i should be stored in the cache or alternatively the probability to store i in the cache. Differently from this line of work, GRADES uses the gradient step to modify the objects in the cache and maintains a vector of size equal to the cache-then much smaller than the catalog size.

A costly operation in any similarity search system is to find the closest object to the request. A simple solution is to index the collection, e.g., with a tree based data structure, to find the exact closest object. Unfortunately, when the number of dimensions d of the representation space exceeds 10, such an approach has a computational cost 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]. For this reason a number of approximate search techniques have been developed, which trade accuracy for speed and provide one or more points close to the request, but not necessarily the closest. 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], pivots [START_REF] Naidan | Permutation search methods are efficient, yet faster search is possible[END_REF], or graphs [START_REF] Malkov | Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs[END_REF]. In the experiments in this paper, we have performed an exact similarity search, but any of these approximated search techniques could be used in GRADES.

The paper [START_REF] Li | Accurate learning or fast mixing? Dynamic adaptability of caching algorithms[END_REF] models different caching policies as Markov chains to study the tradeoff between the time required to estimate the popularity distribution of the requested objects and the accuracy of their estimation. GRADES allows to balance these contrasting goals by tuning two parameters: the learning rate and the grafting parameters (see e.g., Fig. 7 and Fig. 8). Our experiments show that GRADES achieves a better tradeoff than state-of-the-art similarity caching policies.

The original envisaged applications of similarity caches were content-based image retrieval (CBIR) [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]. In a CBIR system, given an image (used as a query), users can query the CBIR system to obtain images that are most similar to the query by comparing their visual contents. Here, a cache can respond with the most similar images that are available locally. Similarly, in the case of contextual advertising, the cache can provide ads similar to those matching the user profile [START_REF] Pandey | Nearest-Neighbor Caching for Content-Match Applications[END_REF]. Likewise, recommender systems can leverage similarity caches [START_REF] Sermpezis | Soft cache hits: Improving performance through recommendation and delivery of related content[END_REF], [START_REF] Spyropoulos | Soft cache hits and the impact of alternative content recommendations on mobile edge caching[END_REF]: a recommender system can save operating costs and decrease its response time through recommendation of relevant contents from a cache to user-generated queries, i.e., in case of a cache miss, an application proxy (e.g., YouTube) running close to the helper node (e.g., at a multi-access edge computing server) can recommend the most related files that are locally cached. More recently, similarity caches have been employed extensively for machine learning based inference systems to store queries and the respective inference results to serve future requests, for example, prediction serving systems [START_REF] Crankshaw | Clipper: A low-latency online prediction serving system[END_REF], image recognition systems [START_REF] Drolia | Cachier: Edgecaching for recognition applications[END_REF], [START_REF] Drolia | Precog: Prefetching for image recognition applications at the edge[END_REF], [START_REF] Guo | Potluck: Cross-application approximate deduplication for computation-intensive mobile applications[END_REF], object classification on the cloud [START_REF] Venugopal | Shadow puppets: Cloud-level accurate AI inference at the speed and economy of edge[END_REF], caching hidden layer outputs of a neural network to accelerate computation [START_REF] Kumar | Accelerating deep learning inference via freezing[END_REF], network traffic classification tasks [START_REF] Finamore | Accelerating deep learning classification with error-controlled approximate-key caching[END_REF]. The cache can indeed respond with the results of a previous query that is very similar to the current one, thus reducing the computational burden and latency of running complex machine learning inference models.

We remark that a prior version of the work has been published in [START_REF] Sabnis | Grades: Gradient descent for similarity caching[END_REF]. Here, we extend it by providing a complete proof for our theoretical claims in the Appendix and new experimental results in Sec. V (depicted in Fig. 6, Fig. 9, and Fig. 11).

III. PROBLEM DEFINITION

We consider a similarity search system where a server answers users' queries with the most similar object from a locally stored catalog. In some applications, it is required to serve k similar cached objects instead of a single object. GRADES can be augmented to provide k similar answers using the same techniques introduced in [3], [START_REF] Pandey | Nearest-neighbor caching for content-match applications[END_REF], [START_REF] Salem | AC ¸AI: ascent similarity caching with approximate indexes[END_REF]. For example, the cache may store key-value pairs, where the key is a past query and the value is the set of k closest objects to the query. Upon a new query, the cache looks for the most similar key stored locally and returns the corresponding set of objects.

Requests satisfied by the server incur a retrieval cost C r , which quantifies the delay the user experiences to retrieve the object from the remote server, and/or the additional load for the server, and/or the additional load for the network. Alternatively, the request may be satisfied by a similarity cache which stores a subset of the catalog. The cache provides, in general, a less similar object than what the server could provide, but incurs a negligible retrieval cost, as, for example, it is located closer to the user, or uses a faster memory storage or can perform faster lookup operations on the smaller set of stored contents.

We assume that each request or object in the catalog can be represented as a point in the d-dimensional Euclidean space R d . In what follows we will refer to such representations as embeddings and, for the sake of simplicity, we will identify each object/request with its embedding (e.g., we will say that object x belongs to R d ). We assume all objects have the same size and the cache can store up to k objects.

Our model of the system is similar to the one considered in previous papers on similarity caching in the continuous setting like [START_REF] Pandey | Nearest-neighbor caching for content-match applications[END_REF], [START_REF] Neglia | Similarity caching: Theory and algorithms[END_REF]. Let Z and X denote the catalog and the set of possible requests, respectively. Both sets may be finite or infinite, but we require them to be compact (to be able to retrieve a closest object to a given request). The "quality" of a similarity search for x depends on how similar the response object z is to the request. We assume the dissimilarity cost is quantified by the function C d (x, z) = h( x -z ), where h : R → R + is a non-decreasing non-negative function and • is a norm in R d (e.g., the Euclidean one). For example Faiss (Facebook AI Similarity Search) library [START_REF] Faiss | A library for efficient similarity search[END_REF] for multimedia retrieval supports all p-norms for

p ∈ [1, ∞].
The state of the cache at time t is given by the set of objects S t currently stored in it, S t = {y 1 t , y 2 t , . . . , y k t }, with y i t ∈ X ⊂ R d . Requests arrive first at the cache. Given a request for object x t at time t, let i t denote the index of the most similar object to the request, i.e., i t ∈ arg min i=1,...,k C d x t , y (i) t (if there are many equally similar ones we arbitrarily select one). If the cache satisfies the request x t , it will use content y (it) t , and the user will incur the dissimilarity cost

C d (x t , S t ) C d x t , y (it) t = min y∈St C d (x t ,
y), but the retrieval cost is negligible. Alternatively, the cache can forward the request to the server, where it will be satisfied by the most similar object in the catalog. The request will generate the retrieval cost C r , and the user will experience the dissimilarity cost

C d (x t , Z) = min z∈Z C d (x t , z) ≤ C d (x t , S t ).
Ideally, the cache should compare the costs of serving request locally (C d (x t , S t )) and from the server (C d (x t , Z)+C r ) and select the most convenient action. But, in order to evaluate C d (x t , Z), the cache would need to store locally metadata for the whole set Z and find the closest object in it. The memory and computation requirements could defeat the whole utility to have a cache. For this reason we consider the cache does not know C d (x t , Z), but it is easy to adapt our algorithm when it is not the case and its theoretical guarantees still hold.

In the impossibility to compare C d (x t , S t ) with the requestdependent value C d (x t , Z)+C r , the cache compare C d (x t , S t ) with a constant threshold value C θ . If C d (x t , S t ) ≤ C θ , the cache serves the request locally, otherwise it forwards it to the server. We assume C θ is set once and for all offline. Figure 2 illustrates how requests are served.

As

C d (x t , S t ) = C d x t , y (it) t
, the final cost to serve request x (denoted by C(x t , S t )) depends only on y

(it) t : C(x t , S t ) = C x t , y (it) t = C d x t , y (it) t , if C d x t , y (it) t ≤ C θ , C r + C d (x t , Z) , otherwise. (1)
After a request, the cache can update its state. As updates can themselves generate retrieval costs, we restrain to reactive policies that can only update their state by inserting the object retrieved from the server to satisfy a request.

In our setting, we assume that the two costs, C r and C d , can be expressed in the same unit. For instance, the two costs can quantify different aspects contributing to the overall user's quality of experience (QoE). The dissimilarity cost function C d (x, y) = h(||x -y||) can describe the QoE loss for the end user upon receiving a dissimilar object, while C r can capture the QoE loss due to the experienced delay. As in our model, the ITU-T E-model combines additively different metrics, such as signal-to-noise-ratio, packet loss ratio, and delay, to obtain a single scalar QoE rating for voice communications [START_REF] Bergstra | recommendation g.107 : The e-model, a computational model for use in transmission planning[END_REF].

y i . If x is closer to y i than the critical radius R θ (such that h (R θ ) = C θ ),
x receives y i as reply, otherwise (it falls in the gray shaded area) it generates a miss.

More in general, it is quite common in multi-objective resource allocation problems to express the cost as a weighted sum of the different objective functions [START_REF] Liu | A review on multi-objective optimization framework in wind energy forecasting techniques and applications[END_REF]- [START_REF] Carra | Elastic provisioning of cloud caches: A cost-aware ttl approach[END_REF].

In our theoretical analysis in Sec. III, we consider the case when requests arrive according to a Poisson process and are i.i.d. distributed. In the finite case (|X | < ∞), we recover the classic independent reference model [START_REF] Coffman | Operating systems theory[END_REF], where object x is requested with rate λ x . In the continuous case, we need to consider a spatial density of requests and objects in a set A ⊂ X are requested with rate A λ x dx.

Under the above assumptions, for a given cache state S = {y 1 . . . y k }, we can compute the corresponding expected cost to serve a request:

C(S)

x λ x C(x, S), finite case X λ x C(x, S) dx, continuous case.

(

) 2
Finding an optimal set of objects S * to store in the cache that minimizes the cost C(S) is NP-hard as it is a generalization of the problem considered in [START_REF] Neglia | Similarity caching: Theory and algorithms[END_REF] (where C d (x, Z) = 0 for each x ∈ X ). Nevertheless, for the continuous case, we propose a dynamic gradient descent based algorithm, that, under the stationary request process, can achieve a stationary point of C(S). The gradient descent based algorithm is a natural choice for the continuous setting; the algorithm takes a descent step to decrease C(S) at each time step. Further, in Sec. IV-C, we describe an adaptation of the proposed algorithm for the finite case.

IV. A GRADIENT-BASED ALGORITHM

The key idea of our algorithm is to let the objects stored in the cache gradually "move" in the space R d to reach a configuration where they can be used as approximate answers for a large number of requests (see Fig. 1). Upon a request at time t for x t , the most similar object in the cache, y (it) t , is moved in the direction opposite to the gradient of the service cost (∇ y C(x t , y (it) t )) proportionally to a time-varying stepsize (or learning rate) η t :

y (it) t+1 = y (it) t -η t ∇ y C x t , y (it) t . ( 3
)
It is possible to prove that C(x, y) is differentiable everywhere and then the gradients in (3) exist with probability 1 when the request process is continuous. 1 When the request process is discrete, the probability that the gradient ∇ y C(x t , y t ) does not exist may be non-zero, but we can then perturb the request by a small random vector ∈ R d and consider ∇ y C(x t + , y t ).

Note that the algorithm is oblivious to the request rate (λ xt ) of the object x t . However, every time a request is made for object x t , the most similar object in the cache (y (it) t ) is moved in the direction of the requested object. Therefore, the algorithm dynamics are sensitive to λ xt .

An attentive reader may frown upon the simple algorithm (3). First, it potentially updates the cache upon every request, even when C d (x t , y (i) t ) ≤ C θ and the cache would not need to retrieve any object. Second, even if y (i) t is the embedding of an object in the catalog, y (i) t+1 may not correspond to any object in the catalog.

In the following sections we address all issues mentioned above. After having refined the update rule (3) (Sec. IV-A), we prove that this idealized algorithm indeed converges to a critical point of C(S) (Sec. IV-B). Then, in Sec. IV-C we present a practical algorithm which 1) satisfies all our requirements, 2) keeps the state of the cache "close" to the state of the idealized algorithm, and 3) is more reactive and thus more suitable to non-stationary request processes.

A. Introducing a Projection

As requests are only for objects in the bounded set X , there exists a norm-2 ball with radius R-B 2 (R) = {y ∈ R d , y 2 ≤ R})-such that X ⊂ B 2 (R) and C(x, y) = C r for each y / ∈ B 2 (R) and x ∈ X . There is no advantage to store in the cache objects that do not belong to B 2 (R) as they do not contribute to approximate any request. We then modify (3) in order to make closer to B 2 (R) any cached object y (i) t that the gradient update may have brought out of B 2 (R). We write

y (i) t+1 = y (i) t -η t g (i) t , (4)
g (i) t =        ∇ y C x t , y (i) t , if (i = i t ) ∧ y (i) t ∈ B 2 (R) f ( y (i) t 2 -R) y (i) t y (i) t 2 , if y (i) t / ∈ B 2 (R), 0, otherwise,
where f (•) is an increasing non negative function (so that -g

(i)
t points to the origin of the space). For technical reasons that will be required in the proof of Theorem IV.2, we want

f (0) = f (0) = f (0) = f (0) = 0, and f (∞) ∈ Θ(1). For these reasons, we select f (u) = d du u 4 1+u 2 = 2u 3 2+u 2
(1+u 2 ) 2 for the proof. 1 As far as all the y (i) t are different, ∇yC(x, y

(i t ) t
) exists for all the points in x ∈ X but at most for a measure zero set: the set of points for which ∇yC d (x, y (i) t ) does not exist, the points for which x-y

(i) t = x-y (j) t for i = j, and finally the set of points in ∂{x ∈ R d : C d (x, y (i) t ) > C θ },
where ∂A denotes the boundary of the set A.

B. Convergence

In this section we provide convergence results for the basic algorithm described in (4). We assume the cache update rule generates embeddings that always correspond to objects in the catalog. Moreover, we will ignore the cost of updates made after the request is served. These two simplifications will be removed in the next section.

It will be useful to denote the cache state as a vector y t = (y t,1 , . . . , y t,k ) ∈ R k×d , obtained by concatenating the embeddings of the different objects in the cache. Similarly, we define the different costs as function of y t and then write C d (y t ), C(y t ), and C(y t ). We are now going to prove that algorithm (4) converges almost surely to a stationary point of C(y) and the trajectory of y t is bounded almost surely.

Lemma IV.1. Let the learning rate η t be selected so that

+∞ t=1 η t = +∞ and +∞ t=1 η 2 t < +∞. The sequence (y t ) is bounded almost surely.
The proof of the lemma is in Appendix A. The lemma is used in the proof of the following convergence result.

Theorem IV.2. Let the learning rate η t be selected so that

+∞ t=1 η t = +∞ and +∞ t=1 η 2 t < +∞. If C(•) is continuously differentiable up to the second order then lim inf t→∞ ∇ y C(y t ) 2 = 0 a.s. If C(•) is continuously differentiable up to the third order then lim t→∞ ∇ yt C(y t ) = 0 a.s.
The proof of Theorem IV.2 is in Appendix B. Our proof relies on techniques for non-convex optimization originally proposed in [START_REF] Bottou | On-line learning and stochastic approximations[END_REF]. We think it is possible to derive similar results, under different hypotheses, using the approach based on ordinary differential equations proposed in [START_REF] Borkar | Stochastic Approximation: A Dynamical Systems Viewpoint[END_REF].

Theorem IV.2 states that the sequence (y t ) converges to a critical point of C(•), i.e., a point where the gradient is zero. This may be a saddle point, a local maximum or a local minimum of C(•). The latter is more likely as it is the only one locally stable. The saddle points and local maxima of C(•) are not stable, as on reaching either of these two types of points, requests that appear in the neighborhood may perturb y t and the gradient descent algorithm moves y t away from these points. Given the stochastic nature of the request process this is highly likely to happen.

C. Implementation

In this section we present our complete caching policy GRADES, whose pseudo-code is in Algorithm 1. Theorem IV.2 shows that the basic gradient update (4) attains a critical point of the expected cost C(•). Nevertheless, we have assumed that this update rule always generates embeddings in R d that correspond to objects in the catalog. However, if the catalog has a finite number of objects, this is unlikely to happen, as the update (4) can potentially generate any real vector. Moreover, the update (4) may modify an object in the cache upon each request and then generate a high load on the server and the network to retrieve the new modified objects.

Algorithm 1 GRADES 1: Let k be the cache size and x the object requested

2: if (|S V,t | < k) ∧ (x / ∈ S V,t ) then still space in cache 3: Insert x in VC 4:
Retrieve and insert ρ(x) in PC 5:

µ(x) = ρ(x)

6: y V = arg min y∈S V,t C d (x, y) 7: Update S V,t according to (4) 8: if C d (x, y V ) ≤ C θ then virtual hit 9: if x -y V < µ(y V ) -y V then x approximates y V better than µ(y V ) 10: Evict µ(y V ) 11:
Retrieve and Insert ρ(x) in PC 12:

µ(y V ) = ρ(x) 13:
GRAFT HIT UPDATE(x, S V,t )

µ(ρ(x)) = ρ(x) 22: y P = ρ(x) 23: if (C d (x, y P ) ≤ C θ ) ∨ (ρ(x) inserted in PC) then 24:
Serve y P 25: else 26:

Retrieve and Serve ρ(x)

In Sec. IV-C1 we describe how our algorithm addresses these issues. We then move on in Sec. IV-C2 to describe some additional features that provide a higher adaptivity of the algorithm to deal with highly non-stationary request processes, allowing for some random insertions with probability p.

1) Dealing with Finite Catalogue and Reducing Server Load: We propose to maintain a virtual cache (VC) and a physical cache (PC). The VC only stores some metadata, but no actual object; its use is common to other policies like 2-LRU [START_REF] Garetto | A unified approach to the performance analysis of caching systems[END_REF] or ADAPTSIZE [START_REF] Berger | Adaptsize: Orchestrating the hot object memory cache in a content delivery network[END_REF]. The VC is sometimes called shadow cache.

In our case the VC stores k vectors in R d that are updated upon each request according to the basic algorithm in (4). These vectors are the embeddings of the objects we would like to store in the cache, but, as discussed above, such objects may not exist, or they may not have been retrieved yet from the server. The PC contains objects from the catalog together with their embeddings.

At a high level, the main idea behind GRADES is to maintain the PC as close as possible to the VC. We use then the current state of the VC to drive updates at the PC, i.e., object eviction and insertion. In particular each vector y V in the VC is matched to an actual object µ(y V ) in the PC and GRADES will opportunistically update µ(y V ) to make it as close as possible to y V .

We now describe in details Algorithm 1 using the following additional notation:

• S V,t and S P,t denote the state of the VC and the PC, respectively. • ρ(x) denotes the closest object in the catalogue to x. The gray lines correspond to changes to increase algorithm adaptivity and will be discussed in Sec. IV-C2.

Upon a request for x, if there is still space in the cache, we retrieve the most similar object in the catalogue ρ(x). GRADES inserts x and ρ(x) in the VC and in the PC, respectively, and matches them (µ(x) = ρ(x)). These operations are described in lines 2-5. The cache will finally serve ρ(x).

If the cache is already full, the closest object in VC y V will be updated according to (4) (lines 6-7). Upon a virtual hit, if x is closer to y V than the currently matching object µ(y V ) in the PC, GRADES takes advantage of this request to replace µ(y V ) with ρ(x) (lines 9-12). In a stationary setting, the state of VC converges to a critical point of the cost (Theorem IV.2) and the PC should become closer and closer to it. Finally, the most similar object in PC is served if it is close enough to x, or if in any case ρ(x) has been retrieved (line 11).

2) Increasing Adaptivity: According to what we described above, only the closest object in VC is updated upon a request (unless some projection back to B(R) is needed). A potential problem is that if an object x far from any other object has been accidentally inserted in VC (and the corresponding object ρ(x) in PC), it may never be updated and may uselessly occupy cache space. Moreover, if at some point the request process changes abruptly, some objects in the cache that were initially useful may find themselves too far from the new requests. Again, the gradient algorithm, by itself, would not update such objects. To overcome this problem, we can graft to GRADES a more dynamic caching policy that occasionally (with probability p) updates the VC, hopefully evicting the least useful object in the VC.

The "grafting" is described by the green-shaded lines in Algorithm 1 and has been designed to support general cache eviction algorithms like LRU, LFU, and their variants. The grafted caching policy internally maintains its own data structure, e.g., an ordered queue for LRU. Upon an approximate hit, the hit update rule of the grafted policy is called (line 13). For example, LRU would move the requested object (if present in the cache) to the front of the queue. Also, with probability p, GRADES invokes the miss update rule of the grafted policy, that may lead to select an element ω to be evicted. GRADES then updates accordingly the VC and the PC (lines [START_REF] Venugopal | Shadow puppets: Cloud-level accurate AI inference at the speed and economy of edge[END_REF][START_REF] Kumar | Accelerating deep learning inference via freezing[END_REF][START_REF] Balasubramanian | Accelerating deep learning inference via learned caches[END_REF][START_REF] Salem | Towards inference delivery networks: Distributing machine learning with optimality guarantees[END_REF].

3) Algorithm Complexity: A straightforward implementation of GRADES has a time complexity of O(kd), where k is the cache capacity and d is the embedding dimension. This is because one has to iterate through the k objects in the cache to find the most similar object to the requested object. However, one could use approximate nearest neighbor index, such as those based on hierarchical navigable small worlds (HNSW) graphs [START_REF] Malkov | Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs[END_REF]. Numerically, HNSW is able to answer a 10NN query over a dataset with 1 million objects in a 128dimensional space in less than 0.5 ms with a recall greater than 97% [START_REF] Aumüller | ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms[END_REF]. As for the memory footprint, a typical configuration of the HNSW index requires O(d) bytes per objects, where d is the number of dimensions. For instance, in case of d = 128 dimensional vectors, the memory required to index 10 million objects is approximately 5 GB.

V. EXPERIMENTS In this section, we empirically validate our algorithm through simulations. First we demonstrate the benefit of the algorithm by using synthetic traces. Next, to demonstrate real world applicability of our algorithm, we use GRADES in the domain of caching for 360 • videos and recommendation systems. We assume that the catalog coincides with the set of possible requests (Z = X ) and then set C θ = C r . The retrieval cost C r is always equal to 1. Table I summarizes the main characteristics of the traces. Further details about the experimental setup and the properties of request traces will be described in the corresponding subsections. To the best of our knowledge, there are no public traces for similarity caching; we made our traces available online [START_REF]Similarity caching trace repository[END_REF].

We compare GRADES with the following algorithms. a) GREEDY is an offline static algorithm that progressively fills the cache inserting the object that provides the largest cost saving given the set of objects already inserted. The algorithm provides a 1 2 approximation in terms of cost savings [START_REF] Fisher | An analysis of approximations for maximizing submodular set functions-II[END_REF]. b) LRU+ updates the cache as the classic LRU evicting the least recently used content when needed, but it can provide approximate objects. c) SIM-LRU [START_REF] Pandey | Nearest-neighbor caching for content-match applications[END_REF] maintains the content in an ordered queue as LRU. It moves objects to the front upon an approximate hit, and evicts objects from the back when needed. d) qLRU-∆C [START_REF] Neglia | Similarity caching: Theory and algorithms[END_REF] is a variant of qLRU [START_REF] Garetto | A unified approach to the performance analysis of caching systems[END_REF] that, upon an approximate hit, moves the object to the front with a probability which is proportional to the service cost reduction the object has guaranteed on the current request. e) DUEL [START_REF] Neglia | Similarity caching: Theory and algorithms[END_REF], upon a request for object x not in cache, x is matched with an object y in the cache in a tournament aimed at deciding if x is a better candidate to be stored in the cache as compared to y. The decision is made by comparing the cost savings x and y provide over a fixed interval of time (f ). If the new object x provides a larger cost saving, then x replaces y in the cache.

A. Synthetic Traces

We consider a setting similar to [START_REF] Neglia | Similarity caching: Theory and algorithms[END_REF]. The catalog is made by the points of a L × L bi-dimensional grid with L = 313. The cache hs size k = 313. 2 2 As noted in [START_REF] Neglia | Similarity caching: Theory and algorithms[END_REF], when object requests fall uniformly over the points of a L × L grid (with wrap-around conditions), with k = L = 1 + 2l(l + 1), for some positive integer l, an optimal cache configuration can be computed. The value k = L = 313 results from the particular choice of l = 12. For a nonhomogeneous request process an approximate optimal cost can be computed as well (see Appendix F in [START_REF] Neglia | Similarity caching: Theory and algorithms[END_REF]). For any two objects x and y on the grid we define the approximation cost to be proportional to the norm-1 distance between the two points x and y, in particular C d (x, y) = 1 10 ||x -y|| 1 . In our experiments, we observe that GRADES converges to an expected cost that is slightly better than the approximate optimal cost as computed in [START_REF] Neglia | Similarity caching: Theory and algorithms[END_REF], suggesting that GRADES converges very close to optimal.

The traffic is generated under the Independent Reference Model [START_REF] Coffman | Operating systems theory[END_REF]. There are two popular regions A and B centered around coordinates [START_REF] Wang | Collaborative deep learning for recommender systems[END_REF][START_REF] Wang | Collaborative deep learning for recommender systems[END_REF] and (220, 220), respectively; they are produced by a mix of two Gaussian distributions. In particular, an object at (norm-1) distances d 1 from the center of A and d 2 from the center of B is requested with probability

Pr(d 1 , d 2 ) ∝ 0.4 × e -d 2 1 2×15 2 √ 2π × 15 + 0.6 × e -d 2 2 2×25 2 √ 2π × 25 .
The popularity distribution of the objects in the grid is depicted in the heat-map in Fig. 3. Figure 1 corresponds to a rescaled version of the same process. Figure 4 shows the performance of GRADES without any graft and with different grafts (LRU+, SIM-LRU, qLRU-∆C) for a quite large value of the grafting parameter (p = 10 -2 ). GRADES/X denotes GRADES grafted with policy X. We observe that GRADES achieves the smallest cost, and by grafting GRADES with SIM-LRU we can make the initial transient faster. Figure 3 also shows the final cache configuration reached by GRADES: as expected, the density of the objects in the cache is higher where the request density is higher.

The effect of the grafting parameter p is shown in Fig. 5 and depends on the specific grafted policy. We see that GRADES/qLRU-∆C3 is relatively insensitive to the grafting up to p = 0.05, but for larger values of p the cost increases, and approaches the cost of qLRU-∆C alone (about 0.295 as it can bee seen in Fig. 4). This happens because, for large p, more and more cache updates are due to qLRU-∆C, which, even upon an approximate hit, may introduce the requested object with probability proportional to q. For GRADES/SIM-LRU, the cost again increases as p increases, but it is always much smaller than the cost of SIM-LRU alone (about 0.32). The explanation is that SIM-LRU never introduces new objects on approximate hits. Hence, as far as the current cache allocation is providing approximate answers, the function GRAFT MISS UPDATE in Algorithm 1 does not modify the current cache allocation.

In Fig. 6, we study the effect of the initialization on the the performance of GRADES. We test three different initialization schemes: uniform box, uniform grid, and request-based depicted in Fig. 6 (b),(c),(d), respectively. We sample the initial set of objects uniformly at random without replacement among those at the boundary (x ∈ {0, 312} or y ∈ {0, 312}) and from the whole catalog (313 × 313 grid), respectively under the uniform box initialization and the uniform grid one. Instead, we take the first k distinct requested objects to obtain the request-based initialization. Note how these three schemes lead to store initially in the cache progressively more popular objects. Figure 6 (a) shows the three initializations provide different initial costs, with the configuration with the least (resp. most) popular objects leading to the highest (resp. lowest) initial cost. The figure shows also that, independently of the initial cache configuration, GRADES is able to move to configurations with smaller cost (similar to the one in Fig. 3). Until now, we have considered a stationary request scenario, where there is no evident advantage from grafting a more reactive policy to GRADES. In Fig. 7 we consider a highly non-stationary setting. At time 0, the cache is initialized as in Fig. 3 , i.e., the cache configuration reached by GRADES after a large number of requests (a million) made from a mix of the two gaussian distributions. Then, the request process changes abruptly and no more requests for objects in region A are generated. The cache should reach a new configuration where all cached objects are located in region B, achieving a lower cost, as now the same number of objects should cover a smaller area. Fig. 7 shows that a higher value of p enables faster migration of objects from region A to region B in the cache.

Figure 8 shows the synergy between GRADES and the Fig. 8: Expected cost C(•) incurred by the different policies under the trace Synthetic: qLRU-∆C (q = 10 -3 , 10 -2 ), DUEL , GREEDY, and GRADES (η = 1.28, 0.64 grafted with p = 1 and q = 10 -3 ). Cache size k = 313.

grafted policy. qLRU-∆C, DUEL, and GRADES, all have parameters (q, η, and f ) that can be tuned to find an optimal trade off between convergence speed and final cost. They can converge fast to configurations within a large neighborhood of a critical point (for high q, high η, and low f , respectively), or slowly to configurations within a smaller neighborhood.

Experiments in [START_REF] Neglia | Similarity caching: Theory and algorithms[END_REF], in a setting similar to ours, show that qLRU-∆C achieves a worse cost-vs-speed tradeoff than DUEL. Figure 8 confirms that this is the case, but when qLRU-∆C is grafted on GRADES, the resulting policy improves on top of DUEL. In fact GRADES/qLRU-∆C achieves a better trade-off as it is able to converge to a cost comparable to DUEL in a shorter time, or equivalently to a smaller cost in roughly the same time. Note also that DUEL's expected cost at steady state is noisier than GRADES/qLRU-∆C's cost, showing the advantage of smoothly updating the state using gradients.

We now study the impact of the approximability threshold (C θ ) on the expected cost using the Synthetic trace. We vary the value of C θ from 0.5 to 1.4 in increments of 0.1. Figure 9 shows that, as C θ increases, the expected cost first decreases and then increases. In fact, for C θ C r = 1, a larger C θ increases the number of approximate hits and then avoids the need to pay the cost C r to retrieve the objects from the server. On the contrary, for C θ C r = 1, a larger C θ is not beneficial, because misses are finally less costly than approximate hits. Figure 9 suggests that the optimal configuration is C θ ≈ C r = 1 (in our experiments the server can always provide an exact hit). We observe that, while this choice minimizes the cost to serve a request given the current cache configuration, the choice of C θ also influences how the cache state evolves. This is because newer objects are only introduced into the cache on misses. Therefore, the optimal value for C θ could be, in principle, different.

B. 360 • Videos

We test our algorithms on 360 • video traces. A 360 • video is an immersive, spherical video [START_REF] Corbillon | Viewport-adaptive navigable 360-degree video delivery[END_REF], [START_REF] Qian | Optimizing 360 video delivery over cellular networks[END_REF]. The video is first projected on to a 2D plane to be encoded by classic 2D video encoders. The video is divided into time segments, and each segment is further spatially divided into tiles. The VR headset is optimized to fetch the required tiles based on the head position of the user. A system responsible for the delivery of 360 • videos can store the popular tiles in nearby caches [START_REF] Zink | Scalable 360 video stream delivery: Challenges, solutions, and opportunities[END_REF]. Moreover, tiles at the periphery of the user's field of view could be approximated by neighbouring tiles that are stored at the cache and can then be served with low latency. Similarity caching may then be useful in this context, specially in the future when the number of tiles will increase and close tiles will become more similar.

We generated a sequence of tiles' requests for 360 • videos using the approach proposed in [START_REF] Park | Navigation graph for tiled media streaming[END_REF]. We took real traces from 8 videos watched by 48 users each, and then built a navigation graph for each video, i.e., a Markov Chain that represents the spatial and temporal viewing correlations for the video. The videos we considered have on average 207 segments, each with 25 tiles. From each navigation graph we can generate an arbitrary number of possible views of the video. We generated then a trace with 10,000 users as follows. At time t = 0, each user selects one of the videos at random and starts watching the video from a random segment of the video. The user then walks through the navigation graph to view the complete video. Once the user reaches the last segment in the video, it selects a new video uniformly at random (with replacement) and starts watching the selected video from the first segment. The process is repeated till 10 million requests are generated. We assume each tile can approximate at most 4 tiles (the adjacent ones), with a fixed approximation cost C a = 0.1.

Figure 10 compares the performance of GRADES/qLRU-∆C and qLRU-∆C. Note that in this setting, the representation space exhibits a very rough granularity, as the tiles of a segment cannot be used to approximate those of another segment and each segment is decomposed in a 5 × 5 grid of tiles. Nevertheless, GRADES/qLRU-∆C shows significant improvement with respect to existing similarity caching policies and approaches the cost of GREEDY.

C. Machine Learning Traces

We study the performance of similarity caching under the following traces in high-dimensional spaces.

a) Amazon trace: The paper [START_REF] Mcauley | Imagebased recommendations on styles and substitutes[END_REF] proposes a technique to embed the images of Amazon products in a 100-dimensional space, where the Euclidean distance between two items captures the similarity of the sets of users who purchased or viewed both items. We have restricted ourselves to the products in the category "Baby" and we have assumed that a request for a given item was issued at time t, if a user left a review for the considered item at the same time.

b) CiteULike trace: The CiteULike dataset [START_REF] Wang | Collaborative deep learning for recommender systems[END_REF] contains a bipartite network of 22,715 users and 153,277 tags, where each edge represents a timestamped tag creation. The embeddings in a 100-dimensional space are obtained using the collaborative metric learning model proposed in [START_REF] Hsieh | Collaborative metric learning[END_REF]. As for the Amazon trace, the Euclidean distance within this space encodes the similarity between users and items, where the items here are the tags. We generated the trace considering that an object (tag) is requested when one user adds the corresponding tag. c) Movielens trace: We have trained the RecVAE collaborative filtering model from [START_REF] Shenbin | Recvae: A new variational autoencoder for top-n recommendations with implicit feedback[END_REF] on the Movielens dataset [START_REF] Harper | The movielens datasets: History and context[END_REF] to embed users' rating histories in a d = 200 dimensional space. Users with similar rating histories are mapped to vectors close according to the Euclidean distance. We have generated the trace by embedding every batch of 38 ratings from the same user (38 is the median number of ratings across all users) and assigning it the timestamp of the latest rating in the batch.

In all previous traces similarity is captured by the Euclidean distance. We then assume the dissimilarity cost to be proportional to the squared Euclidean distance, i.e., C d (x, y) = b x -y 2 2 . As the absolute value of such distance has not a clear meaning, we select the constant b so that on average an object can approximate a given fraction α of the catalogue. We say that x can approximate y if C d (x, y) ≤ C r = 1, and we call α the approximability value. We set the cache size to k = 100.

The time-average cost of different caching policies is shown in Fig. 12 for the Amazon trace and 10% approximability. Although an object is able to approximate only 10% of the catalog on average, similarity caching policies significantly reduce the cost in comparison to an exact caching policy like LRU, with qLRU-∆C and GRADES/qLRU-∆C achieving the lowest service cost.

The empirical distribution of pairwise distances in Amazon trace is shown in Fig. 11. The figure shows that objects are quite scattered in this high-dimensional space with mean distance of around 85,000 between any two objects. The objects in the virtual cache are then in general far from any object in the catalog and we could expect gradient methods to perform poorly. Nevertheless, Fig. 12 shows that GRADES/qLRU-∆C outperforms existing similarity caching policies. Similar results hold for the other two traces.

Finally, Fig. 13 reports the costs obtained for the three traces under different values of approximability. As expected, the service cost reduces as the approximability becomes larger. In the CiteULike trace, the service cost flattens rapidly (it is almost constant after 10% approximability): a close look at the dataset shows that popular objects are clustered in a small region of space. Once the approximability value guarantees that these objects can approximate each other, the marginal improvement from further increasing approximability becomes negligible. The other two traces show instead a similar behaviour, with the service cost that is still decreasing after 20% approximability. We also observe that the relative improvement of GRADES/qLRU-∆C in comparison to qLRU-∆C becomes larger as the approximability increases. Fig. 12: The time averaged cost incurred by different policies under the trace Amazon: LRU, LRU+, SIM-LRU, qLRU-∆C (q = 10 -3 ) and GRADES/qLRU-∆C (η = 6.9 × 10 2 , grafted with p = 1). The level of approximability is 10%. Cache size k = 100.

VI. CONCLUSIONS

In this paper we have proposed GRADES, a new caching policy for similarity caching systems that takes advantage from the fact that objects and requests can many times be embedded in a continuous metric space. GRADES outperforms traditional caching policies in stationary scenarios, converging to provably optimal configurations under mild assumptions. Moreover we have shown that GRADES can be grafted to any traditional caching policy, obtaining flexible schemes that achieve arbitrary trade-offs between convergence speed and average costs at steady state. The performance of GRADES and its extensions has been evaluated in several synthetic and realistic scenarios.

VII. ACKNOWLEDGEMENT order, then C(y) is continuously differentiable up to the second/third order when C(y) is so. Moreover, we observe that ∇ y C(y) 2 > 0 for y (i) / ∈ B 2 (R) for some i. Then, lim inf t→∞ ∇ y C(y t ) 2 = 0, implies that lim inf t→∞ ∇ y C(y t ) 2 = 0. Lemma IV.1 shows that the sequence H = (y 1 , y 2 , . . . ) is bounded a.s. Consider a bounded sequence H, such that y t ∈ B 2 (R ) for some R > 0. ∇ C(x, y t ) exists a.s. and it is bounded for any x ∈ X . By the dominated convergence theorem, it follows that we can invert the expectation and the gradient:

E x ∇ y C(x, y t ) = ∇ y E x C(x, y t ) = ∇ y C(y t ).
As C() is continously differentiable up to the second order upon B 2 (R ), the partial derivatives are bounded, in particular, there exist two constants c 1 and c 2 such that |∂ C(y)/∂y i | ≤ c 1 and |∂ 2 C(y)/∂y i ∂y j | ≤ c 2 for each i, j ∈ {1, 2, . . . , kp}.

Consider

The series on the LHS is then summable. It follows that

∞ t=1 η t ∇ y C(y t ) 2 2 < +∞ a.s. ( 18
)
and then we can complete the proof of the first thesis: lim inf t→∞ ∇ y C(y t ) 2 = 0 a.s.

Consider now that C() is continuously differentiable up to the third order and then its third order partial derivatives are bounded over B 2 (R ), i.e., |∂ 3 C(y t )/∂y i ∂y j ∂y l | ≤ c 3 . Let a(y) = ∇ y C(y) 2 2 . This is continuously differentiable up to the second order and we can then use the Taylor formula as above, considering that ∂a(y) ∂y i = 2

) 23
Because of (18) and t η 2 t < ∞, t E[a(y t+1 ) -a(y t )|H t ] < +∞ almost surely and a convergence result for quasimartingales [START_REF] Bottou | On-line learning and stochastic approximations[END_REF]Sec. 4.4] implies that a(y t ) converges almost surely to a random variable a ∞ with finite expected value. As a ∞ > 0 if and only if ∇ y C(y t ) 2 2 > 0 for large t, it is possible to reason as at the end of the proof of Lemma IV.1 and use [START_REF] Guo | Potluck: Cross-application approximate deduplication for computation-intensive mobile applications[END_REF] to conclude that a ∞ = 0 almost surely. It follows that lim t→∞ ∇ C(y t ) = 0 a.s. and this concludes the proof.

Fig. 1 :

 1 Fig. 1: Cached objects' movements in the representation space (R 2 ) during [0, T ] when the cache is managed by GRADES. The catalog is made by the points in a 100 × 100 grid, dark shaded areas correspond to more popular objects. Dissimilarity cost C d (x, y) = 1/10 x -y 1 , retrieval cost C r = 1, cache size k = 50. See the description in Sec. V. ical guarantees in Sec. IV. Finally, experimental results are presented in Sec. V.

Fig. 2 :

 2 Fig.2: Coverage of the request space (⊂ R 2 ) by 4 objects in the cache with norm-2 as dissimilarity cost. Crosses represent the objects. Each object is the closest point to requests in the corresponding Voronoi cell delimited by the red lines. Consider a request x falling in the Voronoi cell of an object y i . If x is closer to y i than the critical radius R θ (such that h (R θ ) = C θ ), x receives y i as reply, otherwise (it falls in the gray shaded area) it generates a miss.

Fig. 3 :

 3 Fig. 3: The heatmap depicts the popularity distribution of objects in the grid. The darker regions A and B contain the most popular content. The circles represent the final configuration produced by the GRADES policy (η = 0.64) under the trace Synthetic.

Fig. 4 :

 4 Fig. 4: Expected cost C(•) incurred by different policies under the trace Synthetic. LRU+, SIM-LRU, qLRU-∆C (q = 10 -2 ), GREEDY, and GRADES (η = 0.64, plain and grafted with p = 10 -1 ). Cache size k = 313.

Fig. 5 :

 5 Fig. 5: Effect of the grafting parameter p on the final expected cost C(•). GRADES/qLRU-∆C (q = 10 -2 ) and GRADES/SIM-LRU for different learning rates under the trace Synthetic. Cache size k = 313.

Fig. 6 :Fig. 7 :

 67 Fig. 6: Subfigure (a) shows the expected cost C(•) incurred by GRADES/qLRU-∆C (η = 0.64 grafted with p = 1 and q = 10 -3 ) for different initialization (uniform box, uniform grid, and request-based depicted in (b), (c), and (d), respectively) under the trace Synthetic. Cache size is k = 313. The heatmap depicts the popularity distribution of objects in the grid.

9 :

 9 Expected cost C(•) incurred by the GRADES/SIM-LRU under the trace Synthetic for different values of the approximation threshold C θ . Cache size k = 313, C r = 1, η = 0.64, 1.28 and p = 0.001.

Fig. 10 :

 10 Fig. 10: Expected cost C(•) incurred by the different caching policies under the trace 360 • videos. GRADES/qLRU-∆C (q = 0.01, 0.05) with η = 1.0 and qLRU-∆C (q = 0.01, 0.05). Cache size k = 4000.

Fig. 11 :

 11 Fig. 11: The empirical distribution of pairwise distances under the trace Amazon. The distribution is computed on a random subset of the catalog containing 1000 products.

Fig. 13 :

 13 Fig. 13: The average cost incurred by qLRU-∆C (q = 10 -3 ) and GRADES/qLRU-∆C (grafted with p = 1) under the machine learning traces. The learning rates picked for different approximability levels are: (a) (η = 5.4 × 10 2 , 6.3 × 10 2 , 6.9×10 2 , 7.7×10 2 ), (b) (η = 2.4×10 -2 , 2.6×10 -2 , 3.0× 10 -2 , 3.2 × 10 -2 ) and (c) (η = 1.6 × 10 -1 , 2.7 × 10 -1 , 3.2 × 10 -1 , 3.8 × 10 -1 ). Cache size k = 100.

2 . ( 14 )

 214 where s ∈ [0, 1]. Denoting the constant c 2 c 2 1 kp/2 by b and summing for t = 1, . . . , T , we obtain T t=1 η t ∇ y C(y t ) • ∇ y C(r t , y t ) ≤ C(y 1 ) -C(y T ) + the expected value, and letting T diverges, we obtain ∞ t=1 η t E ∇ y C(y t ) 2 2 ≤ E C(y 1 ) + ∞ t=1 η 2 t b < +∞.

  14: y P = arg min y∈S P,t C d (x, y) 15: ξ ∼ Uniform(0, 1) 16: if ξ < p then (update, ω) =GRAFT MISS UPDATE(S V,t , x, ρ(x))

	17:
	18:	if update then
	19:	Evict ω and µ(ω)
	20:	Retrieve and Insert ρ(x) in VC and PC
	21:

TABLE I :

 I Traces description

	Trace	Number of requests Catalog size Dimension (d)
	Synthetic	2,000,000	97,969	2
	360 • videos	10,000,000	25,393	3
	Amazon	908,179	63,891	100
	CiteULike	2,411,819	153,277	100
	Movielens	620,222	136,677	200

  y t+1 = y t -η t ∇ C(x t , y t ). Using Taylor formula we can arrive toC(y t+1 ) -C(y t ) =

	kp i=1	∂ C(y t ) ∂y i	(y t+1,i -y t,i ) +	kp i,j=1

∂ 2 C(y t + sy t+1 ) ∂y i ∂y j (y t+1,i -y t,i )(y t+1,j -y t,j ) 2

(12)

≤ -η t ∇ y C(y t ) • ∇ y C(r t , y t ) + η 2 t c 2 kp 2 ∇C(r t , y t ) 2 2

(13)

≤ -η t ∇ y C(y t ) • ∇ y C(r t , y t ) + η 2 t c 2 c 2 1 (kp) 2

  Then |∂ 2 a(y)/∂y i ∂y l | ≤ c 2 = 2kp(c 2 2 + c 1 c 3 ). We obtain:a(y t+1 ) -a(y t ) ≤ -2η tIf we now compute the conditional expectation given the history up to t, H t = (y 1 , y 2 , . . . , y t ), we obtain E[a(y t+1 ) -a(y t )|H t ] ≤ -2η t

			kp i,j=1	∂ C(y) ∂y j	∂ 2 C(y) ∂y i ∂y j	∂ C(x t , y t ) ∂y i	+ η 2 t	c 2 c 2 1 (kp) 2 2	.	(21)
				kp i,j=1	∂ C(y) ∂y j	∂ 2 C(y) ∂y i ∂y j	∂ C(y t ) ∂y i	+ η 2 t	c 2 c 2 1 (kp) 2 2	(22)
		≤ 2c 2 kpη t ∇ y C(y t ) 2 2 + η 2 t	c 2 c 2 1 (kp) 2 2	.	(
		kp j=1	∂ C(y) ∂y j	∂ 2 C(y) ∂y i ∂y j	,	(19)
	∂ 2 a(y) ∂y i ∂y l	= 2

kp j=1 ∂ 2 C(y) ∂y j ∂y l ∂ 2 C(y) ∂y i ∂y j + ∂ C(y) ∂y j ∂ 3 C(y) ∂y i ∂y j ∂y l .

(20)

Note that GRADES grafted with p = p to a qLRU-∆C with q = q is equivalent to GRADES grafted with p = 1 to a qLRU-∆C with parameter q = p × q .

This work was supported in part by the National Science Foundation under Grant No. CNS-1763617 and No. CNS-1901137 and by Inria under the exploratory action MAM-MALS.

Proof. We observe that for y

2 is bounded and for y

2 , then there exists positive constants A l and B l for l = 1, 2, 3, 4, such that for g

2 . We also observe that inf{y

t , ∀y

We will prove boundedness using the function

2

where φ(u) = 1 u≥(R+1) 2 (u -(R + 1) 2 ) 2 . There exist positive constants A and B such that

2 ).

Taking advantage of the inequality

2 , we can derive the following inequality

Using the inequalities above, we obtain

We take now the conditional expectation given H t = (y 1 , y 2 , . . . , y t ):

where the last inequality follows from φ ( y

2 ) = 0 for y

). The proof until now follows logically the same steps as in [34, Sec. 5.2], but 1) we did not need to suppose that g

t have l-th moments bounded by y

2 , as their norm is bounded from our definition of the algorithm, 2) we had to redefine the function f t to take into account separately each subvector y (i) t of y t . From [START_REF] Auch | Standard operating procedure for calculating genome-to-genome distances based on high-scoring segment pairs[END_REF] we can reason as in [START_REF] Bottou | On-line learning and stochastic approximations[END_REF]Sec. 5.2] to show that {f t } t∈N is a quasi-martingale and apply convergence results for quasi-martingales [START_REF] Bottou | On-line learning and stochastic approximations[END_REF]Sec. 4.4] to conclude that f t converges almost surely to a random variable f ∞ ≥ 0 with E[f ∞ ] < ∞. We want to conclude that f ∞ = 0 with probability one, and then y t is bounded almost surely.

The rest of the proof differs from [START_REF] Bottou | On-line learning and stochastic approximations[END_REF]Sec. 5.2]. Moving around the terms in [START_REF] Sermpezis | Soft cache hits: Improving performance through recommendation and delivery of related content[END_REF] and summing over t, we obtain

because t η 2 t < ∞ and f t converges to f ∞ < ∞. Let H be the set of sequences such that f ∞ > 0. For each sequence in H, f t > f ∞ /2 for large t, and then there exists at least a value i t and an opportune > 0 such that y

2 ) are bounded below by positive quantities and the series in the LHS of (10) diverges as t η t = +∞. But we have concluded that this series converges a.s., then Pr (H) = 0 and f ∞ = 0 a.s.. Each sequence (y 1 , y 2 , . . . ) is then bounded a.s.

APPENDIX B PROOF OF THEOREM IV.2

Proof. We denote by y t,i the i-th component of the vector y t ∈ R k×d , and by y i the i-th component of a generic vector y ∈ R k×d .

We define

We observe that ∇ y C(x, y t ) = (g

t , . . . , g

t ), i.e., the dynamic in ( 4) is evolving according to the gradient of C(x, y t ). Similary we define C(y) = E x C(x, y) = C(y) + L(y). The function L(y) is continuously differentiable up to the third