{"id":339,"date":"2008-07-06T23:26:10","date_gmt":"2008-07-07T05:26:10","guid":{"rendered":"http:\/\/hunch.net\/?p=339"},"modified":"2008-07-06T23:26:10","modified_gmt":"2008-07-07T05:26:10","slug":"to-dual-or-not","status":"publish","type":"post","link":"https:\/\/hunch.net\/?p=339","title":{"rendered":"To Dual or Not"},"content":{"rendered":"

Yoram<\/a> and Shai<\/a>‘s online learning tutorial<\/a> at ICML<\/a> brings up a question for me, “Why use the dual<\/a>?”<\/p>\n

The basic setting is learning a weight vector wi<\/sub><\/em> so that the function f(x)= sumi<\/sub> wi<\/sub> xi<\/sub><\/em> optimizes some convex loss function.<\/p>\n

The functional view of the dual is that instead of (or in addition to) keeping track of wi<\/sub><\/em> over the feature space, you keep track of a vector aj<\/sub><\/em> over the examples and define wi<\/sub> = sumj<\/sub> aj<\/sub> xji<\/sub><\/em>.<\/p>\n

The above view of duality makes operating in the dual appear unnecessary, because in the end a weight vector is always used. The tutorial suggests that thinking about the dual gives a unified algorithmic font for deriving online learning algorithms. I haven’t worked with the dual representation much myself, but I have seen a few examples where it appears helpful.<\/p>\n

    \n
  1. Noise<\/strong> When doing online optimization (i.e. online learning where you are allowed to look at individual examples multiple times), the dual representation may be helpful in dealing with noisy labels.<\/li>\n
  2. Rates<\/strong> One annoyance of working in the primal space with a gradient descent style algorithm is that finding the right learning rate can be a bit tricky.<\/li>\n
  3. Kernelization<\/strong> Instead of explicitly computing the weight vector, the representation of the solution can be left in terms of ai<\/sub><\/em>, which is handy when the weight vector is only implicitly defined.<\/li>\n<\/ol>\n

    A substantial drawback of dual analysis is that it doesn’t seem to apply well in nonconvex situations. There is a reasonable (but not bullet-proof) argument that learning over nonconvex functions is unavoidable in solving some problems.<\/p>\n","protected":false},"excerpt":{"rendered":"

    Yoram and Shai‘s online learning tutorial at ICML brings up a question for me, “Why use the dual?” The basic setting is learning a weight vector wi so that the function f(x)= sumi wi xi optimizes some convex loss function. The functional view of the dual is that instead of (or in addition to) keeping … <\/p>\n

    Continue reading “To Dual or Not”<\/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],"tags":[],"class_list":["post-339","post","type-post","status-publish","format-standard","hentry","category-machine-learning","category-online"],"_links":{"self":[{"href":"https:\/\/hunch.net\/index.php?rest_route=\/wp\/v2\/posts\/339","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=339"}],"version-history":[{"count":0,"href":"https:\/\/hunch.net\/index.php?rest_route=\/wp\/v2\/posts\/339\/revisions"}],"wp:attachment":[{"href":"https:\/\/hunch.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=339"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/hunch.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=339"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/hunch.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=339"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}