Si Tareq

Salem

Giovanni Neglia
email: giovanni.neglia@inria.fr

Stratis Ioannidis
email: ioannidis@ece.neu.edu

No-Regret Caching via Online Mirror Descent

We study an online caching problem in which requests can be served by a local cache to avoid retrieval costs from a remote server. The cache can update its state after a batch of requests and store an arbitrarily small fraction of each content. We study no-regret algorithms based on Online Mirror Descent (OMD) strategies. We show that the choice of OMD strategy depends on the request diversity present in a batch and that OMD caching policies may outperform traditional evictionbased policies.

I. INTRODUCTION

Caches are deployed at many different levels in computer systems: from CPU hardware caches to operating system memory caches, from application caches at clients to CDN caches deployed as physical servers in the network or as cloud services like Amazon's ElastiCache [START_REF] Aws | Amazon Web Service ElastiCache[END_REF]. They aim to provide a faster service to the user and/or to reduce the computation/communication load on other system elements, like hard disks, content servers, etc.

Most prior work has assumed that caches serve requests generated according to a stochastic process, ranging from the simple, memory-less independent reference model [START_REF] Coffman | Operating systems theory[END_REF] to more complex models trying to capture temporal locality effects and time-varying popularities (e.g., the shot-noise model [START_REF] Traverso | Temporal Locality in Today's Content Caching: Why It Matters and How to Model It[END_REF]). An alternative modeling approach is to consider the sequence of requests is generated by an adversary, and compare online caching policies to the optimal offline policy that views the sequence of requests in advance [START_REF] Fiat | Competitive paging algorithms[END_REF].

Recently, Paschos et al. [START_REF] Paschos | Learning to cache with no regrets[END_REF] proposed studying caching as an online convex optimization (OCO) problem [START_REF] Hazan | Introduction to online convex optimization[END_REF]. OCO generalizes previous online problems like the experts problem [START_REF] Littlestone | The weighted majority algorithm[END_REF], and has become widely influential in the learning community [START_REF] Hazan | Introduction to online convex optimization[END_REF], [START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF]. This framework considers an adversarial setting, where the metric of interest is the regret, i.e., the difference between the costs incurred over a time horizon T by the algorithm and by the optimal offline static solution. Online algorithms whose regret grows sublinearly with T are called no-regret algorithms, as their time-average regret becomes negligible for large T . Paschos et al. proposed a no-regret caching policy based on the classic online gradient descent method (OGD), under the assumption that (a) the cache can store arbitrarily small fractions of each content (the so-called fractional setting), and (b) the cache state is updated after each request. Bhattacharjee et al. [START_REF] Bhattacharjee | Fundamental limits on the regret of online network-caching[END_REF] extended this work proving tighter lower bounds for the regret and proposing new caching policies for the networked setting that do not require content coding.

In this paper, we extend and generalize the analysis of Paschos et al. in two different directions:

1) We assume the cache can update its state after processing a batch of R ≥ 1 requests. This is of interest both in high-demand settings, as well as in cases when updates may only occur infrequently, because they are costly w.r.t. either computation or communication. 2) We consider a broad family of caching policies based on online mirror descent (OMD); OGD can be seen as a special instance of this family. Our contributions are summarized as follows. First, we show that caching policies based on OMD enjoy O √ T regret. Most importantly, we show that bounds for the regret crucially depend on the diversity of the request process. In particular, the regret depends on the diversity ratio R/h, where R is the size of the request batch, and h is the maximum multiplicity of a request in a given batch. We observe that OMD with neg-entropy mirror map (OMD NE ) surmounts OGD in the high diversity regime, and it is overturned in the low diversity regime.

Second, all OMD algorithms include a gradient update followed by a projection to guarantee that the new solution is in the feasible set (e.g., it does not violate the cache capacity constraints). The projection is often the most computationally expensive step of the algorithm. We show that efficient polynomial algorithms exist both for OGD (slightly improving the algorithm in [START_REF] Paschos | Learning to cache with no regrets[END_REF]) and for OMD NE .

The remainder of this paper is organized as follows. We introduce our model assumptions in Sect. II. We present OMD algorithms and quantify their regret and their computational complexity in Sect. III. Finally, numerical results are presented in Sect. IV.

The complete proofs are available in [START_REF] Salem | No-regret caching via online mirror descent[END_REF].

II. SYSTEM DESCRIPTION

Remote Service and Local Cache. We consider a system in which requests for files are served either remotely or by an intermediate cache of finite capacity. A cache miss incurs a file-dependent remote retrieval cost. This cost could be, e.g., an actual monetary cost for using the network infrastructure, or a quality of service cost incurred due to fetching latency. Costs may vary, as each file may be stored at a different remote location.

Our goal is to study online caching algorithms that attain sublinear regret. Formally, we consider a stream of requests for files of equal size from a catalog N = {1, 2, . . . , N }. These requests can be served by a remote server at cost w i ∈ R + per request for file i ∈ N . We denote by w = [w i ] i∈N ∈ R N + the vector of costs and assume that w is known.

