Jelena Isacenkova

Davide Balzarotti
email: balzarotti@eurecom.fr

Measurement and Evaluation of a Real World Deployment of a Challenge-Response Spam Filter

Keywords: C.4 [Performance of Systems]: Measurement techniques, Performance attributes Experimentation, Measurement Spam, whitelist, challenge-response, blacklisting

Despite the number of existing solutions, spam still accounts for a large percentage of the email traffic on the Internet. Both the effectiveness and the impact of many common antispam techniques have already been largely studied and evaluated against multiple datasets. However, some of the less known solutions still lack a proper experimental validation. For example, Challenge-Response (CR) systems have been largely discussed, and often criticized, because they shift the effort to protect the user's mailbox from the recipient to the sender of the messages. In addition, these systems are believed to produce a lot of backscattered emails that further deteriorate the global Internet situation.

In this paper we present the first comprehensive measurement study of a real anti-spam system based on a challengeresponse technique. In our work we analyze a large amount of data, collected for a period of six months from over forty companies protected by a commercial challenge-response product. We designed our experiments from three different point of views: the end user, the system administrator, and the entire Internet community. Our results cover many different aspects such as the amount of challenges sent, the delay on the message delivery, and the likelihood of getting the challenge server blacklisted.

Our aim is neither to attack nor to defend CR-based solutions. Instead, we hope that our findings will shed some light on some of the myths about these kind of systems, and will help both users and companies to take an informed decision on the topic.

INTRODUCTION

Despite the considerable effort and the large amount of proposed solutions to detect and filter unsolicited emails, according to the MessageLabs Intelligence Annual Security Report [START_REF]Symantec's MessageLabs Intelligence[END_REF] published by Symantec, in 2010 spam still accounted for 89.1% of the emails on the Internet. Even worse, according to the same Symantec's report, in 2010 the spam volume increased by 1.4% compared with the previous year.

Traditional anti-spam solutions are based on two common techniques: filtering emails based on their content, or filtering them based on their senders. The first category includes content-based text classification techniques [START_REF] Bergholz | Improved phishing detection using model-based features[END_REF][START_REF] Drucker | Support vector machines for spam categorization[END_REF][START_REF] Sahami | A Bayesian approach to filtering junk e-mail[END_REF][START_REF] Sakkis | A memory-based approach to anti-spam filtering for mailing lists[END_REF]] that aim at finding (often using supervised learning) the tokens commonly associated to spam messages. The second category includes instead detection methods based on some properties of the sender [START_REF] Hao | Detecting spammers with SNARE: Spatio-temporal network-level automatic reputation engine[END_REF][START_REF] Pathak | Peeking into spammer behavior from a unique vantage point[END_REF][START_REF] Ramachandran | Filtering spam with behavioral blacklisting[END_REF], of his reputation [START_REF]The spamhaus project[END_REF][START_REF] Wong | Sender policy framework (SPF) for authorizing use of domains in e-mail, version 1[END_REF], or of the domain from which the email is delivered [START_REF] Delany | Domain-Based Email Authentication Using Public Keys Advertised[END_REF][START_REF] Fleizach | Slicing spam with occamâ ȂŹ s razor[END_REF][START_REF] Wong | Sender policy framework (SPF) for authorizing use of domains in e-mail, version 1[END_REF].

