Search | arXiv e-print repository

<!DOCTYPE html> <html lang="en"> <head> <meta charset="utf-8"/> <meta name="viewport" content="width=device-width, initial-scale=1"/>  <link rel="apple-touch-icon" sizes="180x180" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/apple-touch-icon.png"> <link rel="icon" type="image/png" sizes="32x32" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/favicon-32x32.png"> <link rel="icon" type="image/png" sizes="16x16" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/favicon-16x16.png"> <link rel="manifest" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/site.webmanifest"> <link rel="mask-icon" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/safari-pinned-tab.svg" color="#b31b1b"> <link rel="shortcut icon" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/favicon.ico"> <meta name="msapplication-TileColor" content="#b31b1b"> <meta name="msapplication-config" content="images/icons/browserconfig.xml"> <meta name="theme-color" content="#b31b1b">  <title>Search | arXiv e-print repository</title> <script defer src="https://static.arxiv.org/static/base/1.0.0a5/fontawesome-free-5.11.2-web/js/all.js"></script> <link rel="stylesheet" href="https://static.arxiv.org/static/base/1.0.0a5/css/arxivstyle.css" /> <script type="text/x-mathjax-config"> MathJax.Hub.Config({ messageStyle: "none", extensions: ["tex2jax.js"], jax: ["input/TeX", "output/HTML-CSS"], tex2jax: { inlineMath: [ ['$','$'], ["\$","\$"] ], displayMath: [ ['$$','$$'], ["\\[","\\]"] ], processEscapes: true, ignoreClass: '.*', processClass: 'mathjax.*' }, TeX: { extensions: ["AMSmath.js", "AMSsymbols.js", "noErrors.js"], noErrors: { inlineDelimiters: ["$","$"], multiLine: false, style: { "font-size": "normal", "border": "" } } }, "HTML-CSS": { availableFonts: ["TeX"] } }); </script> <script src='//static.arxiv.org/MathJax-2.7.3/MathJax.js'></script> <script src="https://static.arxiv.org/static/base/1.0.0a5/js/notification.js"></script> <link rel="stylesheet" href="https://static.arxiv.org/static/search/0.5.6/css/bulma-tooltip.min.css" /> <link rel="stylesheet" href="https://static.arxiv.org/static/search/0.5.6/css/search.css" /> <script src="https://code.jquery.com/jquery-3.2.1.slim.min.js" integrity="sha256-k2WSCIexGzOj3Euiig+TlR8gA0EmPjuc79OEeY5L45g=" crossorigin="anonymous"></script> <script src="https://static.arxiv.org/static/search/0.5.6/js/fieldset.js"></script> <style> radio#cf-customfield_11400 { display: none; } </style> </head> <body> <header><a href="#main-container" class="is-sr-only">Skip to main content</a>  <div class="attribution level is-marginless" role="banner"> <div class="level-left"> <a class="level-item" href="https://cornell.edu/"><img src="https://static.arxiv.org/static/base/1.0.0a5/images/cornell-reduced-white-SMALL.svg" alt="Cornell University" width="200" aria-label="logo" /></a> </div> <div class="level-right is-marginless"><p class="sponsors level-item is-marginless"><span id="support-ack-url">We gratefully acknowledge support from<br /> the Simons Foundation, <a href="https://info.arxiv.org/about/ourmembers.html">member institutions</a>, and all contributors. <a href="https://info.arxiv.org/about/donate.html">Donate</a></span></p></div> </div>  <div class="identity level is-marginless"> <div class="level-left"> <div class="level-item"> <a class="arxiv" href="https://arxiv.org/" aria-label="arxiv-logo"> <img src="https://static.arxiv.org/static/base/1.0.0a5/images/arxiv-logo-one-color-white.svg" aria-label="logo" alt="arxiv logo" width="85" style="width:85px;"/> </a> </div> </div> <div class="search-block level-right"> <form class="level-item mini-search" method="GET" action="https://arxiv.org/search"> <div class="field has-addons"> <div class="control"> <input class="input is-small" type="text" name="query" placeholder="Search..." aria-label="Search term or terms" /> <p class="help"><a href="https://info.arxiv.org/help">Help</a> | <a href="https://arxiv.org/search/advanced">Advanced Search</a></p> </div> <div class="control"> <div class="select is-small"> <select name="searchtype" aria-label="Field to search"> <option value="all" selected="selected">All fields</option> <option value="title">Title</option> <option value="author">Author</option> <option value="abstract">Abstract</option> <option value="comments">Comments</option> <option value="journal_ref">Journal reference</option> <option value="acm_class">ACM classification</option> <option value="msc_class">MSC classification</option> <option value="report_num">Report number</option> <option value="paper_id">arXiv identifier</option> <option value="doi">DOI</option> <option value="orcid">ORCID</option> <option value="author_id">arXiv author ID</option> <option value="help">Help pages</option> <option value="full_text">Full text</option> </select> </div> </div> <input type="hidden" name="source" value="header"> <button class="button is-small is-cul-darker">Search</button> </div> </form> </div> </div>  <div class="container"> <div class="user-tools is-size-7 has-text-right has-text-weight-bold" role="navigation" aria-label="User menu"> <a href="https://arxiv.org/login">Login</a> </div> </div> </header> <main class="container" id="main-container"> <div class="level is-marginless"> <div class="level-left"> <h1 class="title is-clearfix"> Showing 1–50 of 143 results for author: <span class="mathjax">Ramdas, A</span> </h1> </div> <div class="level-right is-hidden-mobile">  <span class="help" style="display: inline-block;"><a href="https://github.com/arXiv/arxiv-search/releases">Search v0.5.6 released 2020-02-24</a>  </span> </div> </div> <div class="content"> <form method="GET" action="/search/stat" aria-role="search"> Searching in archive <strong>stat</strong>. <a href="/search/?searchtype=author&query=Ramdas%2C+A">Search in all archives.</a> <div class="field has-addons-tablet"> <div class="control is-expanded"> <label for="query" class="hidden-label">Search term or terms</label> <input class="input is-medium" id="query" name="query" placeholder="Search term..." type="text" value="Ramdas, A"> </div> <div class="select control is-medium"> <label class="is-hidden" for="searchtype">Field</label> <select class="is-medium" id="searchtype" name="searchtype"><option value="all">All fields</option><option value="title">Title</option><option selected value="author">Author(s)</option><option value="abstract">Abstract</option><option value="comments">Comments</option><option value="journal_ref">Journal reference</option><option value="acm_class">ACM classification</option><option value="msc_class">MSC classification</option><option value="report_num">Report number</option><option value="paper_id">arXiv identifier</option><option value="doi">DOI</option><option value="orcid">ORCID</option><option value="license">License (URI)</option><option value="author_id">arXiv author ID</option><option value="help">Help pages</option><option value="full_text">Full text</option></select> </div> <div class="control"> <button class="button is-link is-medium">Search</button> </div> </div> <div class="field"> <div class="control is-size-7"> <label class="radio"> <input checked id="abstracts-0" name="abstracts" type="radio" value="show"> Show abstracts </label> <label class="radio"> <input id="abstracts-1" name="abstracts" type="radio" value="hide"> Hide abstracts </label> </div> </div> <div class="is-clearfix" style="height: 2.5em"> <div class="is-pulled-right"> <a href="/search/advanced?terms-0-term=Ramdas%2C+A&terms-0-field=author&size=50&order=-announced_date_first">Advanced Search</a> </div> </div> <input type="hidden" name="order" value="-announced_date_first"> <input type="hidden" name="size" value="50"> </form> <div class="level breathe-horizontal"> <div class="level-left"> <form method="GET" action="/search/"> <div style="display: none;"> <select id="searchtype" name="searchtype"><option value="all">All fields</option><option value="title">Title</option><option selected value="author">Author(s)</option><option value="abstract">Abstract</option><option value="comments">Comments</option><option value="journal_ref">Journal reference</option><option value="acm_class">ACM classification</option><option value="msc_class">MSC classification</option><option value="report_num">Report number</option><option value="paper_id">arXiv identifier</option><option value="doi">DOI</option><option value="orcid">ORCID</option><option value="license">License (URI)</option><option value="author_id">arXiv author ID</option><option value="help">Help pages</option><option value="full_text">Full text</option></select> <input id="query" name="query" type="text" value="Ramdas, A"> <ul id="abstracts"><li><input checked id="abstracts-0" name="abstracts" type="radio" value="show"> <label for="abstracts-0">Show abstracts</label></li><li><input id="abstracts-1" name="abstracts" type="radio" value="hide"> <label for="abstracts-1">Hide abstracts</label></li></ul> </div> <div class="box field is-grouped is-grouped-multiline level-item"> <div class="control"> <span class="select is-small"> <select id="size" name="size"><option value="25">25</option><option selected value="50">50</option><option value="100">100</option><option value="200">200</option></select> </span> <label for="size">results per page</label>. </div> <div class="control"> <label for="order">Sort results by</label> <span class="select is-small"> <select id="order" name="order"><option selected value="-announced_date_first">Announcement date (newest first)</option><option value="announced_date_first">Announcement date (oldest first)</option><option value="-submitted_date">Submission date (newest first)</option><option value="submitted_date">Submission date (oldest first)</option><option value="">Relevance</option></select> </span> </div> <div class="control"> <button class="button is-small is-link">Go</button> </div> </div> </form> </div> </div> <nav class="pagination is-small is-centered breathe-horizontal" role="navigation" aria-label="pagination"> <a href="" class="pagination-previous is-invisible">Previous </a> <a href="/search/?searchtype=author&query=Ramdas%2C+A&start=50" class="pagination-next" >Next </a> <ul class="pagination-list"> <li> <a href="/search/?searchtype=author&query=Ramdas%2C+A&start=0" class="pagination-link is-current" aria-label="Goto page 1">1 </a> </li> <li> <a href="/search/?searchtype=author&query=Ramdas%2C+A&start=50" class="pagination-link " aria-label="Page 2" aria-current="page">2 </a> </li> <li> <a href="/search/?searchtype=author&query=Ramdas%2C+A&start=100" class="pagination-link " aria-label="Page 3" aria-current="page">3 </a> </li> </ul> </nav> <ol class="breathe-horizontal" start="1"> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2411.14341">arXiv:2411.14341</a> <span> [<a href="https://arxiv.org/pdf/2411.14341">pdf</a>, <a href="https://arxiv.org/format/2411.14341">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> </div> </div> <p class="title is-5 mathjax"> Logarithmic Neyman Regret for Adaptive Estimation of the Average Treatment Effect </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Neopane%2C+O">Ojash Neopane</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a>, <a href="/search/stat?searchtype=author&query=Singh%2C+A">Aarti Singh</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2411.14341v1-abstract-short" style="display: inline;"> Estimation of the Average Treatment Effect (ATE) is a core problem in causal inference with strong connections to Off-Policy Evaluation in Reinforcement Learning. This paper considers the problem of adaptively selecting the treatment allocation probability in order to improve estimation of the ATE. The majority of prior work on adaptive ATE estimation focus on asymptotic guarantees, and in turn ov… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2411.14341v1-abstract-full').style.display = 'inline'; document.getElementById('2411.14341v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2411.14341v1-abstract-full" style="display: none;"> Estimation of the Average Treatment Effect (ATE) is a core problem in causal inference with strong connections to Off-Policy Evaluation in Reinforcement Learning. This paper considers the problem of adaptively selecting the treatment allocation probability in order to improve estimation of the ATE. The majority of prior work on adaptive ATE estimation focus on asymptotic guarantees, and in turn overlooks important practical considerations such as the difficulty of learning the optimal treatment allocation as well as hyper-parameter selection. Existing non-asymptotic methods are limited by poor empirical performance and exponential scaling of the Neyman regret with respect to problem parameters. In order to address these gaps, we propose and analyze the Clipped Second Moment Tracking (ClipSMT) algorithm, a variant of an existing algorithm with strong asymptotic optimality guarantees, and provide finite sample bounds on its Neyman regret. Our analysis shows that ClipSMT achieves exponential improvements in Neyman regret on two fronts: improving the dependence on $T$ from $O(\sqrt{T})$ to $O(\log T)$, as well as reducing the exponential dependence on problem parameters to a polynomial dependence. Finally, we conclude with simulations which show the marked improvement of ClipSMT over existing approaches. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2411.14341v1-abstract-full').style.display = 'none'; document.getElementById('2411.14341v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 21 November, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2024. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">12 pages, 2 figures. Submitted to AISTATS 2025</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2411.11271">arXiv:2411.11271</a> <span> [<a href="https://arxiv.org/pdf/2411.11271">pdf</a>, <a href="https://arxiv.org/format/2411.11271">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Statistics Theory">math.ST</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Probability">math.PR</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> </div> </div> <p class="title is-5 mathjax"> Mean Estimation in Banach Spaces Under Infinite Variance and Martingale Dependence </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Whitehouse%2C+J">Justin Whitehouse</a>, <a href="/search/stat?searchtype=author&query=Chugg%2C+B">Ben Chugg</a>, <a href="/search/stat?searchtype=author&query=Martinez-Taboada%2C+D">Diego Martinez-Taboada</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2411.11271v1-abstract-short" style="display: inline;"> We consider estimating the shared mean of a sequence of heavy-tailed random variables taking values in a Banach space. In particular, we revisit and extend a simple truncation-based mean estimator by Catoni and Giulini. While existing truncation-based approaches require a bound on the raw (non-central) second moment of observations, our results hold under a bound on either the central or non-centr… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2411.11271v1-abstract-full').style.display = 'inline'; document.getElementById('2411.11271v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2411.11271v1-abstract-full" style="display: none;"> We consider estimating the shared mean of a sequence of heavy-tailed random variables taking values in a Banach space. In particular, we revisit and extend a simple truncation-based mean estimator by Catoni and Giulini. While existing truncation-based approaches require a bound on the raw (non-central) second moment of observations, our results hold under a bound on either the central or non-central $p$th moment for some $p > 1$. In particular, our results hold for distributions with infinite variance. The main contributions of the paper follow from exploiting connections between truncation-based mean estimation and the concentration of martingales in 2-smooth Banach spaces. We prove two types of time-uniform bounds on the distance between the estimator and unknown mean: line-crossing inequalities, which can be optimized for a fixed sample size $n$, and non-asymptotic law of the iterated logarithm type inequalities, which match the tightness of line-crossing inequalities at all points in time up to a doubly logarithmic factor in $n$. Our results do not depend on the dimension of the Banach space, hold under martingale dependence, and all constants in the inequalities are known and small. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2411.11271v1-abstract-full').style.display = 'none'; document.getElementById('2411.11271v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 17 November, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2024. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">26 pages, 2 figures</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2411.09516">arXiv:2411.09516</a> <span> [<a href="https://arxiv.org/pdf/2411.09516">pdf</a>, <a href="https://arxiv.org/ps/2411.09516">ps</a>, <a href="https://arxiv.org/format/2411.09516">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Probability">math.PR</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Functional Analysis">math.FA</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Statistics Theory">math.ST</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> </div> </div> <p class="title is-5 mathjax"> Sharp Matrix Empirical Bernstein Inequalities </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Wang%2C+H">Hongjian Wang</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2411.09516v1-abstract-short" style="display: inline;"> We present two sharp empirical Bernstein inequalities for symmetric random matrices with bounded eigenvalues. By sharp, we mean that both inequalities adapt to the unknown variance in a tight manner: the deviation captured by the first-order $1/\sqrt{n}$ term asymptotically matches the matrix Bernstein inequality exactly, including constants, the latter requiring knowledge of the variance. Our fir… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2411.09516v1-abstract-full').style.display = 'inline'; document.getElementById('2411.09516v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2411.09516v1-abstract-full" style="display: none;"> We present two sharp empirical Bernstein inequalities for symmetric random matrices with bounded eigenvalues. By sharp, we mean that both inequalities adapt to the unknown variance in a tight manner: the deviation captured by the first-order $1/\sqrt{n}$ term asymptotically matches the matrix Bernstein inequality exactly, including constants, the latter requiring knowledge of the variance. Our first inequality holds for the sample mean of independent matrices, and our second inequality holds for a mean estimator under martingale dependence at stopping times. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2411.09516v1-abstract-full').style.display = 'none'; document.getElementById('2411.09516v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 14 November, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2024. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2410.23614">arXiv:2410.23614</a> <span> [<a href="https://arxiv.org/pdf/2410.23614">pdf</a>, <a href="https://arxiv.org/format/2410.23614">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Statistics Theory">math.ST</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> </div> </div> <p class="title is-5 mathjax"> Hypothesis testing with e-values </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a>, <a href="/search/stat?searchtype=author&query=Wang%2C+R">Ruodu Wang</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2410.23614v2-abstract-short" style="display: inline;"> This book is written to offer a humble, but unified, treatment of e-values in hypothesis testing. The book is organized into three parts: Fundamental Concepts, Core Ideas, and Advanced Topics. The first part includes three chapters that introduce the basic concepts. The second part includes five chapters of core ideas such as universal inference, log-optimality, e-processes, operations on e-values… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2410.23614v2-abstract-full').style.display = 'inline'; document.getElementById('2410.23614v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2410.23614v2-abstract-full" style="display: none;"> This book is written to offer a humble, but unified, treatment of e-values in hypothesis testing. The book is organized into three parts: Fundamental Concepts, Core Ideas, and Advanced Topics. The first part includes three chapters that introduce the basic concepts. The second part includes five chapters of core ideas such as universal inference, log-optimality, e-processes, operations on e-values, and e-values in multiple testing. The third part contains five chapters of advanced topics. We hope that, by putting the materials together in this book, the concept of e-values becomes more accessible for educational, research, and practical use. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2410.23614v2-abstract-full').style.display = 'none'; document.getElementById('2410.23614v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 13 November, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 30 October, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2024. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2410.16076">arXiv:2410.16076</a> <span> [<a href="https://arxiv.org/pdf/2410.16076">pdf</a>, <a href="https://arxiv.org/format/2410.16076">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> </div> </div> <p class="title is-5 mathjax"> Improving the (approximate) sequential probability ratio test by avoiding overshoot </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Fischer%2C+L">Lasse Fischer</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2410.16076v2-abstract-short" style="display: inline;"> The sequential probability ratio test (SPRT) by Wald (1945) is a cornerstone of sequential analysis. Based on desired type-I, II error levels $伪, 尾\in (0,1)$, it stops when the likelihood ratio statistic crosses certain upper and lower thresholds, guaranteeing optimality of the expected sample size. However, these thresholds are not closed form and the test is often applied with approximate thresh… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2410.16076v2-abstract-full').style.display = 'inline'; document.getElementById('2410.16076v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2410.16076v2-abstract-full" style="display: none;"> The sequential probability ratio test (SPRT) by Wald (1945) is a cornerstone of sequential analysis. Based on desired type-I, II error levels $伪, 尾\in (0,1)$, it stops when the likelihood ratio statistic crosses certain upper and lower thresholds, guaranteeing optimality of the expected sample size. However, these thresholds are not closed form and the test is often applied with approximate thresholds $(1-尾)/伪$ and $尾/(1-伪)$ (approximate SPRT). When $尾> 0$, this neither guarantees type I,II error control at $伪,尾$ nor optimality. When $尾=0$ (power-one SPRT), it guarantees type I error control at $伪$ that is in general conservative, and thus not optimal. The looseness in both cases is caused by overshoot: the test statistic overshoots the thresholds at the stopping time. One standard way to address this is to calculate the right thresholds numerically, but many papers and software packages do not do this. In this paper, we describe a different way to improve the approximate SPRT: we change the test statistic to avoid overshoot. Our technique uniformly improves power-one SPRTs $(尾=0)$ for simple nulls and alternatives, or for one-sided nulls and alternatives in exponential families. When $尾> 0$, our techniques provide valid type I and type II error guarantees, while needing less samples than Wald's approximated thresholds in all considered simulations. These improved sequential tests can also be used for deriving tighter parametric confidence sequences, and can be extended to nontrivial settings like sampling without replacement and conformal martingales. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2410.16076v2-abstract-full').style.display = 'none'; document.getElementById('2410.16076v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 6 November, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 21 October, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2024. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">23 pages, 7 figures</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2409.19812">arXiv:2409.19812</a> <span> [<a href="https://arxiv.org/pdf/2409.19812">pdf</a>, <a href="https://arxiv.org/ps/2409.19812">ps</a>, <a href="https://arxiv.org/format/2409.19812">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> </div> </div> <p class="title is-5 mathjax"> Compound e-values and empirical Bayes </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Ignatiadis%2C+N">Nikolaos Ignatiadis</a>, <a href="/search/stat?searchtype=author&query=Wang%2C+R">Ruodu Wang</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2409.19812v1-abstract-short" style="display: inline;"> We explicitly define the notion of (exact or approximate) compound e-values which have been implicitly presented and extensively used in the recent multiple testing literature. We show that every FDR controlling procedure can be recovered by instantiating the e-BH procedure with certain compound e-values. Since compound e-values are closed under averaging, this allows for combination and derandomi… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2409.19812v1-abstract-full').style.display = 'inline'; document.getElementById('2409.19812v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2409.19812v1-abstract-full" style="display: none;"> We explicitly define the notion of (exact or approximate) compound e-values which have been implicitly presented and extensively used in the recent multiple testing literature. We show that every FDR controlling procedure can be recovered by instantiating the e-BH procedure with certain compound e-values. Since compound e-values are closed under averaging, this allows for combination and derandomization of any FDR procedure. We then point out and exploit the connections to empirical Bayes. In particular, we use the fundamental theorem of compound decision theory to derive the log-optimal simple separable compound e-value for testing a set of point nulls against point alternatives: it is a ratio of mixture likelihoods. We extend universal inference to the compound setting. As one example, we construct approximate compound e-values for multiple t-tests, where the (nuisance) variances may be different across hypotheses. We provide connections to related notions in the literature stated in terms of p-values. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2409.19812v1-abstract-full').style.display = 'none'; document.getElementById('2409.19812v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 29 September, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2024. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2409.17505">arXiv:2409.17505</a> <span> [<a href="https://arxiv.org/pdf/2409.17505">pdf</a>, <a href="https://arxiv.org/format/2409.17505">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> </div> </div> <p class="title is-5 mathjax"> Sequential Kernelized Stein Discrepancy </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Martinez-Taboada%2C+D">Diego Martinez-Taboada</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2409.17505v1-abstract-short" style="display: inline;"> We present a sequential version of the kernelized Stein discrepancy, which allows for conducting goodness-of-fit tests for unnormalized densities that are continuously monitored and adaptively stopped. That is, the sample size need not be fixed prior to data collection; the practitioner can choose whether to stop the test or continue to gather evidence at any time while controlling the false disco… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2409.17505v1-abstract-full').style.display = 'inline'; document.getElementById('2409.17505v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2409.17505v1-abstract-full" style="display: none;"> We present a sequential version of the kernelized Stein discrepancy, which allows for conducting goodness-of-fit tests for unnormalized densities that are continuously monitored and adaptively stopped. That is, the sample size need not be fixed prior to data collection; the practitioner can choose whether to stop the test or continue to gather evidence at any time while controlling the false discovery rate. In stark contrast to related literature, we do not impose uniform boundedness on the Stein kernel. Instead, we exploit the potential boundedness of the Stein kernel at arbitrary point evaluations to define test martingales, that give way to the subsequent novel sequential tests. We prove the validity of the test, as well as an asymptotic lower bound for the logarithmic growth of the wealth process under the alternative. We further illustrate the empirical performance of the test with a variety of distributions, including restricted Boltzmann machines. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2409.17505v1-abstract-full').style.display = 'none'; document.getElementById('2409.17505v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 25 September, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2024. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2408.14015">arXiv:2408.14015</a> <span> [<a href="https://arxiv.org/pdf/2408.14015">pdf</a>, <a href="https://arxiv.org/format/2408.14015">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> </div> </div> <p class="title is-5 mathjax"> Robust likelihood ratio tests for composite nulls and alternatives </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Saha%2C+A">Aytijhya Saha</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2408.14015v2-abstract-short" style="display: inline;"> We propose an e-value based framework for testing composite nulls against composite alternatives when an $蔚$ fraction of the data can be arbitrarily corrupted. Our tests are inherently sequential, being valid at arbitrary data-dependent stopping times, but they are new even for fixed sample sizes, giving type-I error control without any regularity conditions. We achieve this by modifying and exten… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2408.14015v2-abstract-full').style.display = 'inline'; document.getElementById('2408.14015v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2408.14015v2-abstract-full" style="display: none;"> We propose an e-value based framework for testing composite nulls against composite alternatives when an $蔚$ fraction of the data can be arbitrarily corrupted. Our tests are inherently sequential, being valid at arbitrary data-dependent stopping times, but they are new even for fixed sample sizes, giving type-I error control without any regularity conditions. We achieve this by modifying and extending a proposal by Huber (1965) in the point null versus point alternative case. Our test statistic is a nonnegative supermartingale under the null, even with a sequentially adaptive contamination model where the conditional distribution of each observation given the past data lies within an $蔚$ (total variation) ball of the null. The test is powerful within an $蔚$ ball of the alternative. As a consequence, one obtains anytime-valid p-values that enable continuous monitoring of the data, and adaptive stopping. We analyze the growth rate of our test supermartingale and demonstrate that as $蔚\to 0$, it approaches a certain Kullback-Leibler divergence between the null and alternative, which is the optimal non-robust growth rate. A key step is the derivation of a robust Reverse Information Projection (RIPr). Simulations validate the theory and demonstrate excellent practical performance. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2408.14015v2-abstract-full').style.display = 'none'; document.getElementById('2408.14015v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 25 September, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 26 August, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> August 2024. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2408.09598">arXiv:2408.09598</a> <span> [<a href="https://arxiv.org/pdf/2408.09598">pdf</a>, <a href="https://arxiv.org/format/2408.09598">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Econometrics">econ.EM</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Statistics Theory">math.ST</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> </div> </div> <p class="title is-5 mathjax"> Anytime-Valid Inference for Double/Debiased Machine Learning of Causal Parameters </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Dalal%2C+A">Abhinandan Dalal</a>, <a href="/search/stat?searchtype=author&query=Bl%C3%B6baum%2C+P">Patrick Bl枚baum</a>, <a href="/search/stat?searchtype=author&query=Kasiviswanathan%2C+S">Shiva Kasiviswanathan</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2408.09598v2-abstract-short" style="display: inline;"> Double (debiased) machine learning (DML) has seen widespread use in recent years for learning causal/structural parameters, in part due to its flexibility and adaptability to high-dimensional nuisance functions as well as its ability to avoid bias from regularization or overfitting. However, the classic double-debiased framework is only valid asymptotically for a predetermined sample size, thus la… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2408.09598v2-abstract-full').style.display = 'inline'; document.getElementById('2408.09598v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2408.09598v2-abstract-full" style="display: none;"> Double (debiased) machine learning (DML) has seen widespread use in recent years for learning causal/structural parameters, in part due to its flexibility and adaptability to high-dimensional nuisance functions as well as its ability to avoid bias from regularization or overfitting. However, the classic double-debiased framework is only valid asymptotically for a predetermined sample size, thus lacking the flexibility of collecting more data if sharper inference is needed, or stopping data collection early if useful inferences can be made earlier than expected. This can be of particular concern in large scale experimental studies with huge financial costs or human lives at stake, as well as in observational studies where the length of confidence of intervals do not shrink to zero even with increasing sample size due to partial identifiability of a structural parameter. In this paper, we present time-uniform counterparts to the asymptotic DML results, enabling valid inference and confidence intervals for structural parameters to be constructed at any arbitrary (possibly data-dependent) stopping time. We provide conditions which are only slightly stronger than the standard DML conditions, but offer the stronger guarantee for anytime-valid inference. This facilitates the transformation of any existing DML method to provide anytime-valid guarantees with minimal modifications, making it highly adaptable and easy to use. We illustrate our procedure using two instances: a) local average treatment effect in online experiments with non-compliance, and b) partial identification of average treatment effect in observational studies with potential unmeasured confounding. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2408.09598v2-abstract-full').style.display = 'none'; document.getElementById('2408.09598v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 10 September, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 18 August, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> August 2024. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2407.20683">arXiv:2407.20683</a> <span> [<a href="https://arxiv.org/pdf/2407.20683">pdf</a>, <a href="https://arxiv.org/format/2407.20683">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> </div> </div> <p class="title is-5 mathjax"> Online generalizations of the e-BH and BH procedure </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Fischer%2C+L">Lasse Fischer</a>, <a href="/search/stat?searchtype=author&query=Xu%2C+Z">Ziyu Xu</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2407.20683v2-abstract-short" style="display: inline;"> In online multiple testing, the hypotheses arrive one by one, and at each time we must immediately reject or accept the current hypothesis solely based on the data and hypotheses observed so far. Many procedures have been proposed, but none of them are online generalizations of the Benjamini-Hochberg (BH) procedure based on p-values, or of the e-BH procedures that uses e-values. In this paper, we… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2407.20683v2-abstract-full').style.display = 'inline'; document.getElementById('2407.20683v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2407.20683v2-abstract-full" style="display: none;"> In online multiple testing, the hypotheses arrive one by one, and at each time we must immediately reject or accept the current hypothesis solely based on the data and hypotheses observed so far. Many procedures have been proposed, but none of them are online generalizations of the Benjamini-Hochberg (BH) procedure based on p-values, or of the e-BH procedures that uses e-values. In this paper, we consider a relaxed problem setup that allows the current hypothesis to be rejected at any later step. We show that this relaxation allows us to define -- what we justify extensively to be -- the natural and appropriate online extension of the BH and e-BH procedures. Analogous to e-BH, online e-BH controls the FDR under arbitrary dependence (even at stopping times). Like for e-BH, we show how to boost the power of online e-BH under other dependence assumptions like positive or local dependence. BH and online BH have identical FDR guarantees at fixed times under positive, negative or arbitrary dependence. Further, we prove that online BH has a slightly inflated FDR control at data-adaptive stopping times under weak positive and negative dependence. Based on the same proof techniques, we prove that numerous existing online procedures, which were previously only known to control the FDR at fixed times, also control the FDR at stopping times. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2407.20683v2-abstract-full').style.display = 'none'; document.getElementById('2407.20683v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 26 September, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 30 July, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2024. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">27 pages, 4 figures</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2407.15733">arXiv:2407.15733</a> <span> [<a href="https://arxiv.org/pdf/2407.15733">pdf</a>, <a href="https://arxiv.org/format/2407.15733">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> </div> </div> <p class="title is-5 mathjax"> Online closed testing with e-values </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Fischer%2C+L">Lasse Fischer</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2407.15733v1-abstract-short" style="display: inline;"> In contemporary research, data scientists often test an infinite sequence of hypotheses $H_1,H_2,\ldots $ one by one, and are required to make real-time decisions without knowing the future hypotheses or data. In this paper, we consider such an online multiple testing problem with the goal of providing simultaneous lower bounds for the number of true discoveries in data-adaptively chosen rejection… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2407.15733v1-abstract-full').style.display = 'inline'; document.getElementById('2407.15733v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2407.15733v1-abstract-full" style="display: none;"> In contemporary research, data scientists often test an infinite sequence of hypotheses $H_1,H_2,\ldots $ one by one, and are required to make real-time decisions without knowing the future hypotheses or data. In this paper, we consider such an online multiple testing problem with the goal of providing simultaneous lower bounds for the number of true discoveries in data-adaptively chosen rejection sets. Using the (online) closure principle, we show that for this task it is necessary to use an anytime-valid test for each intersection hypothesis. Motivated by this result, we construct a new online closed testing procedure and a corresponding short-cut with a true discovery guarantee based on multiplying sequential e-values. This general but simple procedure gives uniform improvements over existing methods but also allows to construct entirely new and powerful procedures. In addition, we introduce new ideas for hedging and boosting of sequential e-values that provably increase power. Finally, we also propose the first online true discovery procedure for arbitrarily dependent e-values. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2407.15733v1-abstract-full').style.display = 'none'; document.getElementById('2407.15733v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 22 July, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2024. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">26 pages, 4 figures</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2407.11465">arXiv:2407.11465</a> <span> [<a href="https://arxiv.org/pdf/2407.11465">pdf</a>, <a href="https://arxiv.org/ps/2407.11465">ps</a>, <a href="https://arxiv.org/format/2407.11465">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Statistics Theory">math.ST</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Probability">math.PR</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Mathematical Finance">q-fin.MF</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> </div> </div> <p class="title is-5 mathjax"> Testing by Betting while Borrowing and Bargaining </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Wang%2C+H">Hongjian Wang</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2407.11465v1-abstract-short" style="display: inline;"> Testing by betting has been a cornerstone of the game-theoretic statistics literature. In this framework, a betting score (or more generally an e-process), as opposed to a traditional p-value, is used to quantify the evidence against a null hypothesis: the higher the betting score, the more money one has made betting against the null, and thus the larger the evidence that the null is false. A key… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2407.11465v1-abstract-full').style.display = 'inline'; document.getElementById('2407.11465v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2407.11465v1-abstract-full" style="display: none;"> Testing by betting has been a cornerstone of the game-theoretic statistics literature. In this framework, a betting score (or more generally an e-process), as opposed to a traditional p-value, is used to quantify the evidence against a null hypothesis: the higher the betting score, the more money one has made betting against the null, and thus the larger the evidence that the null is false. A key ingredient assumed throughout past works is that one cannot bet more money than one currently has. In this paper, we ask what happens if the bettor is allowed to borrow money after going bankrupt, allowing further financial flexibility in this game of hypothesis testing. We propose various definitions of (adjusted) evidence relative to the wealth borrowed, indebted, and accumulated. We also ask what happens if the bettor can "bargain", in order to obtain odds bettor than specified by the null hypothesis. The adjustment of wealth in order to serve as evidence appeals to the characterization of arbitrage, interest rates, and num茅raire-adjusted pricing in this setting. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2407.11465v1-abstract-full').style.display = 'none'; document.getElementById('2407.11465v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 16 July, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2024. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2404.15586">arXiv:2404.15586</a> <span> [<a href="https://arxiv.org/pdf/2404.15586">pdf</a>, <a href="https://arxiv.org/format/2404.15586">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> </div> </div> <p class="title is-5 mathjax"> Multiple testing with anytime-valid Monte-Carlo p-values </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Fischer%2C+L">Lasse Fischer</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2404.15586v2-abstract-short" style="display: inline;"> In contemporary problems involving genetic or neuroimaging data, thousands of hypotheses need to be tested. Due to their high power, and finite sample guarantees on type-1 error under weak assumptions, Monte-Carlo permutation tests are often considered as gold standard for these settings. However, the enormous computational effort required for (thousands of) permutation tests is a major burden. Re… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2404.15586v2-abstract-full').style.display = 'inline'; document.getElementById('2404.15586v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2404.15586v2-abstract-full" style="display: none;"> In contemporary problems involving genetic or neuroimaging data, thousands of hypotheses need to be tested. Due to their high power, and finite sample guarantees on type-1 error under weak assumptions, Monte-Carlo permutation tests are often considered as gold standard for these settings. However, the enormous computational effort required for (thousands of) permutation tests is a major burden. Recently, Fischer and Ramdas (2024) constructed a permutation test for a single hypothesis in which the permutations are drawn sequentially one-by-one and the testing process can be stopped at any point without inflating the type I error. They showed that the number of permutations can be substantially reduced (under null and alternative) while the power remains similar. We show how their approach can be modified to make it suitable for a broad class of multiple testing procedures. In particular, we discuss its use with the Benjamini-Hochberg procedure and illustrate the application on a large dataset. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2404.15586v2-abstract-full').style.display = 'none'; document.getElementById('2404.15586v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 14 July, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 23 April, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2024. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">22 pages, 3 figures</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2403.15527">arXiv:2403.15527</a> <span> [<a href="https://arxiv.org/pdf/2403.15527">pdf</a>, <a href="https://arxiv.org/format/2403.15527">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> </div> </div> <p class="title is-5 mathjax"> Conformal online model aggregation </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Gasparin%2C+M">Matteo Gasparin</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2403.15527v2-abstract-short" style="display: inline;"> Conformal prediction equips machine learning models with a reasonable notion of uncertainty quantification without making strong distributional assumptions. It wraps around any black-box prediction model and converts point predictions into set predictions that have a predefined marginal coverage guarantee. However, conformal prediction only works if we fix the underlying machine learning model in… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2403.15527v2-abstract-full').style.display = 'inline'; document.getElementById('2403.15527v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2403.15527v2-abstract-full" style="display: none;"> Conformal prediction equips machine learning models with a reasonable notion of uncertainty quantification without making strong distributional assumptions. It wraps around any black-box prediction model and converts point predictions into set predictions that have a predefined marginal coverage guarantee. However, conformal prediction only works if we fix the underlying machine learning model in advance. A relatively unaddressed issue in conformal prediction is that of model selection and/or aggregation: for a given problem, which of the plethora of prediction methods (random forests, neural nets, regularized linear models, etc.) should we conformalize? This paper proposes a new approach towards conformal model aggregation in online settings that is based on combining the prediction sets from several algorithms by voting, where weights on the models are adapted over time based on past performance. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2403.15527v2-abstract-full').style.display = 'none'; document.getElementById('2403.15527v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 2 May, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 22 March, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> March 2024. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">22 pages, 12 figures. arXiv admin note: text overlap with arXiv:2401.09379</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2402.18810">arXiv:2402.18810</a> <span> [<a href="https://arxiv.org/pdf/2402.18810">pdf</a>, <a href="https://arxiv.org/ps/2402.18810">ps</a>, <a href="https://arxiv.org/format/2402.18810">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Statistics Theory">math.ST</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> </div> </div> <p class="title is-5 mathjax"> The numeraire e-variable and reverse information projection </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Larsson%2C+M">Martin Larsson</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a>, <a href="/search/stat?searchtype=author&query=Ruf%2C+J">Johannes Ruf</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2402.18810v3-abstract-short" style="display: inline;"> We consider testing a composite null hypothesis $\mathcal{P}$ against a point alternative $\mathsf{Q}$ using e-variables, which are nonnegative random variables $X$ such that $\mathbb{E}_\mathsf{P}[X] \leq 1$ for every $\mathsf{P} \in \mathcal{P}$. This paper establishes a fundamental result: under no conditions whatsoever on $\mathcal{P}$ or $\mathsf{Q}$, there exists a special e-variable $X^*$ t… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2402.18810v3-abstract-full').style.display = 'inline'; document.getElementById('2402.18810v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2402.18810v3-abstract-full" style="display: none;"> We consider testing a composite null hypothesis $\mathcal{P}$ against a point alternative $\mathsf{Q}$ using e-variables, which are nonnegative random variables $X$ such that $\mathbb{E}_\mathsf{P}[X] \leq 1$ for every $\mathsf{P} \in \mathcal{P}$. This paper establishes a fundamental result: under no conditions whatsoever on $\mathcal{P}$ or $\mathsf{Q}$, there exists a special e-variable $X^*$ that we call the numeraire, which is strictly positive and satisfies $\mathbb{E}_\mathsf{Q}[X/X^*] \leq 1$ for every other e-variable $X$. In particular, $X^*$ is log-optimal in the sense that $\mathbb{E}_\mathsf{Q}[\log(X/X^*)] \leq 0$. Moreover, $X^*$ identifies a particular sub-probability measure $\mathsf{P}^*$ via the density $d \mathsf{P}^*/d \mathsf{Q} = 1/X^*$. As a result, $X^*$ can be seen as a generalized likelihood ratio of $\mathsf{Q}$ against $\mathcal{P}$. We show that $\mathsf{P}^*$ coincides with the reverse information projection (RIPr) when additional assumptions are made that are required for the latter to exist. Thus $\mathsf{P}^*$ is a natural definition of the RIPr in the absence of any assumptions on $\mathcal{P}$ or $\mathsf{Q}$. In addition to the abstract theory, we provide several tools for finding the numeraire and RIPr in concrete cases. We discuss several nonparametric examples where we can indeed identify the numeraire and RIPr, despite not having a reference measure. Our results have interpretations outside of testing in that they yield the optimal Kelly bet against $\mathcal{P}$ if we believe reality follows $\mathsf{Q}$. We end with a more general optimality theory that goes beyond the ubiquitous logarithmic utility. We focus on certain power utilities, leading to reverse R茅nyi projections in place of the RIPr, which also always exist. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2402.18810v3-abstract-full').style.display = 'none'; document.getElementById('2402.18810v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 4 April, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 28 February, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2024. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2402.09698">arXiv:2402.09698</a> <span> [<a href="https://arxiv.org/pdf/2402.09698">pdf</a>, <a href="https://arxiv.org/format/2402.09698">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Probability">math.PR</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Statistics Theory">math.ST</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> </div> </div> <p class="title is-5 mathjax"> Combining Evidence Across Filtrations Using Adjusters </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Choe%2C+Y+J">Yo Joong Choe</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2402.09698v2-abstract-short" style="display: inline;"> In anytime-valid sequential inference, it is known that any admissible procedure must be based on e-processes, which are composite generalizations of test martingales that quantify the accumulated evidence against a composite null hypothesis at any arbitrary stopping time. This paper studies methods for combining e-processes constructed using different information sets (filtrations) for the same n… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2402.09698v2-abstract-full').style.display = 'inline'; document.getElementById('2402.09698v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2402.09698v2-abstract-full" style="display: none;"> In anytime-valid sequential inference, it is known that any admissible procedure must be based on e-processes, which are composite generalizations of test martingales that quantify the accumulated evidence against a composite null hypothesis at any arbitrary stopping time. This paper studies methods for combining e-processes constructed using different information sets (filtrations) for the same null. Although e-processes constructed in the same filtration can be combined effortlessly (e.g., by averaging), e-processes constructed in different filtrations cannot, because their validity in a coarser filtration does not translate to validity in a finer filtration. This issue arises in exchangeability tests, independence tests, and tests for comparing forecasts with lags. We first establish that a class of functions called adjusters allows us to lift e-processes from a coarser filtration into any finer filtration. We then introduce a characterization theorem for adjusters, formalizing a sense in which using adjusters is necessary. There are two major implications. First, if we have a powerful e-process in a coarsened filtration, then we readily have a powerful e-process in the original filtration. Second, when we coarsen the filtration to construct an e-process, there is an asymptotically logarithmic cost of recovering anytime-validity in the original filtration. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2402.09698v2-abstract-full').style.display = 'none'; document.getElementById('2402.09698v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 28 May, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 14 February, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2024. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">Substantially revised with new results in Sections 5 and 6. Code is available at https://github.com/yjchoe/CombiningEvidenceAcrossFiltrations</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2401.15567">arXiv:2401.15567</a> <span> [<a href="https://arxiv.org/pdf/2401.15567">pdf</a>, <a href="https://arxiv.org/format/2401.15567">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Probability">math.PR</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Functional Analysis">math.FA</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Statistics Theory">math.ST</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> </div> </div> <p class="title is-5 mathjax"> Positive Semidefinite Supermartingales and Randomized Matrix Concentration Inequalities </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Wang%2C+H">Hongjian Wang</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2401.15567v3-abstract-short" style="display: inline;"> We present new concentration inequalities for either martingale dependent or exchangeable random symmetric matrices under a variety of tail conditions, encompassing now-standard Chernoff bounds to self-normalized heavy-tailed settings. These inequalities are often randomized in a way that renders them strictly tighter than existing deterministic results in the literature, are typically expressed i… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2401.15567v3-abstract-full').style.display = 'inline'; document.getElementById('2401.15567v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2401.15567v3-abstract-full" style="display: none;"> We present new concentration inequalities for either martingale dependent or exchangeable random symmetric matrices under a variety of tail conditions, encompassing now-standard Chernoff bounds to self-normalized heavy-tailed settings. These inequalities are often randomized in a way that renders them strictly tighter than existing deterministic results in the literature, are typically expressed in the Loewner order, and are sometimes valid at arbitrary data-dependent stopping times. Along the way, we explore the theory of positive semidefinite supermartingales and maximal inequalities, a natural matrix analog of scalar nonnegative supermartingales that is potentially of independent interest. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2401.15567v3-abstract-full').style.display = 'none'; document.getElementById('2401.15567v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 26 February, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 27 January, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2024. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 60B20; 60G48; 62L10 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2401.15063">arXiv:2401.15063</a> <span> [<a href="https://arxiv.org/pdf/2401.15063">pdf</a>, <a href="https://arxiv.org/format/2401.15063">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Statistics Theory">math.ST</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Other Statistics">stat.OT</span> </div> </div> <p class="title is-5 mathjax"> Graph fission and cross-validation </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Leiner%2C+J">James Leiner</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2401.15063v2-abstract-short" style="display: inline;"> We introduce a technique called graph fission which takes in a graph which potentially contains only one observation per node (whose distribution lies in a known class) and produces two (or more) independent graphs with the same node/edge set in a way that splits the original graph's information amongst them in any desired proportion. Our proposal builds on data fission/thinning, a method that use… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2401.15063v2-abstract-full').style.display = 'inline'; document.getElementById('2401.15063v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2401.15063v2-abstract-full" style="display: none;"> We introduce a technique called graph fission which takes in a graph which potentially contains only one observation per node (whose distribution lies in a known class) and produces two (or more) independent graphs with the same node/edge set in a way that splits the original graph's information amongst them in any desired proportion. Our proposal builds on data fission/thinning, a method that uses external randomization to create independent copies of an unstructured dataset. We extend this idea to the graph setting where there may be latent structure between observations. We demonstrate the utility of this framework via two applications: inference after structural trend estimation on graphs and a model selection procedure we term "graph cross-validation". <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2401.15063v2-abstract-full').style.display = 'none'; document.getElementById('2401.15063v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 29 January, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 26 January, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2024. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">19 pages, 9 figures</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2401.09379">arXiv:2401.09379</a> <span> [<a href="https://arxiv.org/pdf/2401.09379">pdf</a>, <a href="https://arxiv.org/format/2401.09379">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> </div> </div> <p class="title is-5 mathjax"> Merging uncertainty sets via majority vote </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Gasparin%2C+M">Matteo Gasparin</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2401.09379v5-abstract-short" style="display: inline;"> Given $K$ uncertainty sets that are arbitrarily dependent -- for example, confidence intervals for an unknown parameter obtained with $K$ different estimators, or prediction sets obtained via conformal prediction based on $K$ different algorithms on shared data -- we address the question of how to efficiently combine them in a black-box manner to produce a single uncertainty set. We present a simp… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2401.09379v5-abstract-full').style.display = 'inline'; document.getElementById('2401.09379v5-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2401.09379v5-abstract-full" style="display: none;"> Given $K$ uncertainty sets that are arbitrarily dependent -- for example, confidence intervals for an unknown parameter obtained with $K$ different estimators, or prediction sets obtained via conformal prediction based on $K$ different algorithms on shared data -- we address the question of how to efficiently combine them in a black-box manner to produce a single uncertainty set. We present a simple and broadly applicable majority vote procedure that produces a merged set with nearly the same error guarantee as the input sets. We then extend this core idea in a few ways: we show that weighted averaging can be a powerful way to incorporate prior information, and a simple randomization trick produces strictly smaller merged sets without altering the coverage guarantee. Further improvements can be obtained if the sets are exchangeable. We also show that many modern methods, like split conformal prediction, median of means, HulC and cross-fitted ``double machine learning'', can be effectively derandomized using these ideas. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2401.09379v5-abstract-full').style.display = 'none'; document.getElementById('2401.09379v5-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 14 November, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 17 January, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2024. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2401.07365">arXiv:2401.07365</a> <span> [<a href="https://arxiv.org/pdf/2401.07365">pdf</a>, <a href="https://arxiv.org/format/2401.07365">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> </div> </div> <p class="title is-5 mathjax"> Sequential Monte-Carlo testing by betting </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Fischer%2C+L">Lasse Fischer</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2401.07365v4-abstract-short" style="display: inline;"> In a Monte-Carlo test, the observed dataset is fixed, and several resampled or permuted versions of the dataset are generated in order to test a null hypothesis that the original dataset is exchangeable with the resampled/permuted ones. Sequential Monte-Carlo tests aim to save computational resources by generating these additional datasets sequentially one by one, and potentially stopping early. W… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2401.07365v4-abstract-full').style.display = 'inline'; document.getElementById('2401.07365v4-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2401.07365v4-abstract-full" style="display: none;"> In a Monte-Carlo test, the observed dataset is fixed, and several resampled or permuted versions of the dataset are generated in order to test a null hypothesis that the original dataset is exchangeable with the resampled/permuted ones. Sequential Monte-Carlo tests aim to save computational resources by generating these additional datasets sequentially one by one, and potentially stopping early. While earlier tests yield valid inference at a particular prespecified stopping rule, our work develops a new anytime-valid Monte-Carlo test that can be continuously monitored, yielding a p-value or e-value at any stopping time possibly not specified in advance. Despite the added flexibility, it significantly outperforms the well-known method by Besag and Clifford, stopping earlier under both the null and the alternative without compromising power. The core technical advance is the development of new test martingales (nonnegative martingales with initial value one) for testing exchangeability against a very particular alternative. These test martingales are constructed using new and simple betting strategies that smartly bet on the relative ranks of generated test statistics. The betting strategies are guided by the derivation of a simple log-optimal betting strategy, have closed form expressions for the wealth process, provable guarantees on resampling risk, and display excellent power in practice. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2401.07365v4-abstract-full').style.display = 'none'; document.getElementById('2401.07365v4-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 18 March, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 14 January, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2024. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">33 pages, 8 figures</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2311.18274">arXiv:2311.18274</a> <span> [<a href="https://arxiv.org/pdf/2311.18274">pdf</a>, <a href="https://arxiv.org/format/2311.18274">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> </div> </div> <p class="title is-5 mathjax"> Semiparametric Efficient Inference in Adaptive Experiments </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Cook%2C+T">Thomas Cook</a>, <a href="/search/stat?searchtype=author&query=Mishler%2C+A">Alan Mishler</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2311.18274v3-abstract-short" style="display: inline;"> We consider the problem of efficient inference of the Average Treatment Effect in a sequential experiment where the policy governing the assignment of subjects to treatment or control can change over time. We first provide a central limit theorem for the Adaptive Augmented Inverse-Probability Weighted estimator, which is semiparametric efficient, under weaker assumptions than those previously made… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2311.18274v3-abstract-full').style.display = 'inline'; document.getElementById('2311.18274v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2311.18274v3-abstract-full" style="display: none;"> We consider the problem of efficient inference of the Average Treatment Effect in a sequential experiment where the policy governing the assignment of subjects to treatment or control can change over time. We first provide a central limit theorem for the Adaptive Augmented Inverse-Probability Weighted estimator, which is semiparametric efficient, under weaker assumptions than those previously made in the literature. This central limit theorem enables efficient inference at fixed sample sizes. We then consider a sequential inference setting, deriving both asymptotic and nonasymptotic confidence sequences that are considerably tighter than previous methods. These anytime-valid methods enable inference under data-dependent stopping times (sample sizes). Additionally, we use propensity score truncation techniques from the recent off-policy estimation literature to reduce the finite sample variance of our estimator without affecting the asymptotic variance. Empirical results demonstrate that our methods yield narrower confidence sequences than those previously developed in the literature while maintaining time-uniform error control. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2311.18274v3-abstract-full').style.display = 'none'; document.getElementById('2311.18274v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 4 March, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 30 November, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">24 pages, 6 figures. To appear at CLeaR 2024</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2311.08168">arXiv:2311.08168</a> <span> [<a href="https://arxiv.org/pdf/2311.08168">pdf</a>, <a href="https://arxiv.org/format/2311.08168">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Statistics Theory">math.ST</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> </div> </div> <p class="title is-5 mathjax"> Time-Uniform Confidence Spheres for Means of Random Vectors </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Chugg%2C+B">Ben Chugg</a>, <a href="/search/stat?searchtype=author&query=Wang%2C+H">Hongjian Wang</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2311.08168v3-abstract-short" style="display: inline;"> We derive and study time-uniform confidence spheres -- confidence sphere sequences (CSSs) -- which contain the mean of random vectors with high probability simultaneously across all sample sizes. Our results include a dimension-free CSS for log-concave random vectors, a dimension-free CSS for sub-Gaussian random vectors, and CSSs for sub-$蠄$ random vectors (which includes sub-gamma, sub-Poisson, a… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2311.08168v3-abstract-full').style.display = 'inline'; document.getElementById('2311.08168v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2311.08168v3-abstract-full" style="display: none;"> We derive and study time-uniform confidence spheres -- confidence sphere sequences (CSSs) -- which contain the mean of random vectors with high probability simultaneously across all sample sizes. Our results include a dimension-free CSS for log-concave random vectors, a dimension-free CSS for sub-Gaussian random vectors, and CSSs for sub-$蠄$ random vectors (which includes sub-gamma, sub-Poisson, and sub-exponential distributions). For sub-Gaussian distributions we also provide a CSS which tracks a time-varying mean, generalizing Robbins' mixture approach to the multivariate setting. Finally, we provide several CSSs for heavy-tailed random vectors (two moments only). Our bounds hold under a martingale assumption on the mean and do not require that the observations be iid. Our work is based on PAC-Bayesian theory and inspired by an approach of Catoni and Giulini. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2311.08168v3-abstract-full').style.display = 'none'; document.getElementById('2311.08168v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 2 October, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 14 November, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">41 pages, 3 figures</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2311.06412">arXiv:2311.06412</a> <span> [<a href="https://arxiv.org/pdf/2311.06412">pdf</a>, <a href="https://arxiv.org/format/2311.06412">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> </div> </div> <p class="title is-5 mathjax"> Online multiple testing with e-values </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Xu%2C+Z">Ziyu Xu</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2311.06412v1-abstract-short" style="display: inline;"> A scientist tests a continuous stream of hypotheses over time in the course of her investigation -- she does not test a predetermined, fixed number of hypotheses. The scientist wishes to make as many discoveries as possible while ensuring the number of false discoveries is controlled -- a well recognized way for accomplishing this is to control the false discovery rate (FDR). Prior methods for FDR… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2311.06412v1-abstract-full').style.display = 'inline'; document.getElementById('2311.06412v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2311.06412v1-abstract-full" style="display: none;"> A scientist tests a continuous stream of hypotheses over time in the course of her investigation -- she does not test a predetermined, fixed number of hypotheses. The scientist wishes to make as many discoveries as possible while ensuring the number of false discoveries is controlled -- a well recognized way for accomplishing this is to control the false discovery rate (FDR). Prior methods for FDR control in the online setting have focused on formulating algorithms when specific dependency structures are assumed to exist between the test statistics of each hypothesis. However, in practice, these dependencies often cannot be known beforehand or tested after the fact. Our algorithm, e-LOND, provides FDR control under arbitrary, possibly unknown, dependence. We show that our method is more powerful than existing approaches to this problem through simulations. We also formulate extensions of this algorithm to utilize randomization for increased power, and for constructing confidence intervals in online selective inference. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2311.06412v1-abstract-full').style.display = 'none'; document.getElementById('2311.06412v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 10 November, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">26 pages, 4 figures</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2311.03343">arXiv:2311.03343</a> <span> [<a href="https://arxiv.org/pdf/2311.03343">pdf</a>, <a href="https://arxiv.org/format/2311.03343">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Statistics Theory">math.ST</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> </div> </div> <p class="title is-5 mathjax"> Distribution-uniform anytime-valid sequential inference </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Waudby-Smith%2C+I">Ian Waudby-Smith</a>, <a href="/search/stat?searchtype=author&query=Kennedy%2C+E+H">Edward H. Kennedy</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2311.03343v2-abstract-short" style="display: inline;"> Are asymptotic confidence sequences and anytime $p$-values uniformly valid for a nontrivial class of distributions $\mathcal{P}$? We give a positive answer to this question by deriving distribution-uniform anytime-valid inference procedures. Historically, anytime-valid methods -- including confidence sequences, anytime $p$-values, and sequential hypothesis tests that enable inference at stopping t… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2311.03343v2-abstract-full').style.display = 'inline'; document.getElementById('2311.03343v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2311.03343v2-abstract-full" style="display: none;"> Are asymptotic confidence sequences and anytime $p$-values uniformly valid for a nontrivial class of distributions $\mathcal{P}$? We give a positive answer to this question by deriving distribution-uniform anytime-valid inference procedures. Historically, anytime-valid methods -- including confidence sequences, anytime $p$-values, and sequential hypothesis tests that enable inference at stopping times -- have been justified nonasymptotically. Nevertheless, asymptotic procedures such as those based on the central limit theorem occupy an important part of statistical toolbox due to their simplicity, universality, and weak assumptions. While recent work has derived asymptotic analogues of anytime-valid methods with the aforementioned benefits, these were not shown to be $\mathcal{P}$-uniform, meaning that their asymptotics are not uniformly valid in a class of distributions $\mathcal{P}$. Indeed, the anytime-valid inference literature currently has no central limit theory to draw from that is both uniform in $\mathcal{P}$ and in the sample size $n$. This paper fills that gap by deriving a novel $\mathcal{P}$-uniform strong Gaussian approximation theorem. We apply some of these results to obtain an anytime-valid test of conditional independence without the Model-X assumption, as well as a $\mathcal{P}$-uniform law of the iterated logarithm. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2311.03343v2-abstract-full').style.display = 'none'; document.getElementById('2311.03343v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 18 April, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 6 November, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2023. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2310.19384">arXiv:2310.19384</a> <span> [<a href="https://arxiv.org/pdf/2310.19384">pdf</a>, <a href="https://arxiv.org/format/2310.19384">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> </div> </div> <p class="title is-5 mathjax"> Deep anytime-valid hypothesis testing </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Pandeva%2C+T">Teodora Pandeva</a>, <a href="/search/stat?searchtype=author&query=Forr%C3%A9%2C+P">Patrick Forr茅</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a>, <a href="/search/stat?searchtype=author&query=Shekhar%2C+S">Shubhanshu Shekhar</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2310.19384v1-abstract-short" style="display: inline;"> We propose a general framework for constructing powerful, sequential hypothesis tests for a large class of nonparametric testing problems. The null hypothesis for these problems is defined in an abstract form using the action of two known operators on the data distribution. This abstraction allows for a unified treatment of several classical tasks, such as two-sample testing, independence testing,… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2310.19384v1-abstract-full').style.display = 'inline'; document.getElementById('2310.19384v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2310.19384v1-abstract-full" style="display: none;"> We propose a general framework for constructing powerful, sequential hypothesis tests for a large class of nonparametric testing problems. The null hypothesis for these problems is defined in an abstract form using the action of two known operators on the data distribution. This abstraction allows for a unified treatment of several classical tasks, such as two-sample testing, independence testing, and conditional-independence testing, as well as modern problems, such as testing for adversarial robustness of machine learning (ML) models. Our proposed framework has the following advantages over classical batch tests: 1) it continuously monitors online data streams and efficiently aggregates evidence against the null, 2) it provides tight control over the type I error without the need for multiple testing correction, 3) it adapts the sample size requirement to the unknown hardness of the problem. We develop a principled approach of leveraging the representation capability of ML models within the testing-by-betting framework, a game-theoretic approach for designing sequential tests. Empirical results on synthetic and real-world datasets demonstrate that tests instantiated using our general framework are competitive against specialized baselines on several tasks. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2310.19384v1-abstract-full').style.display = 'none'; document.getElementById('2310.19384v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 30 October, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2023. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2310.16626">arXiv:2310.16626</a> <span> [<a href="https://arxiv.org/pdf/2310.16626">pdf</a>, <a href="https://arxiv.org/format/2310.16626">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Applications">stat.AP</span> </div> </div> <p class="title is-5 mathjax"> Scalable Causal Structure Learning via Amortized Conditional Independence Testing </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Leiner%2C+J">James Leiner</a>, <a href="/search/stat?searchtype=author&query=Manzo%2C+B">Brian Manzo</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a>, <a href="/search/stat?searchtype=author&query=Tansey%2C+W">Wesley Tansey</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2310.16626v1-abstract-short" style="display: inline;"> Controlling false positives (Type I errors) through statistical hypothesis testing is a foundation of modern scientific data analysis. Existing causal structure discovery algorithms either do not provide Type I error control or cannot scale to the size of modern scientific datasets. We consider a variant of the causal discovery problem with two sets of nodes, where the only edges of interest form… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2310.16626v1-abstract-full').style.display = 'inline'; document.getElementById('2310.16626v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2310.16626v1-abstract-full" style="display: none;"> Controlling false positives (Type I errors) through statistical hypothesis testing is a foundation of modern scientific data analysis. Existing causal structure discovery algorithms either do not provide Type I error control or cannot scale to the size of modern scientific datasets. We consider a variant of the causal discovery problem with two sets of nodes, where the only edges of interest form a bipartite causal subgraph between the sets. We develop Scalable Causal Structure Learning (SCSL), a method for causal structure discovery on bipartite subgraphs that provides Type I error control. SCSL recasts the discovery problem as a simultaneous hypothesis testing problem and uses discrete optimization over the set of possible confounders to obtain an upper bound on the test statistic for each edge. Semi-synthetic simulations demonstrate that SCSL scales to handle graphs with hundreds of nodes while maintaining error control and good power. We demonstrate the practical applicability of the method by applying it to a cancer dataset to reveal connections between somatic gene mutations and metastases to different tissues. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2310.16626v1-abstract-full').style.display = 'none'; document.getElementById('2310.16626v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 25 October, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">10 figures, 24 pages</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2310.14293">arXiv:2310.14293</a> <span> [<a href="https://arxiv.org/pdf/2310.14293">pdf</a>, <a href="https://arxiv.org/format/2310.14293">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> </div> </div> <p class="title is-5 mathjax"> Testing exchangeability by pairwise betting </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Saha%2C+A">Aytijhya Saha</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2310.14293v2-abstract-short" style="display: inline;"> In this paper, we address the problem of testing exchangeability of a sequence of random variables, $X_1, X_2,\cdots$. This problem has been studied under the recently popular framework of testing by betting. But the mapping of testing problems to game is not one to one: many games can be designed for the same test. Past work established that it is futile to play single game betting on every obser… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2310.14293v2-abstract-full').style.display = 'inline'; document.getElementById('2310.14293v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2310.14293v2-abstract-full" style="display: none;"> In this paper, we address the problem of testing exchangeability of a sequence of random variables, $X_1, X_2,\cdots$. This problem has been studied under the recently popular framework of testing by betting. But the mapping of testing problems to game is not one to one: many games can be designed for the same test. Past work established that it is futile to play single game betting on every observation: test martingales in the data filtration are powerless. Two avenues have been explored to circumvent this impossibility: betting in a reduced filtration (wealth is a test martingale in a coarsened filtration), or playing many games in parallel (wealth is an e-process in the data filtration). The former has proved to be difficult to theoretically analyze, while the latter only works for binary or discrete observation spaces. Here, we introduce a different approach that circumvents both drawbacks. We design a new (yet simple) game in which we observe the data sequence in pairs. Despite the fact that betting on individual observations is futile, we show that betting on pairs of observations is not. To elaborate, we prove that our game leads to a nontrivial test martingale, which is interesting because it has been obtained by shrinking the filtration very slightly. We show that our test controls type-1 error despite continuous monitoring, and achieves power one for both binary and continuous observations, under a broad class of alternatives. Due to the shrunk filtration, optional stopping is only allowed at even stopping times, not at odd ones: a relatively minor price. We provide a wide array of simulations that align with our theoretical findings. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2310.14293v2-abstract-full').style.display = 'none'; document.getElementById('2310.14293v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 30 December, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 22 October, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2023. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2310.09100">arXiv:2310.09100</a> <span> [<a href="https://arxiv.org/pdf/2310.09100">pdf</a>, <a href="https://arxiv.org/format/2310.09100">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Probability">math.PR</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Statistics Theory">math.ST</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> </div> </div> <p class="title is-5 mathjax"> Time-Uniform Self-Normalized Concentration for Vector-Valued Processes </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Whitehouse%2C+J">Justin Whitehouse</a>, <a href="/search/stat?searchtype=author&query=Wu%2C+Z+S">Zhiwei Steven Wu</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2310.09100v1-abstract-short" style="display: inline;"> Self-normalized processes arise naturally in many statistical tasks. While self-normalized concentration has been extensively studied for scalar-valued processes, there is less work on multidimensional processes outside of the sub-Gaussian setting. In this work, we construct a general, self-normalized inequality for $\mathbb{R}^d$-valued processes that satisfy a simple yet broad "sub-$蠄$" tail con… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2310.09100v1-abstract-full').style.display = 'inline'; document.getElementById('2310.09100v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2310.09100v1-abstract-full" style="display: none;"> Self-normalized processes arise naturally in many statistical tasks. While self-normalized concentration has been extensively studied for scalar-valued processes, there is less work on multidimensional processes outside of the sub-Gaussian setting. In this work, we construct a general, self-normalized inequality for $\mathbb{R}^d$-valued processes that satisfy a simple yet broad "sub-$蠄$" tail condition, which generalizes assumptions based on cumulant generating functions. From this general inequality, we derive an upper law of the iterated logarithm for sub-$蠄$ vector-valued processes, which is tight up to small constants. We demonstrate applications in prototypical statistical tasks, such as parameter estimation in online linear regression and auto-regressive modeling, and bounded mean estimation via a new (multivariate) empirical Bernstein concentration inequality. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2310.09100v1-abstract-full').style.display = 'none'; document.getElementById('2310.09100v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 13 October, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">50 pages, 3 figures</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2310.03722">arXiv:2310.03722</a> <span> [<a href="https://arxiv.org/pdf/2310.03722">pdf</a>, <a href="https://arxiv.org/format/2310.03722">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Statistics Theory">math.ST</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> </div> </div> <p class="title is-5 mathjax"> Anytime-valid t-tests and confidence sequences for Gaussian means with unknown variance </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Wang%2C+H">Hongjian Wang</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2310.03722v5-abstract-short" style="display: inline;"> In 1976, Lai constructed a nontrivial confidence sequence for the mean $渭$ of a Gaussian distribution with unknown variance $蟽^2$. Curiously, he employed both an improper (right Haar) mixture over $蟽$ and an improper (flat) mixture over $渭$. Here, we elaborate carefully on the details of his construction, which use generalized nonintegrable martingales and an extended Ville's inequality. While thi… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2310.03722v5-abstract-full').style.display = 'inline'; document.getElementById('2310.03722v5-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2310.03722v5-abstract-full" style="display: none;"> In 1976, Lai constructed a nontrivial confidence sequence for the mean $渭$ of a Gaussian distribution with unknown variance $蟽^2$. Curiously, he employed both an improper (right Haar) mixture over $蟽$ and an improper (flat) mixture over $渭$. Here, we elaborate carefully on the details of his construction, which use generalized nonintegrable martingales and an extended Ville's inequality. While this does yield a sequential t-test, it does not yield an "e-process" (due to the nonintegrability of his martingale). In this paper, we develop two new e-processes and confidence sequences for the same setting: one is a test martingale in a reduced filtration, while the other is an e-process in the canonical data filtration. These are respectively obtained by swapping Lai's flat mixture for a Gaussian mixture, and swapping the right Haar mixture over $蟽$ with the maximum likelihood estimate under the null, as done in universal inference. We also analyze the width of resulting confidence sequences, which have a curious polynomial dependence on the error probability $伪$ that we prove to be not only unavoidable, but (for universal inference) even better than the classical fixed-sample t-test. Numerical experiments are provided along the way to compare and contrast the various approaches, including some recent suboptimal ones. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2310.03722v5-abstract-full').style.display = 'none'; document.getElementById('2310.03722v5-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 6 November, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 5 October, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">Substantive revision in v3 (Apr 23 2024); Final revision in v4 (Nov 6 2024) accepted by the journal Sequential Analysis</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2310.01547">arXiv:2310.01547</a> <span> [<a href="https://arxiv.org/pdf/2310.01547">pdf</a>, <a href="https://arxiv.org/format/2310.01547">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Statistics Theory">math.ST</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Applications">stat.AP</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> </div> </div> <p class="title is-5 mathjax"> On the near-optimality of betting confidence sets for bounded means </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Shekhar%2C+S">Shubhanshu Shekhar</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2310.01547v2-abstract-short" style="display: inline;"> Constructing nonasymptotic confidence intervals (CIs) for the mean of a univariate distribution from independent and identically distributed (i.i.d.) observations is a fundamental task in statistics. For bounded observations, a classical nonparametric approach proceeds by inverting standard concentration bounds, such as Hoeffding's or Bernstein's inequalities. Recently, an alternative betting-base… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2310.01547v2-abstract-full').style.display = 'inline'; document.getElementById('2310.01547v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2310.01547v2-abstract-full" style="display: none;"> Constructing nonasymptotic confidence intervals (CIs) for the mean of a univariate distribution from independent and identically distributed (i.i.d.) observations is a fundamental task in statistics. For bounded observations, a classical nonparametric approach proceeds by inverting standard concentration bounds, such as Hoeffding's or Bernstein's inequalities. Recently, an alternative betting-based approach for defining CIs and their time-uniform variants called confidence sequences (CSs), has been shown to be empirically superior to the classical methods. In this paper, we provide theoretical justification for this improved empirical performance of betting CIs and CSs. Our main contributions are as follows: (i) We first compare CIs using the values of their first-order asymptotic widths (scaled by $\sqrt{n}$), and show that the betting CI of Waudby-Smith and Ramdas (2023) has a smaller limiting width than existing empirical Bernstein (EB)-CIs. (ii) Next, we establish two lower bounds that characterize the minimum width achievable by any method for constructing CIs/CSs in terms of certain inverse information projections. (iii) Finally, we show that the betting CI and CS match the fundamental limits, modulo an additive logarithmic term and a multiplicative constant. Overall these results imply that the betting CI~(and CS) admit stronger theoretical guarantees than the existing state-of-the-art EB-CI~(and CS); both in the asymptotic and finite-sample regimes. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2310.01547v2-abstract-full').style.display = 'none'; document.getElementById('2310.01547v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 24 November, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 2 October, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">53 pages, 2 figures</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2309.09111">arXiv:2309.09111</a> <span> [<a href="https://arxiv.org/pdf/2309.09111">pdf</a>, <a href="https://arxiv.org/ps/2309.09111">ps</a>, <a href="https://arxiv.org/format/2309.09111">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Statistics Theory">math.ST</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> </div> </div> <p class="title is-5 mathjax"> Reducing sequential change detection to sequential estimation </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Shekhar%2C+S">Shubhanshu Shekhar</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2309.09111v2-abstract-short" style="display: inline;"> We consider the problem of sequential change detection, where the goal is to design a scheme for detecting any changes in a parameter or functional $胃$ of the data stream distribution that has small detection delay, but guarantees control on the frequency of false alarms in the absence of changes. In this paper, we describe a simple reduction from sequential change detection to sequential estimati… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2309.09111v2-abstract-full').style.display = 'inline'; document.getElementById('2309.09111v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2309.09111v2-abstract-full" style="display: none;"> We consider the problem of sequential change detection, where the goal is to design a scheme for detecting any changes in a parameter or functional $胃$ of the data stream distribution that has small detection delay, but guarantees control on the frequency of false alarms in the absence of changes. In this paper, we describe a simple reduction from sequential change detection to sequential estimation using confidence sequences: we begin a new $(1-伪)$-confidence sequence at each time step, and proclaim a change when the intersection of all active confidence sequences becomes empty. We prove that the average run length is at least $1/伪$, resulting in a change detection scheme with minimal structural assumptions~(thus allowing for possibly dependent observations, and nonparametric distribution classes), but strong guarantees. Our approach bears an interesting parallel with the reduction from change detection to sequential testing of Lorden (1971) and the e-detector of Shin et al. (2022). <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2309.09111v2-abstract-full').style.display = 'none'; document.getElementById('2309.09111v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 24 November, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 16 September, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">11 pages</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2309.04002">arXiv:2309.04002</a> <span> [<a href="https://arxiv.org/pdf/2309.04002">pdf</a>, <a href="https://arxiv.org/format/2309.04002">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> </div> </div> <p class="title is-5 mathjax"> Total Variation Floodgate for Variable Importance Inference in Classification </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Wang%2C+W">Wenshuo Wang</a>, <a href="/search/stat?searchtype=author&query=Janson%2C+L">Lucas Janson</a>, <a href="/search/stat?searchtype=author&query=Lei%2C+L">Lihua Lei</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2309.04002v1-abstract-short" style="display: inline;"> Inferring variable importance is the key problem of many scientific studies, where researchers seek to learn the effect of a feature $X$ on the outcome $Y$ in the presence of confounding variables $Z$. Focusing on classification problems, we define the expected total variation (ETV), which is an intuitive and deterministic measure of variable importance that does not rely on any model context. We… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2309.04002v1-abstract-full').style.display = 'inline'; document.getElementById('2309.04002v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2309.04002v1-abstract-full" style="display: none;"> Inferring variable importance is the key problem of many scientific studies, where researchers seek to learn the effect of a feature $X$ on the outcome $Y$ in the presence of confounding variables $Z$. Focusing on classification problems, we define the expected total variation (ETV), which is an intuitive and deterministic measure of variable importance that does not rely on any model context. We then introduce algorithms for statistical inference on the ETV under design-based/model-X assumptions. These algorithms build on the floodgate notion for regression problems (Zhang and Janson 2020). The algorithms we introduce can leverage any user-specified regression function and produce asymptotic lower confidence bounds for the ETV. We show the effectiveness of our algorithms with simulations and a case study in conjoint analysis on the US general election. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2309.04002v1-abstract-full').style.display = 'none'; document.getElementById('2309.04002v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 7 September, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2023. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2307.07539">arXiv:2307.07539</a> <span> [<a href="https://arxiv.org/pdf/2307.07539">pdf</a>, <a href="https://arxiv.org/ps/2307.07539">ps</a>, <a href="https://arxiv.org/format/2307.07539">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Statistics Theory">math.ST</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> </div> </div> <p class="title is-5 mathjax"> On the Sublinear Regret of GP-UCB </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Whitehouse%2C+J">Justin Whitehouse</a>, <a href="/search/stat?searchtype=author&query=Wu%2C+Z+S">Zhiwei Steven Wu</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2307.07539v2-abstract-short" style="display: inline;"> In the kernelized bandit problem, a learner aims to sequentially compute the optimum of a function lying in a reproducing kernel Hilbert space given only noisy evaluations at sequentially chosen points. In particular, the learner aims to minimize regret, which is a measure of the suboptimality of the choices made. Arguably the most popular algorithm is the Gaussian Process Upper Confidence Bound (… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2307.07539v2-abstract-full').style.display = 'inline'; document.getElementById('2307.07539v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2307.07539v2-abstract-full" style="display: none;"> In the kernelized bandit problem, a learner aims to sequentially compute the optimum of a function lying in a reproducing kernel Hilbert space given only noisy evaluations at sequentially chosen points. In particular, the learner aims to minimize regret, which is a measure of the suboptimality of the choices made. Arguably the most popular algorithm is the Gaussian Process Upper Confidence Bound (GP-UCB) algorithm, which involves acting based on a simple linear estimator of the unknown function. Despite its popularity, existing analyses of GP-UCB give a suboptimal regret rate, which fails to be sublinear for many commonly used kernels such as the Mat茅rn kernel. This has led to a longstanding open question: are existing regret analyses for GP-UCB tight, or can bounds be improved by using more sophisticated analytical techniques? In this work, we resolve this open question and show that GP-UCB enjoys nearly optimal regret. In particular, our results yield sublinear regret rates for the Mat茅rn kernel, improving over the state-of-the-art analyses and partially resolving a COLT open problem posed by Vakili et al. Our improvements rely on a key technical contribution -- regularizing kernel ridge estimators in proportion to the smoothness of the underlying kernel $k$. Applying this key idea together with a largely overlooked concentration result in separable Hilbert spaces (for which we provide an independent, simplified derivation), we are able to provide a tighter analysis of the GP-UCB algorithm. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2307.07539v2-abstract-full').style.display = 'none'; document.getElementById('2307.07539v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 14 August, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 14 July, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">20 pages, 0 figures</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2306.06721">arXiv:2306.06721</a> <span> [<a href="https://arxiv.org/pdf/2306.06721">pdf</a>, <a href="https://arxiv.org/format/2306.06721">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Cryptography and Security">cs.CR</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> </div> </div> <p class="title is-5 mathjax"> Differentially Private Conditional Independence Testing </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Kalemaj%2C+I">Iden Kalemaj</a>, <a href="/search/stat?searchtype=author&query=Kasiviswanathan%2C+S+P">Shiva Prasad Kasiviswanathan</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2306.06721v3-abstract-short" style="display: inline;"> Conditional independence (CI) tests are widely used in statistical data analysis, e.g., they are the building block of many algorithms for causal graph discovery. The goal of a CI test is to accept or reject the null hypothesis that $X \perp \!\!\! \perp Y \mid Z$, where $X \in \mathbb{R}, Y \in \mathbb{R}, Z \in \mathbb{R}^d$. In this work, we investigate conditional independence testing under th… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2306.06721v3-abstract-full').style.display = 'inline'; document.getElementById('2306.06721v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2306.06721v3-abstract-full" style="display: none;"> Conditional independence (CI) tests are widely used in statistical data analysis, e.g., they are the building block of many algorithms for causal graph discovery. The goal of a CI test is to accept or reject the null hypothesis that $X \perp \!\!\! \perp Y \mid Z$, where $X \in \mathbb{R}, Y \in \mathbb{R}, Z \in \mathbb{R}^d$. In this work, we investigate conditional independence testing under the constraint of differential privacy. We design two private CI testing procedures: one based on the generalized covariance measure of Shah and Peters (2020) and another based on the conditional randomization test of Cand猫s et al. (2016) (under the model-X assumption). We provide theoretical guarantees on the performance of our tests and validate them empirically. These are the first private CI tests with rigorous theoretical guarantees that work for the general case when $Z$ is continuous. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2306.06721v3-abstract-full').style.display = 'none'; document.getElementById('2306.06721v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 22 March, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 11 June, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> June 2023. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2305.17570">arXiv:2305.17570</a> <span> [<a href="https://arxiv.org/pdf/2305.17570">pdf</a>, <a href="https://arxiv.org/format/2305.17570">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Artificial Intelligence">cs.AI</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computers and Society">cs.CY</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Applications">stat.AP</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> </div> </div> <p class="title is-5 mathjax"> Auditing Fairness by Betting </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Chugg%2C+B">Ben Chugg</a>, <a href="/search/stat?searchtype=author&query=Cortes-Gomez%2C+S">Santiago Cortes-Gomez</a>, <a href="/search/stat?searchtype=author&query=Wilder%2C+B">Bryan Wilder</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2305.17570v2-abstract-short" style="display: inline;"> We provide practical, efficient, and nonparametric methods for auditing the fairness of deployed classification and regression models. Whereas previous work relies on a fixed-sample size, our methods are sequential and allow for the continuous monitoring of incoming data, making them highly amenable to tracking the fairness of real-world systems. We also allow the data to be collected by a probabi… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.17570v2-abstract-full').style.display = 'inline'; document.getElementById('2305.17570v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2305.17570v2-abstract-full" style="display: none;"> We provide practical, efficient, and nonparametric methods for auditing the fairness of deployed classification and regression models. Whereas previous work relies on a fixed-sample size, our methods are sequential and allow for the continuous monitoring of incoming data, making them highly amenable to tracking the fairness of real-world systems. We also allow the data to be collected by a probabilistic policy as opposed to sampled uniformly from the population. This enables auditing to be conducted on data gathered for another purpose. Moreover, this policy may change over time and different policies may be used on different subpopulations. Finally, our methods can handle distribution shift resulting from either changes to the model or changes in the underlying population. Our approach is based on recent progress in anytime-valid inference and game-theoretic statistics-the "testing by betting" framework in particular. These connections ensure that our methods are interpretable, fast, and easy to implement. We demonstrate the efficacy of our approach on three benchmark fairness datasets. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.17570v2-abstract-full').style.display = 'none'; document.getElementById('2305.17570v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 29 October, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 27 May, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">Accepted to NeurIPS 2023. 29 pages, 5 figures</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2305.16539">arXiv:2305.16539</a> <span> [<a href="https://arxiv.org/pdf/2305.16539">pdf</a>, <a href="https://arxiv.org/format/2305.16539">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Statistics Theory">math.ST</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Probability">math.PR</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> </div> </div> <p class="title is-5 mathjax"> On the existence of powerful p-values and e-values for composite hypotheses </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Zhang%2C+Z">Zhenyuan Zhang</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a>, <a href="/search/stat?searchtype=author&query=Wang%2C+R">Ruodu Wang</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2305.16539v3-abstract-short" style="display: inline;"> Given a composite null $ \mathcal P$ and composite alternative $ \mathcal Q$, when and how can we construct a p-value whose distribution is exactly uniform under the null, and stochastically smaller than uniform under the alternative? Similarly, when and how can we construct an e-value whose expectation exactly equals one under the null, but its expected logarithm under the alternative is positive… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.16539v3-abstract-full').style.display = 'inline'; document.getElementById('2305.16539v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2305.16539v3-abstract-full" style="display: none;"> Given a composite null $ \mathcal P$ and composite alternative $ \mathcal Q$, when and how can we construct a p-value whose distribution is exactly uniform under the null, and stochastically smaller than uniform under the alternative? Similarly, when and how can we construct an e-value whose expectation exactly equals one under the null, but its expected logarithm under the alternative is positive? We answer these basic questions, and other related ones, when $ \mathcal P$ and $ \mathcal Q$ are convex polytopes (in the space of probability measures). We prove that such constructions are possible if and only if $ \mathcal Q$ does not intersect the span of $ \mathcal P$. If the p-value is allowed to be stochastically larger than uniform under $P\in \mathcal P$, and the e-value can have expectation at most one under $P\in \mathcal P$, then it is achievable whenever $ \mathcal P$ and $ \mathcal Q$ are disjoint. More generally, even when $ \mathcal P$ and $ \mathcal Q$ are not polytopes, we characterize the existence of a bounded nontrivial e-variable whose expectation exactly equals one under any $P \in \mathcal P$. The proofs utilize recently developed techniques in simultaneous optimal transport. A key role is played by coarsening the filtration: sometimes, no such p-value or e-value exists in the richest data filtration, but it does exist in some reduced filtration, and our work provides the first general characterization of this phenomenon. We also provide an iterative construction that explicitly constructs such processes, and under certain conditions it finds the one that grows fastest under a specific alternative $Q$. We discuss implications for the construction of composite nonnegative (super)martingales, and end with some conjectures and open problems. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.16539v3-abstract-full').style.display = 'none'; document.getElementById('2305.16539v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 23 May, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 25 May, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">47 pages, 6 figures</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2305.11126">arXiv:2305.11126</a> <span> [<a href="https://arxiv.org/pdf/2305.11126">pdf</a>, <a href="https://arxiv.org/format/2305.11126">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> </div> </div> <p class="title is-5 mathjax"> More powerful multiple testing under dependence via randomization </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Xu%2C+Z">Ziyu Xu</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2305.11126v3-abstract-short" style="display: inline;"> We show that two procedures for false discovery rate (FDR) control -- the Benjamini-Yekutieli procedure for dependent p-values, and the e-Benjamini-Hochberg procedure for dependent e-values -- can both be made more powerful by a simple randomization involving one independent uniform random variable. As a corollary, the Hommel test under arbitrary dependence is also improved. Importantly, our rando… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.11126v3-abstract-full').style.display = 'inline'; document.getElementById('2305.11126v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2305.11126v3-abstract-full" style="display: none;"> We show that two procedures for false discovery rate (FDR) control -- the Benjamini-Yekutieli procedure for dependent p-values, and the e-Benjamini-Hochberg procedure for dependent e-values -- can both be made more powerful by a simple randomization involving one independent uniform random variable. As a corollary, the Hommel test under arbitrary dependence is also improved. Importantly, our randomized improvements are never worse than the originals and are typically strictly more powerful, with marked improvements in simulations. The same technique also improves essentially every other multiple testing procedure based on e-values. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.11126v3-abstract-full').style.display = 'none'; document.getElementById('2305.11126v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 24 April, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 18 May, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">45 pages, 9 figures</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2305.10564">arXiv:2305.10564</a> <span> [<a href="https://arxiv.org/pdf/2305.10564">pdf</a>, <a href="https://arxiv.org/format/2305.10564">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Artificial Intelligence">cs.AI</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> </div> </div> <p class="title is-5 mathjax"> Counterfactually Comparing Abstaining Classifiers </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Choe%2C+Y+J">Yo Joong Choe</a>, <a href="/search/stat?searchtype=author&query=Gangrade%2C+A">Aditya Gangrade</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2305.10564v2-abstract-short" style="display: inline;"> Abstaining classifiers have the option to abstain from making predictions on inputs that they are unsure about. These classifiers are becoming increasingly popular in high-stakes decision-making problems, as they can withhold uncertain predictions to improve their reliability and safety. When evaluating black-box abstaining classifier(s), however, we lack a principled approach that accounts for wh… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.10564v2-abstract-full').style.display = 'inline'; document.getElementById('2305.10564v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2305.10564v2-abstract-full" style="display: none;"> Abstaining classifiers have the option to abstain from making predictions on inputs that they are unsure about. These classifiers are becoming increasingly popular in high-stakes decision-making problems, as they can withhold uncertain predictions to improve their reliability and safety. When evaluating black-box abstaining classifier(s), however, we lack a principled approach that accounts for what the classifier would have predicted on its abstentions. These missing predictions matter when they can eventually be utilized, either directly or as a backup option in a failure mode. In this paper, we introduce a novel approach and perspective to the problem of evaluating and comparing abstaining classifiers by treating abstentions as missing data. Our evaluation approach is centered around defining the counterfactual score of an abstaining classifier, defined as the expected performance of the classifier had it not been allowed to abstain. We specify the conditions under which the counterfactual score is identifiable: if the abstentions are stochastic, and if the evaluation data is independent of the training data (ensuring that the predictions are missing at random), then the score is identifiable. Note that, if abstentions are deterministic, then the score is unidentifiable because the classifier can perform arbitrarily poorly on its abstentions. Leveraging tools from observational causal inference, we then develop nonparametric and doubly robust methods to efficiently estimate this quantity under identification. Our approach is examined in both simulated and real data experiments. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.10564v2-abstract-full').style.display = 'none'; document.getElementById('2305.10564v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 9 November, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 17 May, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">Accepted to NeurIPS 2023. Preliminary work presented at the ICML 2023 Workshop on Counterfactuals in Minds and Machines. Code available at https://github.com/yjchoe/ComparingAbstainingClassifiers</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2305.06884">arXiv:2305.06884</a> <span> [<a href="https://arxiv.org/pdf/2305.06884">pdf</a>, <a href="https://arxiv.org/ps/2305.06884">ps</a>, <a href="https://arxiv.org/format/2305.06884">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Artificial Intelligence">cs.AI</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Statistics Theory">math.ST</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Applications">stat.AP</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> </div> </div> <p class="title is-5 mathjax"> Risk-limiting Financial Audits via Weighted Sampling without Replacement </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Shekhar%2C+S">Shubhanshu Shekhar</a>, <a href="/search/stat?searchtype=author&query=Xu%2C+Z">Ziyu Xu</a>, <a href="/search/stat?searchtype=author&query=Lipton%2C+Z+C">Zachary C. Lipton</a>, <a href="/search/stat?searchtype=author&query=Liang%2C+P+J">Pierre J. Liang</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2305.06884v1-abstract-short" style="display: inline;"> We introduce the notion of a risk-limiting financial auditing (RLFA): given $N$ transactions, the goal is to estimate the total misstated monetary fraction~($m^*$) to a given accuracy $蔚$, with confidence $1-未$. We do this by constructing new confidence sequences (CSs) for the weighted average of $N$ unknown values, based on samples drawn without replacement according to a (randomized) weighted sa… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.06884v1-abstract-full').style.display = 'inline'; document.getElementById('2305.06884v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2305.06884v1-abstract-full" style="display: none;"> We introduce the notion of a risk-limiting financial auditing (RLFA): given $N$ transactions, the goal is to estimate the total misstated monetary fraction~($m^*$) to a given accuracy $蔚$, with confidence $1-未$. We do this by constructing new confidence sequences (CSs) for the weighted average of $N$ unknown values, based on samples drawn without replacement according to a (randomized) weighted sampling scheme. Using the idea of importance weighting to construct test martingales, we first develop a framework to construct CSs for arbitrary sampling strategies. Next, we develop methods to improve the quality of CSs by incorporating side information about the unknown values associated with each item. We show that when the side information is sufficiently predictive, it can directly drive the sampling. Addressing the case where the accuracy is unknown a priori, we introduce a method that incorporates side information via control variates. Crucially, our construction is adaptive: if the side information is highly predictive of the unknown misstated amounts, then the benefits of incorporating it are significant; but if the side information is uncorrelated, our methods learn to ignore it. Our methods recover state-of-the-art bounds for the special case when the weights are equal, which has already found applications in election auditing. The harder weighted case solves our more challenging problem of AI-assisted financial auditing. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.06884v1-abstract-full').style.display = 'none'; document.getElementById('2305.06884v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 8 May, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">23 pages, 8 figures, to appear in the Proceedings of Uncertainty in Artificial Intelligence (UAI) 2023</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2305.00143">arXiv:2305.00143</a> <span> [<a href="https://arxiv.org/pdf/2305.00143">pdf</a>, <a href="https://arxiv.org/format/2305.00143">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Statistics Theory">math.ST</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> </div> </div> <p class="title is-5 mathjax"> Sequential Predictive Two-Sample and Independence Testing </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Podkopaev%2C+A">Aleksandr Podkopaev</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2305.00143v2-abstract-short" style="display: inline;"> We study the problems of sequential nonparametric two-sample and independence testing. Sequential tests process data online and allow using observed data to decide whether to stop and reject the null hypothesis or to collect more data, while maintaining type I error control. We build upon the principle of (nonparametric) testing by betting, where a gambler places bets on future observations and th… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.00143v2-abstract-full').style.display = 'inline'; document.getElementById('2305.00143v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2305.00143v2-abstract-full" style="display: none;"> We study the problems of sequential nonparametric two-sample and independence testing. Sequential tests process data online and allow using observed data to decide whether to stop and reject the null hypothesis or to collect more data, while maintaining type I error control. We build upon the principle of (nonparametric) testing by betting, where a gambler places bets on future observations and their wealth measures evidence against the null hypothesis. While recently developed kernel-based betting strategies often work well on simple distributions, selecting a suitable kernel for high-dimensional or structured data, such as images, is often nontrivial. To address this drawback, we design prediction-based betting strategies that rely on the following fact: if a sequentially updated predictor starts to consistently determine (a) which distribution an instance is drawn from, or (b) whether an instance is drawn from the joint distribution or the product of the marginal distributions (the latter produced by external randomization), it provides evidence against the two-sample or independence nulls respectively. We empirically demonstrate the superiority of our tests over kernel-based approaches under structured settings. Our tests can be applied beyond the case of independent and identically distributed data, remaining valid and powerful even when the data distribution drifts over time. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.00143v2-abstract-full').style.display = 'none'; document.getElementById('2305.00143v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 19 July, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 28 April, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2023. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2305.00070">arXiv:2305.00070</a> <span> [<a href="https://arxiv.org/pdf/2305.00070">pdf</a>, <a href="https://arxiv.org/format/2305.00070">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Artificial Intelligence">cs.AI</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Statistics Theory">math.ST</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> </div> </div> <p class="title is-5 mathjax"> Online Platt Scaling with Calibeating </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Gupta%2C+C">Chirag Gupta</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2305.00070v3-abstract-short" style="display: inline;"> We present an online post-hoc calibration method, called Online Platt Scaling (OPS), which combines the Platt scaling technique with online logistic regression. We demonstrate that OPS smoothly adapts between i.i.d. and non-i.i.d. settings with distribution drift. Further, in scenarios where the best Platt scaling model is itself miscalibrated, we enhance OPS by incorporating a recently developed… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.00070v3-abstract-full').style.display = 'inline'; document.getElementById('2305.00070v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2305.00070v3-abstract-full" style="display: none;"> We present an online post-hoc calibration method, called Online Platt Scaling (OPS), which combines the Platt scaling technique with online logistic regression. We demonstrate that OPS smoothly adapts between i.i.d. and non-i.i.d. settings with distribution drift. Further, in scenarios where the best Platt scaling model is itself miscalibrated, we enhance OPS by incorporating a recently developed technique called calibeating to make it more robust. Theoretically, our resulting OPS+calibeating method is guaranteed to be calibrated for adversarial outcome sequences. Empirically, it is effective on a range of synthetic and real-world datasets, with and without distribution drifts, achieving superior performance without hyperparameter tuning. Finally, we extend all OPS ideas to the beta scaling method. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.00070v3-abstract-full').style.display = 'none'; document.getElementById('2305.00070v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 16 August, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 28 April, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">ICML 2023; 24 pages and 16 figures</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2304.13237">arXiv:2304.13237</a> <span> [<a href="https://arxiv.org/pdf/2304.13237">pdf</a>, <a href="https://arxiv.org/format/2304.13237">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> </div> </div> <p class="title is-5 mathjax"> An Efficient Doubly-Robust Test for the Kernel Treatment Effect </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Martinez-Taboada%2C+D">Diego Martinez-Taboada</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a>, <a href="/search/stat?searchtype=author&query=Kennedy%2C+E+H">Edward H. Kennedy</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2304.13237v2-abstract-short" style="display: inline;"> The average treatment effect, which is the difference in expectation of the counterfactuals, is probably the most popular target effect in causal inference with binary treatments. However, treatments may have effects beyond the mean, for instance decreasing or increasing the variance. We propose a new kernel-based test for distributional effects of the treatment. It is, to the best of our knowledg… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2304.13237v2-abstract-full').style.display = 'inline'; document.getElementById('2304.13237v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2304.13237v2-abstract-full" style="display: none;"> The average treatment effect, which is the difference in expectation of the counterfactuals, is probably the most popular target effect in causal inference with binary treatments. However, treatments may have effects beyond the mean, for instance decreasing or increasing the variance. We propose a new kernel-based test for distributional effects of the treatment. It is, to the best of our knowledge, the first kernel-based, doubly-robust test with provably valid type-I error. Furthermore, our proposed algorithm is computationally efficient, avoiding the use of permutations. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2304.13237v2-abstract-full').style.display = 'none'; document.getElementById('2304.13237v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 31 October, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 25 April, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2023. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2304.02611">arXiv:2304.02611</a> <span> [<a href="https://arxiv.org/pdf/2304.02611">pdf</a>, <a href="https://arxiv.org/format/2304.02611">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Statistics Theory">math.ST</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Probability">math.PR</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> </div> </div> <p class="title is-5 mathjax"> Randomized and Exchangeable Improvements of Markov's, Chebyshev's and Chernoff's Inequalities </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a>, <a href="/search/stat?searchtype=author&query=Manole%2C+T">Tudor Manole</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2304.02611v3-abstract-short" style="display: inline;"> We present simple randomized and exchangeable improvements of Markov's inequality, as well as Chebyshev's inequality and Chernoff bounds. Our variants are never worse and typically strictly more powerful than the original inequalities. The proofs are short and elementary, and can easily yield similarly randomized or exchangeable versions of a host of other inequalities that employ Markov's inequal… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2304.02611v3-abstract-full').style.display = 'inline'; document.getElementById('2304.02611v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2304.02611v3-abstract-full" style="display: none;"> We present simple randomized and exchangeable improvements of Markov's inequality, as well as Chebyshev's inequality and Chernoff bounds. Our variants are never worse and typically strictly more powerful than the original inequalities. The proofs are short and elementary, and can easily yield similarly randomized or exchangeable versions of a host of other inequalities that employ Markov's inequality as an intermediate step. We point out some simple statistical applications involving tests that combine dependent e-values. In particular, we uniformly improve the power of universal inference, and obtain tighter betting-based nonparametric confidence intervals. Simulations reveal nontrivial gains in power (and no losses) in a variety of settings. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2304.02611v3-abstract-full').style.display = 'none'; document.getElementById('2304.02611v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 9 May, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 5 April, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2023. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2304.01163">arXiv:2304.01163</a> <span> [<a href="https://arxiv.org/pdf/2304.01163">pdf</a>, <a href="https://arxiv.org/ps/2304.01163">ps</a>, <a href="https://arxiv.org/format/2304.01163">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Probability">math.PR</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Statistics Theory">math.ST</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> </div> </div> <p class="title is-5 mathjax"> The extended Ville's inequality for nonintegrable nonnegative supermartingales </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Wang%2C+H">Hongjian Wang</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2304.01163v3-abstract-short" style="display: inline;"> Following the initial work by Robbins, we rigorously present an extended theory of nonnegative supermartingales, requiring neither integrability nor finiteness. In particular, we derive a key maximal inequality foreshadowed by Robbins, which we call the extended Ville's inequality, that strengthens the classical Ville's inequality (for integrable nonnegative supermartingales), and also applies to… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2304.01163v3-abstract-full').style.display = 'inline'; document.getElementById('2304.01163v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2304.01163v3-abstract-full" style="display: none;"> Following the initial work by Robbins, we rigorously present an extended theory of nonnegative supermartingales, requiring neither integrability nor finiteness. In particular, we derive a key maximal inequality foreshadowed by Robbins, which we call the extended Ville's inequality, that strengthens the classical Ville's inequality (for integrable nonnegative supermartingales), and also applies to our nonintegrable setting. We derive an extension of the method of mixtures, which applies to $蟽$-finite mixtures of our extended nonnegative supermartingales. We present some implications of our theory for sequential statistics, such as the use of improper mixtures (priors) in deriving nonparametric confidence sequences and (extended) e-processes. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2304.01163v3-abstract-full').style.display = 'none'; document.getElementById('2304.01163v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 8 October, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 3 April, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2023. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2302.10108">arXiv:2302.10108</a> <span> [<a href="https://arxiv.org/pdf/2302.10108">pdf</a>, <a href="https://arxiv.org/format/2302.10108">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Applications">stat.AP</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1145/3543873.3584635">10.1145/3543873.3584635 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Anytime-Valid Confidence Sequences in an Enterprise A/B Testing Platform </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Maharaj%2C+A+V">Akash V. Maharaj</a>, <a href="/search/stat?searchtype=author&query=Sinha%2C+R">Ritwik Sinha</a>, <a href="/search/stat?searchtype=author&query=Arbour%2C+D">David Arbour</a>, <a href="/search/stat?searchtype=author&query=Waudby-Smith%2C+I">Ian Waudby-Smith</a>, <a href="/search/stat?searchtype=author&query=Liu%2C+S+Z">Simon Z. Liu</a>, <a href="/search/stat?searchtype=author&query=Sinha%2C+M">Moumita Sinha</a>, <a href="/search/stat?searchtype=author&query=Addanki%2C+R">Raghavendra Addanki</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a>, <a href="/search/stat?searchtype=author&query=Garg%2C+M">Manas Garg</a>, <a href="/search/stat?searchtype=author&query=Swaminathan%2C+V">Viswanathan Swaminathan</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2302.10108v1-abstract-short" style="display: inline;"> A/B tests are the gold standard for evaluating digital experiences on the web. However, traditional "fixed-horizon" statistical methods are often incompatible with the needs of modern industry practitioners as they do not permit continuous monitoring of experiments. Frequent evaluation of fixed-horizon tests ("peeking") leads to inflated type-I error and can result in erroneous conclusions. We hav… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2302.10108v1-abstract-full').style.display = 'inline'; document.getElementById('2302.10108v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2302.10108v1-abstract-full" style="display: none;"> A/B tests are the gold standard for evaluating digital experiences on the web. However, traditional "fixed-horizon" statistical methods are often incompatible with the needs of modern industry practitioners as they do not permit continuous monitoring of experiments. Frequent evaluation of fixed-horizon tests ("peeking") leads to inflated type-I error and can result in erroneous conclusions. We have released an experimentation service on the Adobe Experience Platform based on anytime-valid confidence sequences, allowing for continuous monitoring of the A/B test and data-dependent stopping. We demonstrate how we adapted and deployed asymptotic confidence sequences in a full featured A/B testing platform, describe how sample size calculations can be performed, and how alternate test statistics like "lift" can be analyzed. On both simulated data and thousands of real experiments, we show the desirable properties of using anytime-valid methods instead of traditional approaches. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2302.10108v1-abstract-full').style.display = 'none'; document.getElementById('2302.10108v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 20 February, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">15 pages, 12 figures. Expanded version of ACM Web Conference Proceedings paper</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">ACM Class:</span> G.3 </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Companion Proceedings of the ACM Web Conference 2023 (WWW '23 Companion) </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2302.03421">arXiv:2302.03421</a> <span> [<a href="https://arxiv.org/pdf/2302.03421">pdf</a>, <a href="https://arxiv.org/ps/2302.03421">ps</a>, <a href="https://arxiv.org/format/2302.03421">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Statistics Theory">math.ST</span> </div> </div> <p class="title is-5 mathjax"> A unified recipe for deriving (time-uniform) PAC-Bayes bounds </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Chugg%2C+B">Ben Chugg</a>, <a href="/search/stat?searchtype=author&query=Wang%2C+H">Hongjian Wang</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2302.03421v5-abstract-short" style="display: inline;"> We present a unified framework for deriving PAC-Bayesian generalization bounds. Unlike most previous literature on this topic, our bounds are anytime-valid (i.e., time-uniform), meaning that they hold at all stopping times, not only for a fixed sample size. Our approach combines four tools in the following order: (a) nonnegative supermartingales or reverse submartingales, (b) the method of mixture… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2302.03421v5-abstract-full').style.display = 'inline'; document.getElementById('2302.03421v5-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2302.03421v5-abstract-full" style="display: none;"> We present a unified framework for deriving PAC-Bayesian generalization bounds. Unlike most previous literature on this topic, our bounds are anytime-valid (i.e., time-uniform), meaning that they hold at all stopping times, not only for a fixed sample size. Our approach combines four tools in the following order: (a) nonnegative supermartingales or reverse submartingales, (b) the method of mixtures, (c) the Donsker-Varadhan formula (or other convex duality principles), and (d) Ville's inequality. Our main result is a PAC-Bayes theorem which holds for a wide class of discrete stochastic processes. We show how this result implies time-uniform versions of well-known classical PAC-Bayes bounds, such as those of Seeger, McAllester, Maurer, and Catoni, in addition to many recent bounds. We also present several novel bounds. Our framework also enables us to relax traditional assumptions; in particular, we consider nonstationary loss functions and non-i.i.d. data. In sum, we unify the derivation of past bounds and ease the search for future bounds: one may simply check if our supermartingale or submartingale conditions are met and, if so, be guaranteed a (time-uniform) PAC-Bayes bound. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2302.03421v5-abstract-full').style.display = 'none'; document.getElementById('2302.03421v5-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 3 January, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 7 February, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">56 pages. Published in the Journal of Machine Learning Research, Volume 24 Issue 372</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2302.02544">arXiv:2302.02544</a> <span> [<a href="https://arxiv.org/pdf/2302.02544">pdf</a>, <a href="https://arxiv.org/format/2302.02544">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Statistics Theory">math.ST</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> </div> </div> <p class="title is-5 mathjax"> Sequential change detection via backward confidence sequences </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Shekhar%2C+S">Shubhanshu Shekhar</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2302.02544v1-abstract-short" style="display: inline;"> We present a simple reduction from sequential estimation to sequential changepoint detection (SCD). In short, suppose we are interested in detecting changepoints in some parameter or functional $胃$ of the underlying distribution. We demonstrate that if we can construct a confidence sequence (CS) for $胃$, then we can also successfully perform SCD for $胃$. This is accomplished by checking if two CSs… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2302.02544v1-abstract-full').style.display = 'inline'; document.getElementById('2302.02544v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2302.02544v1-abstract-full" style="display: none;"> We present a simple reduction from sequential estimation to sequential changepoint detection (SCD). In short, suppose we are interested in detecting changepoints in some parameter or functional $胃$ of the underlying distribution. We demonstrate that if we can construct a confidence sequence (CS) for $胃$, then we can also successfully perform SCD for $胃$. This is accomplished by checking if two CSs -- one forwards and the other backwards -- ever fail to intersect. Since the literature on CSs has been rapidly evolving recently, the reduction provided in this paper immediately solves several old and new change detection problems. Further, our "backward CS", constructed by reversing time, is new and potentially of independent interest. We provide strong nonasymptotic guarantees on the frequency of false alarms and detection delay, and demonstrate numerical effectiveness on several problems. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2302.02544v1-abstract-full').style.display = 'none'; document.getElementById('2302.02544v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 5 February, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">24 pages, 10 figures</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2301.09573">arXiv:2301.09573</a> <span> [<a href="https://arxiv.org/pdf/2301.09573">pdf</a>, <a href="https://arxiv.org/format/2301.09573">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Statistics Theory">math.ST</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> </div> </div> <p class="title is-5 mathjax"> Huber-Robust Confidence Sequences </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Wang%2C+H">Hongjian Wang</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2301.09573v2-abstract-short" style="display: inline;"> Confidence sequences are confidence intervals that can be sequentially tracked, and are valid at arbitrary data-dependent stopping times. This paper presents confidence sequences for a univariate mean of an unknown distribution with a known upper bound on the $p$-th central moment ($p$ > 1), but allowing for (at most) $蔚$ fraction of arbitrary distribution corruption, as in Huber's contamination m… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2301.09573v2-abstract-full').style.display = 'inline'; document.getElementById('2301.09573v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2301.09573v2-abstract-full" style="display: none;"> Confidence sequences are confidence intervals that can be sequentially tracked, and are valid at arbitrary data-dependent stopping times. This paper presents confidence sequences for a univariate mean of an unknown distribution with a known upper bound on the $p$-th central moment ($p$ > 1), but allowing for (at most) $蔚$ fraction of arbitrary distribution corruption, as in Huber's contamination model. We do this by designing new robust exponential supermartingales, and show that the resulting confidence sequences attain the optimal width achieved in the nonsequential setting. Perhaps surprisingly, the constant margin between our sequential result and the lower bound is smaller than even fixed-time robust confidence intervals based on the trimmed mean, for example. Since confidence sequences are a common tool used within A/B/n testing and bandits, these results open the door to sequential experimentation that is robust to outliers and adversarial corruptions. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2301.09573v2-abstract-full').style.display = 'none'; document.getElementById('2301.09573v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 7 February, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 23 January, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">Accepted for publication at the 26th International Conference on Artificial Intelligence and Statistics (AISTATS 2023)</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2301.03542">arXiv:2301.03542</a> <span> [<a href="https://arxiv.org/pdf/2301.03542">pdf</a>, <a href="https://arxiv.org/ps/2301.03542">ps</a>, <a href="https://arxiv.org/format/2301.03542">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Statistics Theory">math.ST</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> </div> </div> <p class="title is-5 mathjax"> A Sequential Test for Log-Concavity </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Gangrade%2C+A">Aditya Gangrade</a>, <a href="/search/stat?searchtype=author&query=Rinaldo%2C+A">Alessandro Rinaldo</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2301.03542v1-abstract-short" style="display: inline;"> On observing a sequence of i.i.d.\ data with distribution $P$ on $\mathbb{R}^d$, we ask the question of how one can test the null hypothesis that $P$ has a log-concave density. This paper proves one interesting negative and positive result: the non-existence of test (super)martingales, and the consistency of universal inference. To elaborate, the set of log-concave distributions $\mathcal{L}$ is a… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2301.03542v1-abstract-full').style.display = 'inline'; document.getElementById('2301.03542v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2301.03542v1-abstract-full" style="display: none;"> On observing a sequence of i.i.d.\ data with distribution $P$ on $\mathbb{R}^d$, we ask the question of how one can test the null hypothesis that $P$ has a log-concave density. This paper proves one interesting negative and positive result: the non-existence of test (super)martingales, and the consistency of universal inference. To elaborate, the set of log-concave distributions $\mathcal{L}$ is a nonparametric class, which contains the set $\mathcal G$ of all possible Gaussians with any mean and covariance. Developing further the recent geometric concept of fork-convexity, we first prove that there do no exist any nontrivial test martingales or test supermartingales for $\mathcal G$ (a process that is simultaneously a nonnegative supermartingale for every distribution in $\mathcal G$), and hence also for its superset $\mathcal{L}$. Due to this negative result, we turn our attention to constructing an e-process -- a process whose expectation at any stopping time is at most one, under any distribution in $\mathcal{L}$ -- which yields a level-$伪$ test by simply thresholding at $1/伪$. We take the approach of universal inference, which avoids intractable likelihood asymptotics by taking the ratio of a nonanticipating likelihood over alternatives against the maximum likelihood under the null. Despite its conservatism, we show that the resulting test is consistent (power one), and derive its power against Hellinger alternatives. To the best of our knowledge, there is no other e-process or sequential test for $\mathcal{L}$. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2301.03542v1-abstract-full').style.display = 'none'; document.getElementById('2301.03542v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 9 January, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2023. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2212.09706">arXiv:2212.09706</a> <span> [<a href="https://arxiv.org/pdf/2212.09706">pdf</a>, <a href="https://arxiv.org/ps/2212.09706">ps</a>, <a href="https://arxiv.org/format/2212.09706">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Statistics Theory">math.ST</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Probability">math.PR</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Methodology">stat.ME</span> </div> </div> <p class="title is-5 mathjax"> Multiple testing under negative dependence </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/stat?searchtype=author&query=Chi%2C+Z">Ziyu Chi</a>, <a href="/search/stat?searchtype=author&query=Ramdas%2C+A">Aaditya Ramdas</a>, <a href="/search/stat?searchtype=author&query=Wang%2C+R">Ruodu Wang</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2212.09706v4-abstract-short" style="display: inline;"> The multiple testing literature has primarily dealt with three types of dependence assumptions between p-values: independence, positive regression dependence, and arbitrary dependence. In this paper, we provide what we believe are the first theoretical results under various notions of negative dependence (negative Gaussian dependence, negative regression dependence, negative association, negative… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2212.09706v4-abstract-full').style.display = 'inline'; document.getElementById('2212.09706v4-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2212.09706v4-abstract-full" style="display: none;"> The multiple testing literature has primarily dealt with three types of dependence assumptions between p-values: independence, positive regression dependence, and arbitrary dependence. In this paper, we provide what we believe are the first theoretical results under various notions of negative dependence (negative Gaussian dependence, negative regression dependence, negative association, negative orthant dependence and weak negative dependence). These include the Simes global null test and the Benjamini-Hochberg procedure, which are known experimentally to be anti-conservative under negative dependence. The anti-conservativeness of these procedures is bounded by factors smaller than that under arbitrary dependence (in particular, by factors independent of the number of hypotheses). We also provide new results about negatively dependent e-values, and provide several examples as to when negative dependence may arise. Our proofs are elementary and short, thus amenable to extensions. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2212.09706v4-abstract-full').style.display = 'none'; document.getElementById('2212.09706v4-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 8 May, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 19 December, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> December 2022. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">28 pages, 5 figures</span> </p> </li> </ol> <nav class="pagination is-small is-centered breathe-horizontal" role="navigation" aria-label="pagination"> <a href="" class="pagination-previous is-invisible">Previous </a> <a href="/search/?searchtype=author&query=Ramdas%2C+A&start=50" class="pagination-next" >Next </a> <ul class="pagination-list"> <li> <a href="/search/?searchtype=author&query=Ramdas%2C+A&start=0" class="pagination-link is-current" aria-label="Goto page 1">1 </a> </li> <li> <a href="/search/?searchtype=author&query=Ramdas%2C+A&start=50" class="pagination-link " aria-label="Page 2" aria-current="page">2 </a> </li> <li> <a href="/search/?searchtype=author&query=Ramdas%2C+A&start=100" class="pagination-link " aria-label="Page 3" aria-current="page">3 </a> </li> </ul> </nav> <div class="is-hidden-tablet">  <span class="help" style="display: inline-block;"><a href="https://github.com/arXiv/arxiv-search/releases">Search v0.5.6 released 2020-02-24</a>  </span> </div> </div> </main> <footer> <div class="columns is-desktop" role="navigation" aria-label="Secondary">  <div class="column"> <div class="columns"> <div class="column"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/about">About</a></li> <li><a href="https://info.arxiv.org/help">Help</a></li> </ul> </div> <div class="column"> <ul class="nav-spaced"> <li> <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><title>contact arXiv</title><desc>Click here to contact arXiv</desc><path d="M502.3 190.8c3.9-3.1 9.7-.2 9.7 4.7V400c0 26.5-21.5 48-48 48H48c-26.5 0-48-21.5-48-48V195.6c0-5 5.7-7.8 9.7-4.7 22.4 17.4 52.1 39.5 154.1 113.6 21.1 15.4 56.7 47.8 92.2 47.6 35.7.3 72-32.8 92.3-47.6 102-74.1 131.6-96.3 154-113.7zM256 320c23.2.4 56.6-29.2 73.4-41.4 132.7-96.3 142.8-104.7 173.4-128.7 5.8-4.5 9.2-11.5 9.2-18.9v-19c0-26.5-21.5-48-48-48H48C21.5 64 0 85.5 0 112v19c0 7.4 3.4 14.3 9.2 18.9 30.6 23.9 40.7 32.4 173.4 128.7 16.8 12.2 50.2 41.8 73.4 41.4z"/></svg> <a href="https://info.arxiv.org/help/contact.html"> Contact</a> </li> <li> <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><title>subscribe to arXiv mailings</title><desc>Click here to subscribe</desc><path d="M476 3.2L12.5 270.6c-18.1 10.4-15.8 35.6 2.2 43.2L121 358.4l287.3-253.2c5.5-4.9 13.3 2.6 8.6 8.3L176 407v80.5c0 23.6 28.5 32.9 42.5 15.8L282 426l124.6 52.2c14.2 6 30.4-2.9 33-18.2l72-432C515 7.8 493.3-6.8 476 3.2z"/></svg> <a href="https://info.arxiv.org/help/subscribe"> Subscribe</a> </li> </ul> </div> </div> </div>   <div class="column"> <div class="columns"> <div class="column"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/help/license/index.html">Copyright</a></li> <li><a href="https://info.arxiv.org/help/policies/privacy_policy.html">Privacy Policy</a></li> </ul> </div> <div class="column sorry-app-links"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/help/web_accessibility.html">Web Accessibility Assistance</a></li> <li> <p class="help"> <a class="a11y-main-link" href="https://status.arxiv.org" target="_blank">arXiv Operational Status <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 256 512" class="icon filter-dark_grey" role="presentation"><path d="M224.3 273l-136 136c-9.4 9.4-24.6 9.4-33.9 0l-22.6-22.6c-9.4-9.4-9.4-24.6 0-33.9l96.4-96.4-96.4-96.4c-9.4-9.4-9.4-24.6 0-33.9L54.3 103c9.4-9.4 24.6-9.4 33.9 0l136 136c9.5 9.4 9.5 24.6.1 34z"/></svg></a><br> Get status notifications via <a class="is-link" href="https://subscribe.sorryapp.com/24846f03/email/new" target="_blank"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><path d="M502.3 190.8c3.9-3.1 9.7-.2 9.7 4.7V400c0 26.5-21.5 48-48 48H48c-26.5 0-48-21.5-48-48V195.6c0-5 5.7-7.8 9.7-4.7 22.4 17.4 52.1 39.5 154.1 113.6 21.1 15.4 56.7 47.8 92.2 47.6 35.7.3 72-32.8 92.3-47.6 102-74.1 131.6-96.3 154-113.7zM256 320c23.2.4 56.6-29.2 73.4-41.4 132.7-96.3 142.8-104.7 173.4-128.7 5.8-4.5 9.2-11.5 9.2-18.9v-19c0-26.5-21.5-48-48-48H48C21.5 64 0 85.5 0 112v19c0 7.4 3.4 14.3 9.2 18.9 30.6 23.9 40.7 32.4 173.4 128.7 16.8 12.2 50.2 41.8 73.4 41.4z"/></svg>email</a> or <a class="is-link" href="https://subscribe.sorryapp.com/24846f03/slack/new" target="_blank"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 448 512" class="icon filter-black" role="presentation"><path d="M94.12 315.1c0 25.9-21.16 47.06-47.06 47.06S0 341 0 315.1c0-25.9 21.16-47.06 47.06-47.06h47.06v47.06zm23.72 0c0-25.9 21.16-47.06 47.06-47.06s47.06 21.16 47.06 47.06v117.84c0 25.9-21.16 47.06-47.06 47.06s-47.06-21.16-47.06-47.06V315.1zm47.06-188.98c-25.9 0-47.06-21.16-47.06-47.06S139 32 164.9 32s47.06 21.16 47.06 47.06v47.06H164.9zm0 23.72c25.9 0 47.06 21.16 47.06 47.06s-21.16 47.06-47.06 47.06H47.06C21.16 243.96 0 222.8 0 196.9s21.16-47.06 47.06-47.06H164.9zm188.98 47.06c0-25.9 21.16-47.06 47.06-47.06 25.9 0 47.06 21.16 47.06 47.06s-21.16 47.06-47.06 47.06h-47.06V196.9zm-23.72 0c0 25.9-21.16 47.06-47.06 47.06-25.9 0-47.06-21.16-47.06-47.06V79.06c0-25.9 21.16-47.06 47.06-47.06 25.9 0 47.06 21.16 47.06 47.06V196.9zM283.1 385.88c25.9 0 47.06 21.16 47.06 47.06 0 25.9-21.16 47.06-47.06 47.06-25.9 0-47.06-21.16-47.06-47.06v-47.06h47.06zm0-23.72c-25.9 0-47.06-21.16-47.06-47.06 0-25.9 21.16-47.06 47.06-47.06h117.84c25.9 0 47.06 21.16 47.06 47.06 0 25.9-21.16 47.06-47.06 47.06H283.1z"/></svg>slack</a> </p> </li> </ul> </div> </div> </div>  </div> </footer> <script src="https://static.arxiv.org/static/base/1.0.0a5/js/member_acknowledgement.js"></script> </body> </html>

CINXE.COM

Search | arXiv e-print repository