A local cache of finite capacity is placed in between the source of requests and the remote server(s). The local cache's role is to reduce the costs incurred by satisfying requests locally. We denote by k ∈ {1, . . . , N } the capacity of the cache. The cache is allowed to store arbitrary fractions of files, a common assumption in the literature [START_REF] Paschos | Learning to cache with no regrets[END_REF], [START_REF] Maggi | Adapting caching to audience retention rate[END_REF], [START_REF] Shanmugam | Femtocaching: Wireless content delivery through distributed caching helpers[END_REF] and a good approximation when the cache can store chunks of a file and chunk sizes are much smaller than file size. We assume that time is slotted, and denote by x t,i ∈ [0, 1] the fraction of file i ∈ N stored in the cache at time slot t ∈ {1, 2, . . . , T }. The cache state is then given by vector x t = [x t,i ] i∈N ∈ X , where X is the capped simplex determined by the capacity constraint, i.e.:

X = x ∈ [0, 1] N : N i=1 x i = k . (1)
Requests. We assume that a batch of multiple requests may arrive within a single time slot. Moreover, a file may be requested times within a single time slot (e.g., by different users, whose aggregated requests form the stream reaching the cache). We denote by r t,i ∈ N the number of requests-also called multiplicity-for file i ∈ N at time t, and by r t = [r t,i ] i∈N ∈ N N the vector of such requests, representing the entire batch. We assume that the number of requests (i.e., the batch size) at each timeslot is given by R ∈ N. We also assume that the maximum multiplicity of a file in a batch is bounded by h ∈ N. As a result, r t belongs to set: R R,h = r ∈ {0, . . . , h} N :

N i=1 r i = R . (2)
Intuitively, the ratio R h defines the diversity of request batches in a timeslot. For example, when R h = 1, requests are concentrated on a single content. When R h = N , requests are spread evenly across the catalog N . For that reason, we refer to R h as the diversity ratio. We note that our request model generalizes the setting by Paschos et al. [START_REF] Paschos | Learning to cache with no regrets[END_REF] or Bhattacharjee et al. [START_REF] Bhattacharjee | Fundamental limits on the regret of online network-caching[END_REF], which can be seen as the case R = h = 1 under our request model. We make no additional assumptions on the request arrival process; put differently, we operate in the adversarial online setting, where a potential adversary may select an arbitrary request sequence in R R,h to increase system costs. Service Cost Objective. When a request batch r t arrives, the cache incurs the following cost:

f rt (x t ) = N i=1 w i r t,i (1 -x t,i ). (3)
In other words, for each file i ∈ N , the system pays a cost proportional to the file fraction (1 -x t,i ) missing from the local cache, weighted by the file cost w i and by the number of times r t,i file i is requested in the current batch r t . The cost objective (3) captures several possible real-life settings. First, it can be interpreted as a QoS cost paid by each user for the additional delay to retrieve part of the file from the server. Second, assuming that the R requests arrive and are served individually (e.g., because they are spread-out within a timeslot), Eq. ( 3) can represent the load on the servers or on the network to provide the missing part of the requested objects. Online Caching Algorithms and Regret. Cache contents are determined online: that is, the cache has selected a state x t ∈ X at the beginning of a time slot. The request batch r t arrives, and the linear cost f rt (x t ) : X → R + is incurred; the state is subsequently updated to x t+1 . Formally, the cache state is determined by an online policy A, i.e., a sequence of mappings

{A t } T -1
t=1 , where for every t ≥ 1, A t : (R R,h ×X ) t → X maps the sequence of the request batches and previous decisions {(r s , x s )} t s=1 to the next state x t+1 ∈ X . We assume that the policy is initialized with a feasible state x 1 ∈ X .

We measure the performance of an online algorithm A in terms of regret, i.e., the difference between the total cost experienced by a policy A over a time horizon T and that of the best static state x * in hindsight, i.e., x * = arg min x∈X

T t=1 f rt (x). Formally, Regret T (A) = sup {r1,...,r T }∈R T R,h T t=1 f rt (x t ) - T t=1 f rt (x * ) , (4)
Note that, by taking the supremum in Eq. ( 4), we indeed measure regret in the adversarial setting, i.e., against an adversary that potentially picks requests in R R,h trying to jeopardize cache performance. In Sect. IV we show our caching policies performs well also under stochastic request processes and real request traces.

III. ONLINE MIRROR DESCENT ALGORITHMS

Upon seeing r t , the policy A could select as x t+1 the state that would have minimized (on hindsight) the aggregate cost up to time t (i.e., t τ =1 f rτ (x)). This can fail catastrophically, because of the adversarial nature of the requests. A more conservative approach, that indeed leads to sublinear regret, is to take gradient steps, moving in the direction of a better decision according to the latest cost. OMD denotes a family of gradient techniques.