Even though these two categories cover most of the widely adopted techniques, a number of other solutions have also been proposed to fight spam. One notable example is represented by Challenge-Response (CR) filters [START_REF] Erickson | The Effectiveness of Whitelisting: a User-Study[END_REF][START_REF] Paganini | ASK: active spam killer[END_REF], a solution based on the observation that the large majority of good emails are delivered from senders that are already known to, and trusted by, the recipient. The name of the approach comes from the fact that, whenever the sender of an email is unknown (i.e., not yet in the user's personal whitelist), the system temporarily quarantines the email and automatically sends back a message to the sender, asking him to solve a simple challenge to verify his legitimacy. This technique somehow changes the traditional approach of treating incoming emails, shifting the delivery responsibility from the recipient to the sender of the message.

Since their first introduction, CR-based techniques have been considered an extremely controversial solution [START_REF]Why are auto responders bad[END_REF][START_REF]Challenge-Response Anti-Spam Systems Considered Harmful[END_REF]. On the one hand, they seem to be able to completely block any unsolicited email, but, on the other hand, they also have a number of side-effects that can seriously hamper their adoption on a large scale.

In particular, it is possible to group the main criticisms against CR systems around three main points. First, the social and usability issues that, on one side, are related to the efforts required from the user to maintain a proper whitelist, and, on the other, to the annoyance for the sender that has to invest time to solve a challenge in order to have his message delivered. Previous studies, in particular Erickson et al. [START_REF] Erickson | The Effectiveness of Whitelisting: a User-Study[END_REF], have already studied the usability of CR systems in controlled experiments. Their study concludes that such systems are very effective when accompanied with already existing anti-spoofing techniques. The authors also measure that CR solutions outperform traditional systems like Spa-mAssassin, generating on average 1% of false positives with zero false negatives.

The second point against CR systems concerns the fact that they can introduce a (possibly conspicuous) delay in the emails delivery due to the quarantine period applied to previously unknown senders. Finally, the last (and one of the main) critique against CR systems is due to the challenge emails sent in response to spam messages. Since unsolicited emails often contain spoofed sender addresses, the challenges are often delivered to non-existing recipients or to innocent users. These misdirected messages (often referred as "backscattered" spam) pollute the Internet with unnecessary traffic and damage other users that may receive challenges for emails they never sent. From this point of view, CR antispam filters seem to literally bounce the spam back towards other innocent users. However, supporters of the CR approach often rebut by saying that well-designed systems only send back a challenge to a few percents of the spam messages they receive. Therefore, considering the fact that real forged addresses are not too common, normal users are very unlikely to often receive misdirected challenges. Unfortunately, since both sides lack real data to support their own hypothesis, it is hard for users and companies to tell which is the truth and take a conscious decision.

To the best of our knowledge, this paper presents the first study on both the effectiveness and the impact of a realworld deployment of a challenge-based antispam solution.

In our work we measure and analyze a large amount of data collected for a period of six months from 47 companies protected by a commercial CR-based antispam product.

In particular, we conduct our measurements to analyze the behavior of CR systems from three different perspectives:

1. From the end user point of view, to measure how this technique affects the delivery of both spam and normal messages to the end user's mailbox;

2. From the server's administrator point of view, focusing on some of the problems of maintaining a CR installation in a real company;

3. From the Internet point of view, to measure the amount and the impact of backscattered messages and misdirected challenges.

It is important to stress the fact that the purpose of this study is neither to attack nor to defend CR-based solutions. Instead, our goal is to provide real-world figures and statistics that can help both users and companies to take an informed decision based on our study. Our results can also help to shed some light on some of the myths related to CR antispam techniques.

The rest of the paper is organized as follows. In Section 2 we introduce our data collection methodology and the dataset we used in our measurements. Section 3 presents a study of the amount of challenges sent by a CR system. Section 4 describes the effectiveness of CR systems in distinguishing spam from legitimate messages. Section 5 introduces some of the problems related to maintaining this type of antispam filter. Then, we summarize our findings in Section 6, present a survey of related work in Section 7, and finally conclude the paper in Section 8.

DATA COLLECTION

In this section, we describe the dataset we used in our experiments and we provide a short overview of our data collection methodology.

System Overview

Our study has been carried out within a company providing an anti-spam solution based on a challenge-response technique. Figure 1 presents the overall system architecture and a "weighted" lifecycle of the incoming emails. The CR filter consists of two main components: a message dispatcher and a set of additional spam filters.

The dispatcher receives the incoming messages from the company's Incoming Mail Transfer Agent (MTA-IN) server. Some of the email servers were configured to work as open relays, serving emails also for a restricted number of domains that are different from the ones in which the systems are installed. This configuration allows the server to accept messages not targeting to, or originating from, known users in the system.

The MTA-IN server first checks if the email address is well formed (according to RFC822 [START_REF] Crocker | RFC822: Standard for ARPA Internet Text Messages[END_REF]) and then if it is able to resolve the incoming email domain. In addition, if the server is not configured as an open relay, it also verifies that the recipient exists in the system.

Our study shows that this first layer of simple checks is responsible to drop more than 75% of the incoming messages (see Figure 2), while open-relay systems pass most of the messages to the next layer. These results are perfectly in line with similar values reported by the other analysis of spam delivery rate [START_REF] Stone-Gross | The underground economy of spam: A botmaster 2019s perspective of coordinating large-scale spam campaigns[END_REF][START_REF] Kanich | Spamalytics: An empirical analysis of spam marketing conversion[END_REF]. The reasons behind the dropped messages are summarized in the following The second check point for the incoming emails is at the internal email dispatcher. This component is the core of the CR infrastructure and it is the one responsible for deciding to which category the email belongs to: white, black or gray.

The white and black spools are controlled by the user's whitelist and blacklist. Emails in the black category are dropped immediately, while emails from senders in the whitelist are delivered to the user's INBOX. Emails matching none of the previous lists fall in the gray category. These messages are then filtered with additional antispam techniques (e.g., virus scan, reverse DNS and IP blacklisting). If an email passes the filters, then dispatcher sends a challenge-response message to the original sender containing a request to solve a CAPTCHA. Otherwise, the email is considered spam and it is dropped.

Figure 1 also reports the average number of messages for each spool, assuming that 1,000 emails are received by the MTA-IN. The figures are computed by aggregating the data of all the monitored servers not configured as open relay. Figure 3 shows that the other spam filters included in the CR engine drop on average 54% of the gray emails. Challenge messages are instead generated for 28% of emails. In the open relay cases, the engine filters have a lower performance rate, and the number of challenges sent increases by an extra 9%. This shows that, in an open relay configuration, the CR system receives more junk messages and it is more likely to reply with a challenge to illegitimate emails.

Whitelisting process

The process of email whitelisting involves both parties: the sender and the recipient. There exist several alternative ways for the email address to get added to a user's whitelist. In particular, the system we tested in our experiments supported the following mechanisms:

• The sender solves a challenge sent by the CR system as a response to one of his messages;

• The user authorizes the sender from the daily message digest;

• The address is manually added to the whitelist by the user;

• The user previously sent an email to that address.

In the general scenario, suppose that Alice sends an email to Bob, a user protected by a challenge-response system. If this is the first communication between Alice and Bob, the system temporarily stores the email in a "gray" spool and sends back a message to Alice. The message includes a link to a webpage that contains a CAPTCHA (the challenge) that Alice has to solve to get her email delivered and her address added to Bob's whitelist. After this simple authentication step, Alice's address is considered trustworthy, and the CR system will not interfere in any future communication between the two users, promptly delivering to Bob any further message coming from Alice.

If Alice does not solve the challenge, the email stays in the gray spool for a period of 30 days, after which it is dropped by the system. Bob also receives a daily digest that summarizes the quarantined messages, so that he can manually authorize them or delete them from the list.

General Statistics

In our experiment we collected statistical data about a commercial system deployed in 47 companies of different sizes. The monitoring period lasted for 6 months, between July and December 2010. For some of the servers we had access to the data for the entire time frame, while for other companies our collection was limited to a shorter period of time (with a minimum of 2 months).

In total we collected statics for 90 millions of incoming emails. All the results were sanitized to protect both the end users and the companies privacy. In particular, we never got access to the message bodies and we stored only aggregated figures obtained from the automated analysis of the email headers.

The data collection was performed on a daily basis by analyzing the logs of the MTAs and of the challenge-response engines. In addition, information about the solved CAPTCHAs was collected by analyzing the access logs of the web-server serving the challenges. The extracted information was stored 1 shows some general statistics about the dataset we collected. Each company's server was configured to protect certain users with the challenge-response system, while protecting other accounts by traditional anti-spam techniques. In this paper we limit our analysis to the 19,426 users protected by the CR solution (this number includes normal users as well as administrative accounts and other rarely used email addresses). The table also shows the total number of the messages that we analyzed, the breakdown in the different spools (white, black, and gray), and some statistics about the effectiveness of the other spam filters included in the system (discussed in more details in Section 5).

Finally, since the number of days in which we were able to collect data varies between companies (for a total of 5,249 analyzed days), the table also report some daily statistics.

PART I: THE INTERNET POINT OF VIEW

In this section we focus on the consequences of adopting CR spam filters from a global point of view. In particular, we present an evaluation of the amount of challenge emails sent out by a challenge-response system during normal operation.

These backscattered messages are often criticized for two main reasons: the fact that misdirected challenges can be delivered to innocent users, and the fact that a large amount of useless messages are poured into the Internet, thus increasing the global traffic and overloading third parties email servers.

In the rest of the section we provide real-world measurements to estimate the impact of these two phenomena.

Email Backscattering

From an external point of view, a challenge response system can be approximated by a black box that receives emails from the Internet and separates them in three categories: some (the white set) are delivered to the users Inbox, while others (the black set) are immediately flagged as spam and discarded. The remaining messages (the gray set) are the ones for which the system is unable to take a decision. Therefore, for each email in this set, the system sends back to the sender another email containing a challenge to be solved. In this simplified model, a challenge-response system can be seen as a software that receives a certain amount of emails, and "reflects" a fraction of them back to the senders. This fraction, that we call Reflection Ratio R, is an important parameter of a CR system.

By using the numbers in Figure 1, it is easy to compute the average reflection ratio: R = 48/249 = 19.3% for the emails reaching the CR filter (or, R = 48/1000 = 4.8% if we consider all the emails reaching companies' MTA-INs).

Understanding the Reflection Ratio

Is 19.3% a good value for R? If not, what would be a reasonable value? Unfortunately, it is very hard to answer these questions since it is not clear how to estimate which is an acceptable range for the reflection ratio.

To explain why, let us consider two extreme cases. In the first case, the CR system does not contain any other spam detector or blacklist mechanism. Therefore, the amount of challenges it sends is roughly the same as the amount of spam it receives, currently estimated between 80 and 90% [START_REF]Symantec's MessageLabs Intelligence[END_REF] of the total email traffic. Values of R close to this range are obviously unacceptable, since, from a global point of view, the system would just act as a spam multiplier.

In the second scenario, the CR system has been carefully configured and it has been associated with another perfect spam detector. In this case, the system never replies to spam and only sends back challenges to legitimate messages whose senders are not already in the recipients whitelist. In this case (represented by very low values of R) the system does not generate any backscattered emails. Therefore, it may seem to be the final goal to reach in a perfect CR system.

Unfortunately, a very low value of R also corresponds to a completely useless system. In fact, if the internal spam filter can already distinguish good messages from spam, there is no need to add a challenge response system on top of it. In other words, in order to be useful a CR system has to be able to "substantially" reduce the amount of spam received by the users. However, this can only happen if the system sends back an equivalent "substantial" number of backscattered messages.

To conclude, the reflection ratio is a good indicator of the amount of challenges generated by a CR system. At the same time, it is important to be extremely careful to use this value alone to draw conclusions about the quality of such systems.

Misdirected Challenges

So far, we focused on the amount of challenges generated by a CR system. However, this value only measures the amount and not the real impact of the generated emails. In fact, not all the challenges are the same. Some of them reach the real senders and, despite being a little nuisance, could be tolerated as an acceptable price to pay for fight- ing spam. We refer to them as legitimate challenges. A second class of them is directed to non-existing addresses, and, thus, constitutes garbage traffic on the network. Finally, some misdirected challenges are delivered to existing spoofed email addresses, therefore reaching other innocent users. This category is much more harmful, and it is often referred to as backscatter spam (note that not all the backscattered messages are spam).

In order to distinguish the three categories of challenges, we analyzed the status of the challenge delivery in the servers' logs. In the systems under analysis, we found that only 49% of the challenges were successfully delivered to the destination servers. The remaining 51% were either bounced, or expired after many unsuccessful attempts (see Figure 4(a)). In the bounced set, a small portion has been stopped because the server that sent the challenges has been temporarily blacklisted (the problem will be discussed in more details in Section 5), while the large majority (71.7%) has been bounced due to the fact that the recipient address did not exist. This value provide a reasonable estimation of the amount of challenges that belong to the second category.

Another piece of the puzzle can be found by measuring the number of challenges that were actually solved. Previous work [START_REF] Erickson | The Effectiveness of Whitelisting: a User-Study[END_REF], conducted in a controlled environment, estimated that about 50% of the challenges were never solved. Unfortunately, our study shows a completely different picture. According to the web servers' logs of the companies we analyzed, on average 94% of the CAPTCHA URLs included in the delivered challenges were never even opened. The remaining were either solved (4%) or were visited by the user but not solved (0.25%). Figure 4(b) also shows the average number of attempts required to solve the CAPTCHAs. The fact that we never observed more than five attempts support the fact that probably there are still no real cases of attack against CR systems based on trying to automatically solve the challenges.

So far, we estimated the legitimate challenges to be at least 4% and the ones sent to non-existing recipients to be around 36.6% (71.7% of the 51% of undelivered messages). The third category, i.e., the backscattered spam, can instead be approximated with the number of challenges correctly delivered but never solved, i.e. somewhere between 0 and 45 %.

By combining the percentage of backscattered spam with the reflection ratio we presented before, we obtain the Backscattered Ratio β, i.e., the ratio of incoming emails for which the CR system sends back a misdirected challenge to the wrong user. In our experiments, we obtain, in the worst case, β = 8.7% (at the CR filter) or 2.1% (at the MTA-IN).

However useful, these figures must be considered only approximate upper bounds. For example, it is possible that challenge messages get dropped by some spam filter after being successfully delivered, or that real users ignore or intentionally decide to not solve a particular challenge. Finally, there are automatically generated emails (notifications from websites, mailing lists, receipts of purchase, . . . ) to take into account. When a user expects to receive such messages, he should either use an email address not protected by the CR system (functionality provided by the commercial product we have evaluated), or manually add the address to the whitelist.

Unfortunately, this is not always the case. In fact, we measured that around 2% of the message addresses in the gray spool have been whitelisted manually by the users from the daily digest. In other words, the challenge was not delivered or it was not solved, but the user recognized that the message was not spam and he manually added the sender to his whitelist to allow future communications.

Traffic Pollution

The reflection ratio only measures the number of messages, without taking into account their size. Therefore, it is not a very accurate indicator to estimate the amount of traffic generated by a challenge response system. For that purpose, we need to extend the previous definition by introducing the ReflecteD Traffic ratio RT , that represents the ratio between the amount of traffic received by the system and the amount of email traffic generated for the challenges.

To measure this new value, we deployed to all the servers a new sensor that extracts from the email headers the total size of the incoming messages and the total size of the outgoing challenges. Over a month period, the average ratio we measured at the CR filter was RT = 2.5%. Unfortunately, we could not get a similar measure at the entrance of the MTA-IN servers. However, since the number of messages at MTA-IN is in average four times bigger than at the CR filter (see Figure 1), we can estimate that a large scale deployment of challenge-response spam filters would increase the email traffic on the Internet of around 0.62%.

Data Variability

In previous sections we reported aggregated figures for a number of different factors that can be used to estimate the "external" impact of a CR system.

In order to preserve the companies' privacy, each value was obtained by combining together the data collected from all the monitored installations. However, it is interesting to investigate what the variance of those values is, and if the size of the company affects in some way the presented indicators. For instance, it could be the case that CR filters work better for small companies, but fail to scale well to larger installations.

Figure 5 shows a scatter plot of five variables: the number of protected accounts (users), the amount of emails re- ceived daily (emails), the percentage of emails delivered in the white spool (white), the reflection ratio at the CR filter (reflection), and the percentage of challenges solved (captcha).

This graph represents a very efficient way to convey a large amount of information about the five variables. On the diagonal, it shows the histograms of the values of each variable. For example, the first element on the diagonal shows that most of the companies have less than 500 users, with few exceptions that have more than 2,000 users. Some values have a very high variability, such as the percentage of white emails that varies from less than 10% to over 70%. However, the two main coefficients we have measured in this Section, i.e. the reflection ratio and the percentage of solved challenges, seem to stay constant between different installations. The percentage of solved challenges only varies between 2% and 12%, and the reflection ratio stays in the range of 10% to 25%.

In Figure 5, the plots below the diagonals show the correlation between every pair of variables, while the upper part of the graph reports the corresponding correlation values (the font size allows to immediately focus on the higher values). Notably, the percentage of challenges sent by a CR system (reflection) is not correlated to the size of the companies (users) or to the amount of emails received. Not surprisingly, a small inverse correlation exists instead with the percentage of white emails. In other words, servers that receive a large amount of white emails (and therefore a lower amount of spam), tend to send less challenges and vice versa.

The rate of solved challenges (captcha) shows more correlations with other values, and in particular it is also strongly correlated with the white percentage. However, as the histogram shows, the variability of the captcha variable is so small that it can be considered almost a constant between the different installations.

PART II: THE USER POINT OF VIEW

Despite the backscattering phenomenon described in the previous section, CR systems are often considered one of the most effective ways to protect users from spam. In theory, if the challenge-response system is properly configured, these systems should be able to achieve a 100% detection rate, thus blocking all unsolicited emails. However, previ- ous studies [START_REF] Erickson | The Effectiveness of Whitelisting: a User-Study[END_REF] that confirmed this value were conducted on prototype systems evaluated in a controlled environment.

In this section we measure if this is actually the case in a real-world installation, and we evaluate the real impact for the end users protected by a CR system. In particular, we measure the delay introduced in the legitimate emails delivery, and the amount of spam that is able to reach the final users despite the CR filter. In addition, we also measure the change rate of the users' whitelists, one of the foundations of this kind of antispam solution.

Spam Protection

The main purpose of a CR system is to block all automatically generated emails coming from addresses previously unknown to the recipient. The first obvious consequence of this approach is that CR solutions are ineffective by design against targeted attacks, i.e., attacks in which the attacker manually composes a malicious message to target a particular individual. In fact, if the attacker receives back the challenge message, he can easily solve it and have his message delivered to the recipient. However, a recent Symantec report [START_REF]Symantec's MessageLabs Intelligence[END_REF] estimated that only one out of 5,000 spam messages contains a targeted attack. In addition, all the existing anti-spam mechanisms can be easily evaded by targeted attacks, and, therefore, we can consider this threat beyond reach of all existing anti-spam solutions.

Unfortunately, targeted attacks are not the only ones that can pass through a CR filter. By studying a dataset of bounced challenges, we noticed that a large number of messages had the same subject and the same size. Per se, this is not surprising. However, a closer look revealed that while most of the messages were bounced or dropped by the filter, in some cases one of those emails was successfully delivered to the final user's mailbox.

To better investigate the reason behind this sporadic phenomenon, we decided to analyze the behavior, in terms of challenges and delivered messages, of a number of large spam campaigns.

For our experiment we applied standard clustering algorithms to the subject of the messages in the gray spool (i.e., the ones for which the system generated a challenge message). In particular, we put in the same cluster the messages with the same subject, limiting the analysis to the ones at least 10 words long. Finally, we discarded the clus-ters containing less than 50 emails. These very conservative thresholds were adopted to greatly reduce the risk of misclassification. In reality, the large majority of emails (including spam) have much shorter subjects, or they have enough variability to elude our simple comparison algorithm. However, our target was not to be able to cluster and identify all the incoming emails or all the spam campaigns, but just to identify a number of them with a low percentage of false positives.

The results obtained over a three month monitoring period are summarized in Figure 6. Our system identified 1,775 clusters, containing between 50 and 3696 messages each. In the next step, we divided the clusters in two categories, based on the sender email similarity. In the first group we put all the clusters where emails are sent by a very limited number of senders, or in which the sender addresses are very similar to each other (for example, deptx.p@scn-1.com, dept-x.q@scn-1.com, and dept-x.p@scn-2.com). These clusters are likely associated to newsletters or marketing campaigns. The second group contains instead the clusters with a very low sender similarity, i.e., the ones in which most of the emails originate from different domains and different senders' addresses. This behavior is very common in spam campaigns sent by malware infected machines.

Figure 6 shows that only 28 out of 1774 clusters contain at least one solved challenge. Moreover, these few clusters have very different characteristics, depending on whether they belong to the first or the second category. The ones with high sender similarity have a higher rate of solved challenges (some clusters as high as 97%) and almost no bounced emails. The clusters with low sender similarity have instead on average 31% of emails bounced because of non-existing recipient, and only one or two captchas solved each.

This second category is particularly interesting for our study. Each cluster in this group contains hundreds of emails, coming from many different domains, and often from nonexisting sender addresses. However, out of these messages, sometimes one of the challenges was solved and, therefore, the email got whitelisted and delivered to the recipient's mailbox. These spam messages that are able to pass through the CR defense are likely a side effect of backscattered challenges that are sometimes erroneously delivered to innocent users. As a result, it is possible that one of these users solves a challenge for a mail he never sent. This phenomenon is, however, extremely rare. According to our measurements, we estimate that this kind of spurious spam delivery occurs ∼1 every 10,000 challenges sent. According to Table 1, this rate translates to an average of five spam delivery a day, over the 47 companies in our dataset. Excluding these isolated cases, CR systems are actually able to block all incoming spam messages.

Impact on Messages Delivery

Another consequence of blocking automatically generated emails is the fact that also normal emails can get blocked and remain in the user's graylist waiting for the corresponding challenges to be solved. This can happen for two reasons: because the sender still has to solve the challenge, or because the email is sent by an automatic system and the challenge is, therefore, dropped or never delivered. In both cases, the user fails to receive a (maybe important) email.

Figure 7 shows the CDF of the messages that were moved from the graylist to the whitelist in the monitored servers. The two curves report the percentage of messages that were whitelisted because the sender solved the challenge, and the ones that were whitelisted manually by the user from the daily digest. According to the graph, 30% of the messages are delayed less than 5 minutes, and half of them are delivered in less than 30 minutes. However, if the challenge was not solved after 4 hours, then it is likely that it will not be solved at all (Figure 8). In those cases, the user has to manually select the messages from the digest, with a delivery delay that is on average between 4 hours and 3 days.

Combining the values from these figures with the number of white and whitelisted emails (31 and 2 respectively) in Figure 1, we can conclude that:

• 31/33 = 94% of the emails in the user's INBOX are sent from addresses already in the whitelist, and, therefore, are delivered instantly.

• Out of the remaining 6% (2/33) of the messages that are quarantined in the gray spool, half of them are • Only 0.6% (10% of the 6%) of the messages were delivered with more than one day of delay.

Whitelists' Change Rate

We conclude this section on the user point of view with an analysis of the rate at which the users' whitelists change over time. For this experiment we monitored the number of changes in the users' whitelists for a period of two months. Email addresses can be added to a whitelist in four different ways, two manual and two automated. A user can manually import a new entry or he can whitelist a certain address from the digest. Automatically, new entries are included when the user sends a mail to those addresses or when the senders solve the challenges generated by the CR system.

During the monitored period, 9267 whitelists were modified at least once. Out of them, only 6.8% had at least 1 new entry per day (on average), and the percentage drops even further when we look at higher changing rates (2.1% of the whitelists had at least 2 new entries per day, and 0.2% at least 5). Figure 9 presents a more detailed histogram of the frequency of changes. The graph shows how the large majority of the whitelists are, in fact, constantly in a steady state.

Finally, we monitored the amount of new messages present in the daily digest. This value varies greatly between users and also between different days. Figure 10 shows examples extracted from three different users. Some of them have constantly a large number of messages in the gray spool, while others have normally very small daily digests with anomalous peaks in conjunction to particular user behavior or unusually large amount of spam messages.

Again, a large size of the digest is at the same time a good and a bad factor for a CR system. In fact, a high number of messages means that the system is blocking a substantial amount of spam that would have been otherwise delivered to the user (remember that these are messages that successfully pass through the antivirus, reverse DNS, and the SpamHouse blacklist). On the other side, a large digest is also a negative factor as it increases the amount of work for the user that has to manually verify its content to doublecheck that he did not miss any important message. Finally, this also demonstrates that the degree to which CR system works depends a lot on the interplay of users' involvement. Some recipients may diligently weed out their digest, while others may let it grow hoping for the senders to respond to the challenges.

PART III: THE ADMINISTRATOR POINT OF VIEW

In this section we analyze some of the issues related to maintaining challenge-response systems from the system administrator point of view. In particular, we focus on the effort required to maintain the challenge-response infrastructure, and on the additional antispam techniques that can be integrated in the system to reduce the backscattering effect.

Server Blacklisting

As we already described in Section 4, when a CR system sends a challenge in response to a message with a spoofed sender's address, the challenge is delivered to a recipient that may not exist. As a result, these challenge-response messages can hit a spam trap [START_REF] Ramachandran | Filtering spam with behavioral blacklisting[END_REF], i.e., a set of email addresses that are maintained and distributed with the sole purpose to lure spam.

The emails collected by those traps are often adopted by popular services (e.g., SpamHaus [START_REF]The spamhaus project[END_REF], SORBS [START_REF]Spam and Open-Relay Blocking System[END_REF], Spam-Cop [START_REF]SpamCop[END_REF]) to update their blacklists. Hence, the IP used to send the challenges can itself get blacklisted as a result of the backscattered spam it sends. In order to reduce the impact of being blacklisted, one third of the systems we tested in our experiments were configured to rely on two MTA-OUT servers (with different IP addresses): one to send the challenges and another to send the outgoing user emails.

Our initial hypothesis was that the probability that a In other words, we expected that systems sending more challenges were blacklisted more often, thus making CR solutions more difficult to maintain for large companies. Surprisingly, our experiments proved us wrong. Using the data we collected we were able to estimate the rate at which various challenge server IPs get blacklisted. In particular, we followed two parallel approaches. In the first, we analyzed one month of data for 32 companies, measuring the ratio between the number of challenges sent and the number of blacklist-related error messages received from the challengeresponse recipients. The result, summarized on a logarithmic scale in Figure 11, shows that while most of the servers had no problem at all with blacklisting, some of them were often blacklisted, even for a few days in a row. However, there seems to be no relationship between the server blacklisting ratio and the number of challenges it sends.

The main problem with this approach is that the error messages received when delivering the challenges were not always very accurate, providing results that may not be completely reliable. Therefore, we decided to complement our analysis with a second technique, based on an automated script that periodically checked for the IP addresses of the CR servers in a number of services that provide an IP blacklist for spam filtering. In particular, our tool queried the blacklists provided by Barracuda [1], SpamCop [START_REF]SpamCop[END_REF], SpamHause [START_REF]The spamhaus project[END_REF], Cannibal [START_REF]Spam Cannibal[END_REF], Orbit [START_REF] Orbitrbl | [END_REF], SORBS [START_REF]Spam and Open-Relay Blocking System[END_REF], CBL [START_REF]Composite Blocking List[END_REF], and Surriel [START_REF]Passive Spam Block List[END_REF]. The queries were performed every 4 hours for a period of 132 days (between September 2010 and January 2011).

The results of this second analysis confirm our previous finding. In more than four months, 75% of the servers never appeared in any blacklists. Few servers were blacklisted for less than one day, while the remaining four servers experienced some serious problems, appearing in at least one of the blacklists for many consecutive days (17, 33, 113, and 129 respectively). Again, between the top 3 server (according to the traffic and the number of challenges sent) none appeared in any of the blacklists during our experiment. Thus, proving again that there is no direct link between the number of times a server gets blacklisted and the server size.

Combining CR Systems Other Spam Filters

Our final evaluation focuses on the combination of CR systems with other antispam solutions. As already mentioned in Section 2, the product analyzed in our experiments includes three other spam filters in order to reduce the number of useless challenges sent in response to spam messages. It employs a traditional antivirus to scan the emails, an IP blacklist provided by SpamHause [START_REF]The spamhaus project[END_REF] to filter out known spammers, and a reverse DNS lookup to exclude suspicious origins.

According to Table 1 and Figure 1, the combination of these filters was responsible for dropping 77.5% of the messages in the gray spool. One may argue if this is good enough, or if a much better result could be obtained by introducing other antispam techniques. This is a difficult question to answer, since the main drawback of adding new filters is that they also introduce false positives, to avoid which CR systems were introduced in the first place.

However, we decided to experiment with one additional spam filter based on the verification of the Sender Policy Frawework [START_REF] Wong | Sender policy framework (SPF) for authorizing use of domains in e-mail, version 1[END_REF] (SPF). SPF was introduced to detect source address spoofing, that is one of the main problems of CR systems. Since SPF checks were not included in the product we evaluated in this paper, we decided to evaluate the potential impact of this filter by using an offline tool to automatically test all the emails in the gray spool. Figure 12 shows the results of our experiment, grouped by different message categories. For instance, by dropping the emails for which the SPF test fails, it would be possible to reduce by almost 9% the challenges that cannot be delivered (expired), and 4.10% of the bounced ones. The overall result shows that SPF can further reduce the number of "bad" challenges by 2.5%, at the cost of loosing 0.25% of the challenges that are actually solved by the sender.

DISCUSSION

Even though the aim of this work is neither to attack nor to defend challenge-response systems, it may be natural to ask what conclusions about this class of antispam solutions could be drawn from our measurements.

In the rest of this section we summarize the main findings we presented in the previous three sections.

Whitelist Assumptions

All approaches based on white-lists share two main assumptions: first, that the large majority of the "good" emails come from senders already in the recipient's whitelist, and, second, that these lists eventually reach a steady state where changes do not occur very often.

Both claims are supported by our experiments. In fact, over 43 companies, only 2/33 = 6.1% of the incoming emails delivered to the users' INBOX require a challenge-response phase (see Figure 4) and 2% require the user to manually pick the message from the digest.

The stability of the whitelists was already evaluated by Erickson et al. [START_REF] Erickson | The Effectiveness of Whitelisting: a User-Study[END_REF], showing that the major burden on the user is concentrated in the first three weeks, after which the number of changes drops on average to one per day. Our experiments show that, in a real deployment, there are on average 0.3 new entry per user per day (excluding new users). Only 6.8% of the users had at least one daily change in their whitelists.

Delivery Delay

Another common critique of CR systems is due to the fact that the challenge-response step introduces a delay in the incoming email delivery. This is obviously an unavoidable side-effect, but our measurements show that it also has a limited impact. In fact, according to our study, it concerns only 4.3% of incoming emails and in half of the cases the delay is below 30 minutes. Even though the remaining 2.15% may still be an unacceptable inconvenient for certain users, we believe that for most of the users it would be a reasonable price to pay to protect against spam.

Challenge Traffic

Most of the criticisms against CR systems, and most of the hassles for the system administrators, come from the challenges that are sent to the wrong recipients. If they correspond to existing email accounts, the misdirected challenges become a spam for other users. On the other hand, if the addresses do not exist, the challange may hit a spamtrap. And on top of that, they constitute useless traffic over the Internet.

Our study shows that, on average, a CR system sends back one challenge for every 21 emails it receives (see Section 3), accounting for a traffic increase of less than 1%. These figures depend on the amount of spam received by the server, and seems to be more or less constant between small and large servers.

Unfortunately, the large part of the challenges sent are indeed useless (only about 5% of them are solved). But, as we already explained in the paper, these challenges are "required" to justify the system. In other words, without useless challenges, it would be the CR system to be useless. Therefore, this can be considered an intrinsic and unavoidable limitation of systems based on a challenge-response approach.

Our findings confirm that the backscattered phenomenon is the main problem of solutions based on challenge-response technique. Each installation must be carefully configured in order to minimize the impact of misdirected challenges on other real users. The administrator also has to decide which other additional antispam techniques should be combined with the CR filter to maximize the benefits and, at the same time, to reduce the side effects and the risk of having the servers' IP blacklisted. However, the backscattered phenomenon is intrinsic in the behavior of a CR system and cannot be completely eliminated. From a company, the single most negative argument against the adoption of CR system is the fact that the challenge server can occasionally get blacklisted. Even worse, an attacker could intentionally forge malicious messages with the goal of forcing the server to send back the challenge to spam trap addresses, thus increasing the likelihood of getting the server IP added to one or more blacklist.

Other Limitations

This paper does not cover all aspects related to the adoption of a challenge-response system. We focused on performing a set of measurements based on real installations that were not under our direct control. Therefore, we intentionally excluded from our studies any evaluation of potential attacks against CR systems (like trying to spoof the sender address using a likely-whitelisted address).

In addition, in order to protect the users and the companies' privacy, we limited our study to the statistical information that can be automatically extracted from the headers of the messages. This ruled out other potentially interesting experiments that would have required access to the email bodies.

RELATED WORK

Most of the spam blocking techniques proposed by previous research fall into two categories: content-based and sender-based filtering. Content-based spam filtering techniques rely on signatures and classification algorithms applied to the emails content [START_REF] Sahami | A Bayesian approach to filtering junk e-mail[END_REF][START_REF] Androutsopoulos | An evaluation of naive bayesian anti-spam filtering[END_REF][START_REF] Drucker | Support vector machines for spam categorization[END_REF][START_REF] Bergholz | Improved phishing detection using model-based features[END_REF][START_REF] Sakkis | A memory-based approach to anti-spam filtering for mailing lists[END_REF]. Although content-based filters were initially very effective and provided an acceptable defense against spam [START_REF] Lowd | Good word attacks on statistical spam filters[END_REF], with the evolution of the spam sophistication they became less effective over time.

Sender-based spam filtering techniques aim instead at blocking spams by analyzing information about the sender. To date, a wide range of sender-based filtering solutions has been proposed, including sender authentication (e.g., SPF [START_REF] Wong | Sender policy framework (SPF) for authorizing use of domains in e-mail, version 1[END_REF], DMIK [START_REF] Delany | Domain-Based Email Authentication Using Public Keys Advertised[END_REF], and Occam [START_REF] Fleizach | Slicing spam with occamâ ȂŹ s razor[END_REF]), sender IP reputation [START_REF]The spamhaus project[END_REF], network-level feature categorization, sender whitelisting, and detecting anomalies on the sender's behavior.

Sender authentication techniques authenticate the sender either by verifying it's domain [START_REF] Wong | Sender policy framework (SPF) for authorizing use of domains in e-mail, version 1[END_REF][START_REF] Delany | Domain-Based Email Authentication Using Public Keys Advertised[END_REF] or by providing a protocol to authenticate the server at each message delivery [START_REF] Fleizach | Slicing spam with occamâ ȂŹ s razor[END_REF]. These kind of solutions are quite effective to prevent email spoofing, a phenomenon that is very common among spammers.

Approaches based on IP reputation [START_REF]The spamhaus project[END_REF][START_REF] Jung | An empirical study of spam traffic and the use of DNS black lists[END_REF] rely on whitelists or/and blacklists of IP addresses that are known either to send spam or to be a trusted source. Therefore, these approaches are effective against static spammers and openrelay servers used for spam distribution. On the other hand, they are not able to provide the same degree of protection against spam sent through botnets, since botnets can change the sender's IP address by using a large number of different infected machines to deliver the messages.

Behavior-based solutions, like the ones proposed by Pathak et al. [START_REF] Pathak | Peeking into spammer behavior from a unique vantage point[END_REF] or Ramachandran et al. [START_REF] Ramachandran | Filtering spam with behavioral blacklisting[END_REF], and network-level de-tection techniques, like the one proposed by Hao et al. [START_REF] Hao | Detecting spammers with SNARE: Spatio-temporal network-level automatic reputation engine[END_REF], tend to react faster to spam campaigns and have a lower number of false-positive. However, these kind of solutions block only part of illegitimate emails, and, therefore, they have to be used in combination with other filters.

Beside the more common techniques presented so far, a number of other solutions have been proposed to protect users against spam. For example, fine-grained approaches have been proposed based on personal white and blacklists.

The assumption behind such techniques is that users communicate mainly with a list of contacts that does not change much over time [START_REF] Bernstein | Internet mail 2000[END_REF][START_REF] Duan | Diffmail: A Differentiated Message Delivery Architecture to Control Spam[END_REF][START_REF] Erickson | The Effectiveness of Whitelisting: a User-Study[END_REF].

In this case, the main problem is to provide an automated way to populate and maintain the users whitelist. Garris et. al. [START_REF] Garriss | Reliable email[END_REF] proposed a solution to this problem based on the idea of sharing the whitelist content with the user's friends on social networks. Their cryptographic solution addresses also the sender spoofing problem, and the protection of the privacy of the users during the friend list sharing process. The main limitation of their system is the fact that it requires a large-scale adoption by many social networking users.

One of the most wide-spread approaches for building and maintaining a list of trusted senders is based on the adoption of a challenge-response technique [START_REF] Mastaler | Tagged message delivery agent[END_REF][START_REF] Paganini | ASK: active spam killer[END_REF][START_REF]Spam Arrest[END_REF][START_REF]Total Block[END_REF]6], already largely described in the rest of the paper.

Although challenge-response schemes are extremely successful in blocking spam, they also have a number of limitations that makes them disadvantageous over other solutions [START_REF] Erickson | The Effectiveness of Whitelisting: a User-Study[END_REF]. Additionally, CR solutions received a great amount of critiques from the anti-spam community [START_REF]Why are auto responders bad[END_REF][START_REF]Challenge-Response Anti-Spam Systems Considered Harmful[END_REF], often because of the amount of challenge emails they generate.

To the best of our knowledge, the only empirical study that analyzes challenge-response based whitelisting systems is presented by Erickson et.al. [START_REF] Erickson | The Effectiveness of Whitelisting: a User-Study[END_REF]. The authors focus on the deployment and the usability of such systems. The results of their evaluation support the usability of CR systems, but also show their limitations in coping with automatically generated legitimate emails, such as newsletters and notifications. On the other hand, the authors concluded that challenge-response systems are very successful to prevent spam and have lower false positives and false negatives rates compared to traditional content filtering techniques like Spa-mAssassin.

Our work aims instead to present a comprehensive study of a real-world whitelisting challenge-response antispam system, evaluating it's effectiveness and it's impact on the endusers, Internet, and server administration.

CONCLUSIONS

In this paper we present the first measurement study of the behavior of a real world deployment of a challengeresponse antispam system. The experiments lasted for a period of six months, covering 47 different companies protected by a commercial CR solution.

In particular, we measure the amount of challenges generated by these systems and their impact in terms of traffic pollution and possible backscattered messages delivered to innocent users. We then measure the amount of emails that are delayed due to the quarantine phase, and the amount of spam that is able to pass through the filter and reach the users mailboxes. Finally, we focus on a problem that is less known, i.e., the fact that the invitations sent by these sys-tems can accidentally hit a spamtrap and cause the email server to be blacklisted.

Our findings can be used to evaluate both the effectiveness and the impact of adopting this class of techniques. We hope that the figures provided in this paper may help to settle the long debate between advocates and opponents of CR systems.

Figure 1 :

 1 Figure 1: Lifecycle and distribution of incoming emails

Figure 2 :

 2 Figure 2: MTA-IN email treatment

Figure 3 :

 3 Figure 3: Message category at the internal email processing engine

Figure 4 :

 4 Figure 4: Challenge statistics

Figure 5 :

 5 Figure 5: Histograms and correlations between different dimensions. Graphs on the diagonal represent the data histogram. Below the diagonal are the plots of the correlation between every pair of variables, summarized by the correlation values reported above the diagonals.

Figure 6 :

 6 Figure 6: Spam clustering statistics

Figure 7 :Figure 8 :

 78 Figure 7: Cumulative effect of Captcha and Digest whitelisting

Figure 9 :Figure 10 :

 910 Figure 9: Distribution of the number of changes in users' whitelist

Figure 11 :

 11 Figure 11: Server blacklisting rate

Figure 12 :

 12 Figure 12: SPF validation test

table :

 :

	Dropped Percentage Reason
	0.06% Malformed email
	4.19% Unable to resolve the domain
	2.27% No relay
	0.03% Sender rejected
	62.36% Unknown Recipient


Nicolò Cesa-Bianchi
email: nicolo.cesa-bianchi@unimi.it

Pierre Gaillard
email: pierre.gaillard@ens.fr

Gábor Lugosi
email: gabor.lugosi@upf.edu

Gilles Stoltz
email: gilles.stoltz@ens.fr

Mirror Descent Meets Fixed Share (and feels no regret)

Mirror descent with an entropic regularizer is known to achieve shifting regret bounds that are logarithmic in the dimension. This is done using either a carefully designed projection or by a weight sharing technique. Via a novel unified analysis, we show that these two approaches deliver essentially equivalent bounds on a notion of regret generalizing shifting, adaptive, discounted, and other related regrets. Our analysis also captures and extends the generalized weight sharing technique of Bousquet and Warmuth, and can be refined in several ways, including improvements for small losses and adaptive tuning of parameters.

Introduction

Online convex optimization is a sequential prediction paradigm in which, at each time step, the learner chooses an element from a fixed convex set S and then is given access to a convex loss function defined on the same set. The value of the function on the chosen element is the learner's loss. Many problems such as prediction with expert advice, sequential investment, and online regression/classification can be viewed as special cases of this general framework. Online learning algorithms are designed to minimize the regret. The standard notion of regret is the difference between the learner's cumulative loss and the cumulative loss of the single best element in S. A much harder criterion to minimize is shifting regret, which is defined as the difference between the learner's cumulative loss and the cumulative loss of an arbitrary sequence of elements in S. Shifting regret bounds are typically expressed in terms of the shift, a notion of regularity measuring the length of the trajectory in S described by the comparison sequence (i.e., the sequence of elements against which the regret is evaluated). In online convex optimization, shifting regret bounds for convex subsets S ⊆ R d are obtained for the projected online mirror descent (or follow-the-regularized-leader) algorithm. In this case the shift is typically computed in terms of the p-norm of the difference of consecutive elements in the comparison sequence -see [START_REF] Herbster | Tracking the best linear predictor[END_REF][START_REF] Zinkevich | Online convex programming and generalized infinitesimal gradient ascent[END_REF] and [START_REF] Cesa-Bianchi | Prediction, learning, and games[END_REF].

We focus on the important special case when S is the simplex. In [START_REF] Herbster | Tracking the best linear predictor[END_REF] shifting bounds are shown for projected mirror descent with entropic regularizers using a 1-norm to measure the shift. 1 When the comparison sequence is restricted to the corners of the simplex (which is the setting of prediction with expert advice), then the shift is naturally defined to be the number of times the trajectory moves to a different corner. This problem is often called "tracking the best expert" -see, e.g., [START_REF] Herbster | Tracking the best expert[END_REF][START_REF] Vovk | Derandomizing stochastic prediction strategies[END_REF][START_REF] Herbster | Tracking the best linear predictor[END_REF][START_REF] Bousquet | Tracking a small set of experts by mixing past posteriors[END_REF][START_REF] György | Tracking the best of many experts[END_REF], and it is well known that exponential weights with weight sharing, which corresponds to the fixedshare algorithm of [START_REF] Herbster | Tracking the best expert[END_REF], achieves a good shifting bound in this setting. In [START_REF] Bousquet | Tracking a small set of experts by mixing past posteriors[END_REF] the authors introduce a generalization of the fixed-share algorithm, and prove various shifting bounds for any trajectory in the simplex. However, their bounds are expressed using a quantity that corresponds to a proper shift only for trajectories on the simplex corners.

In this paper we offer a unified analysis of mirror descent, fixed share, and the generalized fixed share of [START_REF] Bousquet | Tracking a small set of experts by mixing past posteriors[END_REF] for the setting of online convex optimization in the simplex. Our bounds are expressed in terms of a notion of shift based on the total variation distance. Our analysis relies on a generalized notion of shifting regret which includes, as special cases, related notions of regret such as adaptive regret, discounted regret, and regret with time-selection functions. Perhaps surprisingly, we show that projected mirror descent and fixed share achieve essentially the same generalized regret bound. Finally, we show that widespread techniques in online learning, such as improvements for small losses and adaptive tuning of parameters, are all easily captured by our analysis.

Preliminaries

For simplicity, we derive our results in the setting of online linear optimization. As we show in the supplementary material, these results can be easily extended to the more general setting of online convex optimization through a standard linearization step.

Online linear optimization may be cast as a repeated game between the forecaster and the environment as follows. We use ∆ d to denote the simplex q ∈ [0, 1] d : q 1 = 1 .

Online linear optimization in the simplex. For each round t = 1, . . . , T , 1. Forecaster chooses

p t = ( p 1,t , . . . , p d,t ) ∈ ∆ d 2. Environment chooses a loss vector ℓ t = (ℓ 1,t , . . . , ℓ d,t ) ∈ [0, 1] d 3. Forecaster suffers loss p ⊤ t ℓ t .
The goal of the forecaster is to minimize the accumulated loss, e.g., L T = T t=1 p ⊤ t ℓ t . In the now classical problem of prediction with expert advice, the goal of the forecaster is to compete with the best fixed component (often called "expert") chosen in hindsight, that is, with min i=1,...,T T t=1 ℓ i,t ; or even to compete with a richer class of sequences of components. In Section 3 we state more specifically the goals considered in this paper.

We start by introducing our main algorithmic tool, described in Figure 1, a share algorithm whose formulation generalizes the seemingly unrelated formulations of the algorithms studied in [START_REF] Herbster | Tracking the best expert[END_REF][START_REF] Herbster | Tracking the best linear predictor[END_REF][START_REF] Bousquet | Tracking a small set of experts by mixing past posteriors[END_REF]. It is parameterized by the "mixing functions" ψ t : [0, 1] td → ∆ d for t 2 that assign probabilities to past "pre-weights" as defined below. In all examples discussed in this paper, these mixing functions are quite simple, but working with such a general model makes the main ideas more transparent. We then provide a simple lemma that serves as the starting point2 for analyzing different instances of this generalized share algorithm. Lemma 1. For all t 1 and for all q t ∈ ∆ d , Algorithm 1 satisfies

p t -q t ⊤ ℓ t 1 η d i=1 q i,t ln v i,t+1 p i,t + η 8 .
Proof. By Hoeffding's inequality (see, e.g., [3, Section A.1.1]),

d j=1 p j,t ℓ j,t - 1 η ln   d j=1 p j,t e -η ℓj,t   + η 8 . (1)
By definition of v i,t+1 , for all i = 1, . . . , d we then have d j=1 p j,t e -η ℓj,t = p i,t e -η ℓi,t /v i,t+1 , which implies p ⊤ t ℓ t ℓ i,t + (1/η) ln(v i,t+1 / p i,t ) + η/8. The proof is concluded by taking a convex aggregation with respect to q t . Parameters: learning rate η > 0 and mixing functions ψ t for t 2 Initialization:

p 1 = v 1 = (1/d, . . . , 1/d) For each round t = 1, . . . , T , 1. Predict p t ; 2. Observe loss ℓ t ∈ [0, 1] d ; 3. [loss update] For each j = 1, . . . , d define v j,t+1 = p j,t e -η ℓj,t d i=1 p i,t e -η ℓi,t
the current pre-weights, and v t+1 = (v 1,t+1 , . . . , v d,t+1 );

V t+1 = v i,s 1 i d, 1 s t+1 the d × (t + 1
) matrix of all past and current pre-weights;

4. [shared update] Define p t+1 = ψ t+1 V t+1 .

Algorithm 1: The generalized share algorithm.

A generalized shifting regret for the simplex

We now introduce a generalized notion of shifting regret which unifies and generalizes the notions of discounted regret (see [START_REF] Cesa-Bianchi | Prediction, learning, and games[END_REF]Section 2.11]), adaptive regret (see [START_REF] Hazan | Efficient learning algorithms for changing environments[END_REF]), and shifting regret (see [START_REF] Zinkevich | Online convex programming and generalized infinitesimal gradient ascent[END_REF]). For a fixed horizon T , a sequence of discount factors β t,T 0 for t = 1, . . . , T assigns varying weights to the instantaneous losses suffered at each round. We compare the total loss of the forecaster with the loss of an arbitrary sequence of vectors q 1 , . . . , q T in the simplex ∆ d . Our goal is to bound the regret

