Click-Through Rate Estimation for Rare Events in Online Advertising INTRODUCTION The Internet revolution has driven a transformation of how people experience information, media and advertising. Web advertising did not even exist twenty years ago, but nowadays it has become a vital component of the modern Internet, where advertisements are delivered from advertisers to users through different channels such as display ads, sponsored search and contextual advertising. Based on a recent study by Interactive Advertising Bureau and PricewaterhouseCoopers Interna- tional, online advertising revenue in the first half of 2009 reached over 10.9 billion US dollars (IAB & PwC, 2009). Recent trends have also witnessed that larger and larger share of advertisers' bud- gets are devoted to the online world, and online advertising spending growth has greatly outpaced some of the traditional advertising media, such as radio and magazine. In addition, advertisers often plan their budget based on historical CTRs or predicted CTRs. In online advertising, a serving event refers to the showing of an ad in response to a user query, which can be a search query in sponsored search or a Web page in display and contextual adver- tising. The serving frequency varies for different queries and ads. Some popular ones account for a large fraction of Internet traffic while the over- whelming counterparts are extremely rare events, whose behaviors follow a typical power-law pattern. Even being infrequent, the revenue from the rare events generates a several-billion-dollar business, which makes estimating CTR for such rare events an extremely important and practical problem. Unfortunately, due to the sparseness, the CTR estimation for rare events is notoriously challenging and extremely unreliable, often with huge variance. There are two scenarios that are especially difficult to deal with. The first one is