Monday, February 21, 2011

Worst-case vs. average-case learning

Classical statistical learning theory deals with finding a consistent hypothesis given sufficiently many examples. Such a hypothesis may be a rule for classifying emails into spam/not-spam, and examples are classified emails.

Statistical and computational learning theories tell us how many examples are needed to be able to generate a good hypothesis - one that can correctly classify instances that it had not seen, given that they are generated from the same distribution from which we have seen classified examples.

This spam problem precisely demonstrates the caveat of making statistical assumptions - clearly the spammers are adaptive and adversarial. The characteristics of spam emails change over time, adapting to the filters.

Here comes online learning theory: in online learning we do not make any assumptions about the data, but rather sequentially modify our hypothesis such that our average performance approaches that of the best hypothesis in hindsight.  The difference between this average performance and the best-in-hindsight performance is called  regret, and the foundation of online learning are algorithms whose regret is bounded by a sublinear function of the number of iterations (hence the average regret approaches zero).

Can we interpolate between the two approaches ? That is, can we design algorithms which have a good regret-guarantee if the data is adversarial, but perform much better if there exists benign and simple distribution governing nature.

This natural question was raised several times in the last few years, with some partial progress and many interesting open questions, one of which is made explicit with all required background here (submitted to COLT 2011 open problems session).


  1. Thank you for your sharing articles.I really want to express my gratitude to you.The articles brings some advice. I think that they are really helpful for me but also other readers.
    best autoketing, Shipping Bar for Shopify, shipping bar app

  2. I'm flawed to reveal this page. Thanks for the great information you have provided! The next occasion I read a weblog, Lets hope so it doesnt disappoint me as much as this.
    best autoketing app, facebook inbox messages, facebook support chat

  3. Hey there! Do you know if they make any plugins to safeguard against hackers?
    I’m kinda paranoid about losing everything I’ve worked hard on. Any suggestions?
    email with love online
    apps autoketing
    email with love free

  4. I am very interested in this post, let's discuss it because I think there will be a lot of opinions and different views on it, let's share it so that we can receive it properly in the best way.
    currency converter master, currency converter box by autoketing, best autoketing app

  5. Your blog provi
    iogames 2 player
    abcya online games
    friv land games
    ded us with valuable information to work with. Each & every tips of your post are awesome. Thanks a lot for sharing. Keep blogging

  6. This website basically beautiful points and things right. This is a great inspiring article. You can do something much better but i still say this perfect.Keep trying for the best.
    abcya3 Games girl juegos motox3m3 gogy 2 player

  7. The story of cinderella Games to play
    Crime city 3d 2 Games online
    Top burger Games for girls
    I'm a decent implied for all articles or blog entries, That I emphatically relished, We'd to a great degree pick much more records identified with the, because of the reality it is in reality okay

  8. Thanks for your sharing. The articles brings some advice. After reading them, I get more information and knowledge.I hope I can read your new posts soon.
    best game Battle for the Galaxy Break The Cup For Free Game Toon Cup 2017

  9. Delight maintain this approach awesome succeed and additionally Document wait for a great deal more on your stunning blog posts. I just want to let you know that I just check out your site and I find it very interesting and informative.
    Ice cream maker game online
    4 player sheep party best online game
    Colorzzle online

  10. Fire truck crazy race free
    Free unblock the ball
    Games princess and adult princess
    Thanks for a very interesting blog. What else may I get that kind of info written in such a perfect approach? I’ve a undertaking that I am simply now operating on, and I have been at the look out for such info

  11. The author of this post is admirable, it brings a lot of emotion to everyone reading it, let's share it more widely.
    Happy Glass unblocked, juegos Wheelie Challenge, Cooking Christmas Traditional Food excellent games