The main premise behind OMD [6, Sect. 5.3] is that variables and gradients live into two distinct spaces: the primal space, for variables, and the dual space, for gradients. The two are linked via a function known as a mirror map. Updates using the gradient occur on the dual space; the mirror map is used to invert this update to a change on the primal variables. The standard online gradient descent OGD is a particular OMD algorithm where the mirror map is the squared Euclidean distance. Other mirror maps may lead to better performance depending on the specific problem [START_REF] Bubeck | Convex optimization: Algorithms and complexity[END_REF]Section 4.3]. OMD for Caching. Applied to our caching problem, both the primal and dual spaces are R N . To disambiguate between the two, we denote primal points by x, y ∈ R N and dual points by x, ŷ ∈ R N , respectively. Formally, OMD is parameterized by (a) a fixed learning rate η ∈ R + , and (b) a differentiable map Φ : D → R, strictly convex over D and ρ-strongly convex w.r.t. a norm • over X ∩D, where X is included in the closure of D. The set X is the constraint set over which we optimize. The function Φ is called the mirror map, that links the primal to the dual space. Two additional technical assumptions on Φ and D must hold. First, the gradient of Φ must diverge at the boundary of D. Second, the image of D under the gradient of Φ should take all possible values, that is ∇Φ(D) = R N .

Given η and Φ, an OMD iteration proceeds as follows. After observing the request batch r t and incurring the cost f rt (x t ), the current state x t is first mapped from the primal to the dual space via:

xt = ∇Φ(x t ). (5)
Then, a regular gradient descent step is performed in the dual space to obtain an updated dual point:

ŷt+1 = xt -η∇f rt (x t ). (6)
This updated dual point is then mapped back to the primal space using the inverse of mapping ∇Φ, i.e.:

y t+1 = (∇Φ) -1 (ŷ t+1 ). (7)
The resulting primal point y t+1 may lie outside the constraint set X . To obtain the final feasible point x t+1 ∈ X , a projection is made using the Bregman divergence associated with the mirror map Φ; the final cache state becomes:

x t+1 = Φ X ∩D (y t+1 ), (8) where

A. Euclidean mirror map

The selection of the mirror map Φ(x) = 1 2 x 2 2 and D = R N yields the identity mapping ∇Φ(x) = x, for all x ∈ D. Furthermore, the Bregman divergence associated with this map is just the Euclidean distance

D Φ (x, y) = 1 2 x -y 2 2 [13, Section 4.3]
. Upon receiving a request batch r t , the algorithm updates its current state according to steps ( 5)-( 8), this gives the OGD update rule:

x t+1 = Π X (x t -η∇f rt (x t )), ∀t ∈ {1, . . . , T -1}, (9)
where Π X (•) is the Euclidean projection onto X . This setup of OMD coincides with OGD, studied by Paschos et al. [START_REF] Paschos | Learning to cache with no regrets[END_REF]. We present a new regret bound in Theorem III.1, that takes into account diversity, and improves over the bound in [START_REF] Paschos | Learning to cache with no regrets[END_REF] (valid only for R = h = 1) by a factor at least √ 2.

Theorem III.1.

For η = k(1-k N ) w 2
∞ hRT the regret of OGD, satisfies:

Regret T (OGD) ≤ w ∞ hRk 1 -k N T (10)
Proof. Bubeck [START_REF] Bubeck | Convex optimization: Algorithms and complexity[END_REF]Theorem 4.2] provides a general bound on the regret of OMD, which in our caching setting becomes

Regret T (OMD Φ ) ≤ DΦ(x * ,x1) η + η 2ρ T t=1 ∇f rt (x t ) 2 *
(11) where . * is the dual norm of . , and x * is the best fixed decision in hindsight. The mirror map for OGD is Φ(x) = 1 2 x 2 2 that is 1-strongly convex with regard to the Euclidean norm (ρ = 1) and the dual norm is also the Euclidean one.

Let x 1 be the minimizer of Φ(x), then we have ∇Φ T (x 1 )(x -x 1 ) ≥ 0, ∀x ∈ X [6, Theorem 2.2] and, from the definition of the Bregman divergence, D Φ (x * , x 1 ) ≤ Φ(x * ) -Φ(x 1 ).

The minimum value of Φ(x) over X is achieved when andx * is an integral solution (i.e., k components of x * equal 1 and the others equal 0). Then Φ(x * ) = 1 2 k and we get:

x i = k N , i ∈ N ,
D Φ (x * , x 1 ) ≤ 1 2 k (1 -k/N ) (12)
We now bound the second term in [START_REF] Maggi | Adapting caching to audience retention rate[END_REF]. The maximum of r 2 is achieved when R h components are set to h, then:

max r∈R ∇f r (x) 2 ≤ max r∈R w ∞ r 2 = w ∞ √ Rh. ( 13
)
Plugging ( 13) and ( 12) in [START_REF] Maggi | Adapting caching to audience retention rate[END_REF], and selecting the learning rate

η = k 1 -k N /( w 2
∞ hRT ), we obtain the upper bound in [START_REF] Salem | No-regret caching via online mirror descent[END_REF].

