## 16 December 2009

### From Kivenen/Warmuth and EG to CW learning and Adaptive Regularization

This post is a bit of a historical retrospective, because it's only been recently that these things have aligned themselves in my head.

The all goes back to Jyrki Kivenen and Manfred Warmuth's paper on exponentiated gradient descent that dates back to STOC 1995. For those who haven't read this paper, or haven't read it recently, it's a great read (although it tends to repeat itself a lot). It's particularly interesting because they derive gradient descent and exponentiated gradient descent (GD and EG) as a consequence of other assumptions.

In particular, suppose we have an online learning problem, where at each time step we receive an example x, make a linear prediction (w'x) and then suffer a loss. The idea is that if we suffer no loss, then we leave w as is; if we do suffer a loss, then we want to balance two goals:

1. Change w enough so that we wouldn't make this error again
2. Don't change w too much
The key question is how to define "too much." Suppose that we measure changes in w by looking at Euclidean distance between the updated w and the old w. If we work through the math for enforcing 1 while minimizing 2, we derive the gradient descent update rule that's been used for optimizing, eg., perceptrons for squared loss for ages.

The magic is what happens if we use something other than Euclidean distance. If, instead, we assume that the ws are all positive, we can use an (unnormalized) KL divergence to measure differences between weight vectors. Doing this leads to multiplicative updates, or the exponentiated gradient algorithm.

(Obvious (maybe?) open question: what happens if you replace the distance with some other divergence, say a Bregman, or alpha or phi-divergence?)

This line of thinking leads naturally to Crammer et al.'s work on Online Passive Aggressive algorithms, from JMLR 2006. Here, the idea remains the same, but instead of simply ensuring that we make a correct classification, ala rule (1) above, we ensure that we make a correct classification with a margin of at least 1. They use Euclidean distance to measure the difference in weight vectors, and, for many cases, can get closed-form updates that look GD-like, but not exactly GD. (Aside: what happens if you use, eg., KL instead of Euclidean?)

Two years later, Mark Dredze, Koby Crammer and Fernando Pereira presented Confidence-Weighted Linear Classification. The idea here is the same: don't change the weight vectors too much, but achieve good classification. The insight here is to represent weight vectors by distributions over weight vectors, and the goal is to change these distributions enough, but not too much. Here, we go back to KL, because KL makes more sense for distributions, and make a Gaussian assumption on the weight vector distribution. (This has close connections both to PAC-Bayes and, if I'm wearing my Bayesian hat, Kalman filtering when you make a Gaussian assumption on the posterior, even though it's not really Gaussian... it would be interesting to see how these similarities play out.)

The cool thing here is that you effectively get variable learning rates on different parameters, where confident parameters get moved less. (In practice, one really awesome effect is that you tend to only need one pass over your training data to do a good job!) If you're interested in the Bayesian connection, you can get a very similar style algorithm if you do EP on a Bayesian classification algorithm (by Stern, Herbrich and Graepel), which is what Microsoft Bing uses for online ads.

This finally bring us to NIPS this year, where Koby Crammer, Alex Kulesza and Mark Dredze presented work on Adaptive Regularization of Weight Vectors. Here, they take Confidence Weighted classification and turn the constraints into pieces of the regularizer (somewhat akin to doing a Lagrangian trick). Doing so allows them to derive a representer theorem. But again, the intuition is exactly the same: don't change the classifier too much, but enough.

All in all, this is a very interesting line of work. The reason I'm posting about it is because I think seeing the connections makes it easier to sort these different ideas into bins in my head, depending on what your loss is (squared versus hinge), what your classifier looks like (linear versus distribution over linear) and what your notion of "similar classifiers" is (Euclidean or KL).

(Aside: Tong Zhang has a paper on regularized winnow methods, which fits in here somewhere, but not quite as cleanly.)

Nikos said...

Hi Hal,

Thank you for blogging about the interesting developments in online learning. I may be wrong, but I think the open question you pose has been answered in the last few years.

Take any strictly convex function F mapping a convex set A to the real numbers. Assume F has continuous gradient whose norm goes to infinity as we approach the boundary of A. Then the following algorithm can learn a linear classifier that makes sure the changes in Bregman divergences induced by F are small:

Repeat
Predict with sign(w*x)

where F* is the convex conjugate of F. A good explanation of all these can be found in "Prediction Learning and Games" by Cesa-Bianchi and Lugosi.

P.S. Is there a way to write math in LaTeX in the comments?

Ambuj Tewari said...

Following up on the last comment by Nikos, here's a beautiful paper by Beck and Teboulle that shows how the classic "Mirror Descent" algorithm can be viewed as a projected gradient method where the Euclidean distance had been replaced by a Bregman divergence:

Similar algorithms are known where we use a Csiszar f-divergence instead. A query like "proximal algorithm csiszar" on your favourite search engine is sure to turn up some good reference.

Fernando Pereira said...

Thanks for the nice survey! Koby, Mehryar, and I had a paper at last AIStats where we explored the PAC-bayesian connection in the analysis of a batch CW algorithm.

rr8004 said...

Very nice information. Thanks for this. Please come visit my site City Guide Aurora when you got time.

rr8004 said...

Very nice information. Thanks for this. Please come visit my site Aurora City Business Listings when you got time.

Michigan Lawyer said...

This is such a great resource that you are providing and you give it away for free. I love seeing websites that understand the value of providing a quality resource for free. It’s the old what goes around comes around routine.

Michigan Attorneys, Michigan
Lawyers
, Michigan Law Firms,
Michigan Law Offices, Michigan
Legal Services
, Attorneys
In Michigan
, Michigan Lawyer
Directory
, Michigan Attorney
Directory
, Michigan Accident Attorneys, Michigan Administrative & Governmental Law Attorneys, Michigan Adoption Attorneys, Michigan Agricultural Law Attorneys, Michigan Appeals Attorneys, Michigan Arbitration & Mediation Services, Michigan Arbitration & Mediation Services Attorneys, Michigan Asbestos Diseases Attorneys, Michigan Asset Protection Attorneys, Michigan Attorneys, Michigan Attorneys&#; Information & Referral Services, Michigan Attorneys&#; Support Services, Michigan Banking & Investment Law Attorneys, Michigan Bankruptcy Attorneys, Michigan Business Services, Michigan Child Abuse Law Attorneys

Family Lawyer Minnesota said...

There are certainly a lot of details like that to take into consideration. That’s a great point to bring up. I offer the thoughts above as general inspiration but clearly there are questions like the one you bring up where the most important thing will be working in honest good faith.

Minnesota Attorneys, Minnesota
Lawyers
, Minnesota Law Firms,
Minnesota Law Offices, Minnesota
Legal Services
, Attorneys
In Minnesota
, Minnesota Lawyer
Directory
, Minnesota Attorney
Directory
, Minnesota Accident Attorneys, Minnesota Administrative & Governmental Law Attorneys, Minnesota Adoption Attorneys, Minnesota Agricultural Law Attorneys, Minnesota Appeals Attorneys, Minnesota Arbitration & Mediation Services, Minnesota Arbitration & Mediation Services Attorneys, Minnesota Asbestos Diseases Attorneys, Minnesota Asset Protection Attorneys, Minnesota Attorneys, Minnesota Attorneys&#; Information & Referral Services, Minnesota Attorneys&#; Support Services, Minnesota Banking & Investment Law Attorneys, Minnesota Bankruptcy Attorneys, Minnesota Business Services, Minnesota Child Abuse Law Attorneys

Unknown said...
Unknown said...
Unknown 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

Unknown said...
Unknown said...

Fashion trends change on daily basis, like Gold GHD. Following the latest in designer shades has become a passion of everyone, now Burberry Sunglasses. If you are the type of a woman who loves to explore in fashion, our ED Hardy Sunglasses will definitely satisfy your taste. Cheap Ed Hardy Sunglasses is also OK. Ed hardy streak of clothing is expanded into its wholesale ED Hardy T-shirt chain so that a large number of fans and users can enjoy the cheap ED Hardy Clothing range easily with the help of numerous secured websites, actually, our ED Hardy Outlet. As we all know, in fact discount ED Hardy, is based on the creations of the world renowned tattoo artist Don Ed Hardy. Well, this question is bound to strike the minds of all individuals. Many people may say Prada shoes is a joke, but we can give you Prada Sunglasses, because we have Prada handbags. Almost everyone will agree that Prada Purses are some of the most beautiful designer handbags marketed today. Now we have one new product: Prada totes. The reason is simple: fashion prohibited by ugg boots, in other words, we can say it as Cheap ugg boots. Would you like to wear Discount ugg boots. We have two kinds of fashionable boots: classic ugg boots and ugg classic tall boots. Ankh Royalty--the Cultural Revolution. Straightens out the collar, the epaulette epaulet, the Ankh Royalty Clothing two-row buckle. Now welcome to our Ankh Royalty Outlet. And these are different products that bear the most famous names in the world of fashion, like Ankh Royalty T shirt by the way -Prada, Spyder, Moncler(Moncler jackets，or you can say Moncler coats, Moncler T-shirt, Moncler vest，and you can buy them from our discount Moncler outlet), GHD, ED Hardy, Ankh Royalty, Twisted Heart.

Unknown said...

New Jersey Arbitration & Mediation Services Attorneys, New Jersey Asbestos Diseases Attorneys, New Jersey Asset Protection Attorneys, New Jersey Attorneys, New Jersey Attorneys&#; Information & Referral Services, New Jersey Attorneys&#; Support Services, New Jersey Banking & Investment Law Attorneys, New Jersey Bankruptcy Attorneys, New Jersey Business Services, New Jersey Child Abuse Law Attorneys

Unknown said...

found your site on del.icio.us today and really liked it.. i bookmarked it and will be back to check it out some more later ..
State of New Jersey Lawyer Directory,
New Jersey Attorney Search,
New Jersey Lawyers Search, Find
A New Jersey Attorney Lawyers
, New Jersey Civil Law Attorneys, New Jersey Collection Law Attorneys, New Jersey Computers & Technology Law Attorneys, New Jersey Constitutional Law Attorneys, New Jersey Construction Law Attorneys, New Jersey Consumer Protection Attorneys, New Jersey Domestic Partnerships Attorneys, New Jersey Drug Charges Attorneys, New Jersey DUI/DWI Attorneys,

Unknown said...

Online shoe shopping has never been so easy.A one-stop destination for all your footwear needs!Nike Shox R4,Shox shoes,shox nz,ugg boots or new spyder,you name it and we have it.We are not only the premier shopping destination for spyder jacketsonline but also for people of all age-groups and for all brands. Buy online without leaving the comfort of your home. Whatever your needs: from clothing and accessories to all brands (cheap ugg boots,discount ugg boots,ugg boots,cheap ugg boots,discount ugg boots,Rare ghd,MBT boots,MBT shoes in fashion,cheap mbt shoes sale,discount mbt outlet 2010,MBT Walking Shoes)of shoes and sports gear,we has it all for you.

Anonymous said...

If you had some way of rating posts I would for sure give you a high rating my friend!
South Carolina health insurance, South Dakota health insurance, Tennessee health insurance, Texas health insurance, Utah health insurance, Vermont health insurance, Virginia health insurance, Washington health insurance, West Virginia health insurance, Wisconsin health insurance, Wyoming health insurance

Anonymous said...

Your summaries are always top-notch. Thanks for keeping us apprised. I’m reading every word here.
Your summaries are always top-notch. Thanks for keeping us apprised. I’m reading every word here.

Ann said...

Fashion trends change on daily basis, like Gold GHD. Now Burberry Sunglasses.Our ED Hardy Sunglasses will definitely satisfy your taste. ED Hardy T-shirt chain makes people enjoy the cheap ED Hardy Clothing range easily our ED Hardy Outlet. As we all know, in fact discount ED Hardy, is based. The reason is simple: fashion prohibited by polo boots, in other words, we can say it as polo shoes. Would you like to wear cheap ugg boots? Now welcome to our paul smith outlet. And these are different products, like Puma Shoes (or you can say Puma Sneaker, and you can buy them from our puma outlet), GHD, ED Hardy, UGG, Paul Smith and brand Sunglasses. For those who desire for a ugg boots but have to refrain themselves from buying one ugg boots, there are some company that offer discount ugg boots.

Unknown 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

Unknown said...

NewStreetFashion
Ed Hardy
stylish design
Ed Hardy Wholesale
fashion excellent quality
wholesale Ed Hardy
ED Hardy clothing bring you a super surprise!
ed hardy wholesale clothing
The quality is so good
christian audigier
if you really want it
jordan 8
jordan 9
jordan 10

Unknown said...

coats & jackets
If one knows where to, the world will give way.
north face jackets
moncler
World-class brands
moncler jackets
The top fabric produced in France is 100%
duvetica
Italy's top outdoor brands
peuterey
Good quality and function, more accord with fashionable design
spyder jackets
High-grade, innovation, the trend of the brand
Columbia Sportswear
The quality is so good
quiksilver jackets
Young and creative style
ski jacket

You can have a look at it.
jordan shoes
Wow.
jordan 7
Wonderful!
air yeezy
jordan true flight
jordan 3
jordan 4
We offer different styles.
jordan 1
jordan 2
Thanks.
jordan 5
jordan ajf shoes
There are cheap shoes to choose
nike footwear
jordan flight 45
Good quality with low price.
air jordan 2010
Air Jordan 2009
Enjoy it!
jumpman
nike trainers

Anonymous said...

I can't believe it.
abercrombie outlet
You can have a look at it.
abercrombie fitch outlet
The quality is so good
nike shoes wholesale
wholesale jordan shoes
Young and creative style
wholesale clothing
wholesale nike shoes
wholesale jordans
Young and creative style
china wholesale
There are cheap shoes to choose
jordan 6
jordan 28

Anonymous said...

I can't believe it.
abercrombie outlet
You can have a look at it.
abercrombie fitch outlet
The quality is so good
nike shoes wholesale
wholesale jordan shoes
Young and creative style
wholesale clothing
wholesale nike shoes
wholesale jordans
Young and creative style
china wholesale
There are cheap shoes to choose
jordan 6
jordan 28

Unknown 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

Essay Service said...

Hi,
Online learning are developing and gaining popularity now a day. Thanks for letting us know how the interesting developments in online leaning. I personally like your post. You have shared good insights and experiences. Keep it up.

Essay Help

combattery84 said...
combattery84 said...
combattery84 said...
ylinling001 said...

I like your article, really interesting! My point is also very good, I hope you'll like:chi flat iron are a very popular choice of hair straightener.New Balance,new Blance shoes,new Blance Outlet are some of the most comfortable and stylish shoes on the market today. The designer has a whole range of shoes for all types of athletes. five finger shoes,vibram five fingers,Five fingers shoes give women the feeling of walking barefoot while still keeping the feet protected.

Anonymous 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

Unknown 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