T t=1 β t,T p ⊤ t ℓ t - T t=1 β t,T q ⊤ t ℓ t
in terms of the "regularity" of the comparison sequence q 1 , . . . , q T and of the variations of the discounting weights β t,T . By setting u t = β t,T q ⊤ t ∈ R d + , we can rephrase the above regret as

T t=1 u t 1 p ⊤ t ℓ t - T t=1 u ⊤ t ℓ t . (2)
In the literature on tracking the best expert [START_REF] Herbster | Tracking the best expert[END_REF][START_REF] Vovk | Derandomizing stochastic prediction strategies[END_REF][START_REF] Herbster | Tracking the best linear predictor[END_REF][START_REF] Bousquet | Tracking a small set of experts by mixing past posteriors[END_REF], the regularity of the sequence u 1 , . . . , u T is measured as the number of times u t = u t+1 . We introduce the following regularity measure

m(u T 1 ) = T t=2 D TV (u t , u t-1 ) (3)
where for x = (x 1 , . . . , x d ), y = (y 1 , . . . , y d ) ∈ R d + , we define D TV (x, y) = xi yi (x i -y i ). Note that when x, y ∈ ∆ d , we recover the total variation distance D TV (x, y) = 1 2 xy 1 , while for general x, y ∈ R d + , the quantity D TV (x, y) is not necessarily symmetric and is always bounded by xy 1 . The traditional shifting regret of [START_REF] Herbster | Tracking the best expert[END_REF][START_REF] Vovk | Derandomizing stochastic prediction strategies[END_REF][START_REF] Herbster | Tracking the best linear predictor[END_REF][START_REF] Bousquet | Tracking a small set of experts by mixing past posteriors[END_REF] is obtained from (2) when all u t are such that u t 1 = 1.