The OGD Algorithm requires computing an Euclidean projection at each iteration, which, for general values of R and h, can be performed in O N 2 steps using the projection algorithm by Wang and Lu [START_REF] Wang | Projection onto the capped simplex[END_REF]. The algorithm proposed by Paschos et al. [START_REF] Paschos | Learning to cache with no regrets[END_REF], for the case R = h = 1, has O (N log(N )) time-complexity, but we can achieve O (N ) complexity by replacing the preliminary sorting operation with a O (log(N )) binary search and insertion.

B. Neg-Entropy Mirror Map

We now consider a different mirror map, i.e., the negentropy mirror map, defined as follows:

Φ(x) = N i=1 x i log (x i ) , and D = R N >0 . (14)
It can be checked that this map satisfies all requirements in Sect. III., We refer to the OMD algorithm with the neg-entropy mirror map as OMD NE .

We first characterize the regret of OMD NE :

Theorem III.2. For η = 2 log(N/k) w 2
∞ h 2 T , the regret of OMD NE satisfies:

Regret T (OMD NE ) ≤ w ∞ hk 2 log(N/k)T . ( 15
)
Proof. The proof is similar to the proof of Theorem III.1. The neg-entropy mirror map is ρ = 1 k strongly convex w.r.t the . 1 over X [8, Example 2.5] and the corresponding dual norm is • ∞ . Moving from [START_REF] Maggi | Adapting caching to audience retention rate[END_REF], we bound the diameter of X w.r.t. to the Bregman divergence as well as the • ∞ of Algorithm 1 Neg-Entropy Bregman projection onto X Require: N ; k; y 1 ; P ; Sorted y N ≥ .. ≥ y N -k+1 ≥ yi, ∀i ≤ N -k // y is the decision vector that lies outside of X . // The scale P is a global variable initialized to 1.

1: y N +1 ← +∞ 2: for b ∈ {N, . . . , N -k + 1} do 3: m b ← k+b-N y 1 -N i=b+1 y i P 4: if y b m b P < 1 ≤ y b+1 m b P then
// Appropriate b is found.

5:

for i ≥ b+1 do

6:

yi ← 1 m b P

7:

end for

8:

P ← m b P

9:

return yP // yP is the result of the projection. 15) using a sharp upper bound [START_REF] Chesneau | New sharp bounds for the logarithmic function[END_REF], which is subsequently compared to Eq. ( 10), and the second regime is shown by using the lower bound log(1 + x) ≥ x x+1 for x > -1. Theorem III.3 immediately implies the advantage of OMD NE over OGD in the high-diversity ratio regime, and it is overturned in the low-diversity regime.

Beyond its improved performance in terms of regret the neg-entropy mirror map comes with an additional computational advantage: its projection step admits a highly efficient implementation. As ∂Φ(x) ∂xi = 1+log x i , the inverse mapping is given by (∇Φ)

-1 (ŷ t+1 ) i = exp(ŷ t,i -1). Hence, the map to the dual space and back in Eqs. ( 5)-( 7) can be concisely written as:

y t+1,i = x t,i e -η ∂fr t (x t ) ∂x i
, for all i ∈ N .

In other words, OMD under the neg-entropy adapts the cache state via a multiplicative rule, as opposed to the additive rule of OGD. Proof. We adapt the Euclidean projection algorithm in [START_REF] Wang | Projection onto the capped simplex[END_REF]. Finding the projection x = Π Φ X ∩D (y) corresponds to solving a convex problem as D Φ (x, y) is convex in x and X ∩ D is a convex set. Without loss of generality, we assume the components of x = Π Φ X ∩D (y) to be in non-decreasing order. Let b ∈ N be the index of the largest component of x smaller than 1. The KKT conditions lead to conclude that if the components of y are ordered in ascending order, so are the components of x, and it holds y b e γ < 1 ≤ y b+1 e γ , where γ is the Lagrangian multiplier associated with the capacity constraint. The value of b can be found by checking this condition for the possible values of b. We observe that necessarily b ∈ {N -k + 1, . . . , N }. In fact, we cannot have

b ≤ N -k. If b ≤ N -k, we get N i=N -k+1 x i ≥ k and the capacity constraint implies that x i = 0, ∀i ≤ b, but we must have x i > 0 since x ∈ X ∩ D and D = R N >0
. As b > N -k, then we only require the largest k components of y to perform the projection.

For a given b let:

m b := e γ = k+b-N b i=1 yi = k+b-N y 1 -N i=b+1 yi (17)
The projection corresponds to setting map the components y b+1 , . . . , y N to 1 and multiply the other N -b components by m b . In order to avoid updating all components at each step, we can simply set the components x i , i > b (those that should be set equal to 1) to 1 m b . Then, at any time t, we can recover the value of x t,i by P = t i=1 m b,i , where m b,t is the returned m b from the Bregman projection at time step t. Then at any time step, the actual value of the decision variable is xP .

For general values of R and h, the projection step takes O (k) steps per iteration and a partial sort is required to maintain top-k components of y t sorted; this can be done using partial sorting in O (N + k log(k)) [START_REF] Paredes | Optimal incremental sorting[END_REF].

