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

7 comments:

  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete