{"id":731,"date":"2024-06-22T10:35:09","date_gmt":"2024-06-22T10:35:09","guid":{"rendered":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/?p=731"},"modified":"2024-06-22T12:30:26","modified_gmt":"2024-06-22T12:30:26","slug":"couplings-for-metropolized-non-reversible-mcmc","status":"publish","type":"post","link":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/couplings-for-metropolized-non-reversible-mcmc\/","title":{"rendered":"Couplings for Metropolized Non-Reversible MCMC"},"content":{"rendered":"<p>In a highly cited paper, <a href=\"https:\/\/projecteuclid.org\/journals\/annals-of-applied-probability\/volume-10\/issue-3\/Analysis-of-a-nonreversible-Markov-chain-sampler\/10.1214\/aoap\/1019487508.full\">Diaconis et al, (2000)<\/a> lifted the symmetric random walk on the discrete circle by adding an auxiliary velocity variable that is flipped in each step with a specified probability, and proved that a well-tuned <em>lifted<\/em> walk on a circle of circumference n mixes in <span style=\"color: #0000ff\">O(n) steps<\/span> vs. <span style=\"color: #0000ff\">O(n^2) steps<\/span> for the unlifted walk. This work led to an avalanche of research on non-reversible MCMC including notably to the kinetic Langevin diffusion (and related processes) based on couplings <a href=\"https:\/\/projecteuclid.org\/journals\/annals-of-probability\/volume-47\/issue-4\/Couplings-and-quantitative-contraction-rates-for-Langevin-dynamics\/10.1214\/18-AOP1299.full\">Eberle et al. (2019)<\/a> and hypocoercivity <a href=\"https:\/\/link.springer.com\/article\/10.1007\/s00205-023-01922-4\">Cao et al. (2023)<\/a>. (Note, <a href=\"https:\/\/arxiv.org\/abs\/2402.05041\">Eberle and L\u00f6rler (2024)<\/a> recently proved the kinetic Langevin diffusion is a <em>lifted<\/em> Langevin diffusion.) By now, there are numerous non-asymptotic complexity upper bounds for <em>unadjusted<\/em> discretizations of kinetic Langevin diffusions including <a href=\"http:\/\/proceedings.mlr.press\/v75\/cheng18a.html\">Cheng et al. 2018<\/a>, <a href=\"https:\/\/projecteuclid.org\/journals\/bernoulli\/volume-26\/issue-3\/On-sampling-from-a-log-concave-density-using-kinetic-Langevin\/10.3150\/19-BEJ1178.full\">Dalalyan and Riou-Durand (2020)<\/a>, <a href=\"https:\/\/projecteuclid.org\/journals\/electronic-journal-of-statistics\/volume-15\/issue-2\/High-dimensional-MCMC-with-a-standard-splitting-scheme-for-the\/10.1214\/21-EJS1888.full\">Monmarch\u00e9 (2021)<\/a> and <a href=\"https:\/\/epubs.siam.org\/doi\/full\/10.1137\/23M1556289?casa_token=XaZxIXiYpwEAAAAA%3AnEsPEqXtJiMS37rFeHvpxvAFq01TTGZAnrm4dN5QV6vhNPCyLlf_AptGOH3IFOr_l0Kuxn0wV79X\">Leimkuhler et al. (2024)<\/a>, just to name a few. However, quantitative mixing time guarantees for <em>Metropolized<\/em> discretizations are comparatively scarce.<\/p>\n<p>In this context, I am happy to share a paper with Stefan Oberd\u00f6rster (Bonn) which just came out in EJP: <a href=\"https:\/\/projecteuclid.org\/journals\/electronic-journal-of-probability\/volume-29\/issue-none\/Mixing-of-Metropolis-adjusted-Markov-chains-via-couplings--The\/10.1214\/24-EJP1150.full\">Mixing of Metropolis-Adjusted Markov Chains via Couplings: The High Acceptance Regime<\/a>. In this work, we use coupling techniques to prove, for the first time, a log(1\/\\epsilon)-scaling of the \\epsilon-mixing time of Metropolized Non-Reversible Markov chains without restrictive conditions on either the target or starting distribution. The key idea is to turn mixing time results for the unadjusted chain into mixing results for the Metropolized chain by controlling the rejection probability on the time scale it takes for a coupling of the unadjusted chain to meet. By iterating the Metropolized chain over \\log(1\/\\epsilon) such epochs, an upper bound on the mixing time of the Metropolized chain is obtained. The work actually does much more than this: since it uses a localization argument it suffices to assume that the underlying unadjusted chain only locally mixes, which substantially relaxes the regularity and convexity conditions on the target distribution.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In a highly cited paper, Diaconis et al, (2000) lifted the symmetric random walk on the discrete circle by adding an auxiliary velocity variable that is flipped in each step &hellip; <a href=\"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/couplings-for-metropolized-non-reversible-mcmc\/\" class=\"\">Read More<\/a><\/p>\n","protected":false},"author":2614,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[11],"tags":[],"class_list":["post-731","post","type-post","status-publish","format-standard","hentry","category-publications"],"acf":[],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v23.5 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Couplings for Metropolized Non-Reversible MCMC - Nawaf Bou-Rabee<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/couplings-for-metropolized-non-reversible-mcmc\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Couplings for Metropolized Non-Reversible MCMC - Nawaf Bou-Rabee\" \/>\n<meta property=\"og:description\" content=\"In a highly cited paper, Diaconis et al, (2000) lifted the symmetric random walk on the discrete circle by adding an auxiliary velocity variable that is flipped in each step &hellip; Read More\" \/>\n<meta property=\"og:url\" content=\"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/couplings-for-metropolized-non-reversible-mcmc\/\" \/>\n<meta property=\"og:site_name\" content=\"Nawaf Bou-Rabee\" \/>\n<meta property=\"article:published_time\" content=\"2024-06-22T10:35:09+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-06-22T12:30:26+00:00\" \/>\n<meta name=\"author\" content=\"Nawaf Bou-Rabee\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Nawaf Bou-Rabee\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/couplings-for-metropolized-non-reversible-mcmc\/\",\"url\":\"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/couplings-for-metropolized-non-reversible-mcmc\/\",\"name\":\"Couplings for Metropolized Non-Reversible MCMC - Nawaf Bou-Rabee\",\"isPartOf\":{\"@id\":\"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/#website\"},\"datePublished\":\"2024-06-22T10:35:09+00:00\",\"dateModified\":\"2024-06-22T12:30:26+00:00\",\"author\":{\"@id\":\"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/#\/schema\/person\/f9a7363ddc14a33eef77b520728dbde0\"},\"breadcrumb\":{\"@id\":\"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/couplings-for-metropolized-non-reversible-mcmc\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/couplings-for-metropolized-non-reversible-mcmc\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/couplings-for-metropolized-non-reversible-mcmc\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Couplings for Metropolized Non-Reversible MCMC\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/#website\",\"url\":\"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/\",\"name\":\"Nawaf Bou-Rabee\",\"description\":\"\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/#\/schema\/person\/f9a7363ddc14a33eef77b520728dbde0\",\"name\":\"Nawaf Bou-Rabee\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/f3f33e8b5e6e2430997aea3dfec1a454?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/f3f33e8b5e6e2430997aea3dfec1a454?s=96&d=mm&r=g\",\"caption\":\"Nawaf Bou-Rabee\"},\"description\":\"Math Professor at Rutgers\",\"sameAs\":[\"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/\"],\"url\":\"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/author\/nb361\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Couplings for Metropolized Non-Reversible MCMC - Nawaf Bou-Rabee","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/couplings-for-metropolized-non-reversible-mcmc\/","og_locale":"en_US","og_type":"article","og_title":"Couplings for Metropolized Non-Reversible MCMC - Nawaf Bou-Rabee","og_description":"In a highly cited paper, Diaconis et al, (2000) lifted the symmetric random walk on the discrete circle by adding an auxiliary velocity variable that is flipped in each step &hellip; Read More","og_url":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/couplings-for-metropolized-non-reversible-mcmc\/","og_site_name":"Nawaf Bou-Rabee","article_published_time":"2024-06-22T10:35:09+00:00","article_modified_time":"2024-06-22T12:30:26+00:00","author":"Nawaf Bou-Rabee","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Nawaf Bou-Rabee","Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/couplings-for-metropolized-non-reversible-mcmc\/","url":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/couplings-for-metropolized-non-reversible-mcmc\/","name":"Couplings for Metropolized Non-Reversible MCMC - Nawaf Bou-Rabee","isPartOf":{"@id":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/#website"},"datePublished":"2024-06-22T10:35:09+00:00","dateModified":"2024-06-22T12:30:26+00:00","author":{"@id":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/#\/schema\/person\/f9a7363ddc14a33eef77b520728dbde0"},"breadcrumb":{"@id":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/couplings-for-metropolized-non-reversible-mcmc\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/couplings-for-metropolized-non-reversible-mcmc\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/couplings-for-metropolized-non-reversible-mcmc\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/"},{"@type":"ListItem","position":2,"name":"Couplings for Metropolized Non-Reversible MCMC"}]},{"@type":"WebSite","@id":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/#website","url":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/","name":"Nawaf Bou-Rabee","description":"","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/#\/schema\/person\/f9a7363ddc14a33eef77b520728dbde0","name":"Nawaf Bou-Rabee","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/f3f33e8b5e6e2430997aea3dfec1a454?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/f3f33e8b5e6e2430997aea3dfec1a454?s=96&d=mm&r=g","caption":"Nawaf Bou-Rabee"},"description":"Math Professor at Rutgers","sameAs":["https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/"],"url":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/author\/nb361\/"}]}},"_links":{"self":[{"href":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/wp-json\/wp\/v2\/posts\/731"}],"collection":[{"href":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/wp-json\/wp\/v2\/users\/2614"}],"replies":[{"embeddable":true,"href":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/wp-json\/wp\/v2\/comments?post=731"}],"version-history":[{"count":21,"href":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/wp-json\/wp\/v2\/posts\/731\/revisions"}],"predecessor-version":[{"id":753,"href":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/wp-json\/wp\/v2\/posts\/731\/revisions\/753"}],"wp:attachment":[{"href":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/wp-json\/wp\/v2\/media?parent=731"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/wp-json\/wp\/v2\/categories?post=731"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/wp-json\/wp\/v2\/tags?post=731"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}