When R = h = 1, Alg. 1 leads to only a single state coordinate update, and requires O (log(k)) steps to maintain top-k components of x t sorted online.

Theorem III.4 implies that OMD NE has a much smaller computational cost than OGD. In fact, for general value of R and h, OMD NE requires O (N + k log(k)) operations per iteration, while OGD requires O N 2 operations. When R = h = 1, the overall time complexity is O (k) per iteration for OMD NE and O (N ) for OGD.

IV. NUMERICAL EXPERIMENTS

A. Experimental setup 1) Datasets: Throughout all experiments, we assume equal costs per file, i.e., w i = w i = 1, ∀i ∈ N . Synthetic traces We generate synthetic datasets, as summarized in Table I. Individual file requests are i.i.d. and sampled from a catalog of N files according to a Zipf distribution We also generate non-stationary request traces (Partial Popularity Change traces), where the popularity of a subset of files is modified every T = 10 3 time slots. In particular the 5% most popular files become the 5% least popular ones and vice versa. We want to model a situation where the cache knows the timescale over which the request process changes and which files are affected (but not how their popularity changes). Correspondingly, the time horizon is also set to T and, at the end of each time horizon, the cache redistributes uniformly the cache space currently allocated by those files. The cache size is k = 5. Akamai Trace We consider also a real file request from a the Akamai CDN provider [START_REF] Neglia | Access-time-aware cache algorithms[END_REF]. The trace spans 1 week, and we extract from it about 8.5 × 10 7 requests for the N = 10 3 most popular files. We group requests in batches of size R = 5 × 10 3 , and we consider a time horizon T = 100 time slots corresponding roughly to 1 hour. The cache size is k = 25.

2) Online Algorithms: In addition to the gradient based algorithms, we implemented three caching eviction policies: LRU, LFU, and W-LFU. LRU and LFU evict the least recently used and least frequently used, respectively. W-LFU [START_REF] Karakostas | Exploitation of different types of locality for web caches[END_REF] is an LFU variant that only considers the most requested contents during a recent time window W , which we set equal to T × R in our experiments. The policies LRU, LFU, and W-LFU are allowed to update the cache state after each request. Finally, we define Best Static to be the optimal static allocation x * . We also define Best Dynamic to be the cache that stores the k most popular files at any time for the synthetic traces (for which the instantaneous popularity is well defined).

3) Performance Metrics: We measure performance w.r.t. three metrics, that we define here. The Normalized Average Cost NAC(A) ∈ [0, 1] corresponds to the timeaverage cost over the first t time slots, normalized by the batch size R.

NAC(A) = 1 Rt t s=0 f rs (x s ) (18)
The Normalized Moving Average Cost NMAC(A) ∈ [0, 1] is computed similarly using a moving average instead over a time window τ > 0 (we use τ = 500 in our experiments): Finally, we consider the Time Average Regret TAR(A) ∈ [0, R], which is precisely the time average regret over the first t time slots.

NMAC(A) = 1 R min(τ,t) t s=t-min(τ,t) f rs (x s ) (19)
TAR(A) = 1 t t s=1 f rs (x s ) - t s=1 f rs (x * ) (20)
B. Results

1) Stationary Requests: Figures 1 (a) and 1 (b) show the performance w.r.t. NAC of OGD and OMD NE , respectively, under different learning rates η on the Fixed Popularity trace. We observe that both algorithms converge slower under small learning rates, but reach a final lower cost, while larger learning rates lead to faster convergence, albeit to higher final cost. This may motivate the adoption of a diminishing learning rate, that combines the best of the two options, starting large to enable fast convergence, and enabling eventual fine-tuning. We show one curve corresponding to a diminishing learning rate both for OGD and OMD NE , and indeed they achieve the smallest costs. The learning rate denoted by η * is the learning rate that gives the tightest worst-case regrets for OGD and OMD NE , as stated in Theorems III.1 and III.2). While this learning rate is selected to protect against any (adversarial) request sequence, it is not too pessimistic: Figures 1 (a) and 1(b) show it performs well when compared to other learning rates.

Figure 1 (c) shows the time-average regret TAR of OGD and OMD NE over the Fixed Popularity trace. As both algorithms have sub-linear regret, their time average regret goes to 0 for T → ∞. Note how instead LRU exhibits a constant time average regret.

2) Effect of Diversity: Figure 2 shows the NAC performance of OMD NE and OGD on the traces Batched Fixed Popularity (1), (2), and (3) under different cache capacities k and exponent values α. We observe that OMD NE outperforms OGD in the more diverse regimes (α ∈ {0.1, 0.2}). This is more apparent for smaller values of k. In contrast, OGD outperforms OMD NE when requests are less diverse (α = 0.7); again, this is more apparent for larger k. These observations agree with Theorems III.3, which postulated that high diversity favors OMD NE .

3) Robustness to Transient Requests: Across the different diversity regimes, we find the OMD NE is more robust to popularity changes. In (a) and (b) OMD NE outperforms OGD in the non-stationary popularity setting: we observe a wider performance gap as compared to the stationary setting. In (c), the algorithms exhibit similar performance.