Projected update

The shifting variant of the EG algorithm analyzed in [START_REF] Herbster | Tracking the best linear predictor[END_REF] is a special case of the generalized share algorithm in which the function ψ t+1 performs a projection of the pre-weights on the convex set

∆ α d = [α/d, 1] d ∩ ∆ d .
Here α ∈ (0, 1) is a fixed parameter. We can prove (using techniques similar to the ones shown in the next section-see the supplementary material) the following bound which generalizes [START_REF] Herbster | Tracking the best linear predictor[END_REF]Theorem 16].

Theorem 1. For all T 1, for all sequences ℓ 1 , . . . , ℓ t ∈ [0, 1] d of loss vectors, and for all u 1 , . . . , u T ∈ R d + , if Algorithm 1 is run with the above update, then

T t=1 u t 1 p ⊤ t ℓ t - T t=1 u ⊤ t ℓ t u 1 1 ln d η + m(u T 1 ) η ln d α + η 8 + α T t=1 u t 1 . (4)
This bound can be optimized by a proper tuning of α and η parameters. We show a similarly tuned (and slightly better) bound in Corollary 1.

5 Fixed-share update

Next, we consider a different instance of the generalized share algorithm corresponding to the update

p j,t+1 = d i=1 α d + (1 -α)1 i=j v i,t+1 = α d + (1 -α)v j,t+1 , 0 α 1 (5)
Despite seemingly different statements, this update in Algorithm 1 can be seen to lead exactly to the fixed-share algorithm of [START_REF] Herbster | Tracking the best expert[END_REF] for prediction with expert advice. We now show that this update delivers a bound on the regret almost equivalent to (though slightly better than) that achieved by projection on the subset ∆ α d of the simplex. Theorem 2. With the above update, for all T 1, for all sequences ℓ 1 , . . . , ℓ T of loss vectors ℓ t ∈ [0, 1] d , and for all u 1 , . . . ,

u T ∈ R d + , T t=1 u t 1 p ⊤ t ℓ t - T t=1 u ⊤ t ℓ t u 1 1 ln d η + η 8 T t=1 u t 1 + m(u T 1 ) η ln d α + T t=2 u t 1 -m(u T 1 ) η ln 1 1 -α .
Note that if we only consider vectors of the form u t = q t = (0, . . . , 0, 1, 0, . . . , 0) then m(q T 1 ) corresponds to the number of times q t+1 = q t in the sequence q T 1 . We thus recover [4, Theorem 1] and [START_REF] Bousquet | Tracking a small set of experts by mixing past posteriors[END_REF]Lemma 6] from the much more general Theorem 2.

The fixed-share forecaster does not need to "know" anything in advance about the sequence of the norms u t for the bound above to be valid. Of course, in order to minimize the obtained upper bound, the tuning parameters α, η need to be optimized and their values will depend on the maximal values of m(u T 1 ) and T t=1 u t 1 for the sequences one wishes to compete against. This is illustrated in the following corollary, whose proof is omitted. Therein, h(x) = -x ln x -(1x) ln(1 -x) denotes the binary entropy function for x ∈ [0, 1]. We recall3 that h(x) x ln(e/x) for x ∈ [0, 1]. Corollary 1. Suppose Algorithm 1 is run with the update [START_REF] Vovk | Derandomizing stochastic prediction strategies[END_REF]. Let m 0 > 0 and U 0 > 0. For all T 1, for all sequences ℓ 1 , . . . , ℓ T of loss vectors ℓ t ∈ [0, 1] d , and for all sequences u 1 , . . . ,

