{"id":199,"date":"2006-06-24T14:07:21","date_gmt":"2006-06-24T20:07:21","guid":{"rendered":"http:\/\/hunch.net\/?p=199"},"modified":"2006-06-24T14:45:53","modified_gmt":"2006-06-24T20:45:53","slug":"online-convex-optimization","status":"publish","type":"post","link":"https:\/\/hunch.net\/?p=199","title":{"rendered":"Online convex optimization at COLT"},"content":{"rendered":"<p>At <a href=\"http:\/\/www.hpl.hp.com\/conferences\/icml03\/\">ICML 2003<\/a>, <a href=\"http:\/\/www.cs.ualberta.ca\/~maz\/\">Marty Zinkevich<\/a> <a href=\"http:\/\/www.cs.ualberta.ca\/~maz\/publications\/ICML03.pdf\">proposed<\/a> the online convex optimization setting and showed that a particular gradient descent algorithm has regret O(T<sup>0.5<\/sup>) with respect to the best predictor where T is the number of rounds. This seems to be a nice model for online learning, and there has been some significant follow-up work.<\/p>\n<p>At <a href=\"http:\/\/www.learningtheory.org\/colt2006\/\">COLT 2006<\/a> <a href=\"http:\/\/www.cs.princeton.edu\/~ehazan\/\">Elad Hazan<\/a>, <a href=\"http:\/\/people.cs.uchicago.edu\/~kalai\/\">Adam Kalai<\/a>, <a href=\"http:\/\/www.cs.princeton.edu\/~satyen\/\">Satyen Kale<\/a>, and <a href=\"http:\/\/www.cs.princeton.edu\/~aagarwal\/\">Amit Agarwal<\/a> presented <a href=\"http:\/\/www.cs.princeton.edu\/~ehazan\/papers\/colt.pdf\">a modification which takes a Newton step<\/a> guaranteeing O(log T) regret when the first and second derivatives are bounded. <a href=\"http:\/\/www.cs.princeton.edu\/~ehazan\/papers\/icml.pdf\">Then they applied these algorithms to portfolio management<\/a> at <a href=\"http:\/\/www.cs.princeton.edu\/~ehazan\/papers\/icml.pdf\">ICML 2006<\/a> (with <a href=\"http:\/\/www.cs.princeton.edu\/~schapire\/\">Robert Schapire<\/a>) yielding some very fun graphs.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>At ICML 2003, Marty Zinkevich proposed the online convex optimization setting and showed that a particular gradient descent algorithm has regret O(T0.5) with respect to the best predictor where T is the number of rounds. This seems to be a nice model for online learning, and there has been some significant follow-up work. At COLT &hellip; <\/p>\n<p class=\"link-more\"><a href=\"https:\/\/hunch.net\/?p=199\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Online convex optimization at COLT&#8221;<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[29,7,18],"tags":[],"class_list":["post-199","post","type-post","status-publish","format-standard","hentry","category-machine-learning","category-online","category-papers"],"_links":{"self":[{"href":"https:\/\/hunch.net\/index.php?rest_route=\/wp\/v2\/posts\/199","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/hunch.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/hunch.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/hunch.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/hunch.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=199"}],"version-history":[{"count":0,"href":"https:\/\/hunch.net\/index.php?rest_route=\/wp\/v2\/posts\/199\/revisions"}],"wp:attachment":[{"href":"https:\/\/hunch.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=199"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/hunch.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=199"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/hunch.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=199"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}