4) Akamai Trace: Figure 4 shows that the two gradient algorithms, OMD NE and OGD, perform similarly over the Akamai Trace w.r.t. NMAC (the curves almost overlap). LRU, LFU, and W-LFU may update the cache state after each request, while the gradient algorithms can only update the cache after R = 5000 requests. Nevertheless, the gradient algorithms consistently outperform the classic ones.

V. CONCLUSIONS

We studied no-regret caching algorithms based on OMD with the neg-entropy mirror map. Our analysis indicates that batch diversity impacts regret performance; a key finding is that OGD is favourable in low-diversity regimes, while OMD NE outperforms OGD under high diversity. Our preliminary evaluation results also suggest that gradient algorithms outperform classic eviction-based policies. We plan to conduct a more thorough comparison as future research.

ΦX

  ∩D : R N → X is the Bregman projection defined as Π Φ X ∩D (y) = arg min x∈X ∩D D Φ (x, y). D Φ (x, y) = Φ(x) -Φ(y) -∇Φ(y) T (x -y) is the Bregman divergence associated with the mirror map Φ.

  Finally, the projection algorithm onto the capped simplex can be implemented in O (N + k log(k)) time for arbitrary R, h using the waterfilling-like Algorithm 1. The algorithm receives as input the largest k components of y sorted in a descending order. It then re-scales the b largest components and N -b smallest ones by different constant factors; the value of b is determined via a linear search. The following theorem holds: Theorem III.4. Algorithm 1 returns the projection Π Φ X ∩D (y) under the neg-entropy Φ, onto the capped simplex X in O (k) steps per iteration. This results in an overall time complexity of O (N + k log(k)) per iteration of OMD, for general R, h values, and O (k) per iteration of OMD, when R = h = 1.

4

 4 200 5 × 10 3 40 0.1 Batched Fixed Popularity (2) 10 4 10 4 200 5 × 10 3 53 0.2 Batched Fixed Popularity (3) 10 4 10 4 200 5 × 10 3 346 0.7 Partial Popularity Change (1) 5 × 10 3 10 3 500 5 × 10 3 40 0.1 Partial Popularity Change (2) 5 × 10 3 10 3 500 5 × 10 3 169 0.4 Partial Popularity Change (3) 5 × 10 3 10 3 500 5 × 10 3 473 0.7 Akamai Trace 1.7 × 10 4 10 2 10 3 5 × 10 3 380 n/a with exponent α. As we increase the exponent α, the requests become more concentrated. Table I shows the value of h observed in each trace. The requests are grouped into batches of size R, and η * denotes the learning rate value specified in Theorem III.1 and in Theorem III.2 for OGD and OMD NE , respectively.

( a )Fig. 1 :

 a1 Fig. 1: NAC of OGD (a) and OMDNE (b). Subfigure (c) compares their TAC. The cache capacity is k = 10, and α = 0.8.

Figure 3

 3 shows the normalized average cost of OMD NE and OGD over the Partial Popularity Change traces, evaluated under different diversity

7 Fig. 2 : 7 Fig. 3 :

 7273 Fig. 2: NAC of OMDNE and OGD evaluated under different cache sizes and diversity regimes.

Fig. 4 :

 4 Fig. 4: NMAC of the different caching policies evaluated on the Akamai Trace.

  The following theorem characterizes under which diversity regime OMD NE outperforms OGD, and contrariwise the regime where OGD surmounts. The result is obtained by relaxing the regret bound in Eq. (

	10:	end if
	11: end for
	gradients ∇f rt (x t ). Finally, selecting the learning rate that
	gives the tightest upper bound η = 2 log( N k )/( w	2 ∞ h 2 T ),
	we obtain the desired regret upper bound.
	Theorem III.3. OMD NE has a tighter regret bound than OGD when R √ N k, while OGD has a tighter regret h > 2 bound than OMD NE when R h < 2k.

TABLE I :

 I Trace Summary

Acknowledgement. G. Neglia and S. Ioannidis acknowledge support from Inria under the exploratory action MAMMALS and the National Science Foundation (NeTS:1718355), respectively.


Si Tareq

Salem

Giovanni Neglia
email: giovanni.neglia@inria.fr

Damiano Carra
email: damiano.carra@univr.it

AC ¸AI: 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 a 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 a set of 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] Carra | 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 a street artwork. 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 about the memory required to store the objects remain, especially in a distributed edge computing scenario, as edge servers have limited memory resources compared to the cloud.

The selection of which objects a specific edge server should maintain remains an open issue. 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 seen as a cache that contains the set of objects required to reply efficiently to the local requests avoiding to forward them to the cloud.