u T ∈ R d + with u 1 1 + m(u T 1 ) m 0 and T t=1 u t 1 U 0 , T t=1 u t 1 p ⊤ t ℓ t - T t=1 u ⊤ t ℓ t U 0 2 m 0 ln d + U 0 h m 0 U 0 U 0 m 0 2 ln d + ln e U 0 m 0
whenever η and α are optimally chosen in terms of m 0 and U 0 .

Proof of Theorem 2. Applying Lemma 1 with q t = u t / u t 1 , and multiplying by u t 1 , we get for all t 1 and u

t ∈ R d + u t 1 p ⊤ t ℓ t -u ⊤ t ℓ t 1 η d i=1 u i,t ln v i,t+1 p i,t + η 8 u t 1 . (6)
We now examine

d i=1 u i,t ln v i,t+1 p i,t = d i=1 u i,t ln 1 p i,t -u i,t-1 ln 1 v i,t + d i=1 u i,t-1 ln 1 v i,t -u i,t ln 1 v i,t+1
.

(7) For the first term on the right-hand side, we have

d i=1 u i,t ln 1 p i,t -u i,t-1 ln 1 v i,t = i : ui,t ui,t-1 (u i,t -u i,t-1 ) ln 1 p i,t + u i,t-1 ln v i,t p i,t + i : ui,t<ui,t-1 (u i,t -u i,t-1 ) ln 1 v i,t 0 +u i,t ln v i,t p i,t . (8)
In view of the update (5), we have 1/ p i,t d/α and v i,t / p i,t 1/(1 -α). Substituting in (8), we get

d i=1 u i,t ln 1 p i,t -u i,t-1 ln 1 v i,t i : ui,t ui,t-1 (u i,t -u i,t-1 ) ln d α +   i: ui,t ui,t-1 u i,t-1 + i: ui,t<ui,t-1 u i,t   ln 1 1 -α = D TV (u t , u t-1 ) ln d α +   d i=1 u i,t - i : ui,t ui,t-1 (u i,t -u i,t-1 )   = ut 1 -DTV(ut,ut-1) ln 1 1 -α .
The sum of the second term in [START_REF] György | Tracking the best of many experts[END_REF] telescopes. Substituting the obtained bounds in the first sum of the right-hand side in [START_REF] György | Tracking the best of many experts[END_REF], and summing over t = 2, . . . , T , leads to

T t=2 d i=1 u i,t ln v i,t+1 p i,t m(u T 1 ) ln d α + T t=2 u t 1 -m(u T 1 ) ln 1 1 -α + d i=1 u i,1 ln 1 v i,2 -u i,T ln 1 v i,T +1 0 .
We hence get from ( 6), which we use in particular for t = 1,

T t=1 u t 1 p ⊤ t ℓ t -u ⊤ t ℓ t 1 η d i=1 u i,1 ln 1 p i,1 + η 8 T t=1 u t 1 + m(u T 1 ) η ln d α + T t=2 u t 1 m(u T 1 ) η ln 1 1 -α .

Applications

We now show how our regret bounds can be specialized to obtain bounds on adaptive and discounted regret, and on regret with time-selection functions. We show regret bounds only for the specific instance of the generalized share algorithm using update (5); but the discussion below also holds up to minor modifications for the forecaster studied in Theorem 1.

Adaptive regret was introduced by [START_REF] Hazan | Efficient learning algorithms for changing environments[END_REF] and can be viewed as a variant of discounted regret where the monotonicity assumption is dropped. For τ 0 ∈ {1, . . . , T }, the τ 0 -adaptive regret of a forecaster is defined by

R τ0-adapt T = max [r, s] ⊂ [1, T ] s + 1 -r τ0 s t=r p ⊤ t ℓ t -min q∈∆ d s t=r q ⊤ ℓ t . (9)
The fact that this is a special case of (2) clearly emerges from the proof of Corollary 2 below here.

Adaptive regret is an alternative way to measure the performance of a forecaster against a changing environment. It is a straightforward observation that adaptive regret bounds also lead to shifting regret bounds (in terms of hard shifts). In this paper we note that these two notions of regret share an even tighter connection, as they can be both viewed as instances of the same alma mater notion of regret, i.e., the generalized shifting regret introduced in Section 3. The work [START_REF] Hazan | Efficient learning algorithms for changing environments[END_REF] essentially considered the case of online convex optimization with exp-concave loss function; in case of general convex functions, they also mentioned that the greedy projection forecaster of [START_REF] Zinkevich | Online convex programming and generalized infinitesimal gradient ascent[END_REF] enjoys adaptive regret guarantees. This is obtained in much the same way as we obtain an adaptive regret bound for the fixed-share forecaster in the next result. Corollary 2. Suppose that Algorithm 1 is run with the shared update [START_REF] Vovk | Derandomizing stochastic prediction strategies[END_REF]. Then for all T 1, for all sequences ℓ 1 , . . . , ℓ T of loss vectors ℓ t ∈ [0, 1] d , and for all τ 0 ∈ {1, . . . , T },

R τ0-adapt T τ 0 2 τ 0 h 1 τ 0 + ln d τ 0 2 ln(edτ 0 )
whenever η and α are chosen optimally (depending on τ 0 and T ).

As mentioned in [START_REF] Hazan | Efficient learning algorithms for changing environments[END_REF], standard lower bounds on the regret show that the obtained bound is optimal up to the logarithmic factors.

Proof. For 1 r s T and q ∈ ∆ d , the regret in the right-hand side of ( 9) equals the regret considered in Theorem 2 against the sequence u T 1 defined as u t = q for t = r, . . . , s and 0 = (0, . . . , 0) for the remaining t. When r 2, this sequence is such that

D TV (u r , u r-1 ) = D TV (q, 0) = 1 and D TV (u s+1 , u s ) = D TV (0, q) = 0 so that m(u T 1 ) = 1, while u 1 1 = 0. When r = 1, we have u 1 1 = 1 and m(u T 1 ) = 0. In all cases, m(u T 1 ) + u 1 1 = 1, that is, m 0 = 1.
Specializing the bound of Theorem 2 with the additional choice U 0 = τ 0 gives the result.

Discounted regret was introduced in [3, Section 2.11] and is defined by

max q∈∆ d T t=1 β t,T p ⊤ t ℓ t -q ⊤ ℓ t . (10)
The discount factors β t,T measure the relative importance of more recent losses to older losses. For instance, for a given horizon T , the discounts β t,T may be larger as t is closer to T . On the contrary, in a game-theoretic setting, the earlier losses may matter more then the more recent ones (because of interest rates), in which case β t,T would be smaller as t gets closer to T . We mostly consider below monotonic sequences of discounts (both non-decreasing and non-increasing). Up to a normalization, we assume that all discounts β t,T are in [0, 1]. As shown in [START_REF] Cesa-Bianchi | Prediction, learning, and games[END_REF], a minimal requirement to get nontrivial bounds is that the sum of the discounts satisfies

U T = t T β t,T → ∞ as T → ∞.
A natural objective is to show that the quantity in [START_REF] Blum | From extermal to internal regret[END_REF] is o(U T ), for instance, by bounding it by something of the order of √ U T . We claim that Corollary 1 does so, at least whenever the sequences (β t,T ) are monotonic for all T . To support this claim, we only need to show that m 0 = 1 is a suitable value to deal with [START_REF] Blum | From extermal to internal regret[END_REF]. Indeed, for all T 1 and for all q ∈ ∆ d , the measure of regularity involved in the corollary satisfies

β 1,T q 1 + m (β t,T q) t T = β 1,T + T t=2 β t,T -β t-1,T + = max β 1,T , β T,T 1
,
where the second equality follows from the monotonicity assumption on the discounts.

The values of the discounts for all t and T are usually known in advance. However, the horizon T is not. Hence, a calibration issue may arise. The online tuning of the parameters α and η shown in Section 7.3 entails a forecaster that can get discounted regret bounds of the order √ U T for all T . The fundamental reason for this is that the discounts only come in the definition of the fixedshare forecaster via their sums. In contrast, the forecaster discussed in [START_REF] Cesa-Bianchi | Prediction, learning, and games[END_REF]Section 2.11] weighs each instance t directly with β t,T (i.e., in the very definition of the forecaster) and enjoys therefore no regret guarantees for horizons other than T (neither before T nor after T ). Therein, the knowledge of the horizon T is so crucial that it cannot be dealt with easily, not even with online calibration of the parameters or with a doubling trick. We insist that for the fixed-share forecaster, much flexibility is gained as some of the discounts β t,T can change in a drastic manner for a round T to values β t,T +1 for the next round. However we must admit that the bound of [START_REF] Cesa-Bianchi | Prediction, learning, and games[END_REF]Section 2.11] is smaller than the one obtained above, as it of the order of t T β 2 t,T , in contrast to our t T β t,T bound. Again, this improvement was made possible because of the knowledge of the time horizon.

As for the comparison to the setting of discounted losses of [START_REF] Chernov | Prediction with expert advice under discounted loss[END_REF], we note that the latter can be cast as a special case of our setting (since the discounting weights take the special form β t,T = γ t . . . γ T -1 therein, for some sequence γ s of positive numbers). In particular, the fixed-share forecaster can satisfy the bound stated in [9, Theorem 2], for instance, by using the online tuning techniques of Section 7.3. A final reference to mention is the setting of time-selection functions of [10, Section 6], which basically corresponds to knowing in advance the weights u t 1 of the comparison sequence u 1 , . . . , u T the forecaster will be evaluated against. We thus generalize their results as well.

Refinements and extensions

We now show that techniques for refining the standard online analysis can be easily applied to our framework. We focus on the following: improvement for small losses, sparse target sequences, and dynamic tuning of parameters. Not all of them where within reach of previous analyses.

Improvement for small losses

The regret bounds of the fixed-share forecaster can be significantly improved when the cumulative loss of the best sequence of experts is small. The next result improves on Corollary 1 whenever L 0 ≪ U 0 . For concreteness, we focus on the fixed-share update (5). Corollary 3. Suppose Algorithm 1 is run with the update [START_REF] Vovk | Derandomizing stochastic prediction strategies[END_REF]. Let m 0 > 0, U 0 > 0, and L 0 > 0. For all T 1, for all sequences ℓ 1 , . . . , ℓ T of loss vectors ℓ t ∈ [0, 1] d , and for all sequences

