{"id":182962,"date":"2007-05-24T00:00:00","date_gmt":"2009-10-31T10:11:27","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/msr-research-item\/paths-beyond-local-search-a-tight-bound-for-randomized-fixed-point-computation\/"},"modified":"2016-09-09T09:51:36","modified_gmt":"2016-09-09T16:51:36","slug":"paths-beyond-local-search-a-tight-bound-for-randomized-fixed-point-computation","status":"publish","type":"msr-video","link":"https:\/\/www.microsoft.com\/en-us\/research\/video\/paths-beyond-local-search-a-tight-bound-for-randomized-fixed-point-computation\/","title":{"rendered":"Paths Beyond Local Search: A Tight Bound for Randomized Fixed-Point Computation"},"content":{"rendered":"<div class=\"asset-content\">\n<p>In 1983, Aldous proved that randomization can speedup local search. For example, it reduces the query complexity of local search over grid 1:n]<sup>d<\/sup> from Theta (n<sup>d-1<\/sup>) to O (n<sup>d\/2<\/sup>). It remains open whether randomization helps fixed-point computation. Inspired by this problem and recent advances on equilibrium computation, we have been fascinated by the following question:<br \/>\nIs a fixed-point or an equilibrium fundamentally harder to find than a local optimum?<br \/>\nIn this talk, I will present a tight bound of (&Omega;(n))<sup>d-1<\/sup> on the randomized query complexity for computing a fixed point of a discrete Brouwer function over grid [1:n]<sup>d<\/sup>. Since the randomized query complexity of global optimization over [1:n]<sup>d<\/sup> is Theta (n<sup>d<\/sup>), the randomized query model strictly separates these three important search problems:<br \/>\nGlobal optimization is harder than fixed-point computation, and fixed-point computation is harder than local search.<br \/>\nOur result indeed demonstrates that randomization does not help in fixed-point computation in the query model, as its deterministic complexity is also Theta (n<sup>d-1<\/sup>).<br \/>\nThis is a joint work with Xi Chen of Tsinghua University.<\/p>\n<\/div>\n<p><!-- .asset-content --><\/p>\n","protected":false},"excerpt":{"rendered":"<p>In 1983, Aldous proved that randomization can speedup local search. For example, it reduces the query complexity of local search over grid 1:n]d from Theta (nd-1) to O (nd\/2). It remains open whether randomization helps fixed-point computation. Inspired by this problem and recent advances on equilibrium computation, we have been fascinated by the following question: [&hellip;]<\/p>\n","protected":false},"featured_media":194830,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr_hide_image_in_river":0,"footnotes":""},"research-area":[],"msr-video-type":[],"msr-locale":[268875],"msr-post-option":[],"msr-session-type":[],"msr-impact-theme":[],"msr-pillar":[],"msr-episode":[],"msr-research-theme":[],"class_list":["post-182962","msr-video","type-msr-video","status-publish","has-post-thumbnail","hentry","msr-locale-en_us"],"msr_download_urls":"","msr_external_url":"https:\/\/youtu.be\/kWSyHUXdTLk","msr_secondary_video_url":"","msr_video_file":"","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/182962","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-video"}],"version-history":[{"count":0,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/182962\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media\/194830"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=182962"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=182962"},{"taxonomy":"msr-video-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video-type?post=182962"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=182962"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=182962"},{"taxonomy":"msr-session-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-session-type?post=182962"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=182962"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=182962"},{"taxonomy":"msr-episode","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-episode?post=182962"},{"taxonomy":"msr-research-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-theme?post=182962"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}