## 04 February 2009

### Beating the state of the art, big-O style

I used to know a fair amount about math; in fact, I even applied to a few grad schools to do logic (long story, now is not the time). I was never involved in actual math research (primarily because of the necessary ramp-up time -- thank goodness this doesn't exist as much in CS!), but I did get a sense from my unofficial undergrad advisor how things worked. The reason I started thinking of this is because I recently made my way about halfway through a quite dense book on long games by a prof from grad school (I cross-enrolled at UCLA for a few semesters). The basic idea of a countable game is that there is a fixed subset A of [0,1] (subset of the reals) and two players alternate play. In each move, they play an integer from 0 to 9. They play for a countably infinite number of moves, essentially writing down (in decimal form) a real number. If, at the "end", this number is in A, then player 1 wins; otherwise, player 2 wins. Both players know A. The set A is said to be determined if there is a strategy that will force a win; it is undetermined otherwise. A long game is the obvious generalization where you play for longer than countable time. The details don't matter.

This led me to think, as someone who's moved over to working a lot on machine learning: is there an analogous question for online learning? There are several ways to set this up and I won't bore you with the details (I doubt any reader here really cares), but depending on how you set it up, you can prove several relatively trivial, but kind of cute, results (I say trivial because they took me on the order of hours, which means that someone who knows what they're doing probably would see them immediately). I basically did this as a mental exercise, not for any real reason.

But it got me thinking: obviously machine learning people wouldn't care about this because it's too esoteric and not at all a realistic setting (even for COLTers!). I strongly doubt that logicians would care either, but for a totally different reason. From my interaction, they would be interested if and only if two things were satisfied: (a) the result showed some interesting connection between a new model and existing models; (b) the proofs were non-trivial and required some new insight that could be then applied to other problems. Obviously this is not my goal in life, so I've dropped it.

This led to me introspect: what is is that we as a community need in order to find some result interesting? What about other fields that I claim to know a bit about?

Let's take algorithms for a minute. Everything here is about big-O. Like the math types, a result without an interesting proof is much less interesting than a result with an interesting proof, though if you start reading CS theory blogs, you'll find that there's a bit of divide in the community on whether this is good or not. But my sense (which could be totally broken) is that if you have a result with a relatively uninteresting proof that gets you the same big-O running time as the current state of the art, you're in trouble.

I think it's interesting to contrast this with what happens in both NLP and ML. Big-O works a bit differently here. My non-technical description of big-O to someone who knows nothing is that it measure "order of magnitude" improvements. (Okay, O(n log n) versus O(n log log n) is hard to call an order of magnitude, but you get the idea.) An equivalent on the experimental side would seem to be something like: you cut the remaining error on a problem by half or more. In other words, if state of the art is 60% accuracy, then an order of magnitude improvement would be 80% accuracy or better. At 80% it would be 90%. At 90% it would be 95% and so on. 90.5% to 91.2% is not order of magnitude.

I actually like this model for looking at experimental results. Note that this has absolutely nothing to do with statistical significance. It's kind of like reading results graphs with a pair of thick glasses on (for those who don't wear glasses) or no glasses on (for those who wear think glasses). I think the justification is that for less than order of magnitude improvement, it's really just hard to say whether the improvement is due to better tweaking or engineering or dumb luck in how some feature was implemented or what. For order of magnitude improvement, there almost has to be something interesting going on.

Now, I'm not proposing that a paper isn't publishable if it doesn't have order of magnitude improvement. Very few papers would be published this way. I'm just suggesting that improving the state of the art not be -- by itself -- a reason for acceptance unless it's an order of magnitude improvement. That is, you'd either better have a cool idea, be solving a new problem, analyzing the effect of some aspect of a problem that's important, etc., or work on a well trod task and get a big-O improvement.

What I'm saying isn't novel, of course... the various exec boards at the ACL conferences have been trying to find ways to get more "interesting" papers into the conferences for (at least) a few years. This is just a concrete proposal. Obviously it requires buy-in at least of area chairs and probably reviewers. And there are definitely issues with it. Like any attempt to make reviewing non-subjective, there are obviously corner cases (eg., you have a sort-of-interesting idea and an almost-order-of-magnitude improvement). You can't mechanize the reviewing process. But frankly, when I see paper reviews that gush over tiny improvements in the state of the art in an otherwise drab paper, I just get annoyed :).

Suresh said...

Although, even in algorithms land, it's about big-O if the problem is interesting. If not, that doesn't help that much. I think ultimately in theoryCS (as in much of math), interestingness is a kind of PageRank: the more links from the result to other results, the better.

Or you could look at the LONG list that Terry Tao once made

Aji said...

I recently came accross your blog and have been reading along. I thought I would leave my first comment. I dont know what to say except that I have enjoyed reading. Nice blog. I will keep visiting this blog very often.

Miriam

http://www.craigslistposter.info

cutepig said...

I do not know why I was very like to play the EVE, so I need eve isk and the eve gold , do you know the eve online isk.

Anonymous said...
. said...

avineshpvs said...

hey i totally agree to your point. I also came across some papers recently were there was a small tweaking done to the existing work.. I feel this isn't the breakthrough research... Anyways Nice Blog.. I follow your blog :)

Nightlife Web Directory said...

I really liked your blog! You have some great content. Check out my blog and give me some feedback Please come visit my site Free Adult Entertainment when you got time.

Well, nice article buddy… Someone will love to read this infor if I tell her about this. She’s really interested in this subject. Thanks again… Please come visit my site EadvertisingNetwork when you got time.

hotel rooms said...

This is just another reason why I like your website. I like your style of writing you tell your stories without out sending us to 5 other sites to complete the story. Please come visit my site Motelhotel Business Directory when you got time.

personal training said...

Comprehensive web resource of Aerobics Instruction, Classes & Instruction, Exercise & Fitness Clothing Retail, Exercise & Fitness Equipment & Supplies Dealers, Exercise & Fitness Equipment & Supplies Wholesale & Manufacturers, Exercise & Fitness Equipment Rental, Exercise & Fitness Equipment Service & Repair, Fitness Consultants, Gymnasium Equipment & Supplies Dealers, Gymnastics Instruction.

custom homes said...

Really great work. Congrats to everyone who are involved with this project. The website layout and graphics are really cool. Please come visit my site Realtor Home Builders Directory when you got time.

Anonymous said...

Thanks for sharing,
Dissertation | Essay | Research Paper

Anonymous said...

Great post, i really appreciate it.
Term Paper | Thesis

peter.w said...
peter.w said...
peter.w said...
deLi said...
Sheldon said...

sick. well done r-mean.﻿ keep it up
getse hayoutioune

Thesis Writing | Dissertation Writing | Essay Writing | Assignment Writing

tariely said...

Классный фильм на кинозоуне.
электронная почта без регистрации

Sheldon said...

absense of mind can do things without having reasons.. one can say that

Thesis Help | Dissertation Help | Essay Help | Assignment Help

Paul said...

Recently I came across your blog and have been reading along. I think I would leave my first comment. I do not know what to say, but I like reading. Good blog. I will continue to visit the blog very often.
Squidoo Lens Creation Social Media News Squidoo Lens Creation Link Building Services

dissertations quality said...

Thanks

Anonymous said...
Anonymous said...

Hi,
This is inspiring; I am very pleased by this post. Nice work, thanks for such information.

gamefan12 said...

I think this is so good and definitely benefit a lot of people if they use it. I think this is so good.
fort lauderdale auto accident attorney

qishaya said...

one day i went shopping outside,and in an ed hardy store,I found some kinds of ed hardy i love most they are Your website is really good Thank you for the information ed hardy ed hardy ed hardy clothing ed hardy clothing ed hardy shoes ed hardy shoes don ed hardy don ed hardy ed hardy clothes ed hardy clothes ed hardy bags ed hardy bags ed hardy swimwear ed hardy swimwear ed hardy jeans ed hardy jeans ed hardy mens ed hardy mens Thank you for the information

Teenagers in a track adidas tennis shoes can go through shoes rate discount adidas sneakers teenage runner well knows that newest adidas shoes 2010 to wear the right shoes discount moncler outlet any cross country among world cheap adidas shoes especially important to the sportsman wholesale adidas shoes a young person growing up adidas shoes outlet Not only do they want to discount moncler t-shirt grow out of their shoes cheap jordan shoes but shape of their feet changes new jordan shoes which means every time we new jordan shoes the time comes to get air jordan 2010 a new pair of shoes eveyone discount jordan shoes a good choice to get jumpman23 it with a high material Jordan ajf shoes that breathes easily on random Newest Timberland shoes 2010 They should be extended runs cheap Nike shox shoes give enough support to athlets discount brand shoes especially around the ankles area cheap Nike Dunk shoes to avoid injury your ankles AIR MAX shoes outlet when you make your trip 2010 New GHD something in store possible fit Benefit GHD his is also the way to Black GHD that don't fit properly only CHI hair straightener

but they are not returnable GHD IV Salon Styler Every woman needs to have GHD Rare Styler a few tips to spot Gold GHD the inside of the bag Gray GHD Handbags are considered as Kiss GHD Styler will focus on various items Pink GHD is perfect just for you Pure Black GHD is primarily a company that Pure White GHD if you really want to Purple GHD The qualities that make a cheap bourke dooney handbags running shoe with a good grip authentic dooney bourke bags and material that breathes easily newest dooney bourke handbags They should be sure that moncler vest light enough to do sports dooney bourke new purses but still give enough support to discount dooney bourke handbags outlet around the ankles to avoid injury wholesale Rolex watches you want a high quality moncler we can provide many moncler t-shirts moncler jackets does spend a lot of money moncler coats choose us and you will not regret.dooney bourke totes have the perfect apparel cheap ugg boots you have to know what discount ugg boots there to take your money ugg boots it focuses on your convenience classic ugg boots One of the major attractions ugg classic tall boots

seldamuratim said...

Really trustworthy blog. Please keep updating with great posts like this one. I have booked marked your site and am about to email it to a few friends of mine that I know would enjoy reading..
sesli sohbetsesli chatkamerali sohbetseslisohbetsesli sohbet sitelerisesli chat siteleriseslichatsesli sohpetseslisohbet.comsesli chatsesli sohbetkamerali sohbetsesli chatsesli sohbetkamerali sohbet
seslisohbetsesli sohbetkamerali sohbetsesli chatsesli sohbetkamerali sohbet

speed dating in new york said...

As a newbie, this article was really helpful, thanks for sharing!

cilemsin42 said...

Really trustworthy blog. Please keep updating with great posts like this one. I have booked marked your site and am about to email it to a few friends of mine that I know would enjoy reading..
sesli sohbetsesli chat
sesli sohbet siteleri

sesli chat siteleri sesli sohbetsesli chat
sesli sohbet siteleri
sesli chat siteleri
SesliChat
cılgın sohbet
güzel kızlar
bekar kızlar
dul bayanlar
seviyeli insanlar
yarışma
canlı müzik
izdivac
en güzel evlilik
sesliparti
seslisohbet odalari
Sesli Chat
SesliChat Siteleri
Sesli Chat sitesi
SesliChat sitesi
SesliSohbet
Sesli Sohbet
Sesli Sohbet Sitesi
SesliSohbet Sitesi
SesliSohbet Siteleri
Muhabbet Sitesi
kamerali chat
Görüntülü Sohbet
Hasret gülleri
Çet sitesi
SesliSohbet
Sesli Sohbet
Canli sohbet
Turkce sohbet
Kurtce Sohbet
Kurtce Chat
Kurtce Muhabbet
Kurtce Sohbet
Kurdish Chat
SesliChat
Sesli Chat
SesliSanal
Guncel Haber
sohbet Sitesi
Chat sitesi..

daniel john said...

You made some good points there. I did a search on the topic and found most people will agree with your blog.

Term papers

seldamuratim said...

Really trustworthy blog. Please keep updating with great posts like this one. I have booked marked your site and am about to email it to a few friends of mine that I know would enjoy reading..

sesli sohbet
seslisohbet
sesli chat
seslichat
sesli sohbet sitesi
sesli chat sitesi
sesli sohpet
kamerali sohbet
kamerali chat
webcam sohbet

combattery84 said...
combattery84 said...
DiSCo said...

Really trustworthy blog. Please keep updating with great posts like this one. I have booked marked your site and am about to email it

to a few friends of mine that I know would enjoy reading..
seslisohbet
seslichat
sesli sohbet
sesli chat
sesli
sesli site
görünlütü sohbet
görüntülü chat
kameralı sohbet
kameralı chat
sesli sohbet siteleri
sesli chat siteleri
görüntülü sohbet siteleri
görüntülü chat siteleri
kameralı sohbet siteleri
canlı sohbet
sesli muhabbet
görüntülü muhabbet
kameralı muhabbet
seslidunya
seslisehir
sesli sex

Sesli Chat said...

Really trustworthy blog. Please keep updating with great posts like this one. I have booked marked your site and am about to email it

to a few friends of mine that I know would enjoy reading..
seslisohbet
seslichat
sesli sohbet
sesli chat
sesli
sesli site
görünlütü sohbet
görüntülü chat
kameralı sohbet
kameralı chat
sesli sohbet siteleri
sesli chat siteleri
sesli muhabbet siteleri
görüntülü sohbet siteleri
görüntülü chat siteleri
görüntülü muhabbet siteleri
kameralı sohbet siteleri
kameralı chat siteleri
kameralı muhabbet siteleri
canlı sohbet
sesli muhabbet
görüntülü muhabbet
kameralı muhabbet
birsesver
birses
seslidunya
seslisehir
sesli sex