u 1 , . . . , u T ∈ R d + with u 1 1 + m(u T 1 ) m 0 , T t=1 u t 1 U 0 , and T t=1 u ⊤ t ℓ t L 0 , T t=1 u t 1 p ⊤ t ℓ t - T t=1 u ⊤ t ℓ t L 0 m 0 ln d + ln e U 0 m 0 + ln d + ln e U 0 m 0
whenever η and α are optimally chosen in terms of m 0 , U 0 , and L 0 .

Here again, the parameters α and η may be tuned online using the techniques shown in Section 7. [START_REF] Cesa-Bianchi | Prediction, learning, and games[END_REF].

The above refinement is obtained by mimicking the analysis of Hedge forecasters for small losses (see, e.g., [3, Section 2.4]). In particular, one should substitute Lemma 1 with the following lemma in the analysis carried out in Section 5; its proof follows from the mere replacement of Hoeffding's inequality by [START_REF] Cesa-Bianchi | Prediction, learning, and games[END_REF]Lemma A.3], which states that for all η ∈ R and for all random variable X taking values in [0, 1], one has ln E[e -ηX ] (e -η -1)EX.

Lemma 2. Algorithm 1 satisfies 1 -e -η η p ⊤ t ℓ t -q ⊤ t ℓ t 1 η d i=1 q i,t ln v i,t p i,t+1
for all q t ∈ ∆ d .

Sparse target sequences

The work [START_REF] Bousquet | Tracking a small set of experts by mixing past posteriors[END_REF] introduced forecasters that are able to efficiently compete with the best sequence of experts among all those sequences that only switch a bounded number of times and also take a small number of different values. Such "sparse" sequences of experts appear naturally in many applications. In this section we show that their algorithms in fact work very well in comparison with a much larger class of sequences u 1 , . . . , u T that are "regular"-that is, m(u T 1 ), defined in (3) is small-and "sparse" in the sense that the quantity n(u T 1 ) = d i=1 max t=1,...,T u i,t is small. Note that when q t ∈ ∆ d for all t, then two interesting upper bounds can be provided. First, denoting the union of the supports of these convex combinations by S ⊆ {1, . . . , d}, we have n(q T 1 ) |S|, the cardinality of S. Also, n(q T 1 ) {q t , t = 1, . . . , T } , the cardinality of the pool of convex combinations. Thus, n(u T 1 ) generalizes the notion of sparsity of [START_REF] Bousquet | Tracking a small set of experts by mixing past posteriors[END_REF].

Here we consider a family of shared updates of the form

p j,t = (1 -α)v j,t + α w j,t Z t , 0 α 1 , (11)
where the w j,t are nonnegative weights that may depend on past and current pre-weights and Z t = d i=1 w i,t is a normalization constant. Shared updates of this form were proposed by [6, Sections 3 and 5.2]. Apart from generalizing the regret bounds of [START_REF] Bousquet | Tracking a small set of experts by mixing past posteriors[END_REF], we believe that the analysis given below is significantly simpler and more transparent. We are also able to slightly improve their original bounds.

We focus on choices of the weights w j,t that satisfy the following conditions: there exists a constant C 1 such that for all j = 1, . . . , d and t = 1, . . . , T , v j,t w j,t 1 and C w j,t+1 w j,t .

(12) The next result improves on Theorem 2 when T ≪ d and n(u T 1 ) ≪ m(u T 1 ), that is, when the dimension (or number of experts) d is large but the sequence u T 1 is sparse. Its proof can be found in the supplementary material; it is a variation on the proof of Theorem 2. Theorem 3. Suppose Algorithm 1 is run with the shared update [START_REF] Auer | Adaptive and self-confident on-line learning algorithms[END_REF] with weights satisfying the conditions (12). Then for all T 1, for all sequences ℓ 1 , . . . , ℓ T of loss vectors ℓ t ∈ [0, 1] d , and for all sequences u 1 , . . . ,

u T ∈ R d + , T t=1 u t 1 p ⊤ t ℓ t - T t=1 u ⊤ t ℓ t n(u T 1 ) ln d η + n(u T 1 ) T ln C η + η 8 T t=1 u t 1 + m(u T 1 ) η ln max t T Z t α + T t=2 u t 1 -m(u T 1 ) η ln 1 1 -α .
Corollaries 8 and 9 of [START_REF] Bousquet | Tracking a small set of experts by mixing past posteriors[END_REF] can now be generalized (and even improved); we do so-in the supplementary material-by showing two specific instances of the generic update (11) that satisfy (12).

Online tuning of the parameters

The forecasters studied above need their parameters η and α to be tuned according to various quantities, including the time horizon T . We show here how the trick of [START_REF] Auer | Adaptive and self-confident on-line learning algorithms[END_REF] of having these parameters vary over time can be extended to our setting. For the sake of concreteness we focus on the fixedshare update, i.e., Algorithm 1 run with the update [START_REF] Vovk | Derandomizing stochastic prediction strategies[END_REF]. We respectively replace steps 3 and 4 of its description by the loss and shared updates

v j,t+1 = p η t η t-1 j,t e -ηtℓj,t d i=1 p η t η t-1 i,t e -ηtℓi,t and p j,t+1 = α t d + (1 -α t ) v j,t+1 , (13)
for all t 1 and all j ∈ {1, . . . , d}, where (η τ ) and (α τ ) are two sequences of positive numbers, indexed by τ 1. We also conventionally define η 0 = η 1 . Theorem 2 is then adapted in the following way (when η t ≡ η and α t ≡ α, Theorem 2 is exactly recovered). Theorem 4. The forecaster based on the updates (13) is such that whenever η t η t-1 and α t α t-1 for all t 1, the following performance bound is achieved. For all T 1, for all sequences ℓ 1 , . . . , ℓ T of loss vectors ℓ t ∈ [0, 1] d , and for all u 1 , . . . ,

u T ∈ R d + , T t=1 u t 1 p ⊤ t ℓ t - T t=1 u ⊤ t ℓ t u t 1 η 1 + T t=2 u t 1 1 η t - 1 η t-1 ln d + m(u T 1 ) η T ln d(1 -α T ) α T + T t=2 u t 1 η t-1 ln 1 1 -α t + T t=1 η t-1 8 u t 1 .
Due to space constraints, we provide an illustration of this bound only in the supplementary material.

A Online convex optimization on the simplex By using a standard reduction, the results of the main body of the paper (for linear optimization on the simplex) can be applied to online convex optimization on the simplex. In this setting, at each step t the forecaster chooses p t ∈ ∆ d and then is given access to a convex loss ℓ t : ∆ d → [0, 1]. Now, using Algorithm 1 with the loss vector ℓ t ∈ ∂ℓ t ( p t ) given by a subgradient of ℓ t leads to the desired bounds. Indeed, by the convexity of ℓ t , the regret at each time t with respect to any vector u t ∈ R d + with u t 1 > 0 is then bounded as

u t 1 ℓ t ( p t ) -ℓ t u t u t 1 u t 1 p t -u t ⊤ ℓ t .
B Proof of Theorem 3; application of the bound to two different updates

Proof. The beginning and the end of the proof are similar to the one of Theorem 2, as they do not depend on the specific weight update. In particular, inequalities ( 6) and ( 7) remain the same. The proof is modified after [START_REF] Hazan | Efficient learning algorithms for changing environments[END_REF], which this time we upper bound using the first condition in (12),

d i=1 u i,t ln 1 p i,t -u i,t-1 ln 1 v i,t = i : ui,t ui,t-1 (u i,t -u i,t-1 ) ln 1 p i,t + u i,t-1 ln v i,t p i,t + i : ui,t<ui,t-1 (u i,t -u i,t-1 ) 0 ln 1 v i,t ln(1/wi,t) +u i,t ln v i,t p i,t . (14)
By definition of the shared update [START_REF] Auer | Adaptive and self-confident on-line learning algorithms[END_REF], we have 1/ p i,t Z t /(α w i,t ) and v i,t / p i,t 1/(1 -α). We then upper bound the quantity at hand in (14) by i : ui,t ui,t-1

(u i,t -u i,t-1 ) ln Z t α w i,t +   i : ui,t ui,t-1 u i,t-1 + i : ui,t<ui,t-1 u i,t   ln 1 1 -α + i : ui,t<ui,t-1 (u i,t -u i,t-1 ) ln 1 w i,t = D TV (u t , u t-1 ) ln Z t α + u t 1 -D TV (u t , u t-1 ) ln 1 1 -α + d i=1 (u i,t -u i,t-1 ) ln 1 w i,t .
Proceeding as in the end of the proof of Theorem 2, we then get the claimed bound, provided that we can show that

T t=2 d i=1 (u i,t -u i,t-1 ) ln 1 w i,t n(u T 1 ) (ln d + T ln C) -u 1 1 ln d ,
which we do next. Indeed, the left-hand side can be rewritten as

T t=2 d i=1 u i,t ln 1 w i,t -u i,t ln 1 w i,t+1 + T t=2 d i=1 u i,t ln 1 w i,t+1 -u i,t-1 ln 1 w i,t T t=2 d i=1 u i,t ln C w i,t+1 w i,t + d i=1 u i,T ln 1 w i,T +1 - d i=1 u i,1 ln 1 w i,2 d i=1 max t=1,...,T u i,t T t=2 ln C w i,t+1 w i,t + d i=1 max t=1,...,T u i,t ln 1 w i,T +1 - d i=1 u i,1 ln 1 w i,2 = d i=1 max t=1,...,T u i,t (T -1) ln C + ln 1 w i,2 - d i=1 u i,1 ln 1 w i,2 ,
where we used C 1 for the first inequality and the second condition in (12) for the second inequality. The proof is concluded by noting that (12) entails w i,2

(1/C)w i,1

(1/C)v i,1 = 1/(dC) and that the coefficient max t=1,...,T u i,t -u i,1 in front of ln(1/w i,2 ) is nonnegative.

The first update uses w j,t = max s t v j,s . Then (12) is satisfied with C = 1. Moreover, since a sum of maxima of nonnegative elements is smaller than the sum of the sums, Z t min{d, t} T . This immediately gives the following result.

Corollary 4. Suppose Algorithm 1 is run with the update (11) with w j,t = max s t v j,s . For all T 1, for all sequences ℓ 1 , . . . , ℓ T of loss vectors ℓ t ∈ [0, 1] d , and for all q 1 , . . . , q T ∈ ∆ d ,

T t=1 p ⊤ t ℓ t - T t=1 q ⊤ t ℓ t n(q T 1 ) ln d η + η 8 T + m(q T 1 ) η ln T α + T -m(q T 1 ) -1 η ln 1 1 -α .
The second update we discuss uses w j,t = max s t e γ(s-t) v j,s in [START_REF] Auer | Adaptive and self-confident on-line learning algorithms[END_REF] for some γ > 0. Both conditions in (12) are satisfied with C = e γ . One also has that

Z t d and Z t τ 0 e -γτ = 1 1 -e -γ
1 γ as e x 1 + x for all real x. The bound of Theorem 3 then instantiates as