In this paper, we study how to optimize the use of the edge server memory for similarity searches. To this aim, we consider the costs associated to 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 on the network. The aim of our study is 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, that 1) 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 2) uses an online mirror ascent algorithm to update the cache content in order to minimize the total service cost. AC ¸AI offers strong theoretical guarantees without any assumption on the traffic arrival pattern. We call such 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 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], or 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 or cosine similarity 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 in 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 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 on 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 objects the server would provide. 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 true closest neighbors to reduce the fetching cost while increasing-hopefully only slightlythe dissimilarity cost. They named such cache a similarity cache. The original applications envisaged 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] Garetto | Similarity caching: Theory and algorithms[END_REF], the idea has been rediscovered a number of 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].

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 that is justified in practice when objects have a size 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 on the basis of historical information about object popularity and prefetched in the cache. But object popularity can be difficult to estimate and can change fast, specially at the level of small geographical areas (as those that can be 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 specific 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] Garetto | 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), 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 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. If this answer is evaluated to be good enough, 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 a 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. As they assume no knowledge about the catalog at the server, they cannot compare the quality (i.e., the dissimilarity cost) of the answer the cache can provide with the quality of the answer the server can provide. They need then to rely on heuristics.

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 θ . 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 cost 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 (1) at least two of them would have been provided also by the server-a sufficient condition can be obtained from geometric considerations-or (2) 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 block, 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 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 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 showed 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 results 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%. 2As 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. As the server catalog changes less frequently, 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. 3 As for the memory footprint, for a typical configuration (IVFPQ), FAISS is able to represent an object with 30 bytes (independently from 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 index 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 content (k = 1).

We deviate from these works by considering k > 1 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 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].

IV. AC ¸AI DESIGN 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. 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 a 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 , 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] Garetto | 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 in 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 the similarity caching policies. As discussed in Sec. II, such 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 naive 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 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.

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 from 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) + d 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 function of the current cache state and replace the set notation with a vectorial one. First, we define the augmented catalog U to be the set 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 referring to c(., .) as distance.

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 . 4 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 gives 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] 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-G).

The caching gain has the following compact expression [9, Lemma 6]:

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 ∈ N 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 with the goal of greedily maximizing the gain.

The update of the state x t is driven from a continuous fractional state y t ∈ [0, 1] 2N , 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 [41, Ch. 4] that is described in Algorithm 1. 5OMA is parameterized by the function Φ(•), that is called the mirror map. 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 achieves better performance.

Periodically, every M requests, AC ¸AI 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 ∈ {0, 1} 2N from y t+1 ∈ [0, 1] 2N , and the cache can fetch from the server the objects that are in x t+1 but not in x t . In [START_REF] Salem | AC ¸AI: Ascent Similarity Caching with Approximate Indexes[END_REF] we discuss also an approach based on coupling the random variables x t and x t+1 to significantly reduce the number of fetched objects to update the cache state.

F. Time Complexity

AC ¸AI uses OMA in Algorithm 1 coupled with a rounding procedure DEPROUND. The rounding step may take O (N ) operations (amortized every M requests). 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.

Similarly, subgradient computation 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 in [9, Eq. ( 55)] require only a constant number of operations and complexity reduces to O (N ).

Finally, we adapted the Euclidean projection algorithm in [START_REF] Wang | Projection onto the capped simplex[END_REF] to obtain a neg-entropy Bregman projection (line 6 of Algorithm 1) that has O (N log N ) time complexity. The O (N log N ) is due to a sorting operation while the actual projection takes O (h). Again, most of the components of y t are equal to 0, so that we need to sort much less than N points.

G. Theoretical Guarantees

We observe that maximizing the gain ( 6) is NP-hard in general even for k = 1 under a stationary request process [START_REF] Garetto | Similarity caching: Theory and algorithms[END_REF]. Nevertheless, AC ¸AI provides guarantees in terms of the ψregret [START_REF] Krause | Submodular function maximization[END_REF]. In this scenario, the regret is defined as gain loss in comparison to the best static cache allocation in hindsight x * ∈ arg max for t = 1, 2, . . . , T do Incur a gain G(rt, yt), and receive a subgradient gt ∈ ∂yG(rt, yt) using [9, Eq. ( 55

G(r t , x * ) -E T t=1 G(r t , x t ) , (9)
where the expectation is over the randomized choices of DEPROUND. Note that the supremum in ( 9) 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. This modeling approach is commonly used to characterize system performance under highly volatile external parameters (e.g., the sequence of requests r t ) and has been recently successfully applied to caching problems [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] Bhattacharjee | Fundamental limits on the regret of online network-caching[END_REF].

Obviously, regret bounds in the adversarial setting provide strong robustness guarantees in practical scenarios. AC ¸AI has the following regret guarantee: Theorem IV.1. Algorithm 1 with M = 1 has a sublinear (1 -1/e)-regret in the number of requests, i.e., there exists a constant A such that:

(1 -1/e)-Regret T,X (OMA Φ ) ≤ A √ T . ( 10
)
where A ∝ c k d + c f . 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. We fully characterize the regret constant A in [START_REF] Salem | AC ¸AI: Ascent Similarity Caching with Approximate Indexes[END_REF].

A consequence of Theorem IV.1 is that the expected timeaverage (1 -1/e)-regret of AC ¸AI can get arbitrarily close to zero for 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 this kind of problems [START_REF] Nemhauser | Best algorithms for approximating the maximum of a submodular set function[END_REF].

Corollary IV.1.1. (offline solution) Let ȳ be the average fractional allocation ȳ = 1 T T t=1 y t of AC ¸AI, and x the random state sampled from ȳ using DEPROUND. ∀ > 0 and over a sufficiently large time horizon T , x satisfies

E 1 T T t=1 G(r t , x) ≥ 1 -1 e -1 T T t=1 G(r t , x * ).
where x * = arg max x∈X T t=1 G(r t , x).

V. EXPERIMENTS We evaluate AC ¸AI under different real world traces. We 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. Data-sets Description SIFT1M trace. SIFT1M is a classic benchmark data-set to evaluate approximate kNN algorithms [START_REF] Jegou | 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 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 constant probability λ i independently from previous requests. We spatially correlated requests 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 webstore 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. They also collected information about which users purchased or viewed the objects. 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 × 10 5 , 3 × 10 5 ]. 6The number of distinct objects requested in this trace is approximately 2 × 10 4 .

B. 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. 6 and the corresponding discussion for other choices). 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.

