{"id":878,"date":"2025-01-31T11:01:22","date_gmt":"2025-01-31T11:01:22","guid":{"rendered":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/?p=878"},"modified":"2025-01-31T15:17:40","modified_gmt":"2025-01-31T15:17:40","slug":"introducing-the-no-underrun-sampler-nurs-a-locally-adaptive-gradient-free-mcmc-method-inspired-by-the-no-u-turn-sampler","status":"publish","type":"post","link":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/introducing-the-no-underrun-sampler-nurs-a-locally-adaptive-gradient-free-mcmc-method-inspired-by-the-no-u-turn-sampler\/","title":{"rendered":"A Locally Adaptive, Gradient-Free MCMC Method Inspired by the No-U-Turn Sampler"},"content":{"rendered":"<p>Markov Chain Monte Carlo (MCMC) methods are fundamental for sampling from complex probability distributions, but many widely used algorithms either rely on gradients (like NUTS) and\/or struggle with high-dimensional, multi-scale distributions. The No-Underrun Sampler (NURS) is a new approach that offers gradient-free, locally adaptive sampling, combining elements of Hit-and-Run and NUTS while remaining straightforward to implement and inherently parallelizable.<\/p>\n<p><strong>What is NURS?<\/strong><\/p>\n<p>NURS is an implementable approximation of Hit-and-Run, a coordinate-free Gibbs sampler that is theoretically powerful but often computationally infeasible.  Like Hit-and-Run, NURS selects random directions uniformly from the unit sphere.  However, to make the method implementable, NURS introduces additional structure in its &#8220;run&#8221; step:<\/p>\n<ul>\n<li> <em>Locally Adaptive Exploration:<\/em> NURS generates a discrete orbit in the chosen direction and dynamically adjusts its length to match the local scale of the target distribution.\n<li> <em>Precise State Selection:<\/em> State selection is guided by exact density evaluations along the orbit using categorical sampling, ensuring that updates align closely with the target\u2019s local geometry.\n<\/ul>\n<p><strong>Why Does NURS Matter?<\/strong><\/p>\n<p>Many MCMC methods struggle with multi-scale distributions, where different regions require vastly different tuning parameters for efficient exploration. A classic example is Neal\u2019s funnel, a well-known benchmark in Bayesian hierarchical inference. Most samplers fail to efficiently traverse both its narrow neck and broad mouth region effectively.<\/p>\n<p>Empirical tests on Neal\u2019s funnel show that while NURS is diffusive in narrow regions, its ballistic movement in broader regions offsets this, enabling efficient sampling across the distribution\u2019s different scales. This behavior enables efficient sampling where many other gradient-free methods fail.<\/p>\n<p><strong>Mathematical Insights<\/strong><\/p>\n<p>Our recent paper provides a rigorous theoretical foundation for NURS, including:<\/p>\n<ul>\n<li> <em>Quantitative Tuning Guidelines:<\/em> NURS comes with clear, principled guidelines for tuning its parameters.\n<li> <em>Connections to Hit-and-Run:<\/em> We formalize how NURS approximates Hit-and-Run while remaining implementable.\n<li> <em>Coupling Results:<\/em> We extend known coupling results from Hit-and-Run to NURS in the Gaussian case, revealing that NURS inherits Hit-and-Run\u2019s potential for fast convergence.\n<\/ul>\n<p><strong>Looking Ahead<\/strong><\/p>\n<p>By providing an implementable approximation to Hit-and-Run, locally adapting to the different scales of the target, offering strong theoretical foundations, and demonstrating practical effectiveness in challenging multi-scale settings, NURS expands the toolkit for gradient-free MCMC methods.  Despite the wide applicability and potential of gradient-free methods &#8212; this area remains relatively underexplored.<\/p>\n<p>If you&#8217;re interested in learning more, feel free to check out the paper <a href=\"https:\/\/arxiv.org\/abs\/2501.18548\">linked here<\/a>\u2014and stay tuned for further developments!  We welcome your thoughts and ideas!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Markov Chain Monte Carlo (MCMC) methods are fundamental for sampling from complex probability distributions, but many widely used algorithms either rely on gradients (like NUTS) and\/or struggle with high-dimensional, multi-scale &hellip; <a href=\"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/introducing-the-no-underrun-sampler-nurs-a-locally-adaptive-gradient-free-mcmc-method-inspired-by-the-no-u-turn-sampler\/\" 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":[8],"tags":[],"class_list":["post-878","post","type-post","status-publish","format-standard","hentry","category-preprints"],"acf":[],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v23.5 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>A Locally Adaptive, Gradient-Free MCMC Method Inspired by the No-U-Turn Sampler - 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\/introducing-the-no-underrun-sampler-nurs-a-locally-adaptive-gradient-free-mcmc-method-inspired-by-the-no-u-turn-sampler\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"A Locally Adaptive, Gradient-Free MCMC Method Inspired by the No-U-Turn Sampler - Nawaf Bou-Rabee\" \/>\n<meta property=\"og:description\" content=\"Markov Chain Monte Carlo (MCMC) methods are fundamental for sampling from complex probability distributions, but many widely used algorithms either rely on gradients (like NUTS) and\/or struggle with high-dimensional, multi-scale &hellip; Read More\" \/>\n<meta property=\"og:url\" content=\"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/introducing-the-no-underrun-sampler-nurs-a-locally-adaptive-gradient-free-mcmc-method-inspired-by-the-no-u-turn-sampler\/\" \/>\n<meta property=\"og:site_name\" content=\"Nawaf Bou-Rabee\" \/>\n<meta property=\"article:published_time\" content=\"2025-01-31T11:01:22+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2025-01-31T15:17:40+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\/introducing-the-no-underrun-sampler-nurs-a-locally-adaptive-gradient-free-mcmc-method-inspired-by-the-no-u-turn-sampler\/\",\"url\":\"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/introducing-the-no-underrun-sampler-nurs-a-locally-adaptive-gradient-free-mcmc-method-inspired-by-the-no-u-turn-sampler\/\",\"name\":\"A Locally Adaptive, Gradient-Free MCMC Method Inspired by the No-U-Turn Sampler - Nawaf Bou-Rabee\",\"isPartOf\":{\"@id\":\"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/#website\"},\"datePublished\":\"2025-01-31T11:01:22+00:00\",\"dateModified\":\"2025-01-31T15:17:40+00:00\",\"author\":{\"@id\":\"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/#\/schema\/person\/f9a7363ddc14a33eef77b520728dbde0\"},\"breadcrumb\":{\"@id\":\"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/introducing-the-no-underrun-sampler-nurs-a-locally-adaptive-gradient-free-mcmc-method-inspired-by-the-no-u-turn-sampler\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/introducing-the-no-underrun-sampler-nurs-a-locally-adaptive-gradient-free-mcmc-method-inspired-by-the-no-u-turn-sampler\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/introducing-the-no-underrun-sampler-nurs-a-locally-adaptive-gradient-free-mcmc-method-inspired-by-the-no-u-turn-sampler\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"A Locally Adaptive, Gradient-Free MCMC Method Inspired by the No-U-Turn Sampler\"}]},{\"@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":"A Locally Adaptive, Gradient-Free MCMC Method Inspired by the No-U-Turn Sampler - 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\/introducing-the-no-underrun-sampler-nurs-a-locally-adaptive-gradient-free-mcmc-method-inspired-by-the-no-u-turn-sampler\/","og_locale":"en_US","og_type":"article","og_title":"A Locally Adaptive, Gradient-Free MCMC Method Inspired by the No-U-Turn Sampler - Nawaf Bou-Rabee","og_description":"Markov Chain Monte Carlo (MCMC) methods are fundamental for sampling from complex probability distributions, but many widely used algorithms either rely on gradients (like NUTS) and\/or struggle with high-dimensional, multi-scale &hellip; Read More","og_url":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/introducing-the-no-underrun-sampler-nurs-a-locally-adaptive-gradient-free-mcmc-method-inspired-by-the-no-u-turn-sampler\/","og_site_name":"Nawaf Bou-Rabee","article_published_time":"2025-01-31T11:01:22+00:00","article_modified_time":"2025-01-31T15:17:40+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\/introducing-the-no-underrun-sampler-nurs-a-locally-adaptive-gradient-free-mcmc-method-inspired-by-the-no-u-turn-sampler\/","url":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/introducing-the-no-underrun-sampler-nurs-a-locally-adaptive-gradient-free-mcmc-method-inspired-by-the-no-u-turn-sampler\/","name":"A Locally Adaptive, Gradient-Free MCMC Method Inspired by the No-U-Turn Sampler - Nawaf Bou-Rabee","isPartOf":{"@id":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/#website"},"datePublished":"2025-01-31T11:01:22+00:00","dateModified":"2025-01-31T15:17:40+00:00","author":{"@id":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/#\/schema\/person\/f9a7363ddc14a33eef77b520728dbde0"},"breadcrumb":{"@id":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/introducing-the-no-underrun-sampler-nurs-a-locally-adaptive-gradient-free-mcmc-method-inspired-by-the-no-u-turn-sampler\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/introducing-the-no-underrun-sampler-nurs-a-locally-adaptive-gradient-free-mcmc-method-inspired-by-the-no-u-turn-sampler\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/introducing-the-no-underrun-sampler-nurs-a-locally-adaptive-gradient-free-mcmc-method-inspired-by-the-no-u-turn-sampler\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/"},{"@type":"ListItem","position":2,"name":"A Locally Adaptive, Gradient-Free MCMC Method Inspired by the No-U-Turn Sampler"}]},{"@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\/878"}],"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=878"}],"version-history":[{"count":6,"href":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/wp-json\/wp\/v2\/posts\/878\/revisions"}],"predecessor-version":[{"id":884,"href":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/wp-json\/wp\/v2\/posts\/878\/revisions\/884"}],"wp:attachment":[{"href":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/wp-json\/wp\/v2\/media?parent=878"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/wp-json\/wp\/v2\/categories?post=878"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sites.rutgers.edu\/nawaf-bou-rabee\/wp-json\/wp\/v2\/tags?post=878"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}