n(q T 1 ) ln d η + n(q T 1 ) T γ η + η 8 T + m(q T 1 ) η ln min{d, 1/γ} α + T -m(q T 1 ) -1 η ln 1 1 -α
when sequences u t = q t ∈ ∆ d are considered. This bound is best understood when γ is tuned optimally based on T and on two bounds m 0 and n 0 over the quantities m(q T 1 ) and n(q T 1 ). Indeed, by optimizing n 0 T γ+m 0 ln(1/γ), i.e., by choosing γ = m 0 /(n 0 T ), one gets a bound that improves on the one of the previous corollary: Corollary 5. Let m 0 , n 0 > 0. Suppose Algorithm 1 is run with the update w j,t = max s t e γ(s-t) v j,s where γ = m 0 /(n 0 T ). For all T 1, for all sequences ℓ 1 , . . . , ℓ T of loss vectors ℓ t ∈ [0, 1] d , and for all q 1 , . . . , q T ∈ ∆ d such that m(q T 1 ) m 0 and n(q T 1 ) n 0 , we have

T t=1 p ⊤ t ℓ t - T t=1 q ⊤ t ℓ t n 0 ln d η + m 0 η 1 + ln min d, n 0 T m 0 + η 8 T + m 0 η ln 1 α + T -m 0 -1 η ln 1 1 -α .
As the factors e -γt cancel out in the numerator and denominator of the ratio in [START_REF] Auer | Adaptive and self-confident on-line learning algorithms[END_REF], there is a straightforward implementation of the algorithm (not requiring the knowledge of T ) that needs to maintain only d weights.

In contrast, the corresponding algorithm of [START_REF] Bousquet | Tracking a small set of experts by mixing past posteriors[END_REF], using the updates p j,t = (1 -α)v j,t + αS -1 t s t-1 (s -t) -1 v j,s or p j,t = (1 -α)v j,t + αS -1 t max s t-1 (s -t) -1 v j,s , where S t denote normalization factors, needs to maintain O(dT ) weights with a naive implementation, and O(d ln T ) weights with a more sophisticated one. In addition, the obtained bounds are slightly worse than the one stated above in Corollary 5 as an additional factor of m 0 ln(1 + ln T ) is present in [START_REF] Bousquet | Tracking a small set of experts by mixing past posteriors[END_REF]Corollary 9].

C Proof of Theorem 4; illustration of the obtained bound

We first adapt Lemma 1.

Lemma 3. The forecaster based on the loss and shared updates (13) satisfies, for all t 1 and for all q t ∈ ∆ d ,

p t -q t ⊤ ℓ t d i=1 q i,t 1 η t-1 ln 1 p i,t - 1 η t ln 1 v i,t+1 + 1 η t - 1 η t-1 ln d + η t-1 8
p ⊤ t ℓ t ℓ i,t + 1 η t-1 ln 1 p i,t - 1 η t ln 1 v i,t+1 + 1 η t - 1 η t-1 ln d + η t-1 8 ,
valid for all i ∈ {1, . . . , d}. The proof is concluded by taking a convex aggregation over i with respect to q t . The proof of Theorem 4 follows the steps of the one of Theorem 2; we sketch it below.

Proof of Theorem 4. Applying Lemma 3 with q t = u t / u t 1 , and multiplying by u t 1 , we get for all t 1 and u

t ∈ R d + , u t 1 p ⊤ t ℓ t -u ⊤ t ℓ t 1 η t-1 d i=1 u i,t ln 1 p i,t - 1 η t d i=1 u i,t ln 1 v i,t+1 + u t 1 1 η t - 1 η t-1 ln d + η t-1 8 u t 1 . (15)
We will sum these bounds over t 1 to get the desired result but need to perform first some additional boundings for t 2; in particular, we examine

1 η t-1 d i=1 u i,t ln 1 p i,t - 1 η t d i=1 u i,t ln 1 v i,t+1 = 1 η t-1 d i=1 u i,t ln 1 p i,t -u i,t-1 ln 1 v i,t + d i=1 u i,t-1 η t-1 ln 1 v i,t - u i,t η t ln 1 v i,t+1 , (16)
where the first difference in the right-hand side can be bounded as in [START_REF] Hazan | Efficient learning algorithms for changing environments[END_REF] by

d i=1 u i,t ln 1 p i,t -u i,t-1 ln 1 v i,t i : ui,t ui,t-1 (u i,t -u i,t-1 ) ln 1 p i,t + u i,t-1 ln v i,t p i,t + i : ui,t<ui,t-1 u i,t ln v i,t p i,t D T V (u t , u t-1 ) ln d α t + u t 1 -D T V (u t , u t-1 ) ln 1 1 -α t D T V (u t , u t-1 ) ln d(1 -α T ) α T + u t 1 ln 1 1 -α t , (17)
where we used for the second inequality that the shared update in (13) is such that 1/ p i,t d/α t and v i,t / p i,t 1/(1 -α t ), and for the third inequality, that α t α T and x → (1 -x)/x is increasing on (0, 1]. Summing (16) over t = 2, . . . , T using (17) and the fact that η t η T , we get

T t=2 1 η t-1 d i=1 u i,t ln 1 p i,t - 1 η t d i=1 u i,t ln 1 v i,t+1 m(u T 1 ) η T ln d(1 -α T ) α T + T t=2 u t 1 η t-1 ln 1 1 -α t + d i=1 u i,1 η 1 ln 1 v i,2 - u i,T η T ln 1 v i,T +1 0 .
An application of (15) -including for t = 1, for which we recall that p i,1 = 1/d and η 1 = η 0 by convention-concludes the proof.

We now instantiate the obtained bound to the case of, e.g., T -adaptive regret guarantees, when T is unknown and/or can increase without bounds. q ⊤ ℓ t 2T ln(dT ) + 3 ln(3d) .

Proof. The sequence n → ln(n)/n is only non-increasing after round n 3, so that the defined sequences of (α t ) and (η t ) are non-increasing, as desired. For a given pair (r, s) and a given q ∈ ∆ d , we consider the sequence ν T 1 defined in the proof of Corollary 2; it satisfies that m(u

D Proof of Theorem 1

We recall that the forecaster at hand is the one described in Algorithm 1, with the shared update p t+1 = ψ t+1 V t+1 for

ψ t+1 V t+1 ∈ argmin x∈∆ α d K(x, v t+1 ) , where K(x, v t+1 ) = d i=1 x i ln x i v i,t+1 (18)
is the Kullback-Leibler divergence and ∆ α d = [α/d, 1] d ∩ ∆ d is the simplex of convex vectors with the constraint that each component be larger than α/d.

The proof of the performance bound starts with an extension of Lemma 1. Lemma 4. For all t 1 and for all q t ∈ ∆ α d , the generalized forecaster with the shared update (18) satisfies

( p t -q t ) ⊤ ℓ t 1 η d i=1 q i,

Corollary 6 .

 6 The forecaster based on the updates discussed above with η t = ln(dt) /t for t 3 and η 0 = η 1 = η 2 = η 3 on the one hand, α t = 1/t on the other hand, is such that for all T 3 and for all sequences ℓ 1 , . . . , ℓ T of loss vectors ℓ t ∈ [0, 1] d ,

  , whenever η t η t-1 .

	Proof. By Hoeffding's inequality,
	d j=1	p j,t ℓ j,t -	1 η t-1	ln	 	d j=1	p j,t e -ηt-1 ℓj,t	  +	η t-1 8	.
	η t-1 η t η t-1 By Jensen's inequality, since η t η t-1 and thus x → x 1 d d j=1 p j,t e -ηt-1ℓj,t = 1 d d j=1 p η t η t-1 j,t e -ηtℓj,t η t	is convex,   1 j=1 d d p	η t η t-1 j,t	e -ηtℓj,t	η t-1  η t 	.
	Substituting in Hoeffding's bound we get
	p ⊤ t ℓ t -	1 η t	ln	 	d j=1	p	η t η t-1 j,t	e -ηtℓj,t	  +	1 η t	-	1 η t-1	ln d +	η t-1 8	.
	Now, by definition of the loss update in (13), for all i ∈ {1, . . . , d},
				d j=1	p	η t η t-1 j,t	e -ηtℓj,t =	1 v i,t+1	p	η t η t-1 i,t	e -ηtℓi,t ,
	which, after substitution in the previous bound leads to the inequality

  T 1 )1 and u t 1 1 for all t 1. Therefore, Theorem 4 ensures that It only remains to substitute the proposed values of η t and to note that

	s t=r	p ⊤ t ℓ t -min q∈∆ d	s t=r	q ⊤ ℓ t	ln d η T	+	1 η T	ln	d(1 -α T ) α T	+	T t=2	1 η t-1	ln	1 1 -α t	+	T t=1	η t-1 8	.
												dT		(1/ηT ) T t=2 ln(t/(t-1))=(ln T )/ηT
		T t=1	η t-1 3η 3 +	T -1 t=3	1 √ t	ln(dT ) 3	ln(3d) 3	+ 2	√ T ln(dT ) .

  Proof. We rewrite the bound of Lemma 1 in terms of Kullback-Leibler divergences,( p tq t ) ⊤ ℓ t 1 ηwhere the last inequality holds by applying a generalized Pythagorean theorem for Bregman divergences (here, the Kullback-Leibler divergence) -see, e.g.,[START_REF] Cesa-Bianchi | Prediction, learning, and games[END_REF] Lemma 11.3]. We have by rearranging the terms for all t,u t 1 p tu t ⊤ ℓ t = u t 1 ( p tq t ) ⊤ ℓ t + α d u t 1 -αu t ⊤ ℓ t u t 1 ( p tq t ) ⊤ ℓ t + α u t 1 .Therefore, by applying Lemma 4 with q t ∈ ∆ α d , we further upper bound the quantity of interest asu t 1 p tu t ⊤ ℓ t u t 1 η + α u t 1 .The upper bound is rewritten by summing over t and applying an Abel transform to its first term,

									d i=1	q i,t ln	v i,t+1 p i,t	+	η 8	=	K(q t , p t ) -K(q t , v t+1 ) η	+	η 8
								K(q t , p t ) -K(q t , p t+1 ) η	+	η 8	=	1 η	d i=1	q i,t ln	p i,t+1 p i,t	+	η 8	,
	Proof. Let q t = u t 1 T α d + (1 -α) u t u t 1 ∈ ∆ α d . d i=1 q i,t ln p i,t+1 p i,t + η 8 t=1 u t 1 η d i=1 q i,t ln p i,t+1 p i,t + η 8 u t 1 + α u t 1
	=	u 1 1 ln d η	+		u T 1 η	d i=1	q i,T ln p i,T +1	+	1 η	T t=2	d i=1	ln	1 p i,t
											0		0 • ln d α
		+	η 8	+ α	T t=1	u t 1
		u 1 1 ln d η	+	1 -α η	T t=2	D TV (u t , u t-1 ) ln	d α	+	η 8	+ α
													t ln	p i,t+1 p i,t	+	η 8	.

u t 1 q i,tu t-1 q i,t-1 =(1-α)(ui,t-ui,t-1) T t=1 u t 1 .

Similar 1-norm shifting bounds can also be proven using the analysis of[START_REF] Zinkevich | Online convex programming and generalized infinitesimal gradient ascent[END_REF]. However, without using entropic regularizers it is not clear how to achieve a logarithmic dependence on the dimension, which is one of the advantages of working in the simplex.

We only deal with linear losses in this paper. However, it is straightforward that for sequences of η-expconcave loss functions, the additional term η/8 in the bound is no longer needed.

As can be seen by noting that ln 1/(1 -x) < x/(1 -x)

Acknowledgments

The authors acknowledge support from the French National Research Agency (ANR) under grant EXPLO/RA ("Exploration-exploitation for efficient resource allocation") and by the PASCAL2 Network of Excellence under EC grant no. 506778.