For every caching policy P, we can define its caching gain G P (r, x) as in Eq. ( 6). We can then 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 size equal to the whole catalog. In such 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 over T requests can then be defined as:

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

C. 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 1 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 naive 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 different cache sizes (Fig. 2), different values of the fetching cost c f (Fig. 3), and different values of k (Fig. 4). 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 from the server are similar and it is difficult to correctly decide how to satisfy the request. Caching policies performance are 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. 4).

Sensitivity analysis. We now evaluate the robustness of AC ¸AI to the configuration of its single parameter (the learning rate η). Figure 5 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 h = 1000. 7 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 6 shows the superiority of the negative entropy map: it allows 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 caching problems. It is possible to justify theoretically this result, considering the difference of subgradients norms for 7 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. 6. Euclidean: η = 10 -6 Fig. 6: Caching gain for AC ¸AI configured with negative entropy and Euclidean maps (SIFT1M trace). The cache size is h = 100 and k = 10. 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 on the basis of their costs (see Sec. IV-C), while leaving their cache updating mechanism unchanged. We then compute in the setting of Fig. 4 how much the gain of the second best policy (SIM-LRU for SIFT1M and CLS-LRU for Amazon) increases because of the use of AC ¸AI request service mechanism. This is the part of AC ¸AI improvement attributed to the use of the indexes, the rest is attributed to the cache update mechanism through OMA.

We observe from Fig. 7 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 for 20-35% for the Amazon trace.

VI. CONCLUSION

Edge computing provides computing and storage resources that may enable complex applications with tight delay guarantee 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 to reply to similarity search queries. Our solution adapts to the user requests, without any assumption on the traffic arrival pattern. AC ¸AI leverages on 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 state-of-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]Generalization through memorization: Nearest neighbor language models[END_REF], in which the size of the objects in the catalog is comparable to their d-dimensional representation in the index, and, as a consequence, the index size cannot be neglected in comparison to the local catalog size.

  r t , x). The ψ-regret discount the best Algorithm 1 Online Mirror Ascent (OMA Φ ) 1: procedure ONLINEMIRRORASCENT(y 1 = arg min y∈X ∩D Φ(y), x 1 = DEPROUND(y 1 ), η ∈ R + ) 2:

Fig. 1 :

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

Fig. 2 :

 2 Fig. 2: Caching gain for the different policies, for different cache sizes h ∈ {50, 100, 200, 500, 1000, 2000} and k = 10.

Fig. 3 :

 3 Fig.3: Caching gain for the different policies and different retrieval cost. 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. 4 :

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

3 Fig. 5 :

 35 Fig. 5: 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. 7 :

 7 Fig. 7: 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}. similarity caching and exact caching problems [9, Appendix D]. 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 on the basis of their costs (see Sec. IV-C), while leaving their cache updating mechanism unchanged. We then compute in the setting of Fig.4how much the gain of the second best policy (SIM-LRU for SIFT1M and CLS-LRU for Amazon) increases because of the use of AC ¸AI request service mechanism. This is the part of AC ¸AI improvement attributed to the use of the indexes, the rest is attributed to the cache update mechanism through OMA.We observe from Fig.7that 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 for 20-35% for the Amazon trace.

•

  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. {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), that quantifies the dissimilarity of a request r and an object o.

	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. An extended version is available online [9].

It contains additional results and more detailed proofs.

II. SIMILARITY CACHES

Consider a remote server that stores a catalog of objects N :=

More precisely, these are the k objects whose embeddings are closer to the embedding of r. From now on we identify objects and their embeddings.

Experiments on a 4-core Intel Core i7-4790,

GB RAM, 3.6 GHz.[START_REF] Venugopal | Shadow puppets: Cloud-level accurate AI inference at the speed and economy of edge[END_REF] Experiments on 2x2.8GHz Intel Xeon E5-2680v2, 4 Maxwell Titan X GPUs, CUDA 8.0.

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

Properly speaking OMA, only refers to the update of yt and does not include the randomized rounding scheme DEPROUND in lines 7-9.

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]).