tag:blogger.com,1999:blog-6555947.post3675340728333004626..comments2024-03-14T01:32:43.610-06:00Comments on The Geomblog: Multiplicative Weight Updates as Zombie Binary SearchSuresh Venkatasubramanianhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-6555947.post-39019577072018442162012-05-10T14:02:43.670-06:002012-05-10T14:02:43.670-06:00Avrim Blum has some nice slides that present multi...Avrim Blum has some nice slides that present multiplicative weights through this interpretation in the expert advice setting. He starts with the setting in which there is one perfect expert who is always right -- you just don't know who he is ahead of time. Here, you can use the halving algorithm, which is essentially binary search. When you no longer have a perfect expert, this is too brittle, and so you move to the weighted majority algorithm, and finally randomized weighted majority (which is the same algorithm as multiplicative weights). I like this way of presenting these algorithms -- I taught the randomized weighted majority algorithm to my undergrad algorithmic game theory students this semester using this progression.Aaronhttps://www.blogger.com/profile/09952936358739421126noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-56009043277534426882012-05-10T13:30:01.323-06:002012-05-10T13:30:01.323-06:00Sariel, that's why I had the disclaimer. There...Sariel, that's why I had the disclaimer. There are a number of ways of thinking about MWU, but the LP-based view is not something that's accessible to students doing D&C - the view I proposed is a little more gentle. <br /><br />I actually wanted to do a more general post on the different views of MWU, but that was getting too long and complicated. In particular the derandomized Chernoff view is quite interesting.Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-65400568338891272982012-05-10T10:07:09.211-06:002012-05-10T10:07:09.211-06:00I am not convinced that MWU is one unified techniq...I am not convinced that MWU is one unified techniques. My take on the usage of MWU in CG that it is just a technique for solving LPs. You can get low-crossing spanning trees from LP without the reweighting technique (I have a note on this), and the same goes for geometric set cover. <br />--Ssarielhttp://sariel.myopenid.comnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-43276403659000853642012-05-10T01:39:55.373-06:002012-05-10T01:39:55.373-06:00Thanks for the great zombie intuition! I found ano...Thanks for the great zombie intuition! I found another (extended) version of the survey at http://ie.technion.ac.il/~ehazan/papers/MWsurvey.pdfAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-40931003640558471172012-05-09T22:53:10.560-06:002012-05-09T22:53:10.560-06:00In my mind this invokes a graphic comic strip :)
...In my mind this invokes a graphic comic strip :) <br />(Randall Munroe might be up for making one)DCnoreply@blogger.com