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 111 results for author: <span class="mathjax">Bhattacharyya, 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/cs" aria-role="search"> Searching in archive <strong>cs</strong>. <a href="/search/?searchtype=author&query=Bhattacharyya%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="Bhattacharyya, 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=Bhattacharyya%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="Bhattacharyya, 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=Bhattacharyya%2C+A&start=50" class="pagination-next" >Next </a> <ul class="pagination-list"> <li> <a href="/search/?searchtype=author&query=Bhattacharyya%2C+A&start=0" class="pagination-link is-current" aria-label="Goto page 1">1 </a> </li> <li> <a href="/search/?searchtype=author&query=Bhattacharyya%2C+A&start=50" class="pagination-link " aria-label="Page 2" aria-current="page">2 </a> </li> <li> <a href="/search/?searchtype=author&query=Bhattacharyya%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/2502.10527">arXiv:2502.10527</a> <span> [<a href="https://arxiv.org/pdf/2502.10527">pdf</a>, <a href="https://arxiv.org/ps/2502.10527">ps</a>, <a href="https://arxiv.org/format/2502.10527">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> </div> </div> <p class="title is-5 mathjax"> Algorithms and Hardness for Estimating Statistical Similarity </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Gayen%2C+S">Sutanu Gayen</a>, <a href="/search/cs?searchtype=author&query=Meel%2C+K+S">Kuldeep S. Meel</a>, <a href="/search/cs?searchtype=author&query=Myrisiotis%2C+D">Dimitrios Myrisiotis</a>, <a href="/search/cs?searchtype=author&query=Pavan%2C+A">A. Pavan</a>, <a href="/search/cs?searchtype=author&query=Vinodchandran%2C+N+V">N. V. Vinodchandran</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="2502.10527v1-abstract-short" style="display: inline;"> We study the problem of computing statistical similarity between probability distributions. For distributions $P$ and $Q$ over a finite sample space, their statistical similarity is defined as $S_{\mathrm{stat}}(P, Q) := \sum_{x} \min(P(x), Q(x))$. Statistical similarity is a basic measure of similarity between distributions, with several natural interpretations, and captures the Bayes error in pr… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2502.10527v1-abstract-full').style.display = 'inline'; document.getElementById('2502.10527v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2502.10527v1-abstract-full" style="display: none;"> We study the problem of computing statistical similarity between probability distributions. For distributions $P$ and $Q$ over a finite sample space, their statistical similarity is defined as $S_{\mathrm{stat}}(P, Q) := \sum_{x} \min(P(x), Q(x))$. Statistical similarity is a basic measure of similarity between distributions, with several natural interpretations, and captures the Bayes error in prediction and hypothesis testing problems. Recent work has established that, somewhat surprisingly, even for the simple class of product distributions, exactly computing statistical similarity is $\#\mathsf{P}$-hard. This motivates the question of designing approximation algorithms for statistical similarity. Our primary contribution is a Fully Polynomial-Time deterministic Approximation Scheme (FPTAS) for estimating statistical similarity between two product distributions. To obtain this result, we introduce a new variant of the Knapsack problem, which we call the Masked Knapsack problem, and design an FPTAS to estimate the number of solutions of a multidimensional version of this problem. This new technical contribution could be of independent interest. Furthermore, we also establish a complementary hardness result. We show that it is $\mathsf{NP}$-hard to estimate statistical similarity when $P$ and $Q$ are Bayes net distributions of in-degree $2$. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2502.10527v1-abstract-full').style.display = 'none'; document.getElementById('2502.10527v1-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 February, 2025; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2025. </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">21 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/2502.03799">arXiv:2502.03799</a> <span> [<a href="https://arxiv.org/pdf/2502.03799">pdf</a>, <a href="https://arxiv.org/format/2502.03799">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computation and Language">cs.CL</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Systems and Control">eess.SY</span> </div> </div> <p class="title is-5 mathjax"> Enhancing Hallucination Detection through Noise Injection </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Liu%2C+L">Litian Liu</a>, <a href="/search/cs?searchtype=author&query=Pourreza%2C+R">Reza Pourreza</a>, <a href="/search/cs?searchtype=author&query=Panchal%2C+S">Sunny Panchal</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Apratim Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Qin%2C+Y">Yao Qin</a>, <a href="/search/cs?searchtype=author&query=Memisevic%2C+R">Roland Memisevic</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="2502.03799v2-abstract-short" style="display: inline;"> Large Language Models (LLMs) are prone to generating plausible yet incorrect responses, known as hallucinations. Effectively detecting hallucinations is therefore crucial for the safe deployment of LLMs. Recent research has linked hallucinations to model uncertainty, suggesting that hallucinations can be detected by measuring dispersion over answer distributions obtained from a set of samples draw… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2502.03799v2-abstract-full').style.display = 'inline'; document.getElementById('2502.03799v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2502.03799v2-abstract-full" style="display: none;"> Large Language Models (LLMs) are prone to generating plausible yet incorrect responses, known as hallucinations. Effectively detecting hallucinations is therefore crucial for the safe deployment of LLMs. Recent research has linked hallucinations to model uncertainty, suggesting that hallucinations can be detected by measuring dispersion over answer distributions obtained from a set of samples drawn from a model. While drawing from the distribution over tokens defined by the model is a natural way to obtain samples, in this work, we argue that it is sub-optimal for the purpose of detecting hallucinations. We show that detection can be improved significantly by taking into account model uncertainty in the Bayesian sense. To this end, we propose a very simple and efficient approach that perturbs an appropriate subset of model parameters, or equivalently hidden unit activations, during sampling. We demonstrate its effectiveness across a wide range of datasets and model architectures. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2502.03799v2-abstract-full').style.display = 'none'; document.getElementById('2502.03799v2-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 February, 2025; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 6 February, 2025; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2025. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2501.09757">arXiv:2501.09757</a> <span> [<a href="https://arxiv.org/pdf/2501.09757">pdf</a>, <a href="https://arxiv.org/format/2501.09757">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computer Vision and Pattern Recognition">cs.CV</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Robotics">cs.RO</span> </div> </div> <p class="title is-5 mathjax"> Distilling Multi-modal Large Language Models for Autonomous Driving </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Hegde%2C+D">Deepti Hegde</a>, <a href="/search/cs?searchtype=author&query=Yasarla%2C+R">Rajeev Yasarla</a>, <a href="/search/cs?searchtype=author&query=Cai%2C+H">Hong Cai</a>, <a href="/search/cs?searchtype=author&query=Han%2C+S">Shizhong Han</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Apratim Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Mahajan%2C+S">Shweta Mahajan</a>, <a href="/search/cs?searchtype=author&query=Liu%2C+L">Litian Liu</a>, <a href="/search/cs?searchtype=author&query=Garrepalli%2C+R">Risheek Garrepalli</a>, <a href="/search/cs?searchtype=author&query=Patel%2C+V+M">Vishal M. Patel</a>, <a href="/search/cs?searchtype=author&query=Porikli%2C+F">Fatih Porikli</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="2501.09757v1-abstract-short" style="display: inline;"> Autonomous driving demands safe motion planning, especially in critical "long-tail" scenarios. Recent end-to-end autonomous driving systems leverage large language models (LLMs) as planners to improve generalizability to rare events. However, using LLMs at test time introduces high computational costs. To address this, we propose DiMA, an end-to-end autonomous driving system that maintains the eff… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2501.09757v1-abstract-full').style.display = 'inline'; document.getElementById('2501.09757v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2501.09757v1-abstract-full" style="display: none;"> Autonomous driving demands safe motion planning, especially in critical "long-tail" scenarios. Recent end-to-end autonomous driving systems leverage large language models (LLMs) as planners to improve generalizability to rare events. However, using LLMs at test time introduces high computational costs. To address this, we propose DiMA, an end-to-end autonomous driving system that maintains the efficiency of an LLM-free (or vision-based) planner while leveraging the world knowledge of an LLM. DiMA distills the information from a multi-modal LLM to a vision-based end-to-end planner through a set of specially designed surrogate tasks. Under a joint training strategy, a scene encoder common to both networks produces structured representations that are semantically grounded as well as aligned to the final planning objective. Notably, the LLM is optional at inference, enabling robust planning without compromising on efficiency. Training with DiMA results in a 37% reduction in the L2 trajectory error and an 80% reduction in the collision rate of the vision-based planner, as well as a 44% trajectory error reduction in longtail scenarios. DiMA also achieves state-of-the-art performance on the nuScenes planning benchmark. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2501.09757v1-abstract-full').style.display = 'none'; document.getElementById('2501.09757v1-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 January, 2025; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2025. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2412.12746">arXiv:2412.12746</a> <span> [<a href="https://arxiv.org/pdf/2412.12746">pdf</a>, <a href="https://arxiv.org/format/2412.12746">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Cryptography and Security">cs.CR</span> </div> </div> <p class="title is-5 mathjax"> EmbedFuzz: High Speed Fuzzing Through Transplantation </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Hofhammer%2C+F">Florian Hofhammer</a>, <a href="/search/cs?searchtype=author&query=Wang%2C+Q">Qinying Wang</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Atri Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Salehi%2C+M">Majid Salehi</a>, <a href="/search/cs?searchtype=author&query=Crispo%2C+B">Bruno Crispo</a>, <a href="/search/cs?searchtype=author&query=Egele%2C+M">Manuel Egele</a>, <a href="/search/cs?searchtype=author&query=Payer%2C+M">Mathias Payer</a>, <a href="/search/cs?searchtype=author&query=Busch%2C+M">Marcel Busch</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="2412.12746v1-abstract-short" style="display: inline;"> Dynamic analysis and especially fuzzing are challenging tasks for embedded firmware running on modern low-end Microcontroller Units (MCUs) due to performance overheads from instruction emulation, the difficulty of emulating the vast space of available peripherals, and low availability of open-source embedded firmware. Consequently, efficient security testing of MCU firmware has proved to be a reso… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2412.12746v1-abstract-full').style.display = 'inline'; document.getElementById('2412.12746v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2412.12746v1-abstract-full" style="display: none;"> Dynamic analysis and especially fuzzing are challenging tasks for embedded firmware running on modern low-end Microcontroller Units (MCUs) due to performance overheads from instruction emulation, the difficulty of emulating the vast space of available peripherals, and low availability of open-source embedded firmware. Consequently, efficient security testing of MCU firmware has proved to be a resource- and engineering-heavy endeavor. EmbedFuzz introduces an efficient end-to-end fuzzing framework for MCU firmware. Our novel firmware transplantation technique converts binary MCU firmware to a functionally equivalent and fuzzing-enhanced version of the firmware which executes on a compatible high-end device at native performance. Besides the performance gains, our system enables advanced introspection capabilities based on tooling for typical Linux user space processes, thus simplifying analysis of crashes and bug triaging. In our evaluation against state-of-the-art MCU fuzzers, EmbedFuzz exhibits up to eight-fold fuzzing throughput while consuming at most a fourth of the energy thanks to its native execution. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2412.12746v1-abstract-full').style.display = 'none'; document.getElementById('2412.12746v1-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 December, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> December 2024. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2412.10370">arXiv:2412.10370</a> <span> [<a href="https://arxiv.org/pdf/2412.10370">pdf</a>, <a href="https://arxiv.org/ps/2412.10370">ps</a>, <a href="https://arxiv.org/format/2412.10370">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> </div> </div> <p class="title is-5 mathjax"> Computational Explorations of Total Variation Distance </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Gayen%2C+S">Sutanu Gayen</a>, <a href="/search/cs?searchtype=author&query=Meel%2C+K+S">Kuldeep S. Meel</a>, <a href="/search/cs?searchtype=author&query=Myrisiotis%2C+D">Dimitrios Myrisiotis</a>, <a href="/search/cs?searchtype=author&query=Pavan%2C+A">A. Pavan</a>, <a href="/search/cs?searchtype=author&query=Vinodchandran%2C+N+V">N. V. Vinodchandran</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="2412.10370v1-abstract-short" style="display: inline;"> We investigate some previously unexplored (or underexplored) computational aspects of total variation (TV) distance. First, we give a simple deterministic polynomial-time algorithm for checking equivalence between mixtures of product distributions, over arbitrary alphabets. This corresponds to a special case, whereby the TV distance between the two distributions is zero. Second, we prove that unle… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2412.10370v1-abstract-full').style.display = 'inline'; document.getElementById('2412.10370v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2412.10370v1-abstract-full" style="display: none;"> We investigate some previously unexplored (or underexplored) computational aspects of total variation (TV) distance. First, we give a simple deterministic polynomial-time algorithm for checking equivalence between mixtures of product distributions, over arbitrary alphabets. This corresponds to a special case, whereby the TV distance between the two distributions is zero. Second, we prove that unless $\mathsf{NP} \subseteq \mathsf{RP}$, it is impossible to efficiently estimate the TV distance between arbitrary Ising models, even in a bounded-error randomized setting. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2412.10370v1-abstract-full').style.display = 'none'; document.getElementById('2412.10370v1-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 December, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> December 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">17 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/2411.14957">arXiv:2411.14957</a> <span> [<a href="https://arxiv.org/pdf/2411.14957">pdf</a>, <a href="https://arxiv.org/format/2411.14957">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computation and Language">cs.CL</span> </div> </div> <p class="title is-5 mathjax"> Information Extraction from Heterogeneous Documents without Ground Truth Labels using Synthetic Label Generation and Knowledge Distillation </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Aniket Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Tripathi%2C+A">Anurag Tripathi</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.14957v2-abstract-short" style="display: inline;"> Invoices and receipts submitted by employees are visually rich documents (VRDs) with textual, visual and layout information. To protect against the risk of fraud and abuse, it is crucial for organizations to efficiently extract desired information from submitted receipts. This helps in the assessment of key factors such as appropriateness of the expense claim, adherence to spending and transaction… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2411.14957v2-abstract-full').style.display = 'inline'; document.getElementById('2411.14957v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2411.14957v2-abstract-full" style="display: none;"> Invoices and receipts submitted by employees are visually rich documents (VRDs) with textual, visual and layout information. To protect against the risk of fraud and abuse, it is crucial for organizations to efficiently extract desired information from submitted receipts. This helps in the assessment of key factors such as appropriateness of the expense claim, adherence to spending and transaction policies, the validity of the receipt, as well as downstream anomaly detection at various levels. These documents are heterogeneous, with multiple formats and languages, uploaded with different image qualities, and often do not contain ground truth labels for the efficient training of models. In this paper we propose Task Aware Instruction-based Labelling (TAIL), a method for synthetic label generation in VRD corpuses without labels, and fine-tune a multimodal Visually Rich Document Understanding Model (VRDU) on TAIL labels using response-based knowledge distillation without using the teacher model's weights or training dataset to conditionally generate annotations in the appropriate format. Using a benchmark external dataset where ground truth labels are available, we demonstrate conditions under which our approach performs at par with Claude 3 Sonnet through empirical studies. We then show that the resulting model performs at par or better on the internal expense documents of a large multinational organization than state-of-the-art LMM (large multimodal model) Claude 3 Sonnet while being 85% less costly and ~5X faster, and outperforms layout-aware baselines by more than 10% in Average Normalized Levenshtein Similarity (ANLS) scores due to its ability to reason and extract information from rare formats. Finally, we illustrate the usage of our approach in overpayment prevention. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2411.14957v2-abstract-full').style.display = 'none'; document.getElementById('2411.14957v2-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 November, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 22 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">Accepted to WACV 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.12700">arXiv:2411.12700</a> <span> [<a href="https://arxiv.org/pdf/2411.12700">pdf</a>, <a href="https://arxiv.org/format/2411.12700">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="Data Structures and Algorithms">cs.DS</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">stat.ML</span> </div> </div> <p class="title is-5 mathjax"> Learning multivariate Gaussians with imperfect advice </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Choo%2C+D">Davin Choo</a>, <a href="/search/cs?searchtype=author&query=John%2C+P+G">Philips George John</a>, <a href="/search/cs?searchtype=author&query=Gouleakis%2C+T">Themis Gouleakis</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.12700v3-abstract-short" style="display: inline;"> We revisit the problem of distribution learning within the framework of learning-augmented algorithms. In this setting, we explore the scenario where a probability distribution is provided as potentially inaccurate advice on the true, unknown distribution. Our objective is to develop learning algorithms whose sample complexity decreases as the quality of the advice improves, thereby surpassing sta… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2411.12700v3-abstract-full').style.display = 'inline'; document.getElementById('2411.12700v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2411.12700v3-abstract-full" style="display: none;"> We revisit the problem of distribution learning within the framework of learning-augmented algorithms. In this setting, we explore the scenario where a probability distribution is provided as potentially inaccurate advice on the true, unknown distribution. Our objective is to develop learning algorithms whose sample complexity decreases as the quality of the advice improves, thereby surpassing standard learning lower bounds when the advice is sufficiently accurate. Specifically, we demonstrate that this outcome is achievable for the problem of learning a multivariate Gaussian distribution $N(\boldsymbol渭, \boldsymbol危)$ in the PAC learning setting. Classically, in the advice-free setting, $\tilde螛(d^2/\varepsilon^2)$ samples are sufficient and worst case necessary to learn $d$-dimensional Gaussians up to TV distance $\varepsilon$ with constant probability. When we are additionally given a parameter $\tilde{\boldsymbol危}$ as advice, we show that $\tilde{O}(d^{2-尾}/\varepsilon^2)$ samples suffices whenever $\| \tilde{\boldsymbol危}^{-1/2} \boldsymbol危 \tilde{\boldsymbol危}^{-1/2} - \boldsymbol{I_d} \|_1 \leq \varepsilon d^{1-尾}$ (where $\|\cdot\|_1$ denotes the entrywise $\ell_1$ norm) for any $尾> 0$, yielding a polynomial improvement over the advice-free setting. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2411.12700v3-abstract-full').style.display = 'none'; document.getElementById('2411.12700v3-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 January, 2025; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 19 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/2411.10982">arXiv:2411.10982</a> <span> [<a href="https://arxiv.org/pdf/2411.10982">pdf</a>, <a href="https://arxiv.org/format/2411.10982">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="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"> Towards a framework on tabular synthetic data generation: a minimalist approach: theory, use cases, and limitations </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Shen%2C+Y">Yueyang Shen</a>, <a href="/search/cs?searchtype=author&query=Sudjianto%2C+A">Agus Sudjianto</a>, <a href="/search/cs?searchtype=author&query=R%2C+A+P">Arun Prakash R</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Anwesha Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Rao%2C+M">Maorong Rao</a>, <a href="/search/cs?searchtype=author&query=Wang%2C+Y">Yaqun Wang</a>, <a href="/search/cs?searchtype=author&query=Vaughan%2C+J">Joel Vaughan</a>, <a href="/search/cs?searchtype=author&query=Zhou%2C+N">Nengfeng Zhou</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.10982v2-abstract-short" style="display: inline;"> We propose and study a minimalist approach towards synthetic tabular data generation. The model consists of a minimalistic unsupervised SparsePCA encoder (with contingent clustering step or log transformation to handle nonlinearity) and XGboost decoder which is SOTA for structured data regression and classification tasks. We study and contrast the methodologies with (variational) autoencoders in s… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2411.10982v2-abstract-full').style.display = 'inline'; document.getElementById('2411.10982v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2411.10982v2-abstract-full" style="display: none;"> We propose and study a minimalist approach towards synthetic tabular data generation. The model consists of a minimalistic unsupervised SparsePCA encoder (with contingent clustering step or log transformation to handle nonlinearity) and XGboost decoder which is SOTA for structured data regression and classification tasks. We study and contrast the methodologies with (variational) autoencoders in several toy low dimensional scenarios to derive necessary intuitions. The framework is applied to high dimensional simulated credit scoring data which parallels real-life financial applications. We applied the method to robustness testing to demonstrate practical use cases. The case study result suggests that the method provides an alternative to raw and quantile perturbation for model robustness testing. We show that the method is simplistic, guarantees interpretability all the way through, does not require extra tuning and provide unique benefits. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2411.10982v2-abstract-full').style.display = 'none'; document.getElementById('2411.10982v2-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 November, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 17 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/2411.10906">arXiv:2411.10906</a> <span> [<a href="https://arxiv.org/pdf/2411.10906">pdf</a>, <a href="https://arxiv.org/format/2411.10906">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="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=John%2C+P+G">Philips George John</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Maniu%2C+S">Silviu Maniu</a>, <a href="/search/cs?searchtype=author&query=Myrisiotis%2C+D">Dimitrios Myrisiotis</a>, <a href="/search/cs?searchtype=author&query=Wu%2C+Z">Zhenan Wu</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.10906v1-abstract-short" style="display: inline;"> Reinforcement learning algorithms are usually stated without theoretical guarantees regarding their performance. Recently, Jin, Yang, Wang, and Jordan (COLT 2020) showed a polynomial-time reinforcement learning algorithm (namely, LSVI-UCB) for the setting of linear Markov decision processes, and provided theoretical guarantees regarding its running time and regret. In real-world scenarios, however… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2411.10906v1-abstract-full').style.display = 'inline'; document.getElementById('2411.10906v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2411.10906v1-abstract-full" style="display: none;"> Reinforcement learning algorithms are usually stated without theoretical guarantees regarding their performance. Recently, Jin, Yang, Wang, and Jordan (COLT 2020) showed a polynomial-time reinforcement learning algorithm (namely, LSVI-UCB) for the setting of linear Markov decision processes, and provided theoretical guarantees regarding its running time and regret. In real-world scenarios, however, the space usage of this algorithm can be prohibitive due to a utilized linear regression step. We propose and analyze two modifications of LSVI-UCB, which alternate periods of learning and not-learning, to reduce space and time usage while maintaining sublinear regret. We show experimentally, on synthetic data and real-world benchmarks, that our algorithms achieve low space usage and running time, while not significantly sacrificing regret. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2411.10906v1-abstract-full').style.display = 'none'; document.getElementById('2411.10906v1-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 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">27 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/2411.09052">arXiv:2411.09052</a> <span> [<a href="https://arxiv.org/pdf/2411.09052">pdf</a>, <a href="https://arxiv.org/format/2411.09052">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Robotics">cs.RO</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"> ClevrSkills: Compositional Language and Visual Reasoning in Robotics </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Haresh%2C+S">Sanjay Haresh</a>, <a href="/search/cs?searchtype=author&query=Dijkman%2C+D">Daniel Dijkman</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Apratim Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Memisevic%2C+R">Roland Memisevic</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.09052v1-abstract-short" style="display: inline;"> Robotics tasks are highly compositional by nature. For example, to perform a high-level task like cleaning the table a robot must employ low-level capabilities of moving the effectors to the objects on the table, pick them up and then move them off the table one-by-one, while re-evaluating the consequently dynamic scenario in the process. Given that large vision language models (VLMs) have shown p… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2411.09052v1-abstract-full').style.display = 'inline'; document.getElementById('2411.09052v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2411.09052v1-abstract-full" style="display: none;"> Robotics tasks are highly compositional by nature. For example, to perform a high-level task like cleaning the table a robot must employ low-level capabilities of moving the effectors to the objects on the table, pick them up and then move them off the table one-by-one, while re-evaluating the consequently dynamic scenario in the process. Given that large vision language models (VLMs) have shown progress on many tasks that require high level, human-like reasoning, we ask the question: if the models are taught the requisite low-level capabilities, can they compose them in novel ways to achieve interesting high-level tasks like cleaning the table without having to be explicitly taught so? To this end, we present ClevrSkills - a benchmark suite for compositional reasoning in robotics. ClevrSkills is an environment suite developed on top of the ManiSkill2 simulator and an accompanying dataset. The dataset contains trajectories generated on a range of robotics tasks with language and visual annotations as well as multi-modal prompts as task specification. The suite includes a curriculum of tasks with three levels of compositional understanding, starting with simple tasks requiring basic motor skills. We benchmark multiple different VLM baselines on ClevrSkills and show that even after being pre-trained on large numbers of tasks, these models fail on compositional reasoning in robotics tasks. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2411.09052v1-abstract-full').style.display = 'none'; document.getElementById('2411.09052v1-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">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">To appear at NeurIPS 2024 (D&B track)</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2408.01300">arXiv:2408.01300</a> <span> [<a href="https://arxiv.org/pdf/2408.01300">pdf</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"> Assessing Robustness of Machine Learning Models using Covariate Perturbations </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=R%2C+A+P">Arun Prakash R</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Anwesha Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Vaughan%2C+J">Joel Vaughan</a>, <a href="/search/cs?searchtype=author&query=Nair%2C+V+N">Vijayan N. Nair</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.01300v1-abstract-short" style="display: inline;"> As machine learning models become increasingly prevalent in critical decision-making models and systems in fields like finance, healthcare, etc., ensuring their robustness against adversarial attacks and changes in the input data is paramount, especially in cases where models potentially overfit. This paper proposes a comprehensive framework for assessing the robustness of machine learning models… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2408.01300v1-abstract-full').style.display = 'inline'; document.getElementById('2408.01300v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2408.01300v1-abstract-full" style="display: none;"> As machine learning models become increasingly prevalent in critical decision-making models and systems in fields like finance, healthcare, etc., ensuring their robustness against adversarial attacks and changes in the input data is paramount, especially in cases where models potentially overfit. This paper proposes a comprehensive framework for assessing the robustness of machine learning models through covariate perturbation techniques. We explore various perturbation strategies to assess robustness and examine their impact on model predictions, including separate strategies for numeric and non-numeric variables, summaries of perturbations to assess and compare model robustness across different scenarios, and local robustness diagnosis to identify any regions in the data where a model is particularly unstable. Through empirical studies on real world dataset, we demonstrate the effectiveness of our approach in comparing robustness across models, identifying the instabilities in the model, and enhancing model robustness. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2408.01300v1-abstract-full').style.display = 'none'; document.getElementById('2408.01300v1-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 August, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> August 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">31 pages, 11 figures, 14 tables</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.08101">arXiv:2407.08101</a> <span> [<a href="https://arxiv.org/pdf/2407.08101">pdf</a>, <a href="https://arxiv.org/format/2407.08101">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computer Vision and Pattern Recognition">cs.CV</span> </div> </div> <p class="title is-5 mathjax"> What to Say and When to Say it: Live Fitness Coaching as a Testbed for Situated Interaction </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Panchal%2C+S">Sunny Panchal</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Apratim Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Berger%2C+G">Guillaume Berger</a>, <a href="/search/cs?searchtype=author&query=Mercier%2C+A">Antoine Mercier</a>, <a href="/search/cs?searchtype=author&query=Bohm%2C+C">Cornelius Bohm</a>, <a href="/search/cs?searchtype=author&query=Dietrichkeit%2C+F">Florian Dietrichkeit</a>, <a href="/search/cs?searchtype=author&query=Pourreza%2C+R">Reza Pourreza</a>, <a href="/search/cs?searchtype=author&query=Li%2C+X">Xuanlin Li</a>, <a href="/search/cs?searchtype=author&query=Madan%2C+P">Pulkit Madan</a>, <a href="/search/cs?searchtype=author&query=Lee%2C+M">Mingu Lee</a>, <a href="/search/cs?searchtype=author&query=Todorovich%2C+M">Mark Todorovich</a>, <a href="/search/cs?searchtype=author&query=Bax%2C+I">Ingo Bax</a>, <a href="/search/cs?searchtype=author&query=Memisevic%2C+R">Roland Memisevic</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.08101v3-abstract-short" style="display: inline;"> Vision-language models have shown impressive progress in recent years. However, existing models are largely limited to turn-based interactions, where each turn must be stepped (i.e., prompted) by the user. Open-ended, asynchronous interactions, where an AI model may proactively deliver timely responses or feedback based on the unfolding situation in real-time, are an open challenge. In this work,… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2407.08101v3-abstract-full').style.display = 'inline'; document.getElementById('2407.08101v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2407.08101v3-abstract-full" style="display: none;"> Vision-language models have shown impressive progress in recent years. However, existing models are largely limited to turn-based interactions, where each turn must be stepped (i.e., prompted) by the user. Open-ended, asynchronous interactions, where an AI model may proactively deliver timely responses or feedback based on the unfolding situation in real-time, are an open challenge. In this work, we present the QEVD benchmark and dataset, which explores human-AI interaction in the challenging, yet controlled, real-world domain of fitness coaching -- a task which intrinsically requires monitoring live user activity and providing immediate feedback. The benchmark requires vision-language models to recognize complex human actions, identify possible mistakes, and provide appropriate feedback in real-time. Our experiments reveal the limitations of existing state-of-the-art vision-language models for such asynchronous situated interactions. Motivated by this, we propose a simple end-to-end streaming baseline that can respond asynchronously to human actions with appropriate feedback at the appropriate time. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2407.08101v3-abstract-full').style.display = 'none'; document.getElementById('2407.08101v3-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 December, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 10 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">Accepted to the 2024 NeurIPS Datasets and Benchmarks track; data and code are available at: https://www.qualcomm.com/developer/software/qevd-dataset and https://github.com/Qualcomm-AI-research/FitCoach</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.00927">arXiv:2407.00927</a> <span> [<a href="https://arxiv.org/pdf/2407.00927">pdf</a>, <a href="https://arxiv.org/ps/2407.00927">ps</a>, <a href="https://arxiv.org/format/2407.00927">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="Computational Complexity">cs.CC</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"> Learnability of Parameter-Bounded Bayes Nets </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Choo%2C+D">Davin Choo</a>, <a href="/search/cs?searchtype=author&query=Gayen%2C+S">Sutanu Gayen</a>, <a href="/search/cs?searchtype=author&query=Myrisiotis%2C+D">Dimitrios Myrisiotis</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.00927v2-abstract-short" style="display: inline;"> Bayes nets are extensively used in practice to efficiently represent joint probability distributions over a set of random variables and capture dependency relations. In a seminal paper, Chickering et al. (JMLR 2004) showed that given a distribution $\mathbb{P}$, that is defined as the marginal distribution of a Bayes net, it is $\mathsf{NP}$-hard to decide whether there is a parameter-bounded Baye… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2407.00927v2-abstract-full').style.display = 'inline'; document.getElementById('2407.00927v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2407.00927v2-abstract-full" style="display: none;"> Bayes nets are extensively used in practice to efficiently represent joint probability distributions over a set of random variables and capture dependency relations. In a seminal paper, Chickering et al. (JMLR 2004) showed that given a distribution $\mathbb{P}$, that is defined as the marginal distribution of a Bayes net, it is $\mathsf{NP}$-hard to decide whether there is a parameter-bounded Bayes net that represents $\mathbb{P}$. They called this problem LEARN. In this work, we extend the $\mathsf{NP}$-hardness result of LEARN and prove the $\mathsf{NP}$-hardness of a promise search variant of LEARN, whereby the Bayes net in question is guaranteed to exist and one is asked to find such a Bayes net. We complement our hardness result with a positive result about the sample complexity that is sufficient to recover a parameter-bounded Bayes net that is close (in TV distance) to a given distribution $\mathbb{P}$, that is represented by some parameter-bounded Bayes net, generalizing a degree-bounded sample complexity result of Brustle et al. (EC 2020). <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2407.00927v2-abstract-full').style.display = 'none'; document.getElementById('2407.00927v2-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 August, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 30 June, 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">15 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/2405.09784">arXiv:2405.09784</a> <span> [<a href="https://arxiv.org/pdf/2405.09784">pdf</a>, <a href="https://arxiv.org/format/2405.09784">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="Data Structures and Algorithms">cs.DS</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 bipartite matching with imperfect advice </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Choo%2C+D">Davin Choo</a>, <a href="/search/cs?searchtype=author&query=Gouleakis%2C+T">Themis Gouleakis</a>, <a href="/search/cs?searchtype=author&query=Ling%2C+C+K">Chun Kai Ling</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</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="2405.09784v3-abstract-short" style="display: inline;"> We study the problem of online unweighted bipartite matching with $n$ offline vertices and $n$ online vertices where one wishes to be competitive against the optimal offline algorithm. While the classic RANKING algorithm of Karp et al. [1990] provably attains competitive ratio of $1-1/e > 1/2$, we show that no learning-augmented method can be both 1-consistent and strictly better than $1/2$-robust… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2405.09784v3-abstract-full').style.display = 'inline'; document.getElementById('2405.09784v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2405.09784v3-abstract-full" style="display: none;"> We study the problem of online unweighted bipartite matching with $n$ offline vertices and $n$ online vertices where one wishes to be competitive against the optimal offline algorithm. While the classic RANKING algorithm of Karp et al. [1990] provably attains competitive ratio of $1-1/e > 1/2$, we show that no learning-augmented method can be both 1-consistent and strictly better than $1/2$-robust under the adversarial arrival model. Meanwhile, under the random arrival model, we show how one can utilize methods from distribution testing to design an algorithm that takes in external advice about the online vertices and provably achieves competitive ratio interpolating between any ratio attainable by advice-free methods and the optimal ratio of 1, depending on the advice quality. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2405.09784v3-abstract-full').style.display = 'none'; document.getElementById('2405.09784v3-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 15 May, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 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">Accepted into ICML 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/2405.08255">arXiv:2405.08255</a> <span> [<a href="https://arxiv.org/pdf/2405.08255">pdf</a>, <a href="https://arxiv.org/ps/2405.08255">ps</a>, <a href="https://arxiv.org/format/2405.08255">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> </div> </div> <p class="title is-5 mathjax"> Total Variation Distance for Product Distributions is $\#\mathsf{P}$-Complete </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Gayen%2C+S">Sutanu Gayen</a>, <a href="/search/cs?searchtype=author&query=Meel%2C+K+S">Kuldeep S. Meel</a>, <a href="/search/cs?searchtype=author&query=Myrisiotis%2C+D">Dimitrios Myrisiotis</a>, <a href="/search/cs?searchtype=author&query=Pavan%2C+A">A. Pavan</a>, <a href="/search/cs?searchtype=author&query=Vinodchandran%2C+N+V">N. V. Vinodchandran</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="2405.08255v1-abstract-short" style="display: inline;"> We show that computing the total variation distance between two product distributions is $\#\mathsf{P}$-complete. This is in stark contrast with other distance measures such as Kullback-Leibler, Chi-square, and Hellinger, which tensorize over the marginals leading to efficient algorithms. </span> <span class="abstract-full has-text-grey-dark mathjax" id="2405.08255v1-abstract-full" style="display: none;"> We show that computing the total variation distance between two product distributions is $\#\mathsf{P}$-complete. This is in stark contrast with other distance measures such as Kullback-Leibler, Chi-square, and Hellinger, which tensorize over the marginals leading to efficient algorithms. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2405.08255v1-abstract-full').style.display = 'none'; document.getElementById('2405.08255v1-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 May, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 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">5 pages. An extended version of this paper appeared in the proceedings of IJCAI 2023, under the title "On approximating total variation distance" (see https://www.ijcai.org/proceedings/2023/387 and arXiv:2206.07209)</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2405.07914">arXiv:2405.07914</a> <span> [<a href="https://arxiv.org/pdf/2405.07914">pdf</a>, <a href="https://arxiv.org/ps/2405.07914">ps</a>, <a href="https://arxiv.org/format/2405.07914">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="Data Structures and Algorithms">cs.DS</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"> Distribution Learning Meets Graph Structure Sampling </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Gayen%2C+S">Sutanu Gayen</a>, <a href="/search/cs?searchtype=author&query=John%2C+P+G">Philips George John</a>, <a href="/search/cs?searchtype=author&query=Sen%2C+S">Sayantan Sen</a>, <a href="/search/cs?searchtype=author&query=Vinodchandran%2C+N+V">N. V. Vinodchandran</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="2405.07914v1-abstract-short" style="display: inline;"> This work establishes a novel link between the problem of PAC-learning high-dimensional graphical models and the task of (efficient) counting and sampling of graph structures, using an online learning framework. We observe that if we apply the exponentially weighted average (EWA) or randomized weighted majority (RWM) forecasters on a sequence of samples from a distribution P using the log loss f… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2405.07914v1-abstract-full').style.display = 'inline'; document.getElementById('2405.07914v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2405.07914v1-abstract-full" style="display: none;"> This work establishes a novel link between the problem of PAC-learning high-dimensional graphical models and the task of (efficient) counting and sampling of graph structures, using an online learning framework. We observe that if we apply the exponentially weighted average (EWA) or randomized weighted majority (RWM) forecasters on a sequence of samples from a distribution P using the log loss function, the average regret incurred by the forecaster's predictions can be used to bound the expected KL divergence between P and the predictions. Known regret bounds for EWA and RWM then yield new sample complexity bounds for learning Bayes nets. Moreover, these algorithms can be made computationally efficient for several interesting classes of Bayes nets. Specifically, we give a new sample-optimal and polynomial time learning algorithm with respect to trees of unknown structure and the first polynomial sample and time algorithm for learning with respect to Bayes nets over a given chordal skeleton. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2405.07914v1-abstract-full').style.display = 'none'; document.getElementById('2405.07914v1-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 May, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 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">48 pages, 2 figures. Shortened abstract as per arXiv criteria</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.09465">arXiv:2403.09465</a> <span> [<a href="https://arxiv.org/pdf/2403.09465">pdf</a>, <a href="https://arxiv.org/format/2403.09465">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</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="Machine Learning">stat.ML</span> </div> </div> <p class="title is-5 mathjax"> Outlier Robust Multivariate Polynomial Regression </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Arora%2C+V">Vipul Arora</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Boban%2C+M">Mathews Boban</a>, <a href="/search/cs?searchtype=author&query=Guruswami%2C+V">Venkatesan Guruswami</a>, <a href="/search/cs?searchtype=author&query=Kelman%2C+E">Esty Kelman</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.09465v1-abstract-short" style="display: inline;"> We study the problem of robust multivariate polynomial regression: let $p\colon\mathbb{R}^n\to\mathbb{R}$ be an unknown $n$-variate polynomial of degree at most $d$ in each variable. We are given as input a set of random samples $(\mathbf{x}_i,y_i) \in [-1,1]^n \times \mathbb{R}$ that are noisy versions of $(\mathbf{x}_i,p(\mathbf{x}_i))$. More precisely, each $\mathbf{x}_i$ is sampled independent… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2403.09465v1-abstract-full').style.display = 'inline'; document.getElementById('2403.09465v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2403.09465v1-abstract-full" style="display: none;"> We study the problem of robust multivariate polynomial regression: let $p\colon\mathbb{R}^n\to\mathbb{R}$ be an unknown $n$-variate polynomial of degree at most $d$ in each variable. We are given as input a set of random samples $(\mathbf{x}_i,y_i) \in [-1,1]^n \times \mathbb{R}$ that are noisy versions of $(\mathbf{x}_i,p(\mathbf{x}_i))$. More precisely, each $\mathbf{x}_i$ is sampled independently from some distribution $蠂$ on $[-1,1]^n$, and for each $i$ independently, $y_i$ is arbitrary (i.e., an outlier) with probability at most $蟻< 1/2$, and otherwise satisfies $|y_i-p(\mathbf{x}_i)|\leq蟽$. The goal is to output a polynomial $\hat{p}$, of degree at most $d$ in each variable, within an $\ell_\infty$-distance of at most $O(蟽)$ from $p$. Kane, Karmalkar, and Price [FOCS'17] solved this problem for $n=1$. We generalize their results to the $n$-variate setting, showing an algorithm that achieves a sample complexity of $O_n(d^n\log d)$, where the hidden constant depends on $n$, if $蠂$ is the $n$-dimensional Chebyshev distribution. The sample complexity is $O_n(d^{2n}\log d)$, if the samples are drawn from the uniform distribution instead. The approximation error is guaranteed to be at most $O(蟽)$, and the run-time depends on $\log(1/蟽)$. In the setting where each $\mathbf{x}_i$ and $y_i$ are known up to $N$ bits of precision, the run-time's dependence on $N$ is linear. We also show that our sample complexities are optimal in terms of $d^n$. Furthermore, we show that it is possible to have the run-time be independent of $1/蟽$, at the cost of a higher sample complexity. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2403.09465v1-abstract-full').style.display = 'none'; document.getElementById('2403.09465v1-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 March, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> March 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.06380">arXiv:2402.06380</a> <span> [<a href="https://arxiv.org/pdf/2402.06380">pdf</a>, <a href="https://arxiv.org/format/2402.06380">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="Machine Learning">stat.ML</span> </div> </div> <p class="title is-5 mathjax"> Optimal estimation of Gaussian (poly)trees </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Wang%2C+Y">Yuhao Wang</a>, <a href="/search/cs?searchtype=author&query=Gao%2C+M">Ming Gao</a>, <a href="/search/cs?searchtype=author&query=Tai%2C+W+M">Wai Ming Tai</a>, <a href="/search/cs?searchtype=author&query=Aragam%2C+B">Bryon Aragam</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</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.06380v1-abstract-short" style="display: inline;"> We develop optimal algorithms for learning undirected Gaussian trees and directed Gaussian polytrees from data. We consider both problems of distribution learning (i.e. in KL distance) and structure learning (i.e. exact recovery). The first approach is based on the Chow-Liu algorithm, and learns an optimal tree-structured distribution efficiently. The second approach is a modification of the PC al… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2402.06380v1-abstract-full').style.display = 'inline'; document.getElementById('2402.06380v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2402.06380v1-abstract-full" style="display: none;"> We develop optimal algorithms for learning undirected Gaussian trees and directed Gaussian polytrees from data. We consider both problems of distribution learning (i.e. in KL distance) and structure learning (i.e. exact recovery). The first approach is based on the Chow-Liu algorithm, and learns an optimal tree-structured distribution efficiently. The second approach is a modification of the PC algorithm for polytrees that uses partial correlation as a conditional independence tester for constraint-based structure learning. We derive explicit finite-sample guarantees for both approaches, and show that both approaches are optimal by deriving matching lower bounds. Additionally, we conduct numerical experiments to compare the performance of various algorithms, providing further insights and empirical evidence. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2402.06380v1-abstract-full').style.display = 'none'; document.getElementById('2402.06380v1-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 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/2401.07308">arXiv:2401.07308</a> <span> [<a href="https://arxiv.org/pdf/2401.07308">pdf</a>, <a href="https://arxiv.org/ps/2401.07308">ps</a>, <a href="https://arxiv.org/format/2401.07308">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Distributed, Parallel, and Cluster Computing">cs.DC</span> </div> </div> <p class="title is-5 mathjax"> Structured Acyclic Nets </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Alahmadi%2C+M">Mohammed Alahmadi</a>, <a href="/search/cs?searchtype=author&query=Alharbi%2C+S">Salma Alharbi</a>, <a href="/search/cs?searchtype=author&query=Alharbi%2C+T">Talal Alharbi</a>, <a href="/search/cs?searchtype=author&query=Almutairi%2C+N">Nadiyah Almutairi</a>, <a href="/search/cs?searchtype=author&query=Alshammari%2C+T">Tuwailaa Alshammari</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Anirban Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Koutny%2C+M">Maciej Koutny</a>, <a href="/search/cs?searchtype=author&query=Li%2C+B">Bowen Li</a>, <a href="/search/cs?searchtype=author&query=Randell%2C+B">Brian Randell</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.07308v1-abstract-short" style="display: inline;"> The concept of structured occurrence nets is an extension of that of occurrence nets which are directed acyclic graphs that represent causality and concurrency information concerning a single execution of a distributed system. The formalism of structured occurrence nets has been introduced to facilitate the portrayal and analysis of the behaviours, and in particular failures, of complex evolving s… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2401.07308v1-abstract-full').style.display = 'inline'; document.getElementById('2401.07308v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2401.07308v1-abstract-full" style="display: none;"> The concept of structured occurrence nets is an extension of that of occurrence nets which are directed acyclic graphs that represent causality and concurrency information concerning a single execution of a distributed system. The formalism of structured occurrence nets has been introduced to facilitate the portrayal and analysis of the behaviours, and in particular failures, of complex evolving systems. Such systems are composed of a large number of sub-systems which may proceed concurrently and interact with each other and with the external environment while their behaviour is subject to modification by other systems. The purpose of this paper is to provide an extension of structured occurrence nets to include models built up of acyclic nets rather than occurrence nets. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2401.07308v1-abstract-full').style.display = 'none'; document.getElementById('2401.07308v1-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 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/2310.11394">arXiv:2310.11394</a> <span> [<a href="https://arxiv.org/pdf/2310.11394">pdf</a>, <a href="https://arxiv.org/format/2310.11394">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Quantum Physics">quant-ph</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computational Engineering, Finance, and Science">cs.CE</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.1177/29767032231217444">10.1177/29767032231217444 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Quantum Financial Modeling on Noisy Intermediate-Scale Quantum Hardware: Random Walks using Approximate Quantum Counting </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Widdows%2C+D">Dominic Widdows</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Amit Bhattacharyya</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.11394v2-abstract-short" style="display: inline;"> Quantum computers are expected to contribute more efficient and accurate ways of modeling economic processes. Quantum hardware is currently available at a relatively small scale, but effective algorithms are limited by the number of logic gates that can be used, before noise from gate inaccuracies tends to dominate results. Some theoretical algorithms that have been proposed and studied for years… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2310.11394v2-abstract-full').style.display = 'inline'; document.getElementById('2310.11394v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2310.11394v2-abstract-full" style="display: none;"> Quantum computers are expected to contribute more efficient and accurate ways of modeling economic processes. Quantum hardware is currently available at a relatively small scale, but effective algorithms are limited by the number of logic gates that can be used, before noise from gate inaccuracies tends to dominate results. Some theoretical algorithms that have been proposed and studied for years do not perform well yet on quantum hardware in practice. This encourages the development of suitable alternative algorithms that play similar roles in limited contexts. This paper implements this strategy in the case of quantum counting, which is used as a component for keeping track of position in a quantum walk, which is used as a model for simulating asset prices over time. We introduce quantum approximate counting circuits that use far fewer 2-qubit entangling gates than traditional quantum counting that relies on binary positional encoding. The robustness of these circuits to noise is demonstrated. We compare the results to price change distributions from stock indices, and compare the behavior of quantum circuits with and without mid-measurement to trends in the housing market. The housing data shows that low liquidity brings price volatility, as expected with the quantum models. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2310.11394v2-abstract-full').style.display = 'none'; document.getElementById('2310.11394v2-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 December, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 17 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">Journal ref:</span> Quantum Economics and Finance, 2024 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2310.06333">arXiv:2310.06333</a> <span> [<a href="https://arxiv.org/pdf/2310.06333">pdf</a>, <a href="https://arxiv.org/ps/2310.06333">ps</a>, <a href="https://arxiv.org/format/2310.06333">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="Data Structures and Algorithms">cs.DS</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"> Learning bounded-degree polytrees with known skeleton </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Choo%2C+D">Davin Choo</a>, <a href="/search/cs?searchtype=author&query=Yang%2C+J+Q">Joy Qiping Yang</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Canonne%2C+C+L">Cl茅ment L. Canonne</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.06333v2-abstract-short" style="display: inline;"> We establish finite-sample guarantees for efficient proper learning of bounded-degree polytrees, a rich class of high-dimensional probability distributions and a subclass of Bayesian networks, a widely-studied type of graphical model. Recently, Bhattacharyya et al. (2021) obtained finite-sample guarantees for recovering tree-structured Bayesian networks, i.e., 1-polytrees. We extend their results… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2310.06333v2-abstract-full').style.display = 'inline'; document.getElementById('2310.06333v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2310.06333v2-abstract-full" style="display: none;"> We establish finite-sample guarantees for efficient proper learning of bounded-degree polytrees, a rich class of high-dimensional probability distributions and a subclass of Bayesian networks, a widely-studied type of graphical model. Recently, Bhattacharyya et al. (2021) obtained finite-sample guarantees for recovering tree-structured Bayesian networks, i.e., 1-polytrees. We extend their results by providing an efficient algorithm which learns $d$-polytrees in polynomial time and sample complexity for any bounded $d$ when the underlying undirected graph (skeleton) is known. We complement our algorithm with an information-theoretic sample complexity lower bound, showing that the dependence on the dimension and target accuracy parameters are nearly tight. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2310.06333v2-abstract-full').style.display = 'none'; document.getElementById('2310.06333v2-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 January, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 10 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">Fixed some typos. Added some discussions. Accepted to ALT 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/2309.09134">arXiv:2309.09134</a> <span> [<a href="https://arxiv.org/pdf/2309.09134">pdf</a>, <a href="https://arxiv.org/ps/2309.09134">ps</a>, <a href="https://arxiv.org/format/2309.09134">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</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"> Total Variation Distance Meets Probabilistic Inference </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Gayen%2C+S">Sutanu Gayen</a>, <a href="/search/cs?searchtype=author&query=Meel%2C+K+S">Kuldeep S. Meel</a>, <a href="/search/cs?searchtype=author&query=Myrisiotis%2C+D">Dimitrios Myrisiotis</a>, <a href="/search/cs?searchtype=author&query=Pavan%2C+A">A. Pavan</a>, <a href="/search/cs?searchtype=author&query=Vinodchandran%2C+N+V">N. V. Vinodchandran</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.09134v2-abstract-short" style="display: inline;"> In this paper, we establish a novel connection between total variation (TV) distance estimation and probabilistic inference. In particular, we present an efficient, structure-preserving reduction from relative approximation of TV distance to probabilistic inference over directed graphical models. This reduction leads to a fully polynomial randomized approximation scheme (FPRAS) for estimating TV d… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2309.09134v2-abstract-full').style.display = 'inline'; document.getElementById('2309.09134v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2309.09134v2-abstract-full" style="display: none;"> In this paper, we establish a novel connection between total variation (TV) distance estimation and probabilistic inference. In particular, we present an efficient, structure-preserving reduction from relative approximation of TV distance to probabilistic inference over directed graphical models. This reduction leads to a fully polynomial randomized approximation scheme (FPRAS) for estimating TV distances between same-structure distributions over any class of Bayes nets for which there is an efficient probabilistic inference algorithm. In particular, it leads to an FPRAS for estimating TV distances between distributions that are defined over a common Bayes net of small treewidth. Prior to this work, such approximation schemes only existed for estimating TV distances between product distributions. Our approach employs a new notion of $partial$ couplings of high-dimensional distributions, which might be of independent interest. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2309.09134v2-abstract-full').style.display = 'none'; document.getElementById('2309.09134v2-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> 1 July, 2024; <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">25 pages. This work has been accepted for presentation at the International Conference on Machine Learning (ICML) 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/2309.00378">arXiv:2309.00378</a> <span> [<a href="https://arxiv.org/pdf/2309.00378">pdf</a>, <a href="https://arxiv.org/format/2309.00378">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computation and Language">cs.CL</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computer Vision and Pattern Recognition">cs.CV</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Human-Computer Interaction">cs.HC</span> </div> </div> <p class="title is-5 mathjax"> Long-Term Ad Memorability: Understanding & Generating Memorable Ads </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=SI%2C+H">Harini SI</a>, <a href="/search/cs?searchtype=author&query=Singh%2C+S">Somesh Singh</a>, <a href="/search/cs?searchtype=author&query=Singla%2C+Y+K">Yaman K Singla</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Aanisha Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Baths%2C+V">Veeky Baths</a>, <a href="/search/cs?searchtype=author&query=Chen%2C+C">Changyou Chen</a>, <a href="/search/cs?searchtype=author&query=Shah%2C+R+R">Rajiv Ratn Shah</a>, <a href="/search/cs?searchtype=author&query=Krishnamurthy%2C+B">Balaji Krishnamurthy</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.00378v5-abstract-short" style="display: inline;"> Despite the importance of long-term memory in marketing and brand building, until now, there has been no large-scale study on the memorability of ads. All previous memorability studies have been conducted on short-term recall on specific content types like action videos. On the other hand, long-term memorability is crucial for the advertising industry, and ads are almost always highly multimodal.… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2309.00378v5-abstract-full').style.display = 'inline'; document.getElementById('2309.00378v5-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2309.00378v5-abstract-full" style="display: none;"> Despite the importance of long-term memory in marketing and brand building, until now, there has been no large-scale study on the memorability of ads. All previous memorability studies have been conducted on short-term recall on specific content types like action videos. On the other hand, long-term memorability is crucial for the advertising industry, and ads are almost always highly multimodal. Therefore, we release the first memorability dataset, LAMBDA, consisting of 1749 participants and 2205 ads covering 276 brands. Running statistical tests over different participant subpopulations and ad types, we find many interesting insights into what makes an ad memorable, e.g., fast-moving ads are more memorable than those with slower scenes; people who use ad-blockers remember a lower number of ads than those who don't. Next, we present a model, Henry, to predict the memorability of a content. Henry achieves state-of-the-art performance across all prominent literature memorability datasets. It shows strong generalization performance with better results in 0-shot on unseen datasets. Finally, with the intent of memorable ad generation, we present a scalable method to build a high-quality memorable ad generation model by leveraging automatically annotated data. Our approach, SEED (Self rEwarding mEmorability Modeling), starts with a language model trained on LAMBDA as seed data and progressively trains an LLM to generate more memorable ads. We show that the generated advertisements have 44% higher memorability scores than the original ads. We release this large-scale ad dataset, UltraLAMBDA, consisting of 5 million ads. Our code and the datasets, LAMBDA and UltraLAMBDA, are open-sourced at https://behavior-in-the-wild.github.io/memorability. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2309.00378v5-abstract-full').style.display = 'none'; document.getElementById('2309.00378v5-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 November, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 1 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">Published in WACV-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/2309.00359">arXiv:2309.00359</a> <span> [<a href="https://arxiv.org/pdf/2309.00359">pdf</a>, <a href="https://arxiv.org/format/2309.00359">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computation and Language">cs.CL</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computer Vision and Pattern Recognition">cs.CV</span> </div> </div> <p class="title is-5 mathjax"> Large Content And Behavior Models To Understand, Simulate, And Optimize Content And Behavior </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Khandelwal%2C+A">Ashmit Khandelwal</a>, <a href="/search/cs?searchtype=author&query=Agrawal%2C+A">Aditya Agrawal</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Aanisha Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Singla%2C+Y+K">Yaman K Singla</a>, <a href="/search/cs?searchtype=author&query=Singh%2C+S">Somesh Singh</a>, <a href="/search/cs?searchtype=author&query=Bhattacharya%2C+U">Uttaran Bhattacharya</a>, <a href="/search/cs?searchtype=author&query=Dasgupta%2C+I">Ishita Dasgupta</a>, <a href="/search/cs?searchtype=author&query=Petrangeli%2C+S">Stefano Petrangeli</a>, <a href="/search/cs?searchtype=author&query=Shah%2C+R+R">Rajiv Ratn Shah</a>, <a href="/search/cs?searchtype=author&query=Chen%2C+C">Changyou Chen</a>, <a href="/search/cs?searchtype=author&query=Krishnamurthy%2C+B">Balaji Krishnamurthy</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.00359v4-abstract-short" style="display: inline;"> Shannon and Weaver's seminal information theory divides communication into three levels: technical, semantic, and effectiveness. While the technical level deals with the accurate reconstruction of transmitted symbols, the semantic and effectiveness levels deal with the inferred meaning and its effect on the receiver. Large Language Models (LLMs), with their wide generalizability, make some progres… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2309.00359v4-abstract-full').style.display = 'inline'; document.getElementById('2309.00359v4-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2309.00359v4-abstract-full" style="display: none;"> Shannon and Weaver's seminal information theory divides communication into three levels: technical, semantic, and effectiveness. While the technical level deals with the accurate reconstruction of transmitted symbols, the semantic and effectiveness levels deal with the inferred meaning and its effect on the receiver. Large Language Models (LLMs), with their wide generalizability, make some progress towards the second level. However, LLMs and other communication models are not conventionally designed for predicting and optimizing communication for desired receiver behaviors and intents. As a result, the effectiveness level remains largely untouched by modern communication systems. In this paper, we introduce the receivers' "behavior tokens," such as shares, likes, clicks, purchases, and retweets, in the LLM's training corpora to optimize content for the receivers and predict their behaviors. Other than showing similar performance to LLMs on content understanding tasks, our trained models show generalization capabilities on the behavior dimension for behavior simulation, content simulation, behavior understanding, and behavior domain adaptation. We show results on all these capabilities using a wide range of tasks on three corpora. We call these models Large Content and Behavior Models (LCBMs). Further, to spur more research on LCBMs, we release our new Content Behavior Corpus (CBC), a repository containing communicator, message, and corresponding receiver behavior (https://behavior-in-the-wild.github.io/LCBM). <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2309.00359v4-abstract-full').style.display = 'none'; document.getElementById('2309.00359v4-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 March, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 1 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/2308.10858">arXiv:2308.10858</a> <span> [<a href="https://arxiv.org/pdf/2308.10858">pdf</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computational Engineering, Finance, and Science">cs.CE</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.1002/nme.7613">10.1002/nme.7613 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Compliant Mechanism Synthesis Using Nonlinear Elastic Topology Optimization with Variable Boundary Conditions </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Alacoque%2C+L+R">Lee R. Alacoque</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Anurag Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=James%2C+K+A">Kai A. James</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="2308.10858v2-abstract-short" style="display: inline;"> In topology optimization of compliant mechanisms, the specific placement of boundary conditions strongly affects the resulting material distribution and performance of the design. At the same time, the most effective locations of the loads and supports are often difficult to find manually. This substantially limits topology optimization's effectiveness for many mechanism design problems. We remove… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2308.10858v2-abstract-full').style.display = 'inline'; document.getElementById('2308.10858v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2308.10858v2-abstract-full" style="display: none;"> In topology optimization of compliant mechanisms, the specific placement of boundary conditions strongly affects the resulting material distribution and performance of the design. At the same time, the most effective locations of the loads and supports are often difficult to find manually. This substantially limits topology optimization's effectiveness for many mechanism design problems. We remove this limitation by developing a method which automatically determines optimal positioning of a prescribed input displacement and a set of supports simultaneously with an optimal material layout. Using nonlinear elastic physics, we synthesize a variety of compliant mechanisms with large output displacements, snap-through responses, and prescribed output paths, producing designs with significantly improved performance in every case tested. Compared to optimal designs generated using best-guess boundary conditions used in previous studies, the mechanisms presented in this paper see performance increases ranging from 47%-380%. The results show that nonlinear mechanism responses may be particularly sensitive to boundary condition locations and that effective placements can be difficult to find without an automated method. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2308.10858v2-abstract-full').style.display = 'none'; document.getElementById('2308.10858v2-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, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 21 August, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> August 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">30 pages, 14 figures, 4 tables. Version 2: Corrected an error in the formulation of the strain energy interpolation scheme, leading to minor changes in the results. International Journal for Numerical Methods in Engineering. 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/2308.08520">arXiv:2308.08520</a> <span> [<a href="https://arxiv.org/pdf/2308.08520">pdf</a>, <a href="https://arxiv.org/format/2308.08520">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computer Vision and Pattern Recognition">cs.CV</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"> Painter: Teaching Auto-regressive Language Models to Draw Sketches </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Pourreza%2C+R">Reza Pourreza</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Apratim Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Panchal%2C+S">Sunny Panchal</a>, <a href="/search/cs?searchtype=author&query=Lee%2C+M">Mingu Lee</a>, <a href="/search/cs?searchtype=author&query=Madan%2C+P">Pulkit Madan</a>, <a href="/search/cs?searchtype=author&query=Memisevic%2C+R">Roland Memisevic</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="2308.08520v1-abstract-short" style="display: inline;"> Large language models (LLMs) have made tremendous progress in natural language understanding and they have also been successfully adopted in other domains such as computer vision, robotics, reinforcement learning, etc. In this work, we apply LLMs to image generation tasks by directly generating the virtual brush strokes to paint an image. We present Painter, an LLM that can convert user prompts in… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2308.08520v1-abstract-full').style.display = 'inline'; document.getElementById('2308.08520v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2308.08520v1-abstract-full" style="display: none;"> Large language models (LLMs) have made tremendous progress in natural language understanding and they have also been successfully adopted in other domains such as computer vision, robotics, reinforcement learning, etc. In this work, we apply LLMs to image generation tasks by directly generating the virtual brush strokes to paint an image. We present Painter, an LLM that can convert user prompts in text description format to sketches by generating the corresponding brush strokes in an auto-regressive way. We construct Painter based on off-the-shelf LLM that is pre-trained on a large text corpus, by fine-tuning it on the new task while preserving language understanding capabilities. We create a dataset of diverse multi-object sketches paired with textual prompts that covers several object types and tasks. Painter can generate sketches from text descriptions, remove objects from canvas, and detect and classify objects in sketches. Although this is an unprecedented pioneering work in using LLMs for auto-regressive image generation, the results are very encouraging. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2308.08520v1-abstract-full').style.display = 'none'; document.getElementById('2308.08520v1-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">originally announced</span> August 2023. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2306.17778">arXiv:2306.17778</a> <span> [<a href="https://arxiv.org/pdf/2306.17778">pdf</a>, <a href="https://arxiv.org/format/2306.17778">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computer Vision and Pattern Recognition">cs.CV</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"> Look, Remember and Reason: Grounded reasoning in videos with language models </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Apratim Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Panchal%2C+S">Sunny Panchal</a>, <a href="/search/cs?searchtype=author&query=Lee%2C+M">Mingu Lee</a>, <a href="/search/cs?searchtype=author&query=Pourreza%2C+R">Reza Pourreza</a>, <a href="/search/cs?searchtype=author&query=Madan%2C+P">Pulkit Madan</a>, <a href="/search/cs?searchtype=author&query=Memisevic%2C+R">Roland Memisevic</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.17778v3-abstract-short" style="display: inline;"> Multi-modal language models (LM) have recently shown promising performance in high-level reasoning tasks on videos. However, existing methods still fall short in tasks like causal or compositional spatiotemporal reasoning over actions, in which model predictions need to be grounded in fine-grained low-level details, such as object motions and object interactions. In this work, we propose training… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2306.17778v3-abstract-full').style.display = 'inline'; document.getElementById('2306.17778v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2306.17778v3-abstract-full" style="display: none;"> Multi-modal language models (LM) have recently shown promising performance in high-level reasoning tasks on videos. However, existing methods still fall short in tasks like causal or compositional spatiotemporal reasoning over actions, in which model predictions need to be grounded in fine-grained low-level details, such as object motions and object interactions. In this work, we propose training an LM end-to-end on low-level surrogate tasks, including object detection, re-identification, and tracking, to endow the model with the required low-level visual capabilities. We show that a two-stream video encoder with spatiotemporal attention is effective at capturing the required static and motion-based cues in the video. By leveraging the LM's ability to perform the low-level surrogate tasks, we can cast reasoning in videos as the three-step process of Look, Remember, Reason wherein visual information is extracted using low-level visual skills step-by-step and then integrated to arrive at a final answer. We demonstrate the effectiveness of our framework on diverse visual reasoning tasks from the ACRE, CATER, Something-Else and STAR datasets. Our approach is trainable end-to-end and surpasses state-of-the-art task-specific methods across these tasks by a large margin. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2306.17778v3-abstract-full').style.display = 'none'; document.getElementById('2306.17778v3-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 January, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 30 June, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> June 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">To appear at ICLR 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/2306.00233">arXiv:2306.00233</a> <span> [<a href="https://arxiv.org/pdf/2306.00233">pdf</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computational Engineering, Finance, and Science">cs.CE</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Adaptation and Self-Organizing Systems">nlin.AO</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.1115/1.4063970">10.1115/1.4063970 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Bio-Inspired 4D-Printed Mechanisms with Programmable Morphology </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Anurag Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Kim%2C+J">Jin-Young Kim</a>, <a href="/search/cs?searchtype=author&query=Alacoque%2C+L+R">Lee R. Alacoque</a>, <a href="/search/cs?searchtype=author&query=James%2C+K+A">Kai A. James</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.00233v1-abstract-short" style="display: inline;"> Traditional robotic mechanisms contain a series of rigid links connected by rotational joints that provide powered motion, all of which is controlled by a central processor. By contrast, analogous mechanisms found in nature, such as octopus tentacles, contain sensors, actuators, and even neurons distributed throughout the appendage, thereby allowing for motion with superior complexity, fluidity, a… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2306.00233v1-abstract-full').style.display = 'inline'; document.getElementById('2306.00233v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2306.00233v1-abstract-full" style="display: none;"> Traditional robotic mechanisms contain a series of rigid links connected by rotational joints that provide powered motion, all of which is controlled by a central processor. By contrast, analogous mechanisms found in nature, such as octopus tentacles, contain sensors, actuators, and even neurons distributed throughout the appendage, thereby allowing for motion with superior complexity, fluidity, and reaction time. Smart materials provide a means with which we can mimic these features artificially. These specialized materials undergo shape change in response to changes in their environment. Previous studies have developed material-based actuators that could produce targeted shape changes. Here we extend this capability by introducing a novel computational and experimental method for design and synthesis of material-based morphing mechanisms capable of achieving complex pre-programmed motion. By combining active and passive materials, the algorithm can encode the desired movement into the material distribution of the mechanism. We demonstrate this new capability by de novo design of a 3D printed self-tying knot. This method advances a new paradigm in mechanism design that could enable a new generation of material-driven machines that are lightweight, adaptable, robust to damage, and easily manufacturable by 3D printing. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2306.00233v1-abstract-full').style.display = 'none'; document.getElementById('2306.00233v1-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 May, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> June 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Report number:</span> MD-23-1418 </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> J. Mech. Des. 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.19588">arXiv:2305.19588</a> <span> [<a href="https://arxiv.org/pdf/2305.19588">pdf</a>, <a href="https://arxiv.org/format/2305.19588">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="Data Structures and Algorithms">cs.DS</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"> Active causal structure learning with advice </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Choo%2C+D">Davin Choo</a>, <a href="/search/cs?searchtype=author&query=Gouleakis%2C+T">Themis Gouleakis</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</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.19588v1-abstract-short" style="display: inline;"> We introduce the problem of active causal structure learning with advice. In the typical well-studied setting, the learning algorithm is given the essential graph for the observational distribution and is asked to recover the underlying causal directed acyclic graph (DAG) $G^*$ while minimizing the number of interventions made. In our setting, we are additionally given side information about… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.19588v1-abstract-full').style.display = 'inline'; document.getElementById('2305.19588v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2305.19588v1-abstract-full" style="display: none;"> We introduce the problem of active causal structure learning with advice. In the typical well-studied setting, the learning algorithm is given the essential graph for the observational distribution and is asked to recover the underlying causal directed acyclic graph (DAG) $G^*$ while minimizing the number of interventions made. In our setting, we are additionally given side information about $G^*$ as advice, e.g. a DAG $G$ purported to be $G^*$. We ask whether the learning algorithm can benefit from the advice when it is close to being correct, while still having worst-case guarantees even when the advice is arbitrarily bad. Our work is in the same space as the growing body of research on algorithms with predictions. When the advice is a DAG $G$, we design an adaptive search algorithm to recover $G^*$ whose intervention cost is at most $O(\max\{1, \log 蠄\})$ times the cost for verifying $G^*$; here, $蠄$ is a distance measure between $G$ and $G^*$ that is upper bounded by the number of variables $n$, and is exactly 0 when $G=G^*$. Our approximation factor matches the state-of-the-art for the advice-less setting. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.19588v1-abstract-full').style.display = 'none'; document.getElementById('2305.19588v1-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 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 into ICML 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/2304.06733">arXiv:2304.06733</a> <span> [<a href="https://arxiv.org/pdf/2304.06733">pdf</a>, <a href="https://arxiv.org/ps/2304.06733">ps</a>, <a href="https://arxiv.org/format/2304.06733">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="Data Structures and Algorithms">cs.DS</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="Statistics Theory">math.ST</span> </div> </div> <p class="title is-5 mathjax"> Near-Optimal Degree Testing for Bayes Nets </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Arora%2C+V">Vipul Arora</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Canonne%2C+C+L">Cl茅ment L. Canonne</a>, <a href="/search/cs?searchtype=author&query=Yang%2C+J+Q">Joy Qiping Yang</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.06733v1-abstract-short" style="display: inline;"> This paper considers the problem of testing the maximum in-degree of the Bayes net underlying an unknown probability distribution $P$ over $\{0,1\}^n$, given sample access to $P$. We show that the sample complexity of the problem is $\tilde螛(2^{n/2}/\varepsilon^2)$. Our algorithm relies on a testing-by-learning framework, previously used to obtain sample-optimal testers; in order to apply this fra… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2304.06733v1-abstract-full').style.display = 'inline'; document.getElementById('2304.06733v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2304.06733v1-abstract-full" style="display: none;"> This paper considers the problem of testing the maximum in-degree of the Bayes net underlying an unknown probability distribution $P$ over $\{0,1\}^n$, given sample access to $P$. We show that the sample complexity of the problem is $\tilde螛(2^{n/2}/\varepsilon^2)$. Our algorithm relies on a testing-by-learning framework, previously used to obtain sample-optimal testers; in order to apply this framework, we develop new algorithms for ``near-proper'' learning of Bayes nets, and high-probability learning under $蠂^2$ divergence, which are of independent interest. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2304.06733v1-abstract-full').style.display = 'none'; document.getElementById('2304.06733v1-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> 12 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.12937">arXiv:2302.12937</a> <span> [<a href="https://arxiv.org/pdf/2302.12937">pdf</a>, <a href="https://arxiv.org/ps/2302.12937">ps</a>, <a href="https://arxiv.org/format/2302.12937">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Logic in Computer Science">cs.LO</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Databases">cs.DB</span> </div> </div> <p class="title is-5 mathjax"> Constraint Optimization over Semirings </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Pavan%2C+A">A. Pavan</a>, <a href="/search/cs?searchtype=author&query=Meel%2C+K+S">Kuldeep S. Meel</a>, <a href="/search/cs?searchtype=author&query=Vinodchandran%2C+N+V">N. V. Vinodchandran</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</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.12937v1-abstract-short" style="display: inline;"> Interpretations of logical formulas over semirings have applications in various areas of computer science including logic, AI, databases, and security. Such interpretations provide richer information beyond the truth or falsity of a statement. Examples of such semirings include Viterbi semiring, min-max or access control semiring, tropical semiring, and fuzzy semiring. The present work investiga… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2302.12937v1-abstract-full').style.display = 'inline'; document.getElementById('2302.12937v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2302.12937v1-abstract-full" style="display: none;"> Interpretations of logical formulas over semirings have applications in various areas of computer science including logic, AI, databases, and security. Such interpretations provide richer information beyond the truth or falsity of a statement. Examples of such semirings include Viterbi semiring, min-max or access control semiring, tropical semiring, and fuzzy semiring. The present work investigates the complexity of constraint optimization problems over semirings. The generic optimization problem we study is the following: Given a propositional formula $\varphi$ over $n$ variable and a semiring $(K,+,\cdot,0,1)$, find the maximum value over all possible interpretations of $\varphi$ over $K$. This can be seen as a generalization of the well-known satisfiability problem. A related problem is to find an interpretation that achieves the maximum value. In this work, we first focus on these optimization problems over the Viterbi semiring, which we call optConfVal and optConf. We show that for general propositional formulas in negation normal form, optConfVal and optConf are in ${\mathrm{FP}}^{\mathrm{NP}}$. We investigate optConf when the input formula $\varphi$ is represented as a CNF. For CNF formulae, we first derive an upper bound on optConfVal as a function of the number of maximum satisfiable clauses. In particular, we show that if $r$ is the maximum number of satisfiable clauses in a CNF formula with $m$ clauses, then its optConfVal is at most $1/4^{m-r}$. Building on this we establish that optConfVal for CNF formulae is hard for the complexity class ${\mathrm{FP}}^{\mathrm{NP}[\log]}$. We also design polynomial-time approximation algorithms and establish an inapproximability for optConfVal. We establish similar complexity results for these optimization problems over other semirings including tropical, fuzzy, and access control semirings. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2302.12937v1-abstract-full').style.display = 'none'; document.getElementById('2302.12937v1-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 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">Appeared in AAAI 23</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">ACM Class:</span> F.4.1; F.1.3 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2302.05380">arXiv:2302.05380</a> <span> [<a href="https://arxiv.org/pdf/2302.05380">pdf</a>, <a href="https://arxiv.org/format/2302.05380">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> </div> </div> <p class="title is-5 mathjax"> On the Interventional Kullback-Leibler Divergence </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Wildberger%2C+J">Jonas Wildberger</a>, <a href="/search/cs?searchtype=author&query=Guo%2C+S">Siyuan Guo</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Sch%C3%B6lkopf%2C+B">Bernhard Sch枚lkopf</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.05380v1-abstract-short" style="display: inline;"> Modern machine learning approaches excel in static settings where a large amount of i.i.d. training data are available for a given task. In a dynamic environment, though, an intelligent agent needs to be able to transfer knowledge and re-use learned components across domains. It has been argued that this may be possible through causal models, aiming to mirror the modularity of the real world in te… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2302.05380v1-abstract-full').style.display = 'inline'; document.getElementById('2302.05380v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2302.05380v1-abstract-full" style="display: none;"> Modern machine learning approaches excel in static settings where a large amount of i.i.d. training data are available for a given task. In a dynamic environment, though, an intelligent agent needs to be able to transfer knowledge and re-use learned components across domains. It has been argued that this may be possible through causal models, aiming to mirror the modularity of the real world in terms of independent causal mechanisms. However, the true causal structure underlying a given set of data is generally not identifiable, so it is desirable to have means to quantify differences between models (e.g., between the ground truth and an estimate), on both the observational and interventional level. In the present work, we introduce the Interventional Kullback-Leibler (IKL) divergence to quantify both structural and distributional differences between models based on a finite set of multi-environment distributions generated by interventions from the ground truth. Since we generally cannot quantify all differences between causal models for every finite set of interventional distributions, we propose a sufficient condition on the intervention targets to identify subsets of observed variables on which the models provably agree or disagree. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2302.05380v1-abstract-full').style.display = 'none'; document.getElementById('2302.05380v1-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 February, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2023. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2301.00346">arXiv:2301.00346</a> <span> [<a href="https://arxiv.org/pdf/2301.00346">pdf</a>, <a href="https://arxiv.org/format/2301.00346">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="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 Adaptive Kernel Approach to Federated Learning of Heterogeneous Causal Effects </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Vo%2C+T+V">Thanh Vinh Vo</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Lee%2C+Y">Young Lee</a>, <a href="/search/cs?searchtype=author&query=Leong%2C+T">Tze-Yun Leong</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.00346v1-abstract-short" style="display: inline;"> We propose a new causal inference framework to learn causal effects from multiple, decentralized data sources in a federated setting. We introduce an adaptive transfer algorithm that learns the similarities among the data sources by utilizing Random Fourier Features to disentangle the loss function into multiple components, each of which is associated with a data source. The data sources may have… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2301.00346v1-abstract-full').style.display = 'inline'; document.getElementById('2301.00346v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2301.00346v1-abstract-full" style="display: none;"> We propose a new causal inference framework to learn causal effects from multiple, decentralized data sources in a federated setting. We introduce an adaptive transfer algorithm that learns the similarities among the data sources by utilizing Random Fourier Features to disentangle the loss function into multiple components, each of which is associated with a data source. The data sources may have different distributions; the causal effects are independently and systematically incorporated. The proposed method estimates the similarities among the sources through transfer coefficients, and hence requiring no prior information about the similarity measures. The heterogeneous causal effects can be estimated with no sharing of the raw training data among the sources, thus minimizing the risk of privacy leak. We also provide minimax lower bounds to assess the quality of the parameters learned from the disparate sources. The proposed method is empirically shown to outperform the baselines on decentralized data sources with dissimilar distributions. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2301.00346v1-abstract-full').style.display = 'none'; document.getElementById('2301.00346v1-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 December, 2022; <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">NeurIPS 2022</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2211.08536">arXiv:2211.08536</a> <span> [<a href="https://arxiv.org/pdf/2211.08536">pdf</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> </div> </div> <p class="title is-5 mathjax"> Behavior of Hyper-Parameters for Selected Machine Learning Algorithms: An Empirical Investigation </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Anwesha Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Vaughan%2C+J">Joel Vaughan</a>, <a href="/search/cs?searchtype=author&query=Nair%2C+V+N">Vijayan N. Nair</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="2211.08536v1-abstract-short" style="display: inline;"> Hyper-parameters (HPs) are an important part of machine learning (ML) model development and can greatly influence performance. This paper studies their behavior for three algorithms: Extreme Gradient Boosting (XGB), Random Forest (RF), and Feedforward Neural Network (FFNN) with structured data. Our empirical investigation examines the qualitative behavior of model performance as the HPs vary, quan… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2211.08536v1-abstract-full').style.display = 'inline'; document.getElementById('2211.08536v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2211.08536v1-abstract-full" style="display: none;"> Hyper-parameters (HPs) are an important part of machine learning (ML) model development and can greatly influence performance. This paper studies their behavior for three algorithms: Extreme Gradient Boosting (XGB), Random Forest (RF), and Feedforward Neural Network (FFNN) with structured data. Our empirical investigation examines the qualitative behavior of model performance as the HPs vary, quantifies the importance of each HP for different ML algorithms, and stability of the performance near the optimal region. Based on the findings, we propose a set of guidelines for efficient HP tuning by reducing the search space. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2211.08536v1-abstract-full').style.display = 'none'; document.getElementById('2211.08536v1-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> 15 November, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2022. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2206.15374">arXiv:2206.15374</a> <span> [<a href="https://arxiv.org/pdf/2206.15374">pdf</a>, <a href="https://arxiv.org/format/2206.15374">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="Discrete Mathematics">cs.DM</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</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"> Verification and search algorithms for causal DAGs </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Choo%2C+D">Davin Choo</a>, <a href="/search/cs?searchtype=author&query=Shiragur%2C+K">Kirankumar Shiragur</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</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="2206.15374v2-abstract-short" style="display: inline;"> We study two problems related to recovering causal graphs from interventional data: (i) $\textit{verification}$, where the task is to check if a purported causal graph is correct, and (ii) $\textit{search}$, where the task is to recover the correct causal graph. For both, we wish to minimize the number of interventions performed. For the first problem, we give a characterization of a minimal sized… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2206.15374v2-abstract-full').style.display = 'inline'; document.getElementById('2206.15374v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2206.15374v2-abstract-full" style="display: none;"> We study two problems related to recovering causal graphs from interventional data: (i) $\textit{verification}$, where the task is to check if a purported causal graph is correct, and (ii) $\textit{search}$, where the task is to recover the correct causal graph. For both, we wish to minimize the number of interventions performed. For the first problem, we give a characterization of a minimal sized set of atomic interventions that is necessary and sufficient to check the correctness of a claimed causal graph. Our characterization uses the notion of $\textit{covered edges}$, which enables us to obtain simple proofs and also easily reason about earlier known results. We also generalize our results to the settings of bounded size interventions and node-dependent interventional costs. For all the above settings, we provide the first known provable algorithms for efficiently computing (near)-optimal verifying sets on general graphs. For the second problem, we give a simple adaptive algorithm based on graph separators that produces an atomic intervention set which fully orients any essential graph while using $\mathcal{O}(\log n)$ times the optimal number of interventions needed to $\textit{verify}$ (verifying size) the underlying DAG on $n$ vertices. This approximation is tight as $\textit{any}$ search algorithm on an essential line graph has worst case approximation ratio of $惟(\log n)$ with respect to the verifying size. With bounded size interventions, each of size $\leq k$, our algorithm gives an $\mathcal{O}(\log n \cdot \log k)$ factor approximation. Our result is the first known algorithm that gives a non-trivial approximation guarantee to the verifying size on general unweighted graphs and with bounded size interventions. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2206.15374v2-abstract-full').style.display = 'none'; document.getElementById('2206.15374v2-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 October, 2022; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 30 June, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> June 2022. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2206.07209">arXiv:2206.07209</a> <span> [<a href="https://arxiv.org/pdf/2206.07209">pdf</a>, <a href="https://arxiv.org/ps/2206.07209">ps</a>, <a href="https://arxiv.org/format/2206.07209">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</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.24963/ijcai.2023/387">10.24963/ijcai.2023/387 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> On Approximating Total Variation Distance </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Gayen%2C+S">Sutanu Gayen</a>, <a href="/search/cs?searchtype=author&query=Meel%2C+K+S">Kuldeep S. Meel</a>, <a href="/search/cs?searchtype=author&query=Myrisiotis%2C+D">Dimitrios Myrisiotis</a>, <a href="/search/cs?searchtype=author&query=Pavan%2C+A">A. Pavan</a>, <a href="/search/cs?searchtype=author&query=Vinodchandran%2C+N+V">N. V. Vinodchandran</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="2206.07209v2-abstract-short" style="display: inline;"> Total variation distance (TV distance) is a fundamental notion of distance between probability distributions. In this work, we introduce and study the problem of computing the TV distance of two product distributions over the domain $\{0,1\}^n$. In particular, we establish the following results. 1. The problem of exactly computing the TV distance of two product distributions is $\#\mathsf{P}$-co… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2206.07209v2-abstract-full').style.display = 'inline'; document.getElementById('2206.07209v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2206.07209v2-abstract-full" style="display: none;"> Total variation distance (TV distance) is a fundamental notion of distance between probability distributions. In this work, we introduce and study the problem of computing the TV distance of two product distributions over the domain $\{0,1\}^n$. In particular, we establish the following results. 1. The problem of exactly computing the TV distance of two product distributions is $\#\mathsf{P}$-complete. This is in stark contrast with other distance measures such as KL, Chi-square, and Hellinger which tensorize over the marginals leading to efficient algorithms. 2. There is a fully polynomial-time deterministic approximation scheme (FPTAS) for computing the TV distance of two product distributions $P$ and $Q$ where $Q$ is the uniform distribution. This result is extended to the case where $Q$ has a constant number of distinct marginals. In contrast, we show that when $P$ and $Q$ are Bayes net distributions, the relative approximation of their TV distance is $\mathsf{NP}$-hard. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2206.07209v2-abstract-full').style.display = 'none'; document.getElementById('2206.07209v2-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 14 June, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> June 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">20 pages, 1 figure</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (2023) Main Track. Pages 3479-3487 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2204.13683">arXiv:2204.13683</a> <span> [<a href="https://arxiv.org/pdf/2204.13683">pdf</a>, <a href="https://arxiv.org/format/2204.13683">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Robotics">cs.RO</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computer Vision and Pattern Recognition">cs.CV</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"> KING: Generating Safety-Critical Driving Scenarios for Robust Imitation via Kinematics Gradients </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Hanselmann%2C+N">Niklas Hanselmann</a>, <a href="/search/cs?searchtype=author&query=Renz%2C+K">Katrin Renz</a>, <a href="/search/cs?searchtype=author&query=Chitta%2C+K">Kashyap Chitta</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Apratim Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Geiger%2C+A">Andreas Geiger</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="2204.13683v1-abstract-short" style="display: inline;"> Simulators offer the possibility of safe, low-cost development of self-driving systems. However, current driving simulators exhibit na茂ve behavior models for background traffic. Hand-tuned scenarios are typically added during simulation to induce safety-critical situations. An alternative approach is to adversarially perturb the background traffic trajectories. In this paper, we study this approac… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2204.13683v1-abstract-full').style.display = 'inline'; document.getElementById('2204.13683v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2204.13683v1-abstract-full" style="display: none;"> Simulators offer the possibility of safe, low-cost development of self-driving systems. However, current driving simulators exhibit na茂ve behavior models for background traffic. Hand-tuned scenarios are typically added during simulation to induce safety-critical situations. An alternative approach is to adversarially perturb the background traffic trajectories. In this paper, we study this approach to safety-critical driving scenario generation using the CARLA simulator. We use a kinematic bicycle model as a proxy to the simulator's true dynamics and observe that gradients through this proxy model are sufficient for optimizing the background traffic trajectories. Based on this finding, we propose KING, which generates safety-critical driving scenarios with a 20% higher success rate than black-box optimization. By solving the scenarios generated by KING using a privileged rule-based expert algorithm, we obtain training data for an imitation learning policy. After fine-tuning on this new data, we show that the policy becomes better at avoiding collisions. Importantly, our generated data leads to reduced collisions on both held-out scenarios generated via KING as well as traditional hand-crafted scenarios, demonstrating improved robustness. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2204.13683v1-abstract-full').style.display = 'none'; document.getElementById('2204.13683v1-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 April, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2022. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2204.08690">arXiv:2204.08690</a> <span> [<a href="https://arxiv.org/pdf/2204.08690">pdf</a>, <a href="https://arxiv.org/format/2204.08690">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</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"> Independence Testing for Bounded Degree Bayesian Network </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Canonne%2C+C+L">Cl茅ment L. Canonne</a>, <a href="/search/cs?searchtype=author&query=Yang%2C+J+Q">Joy Qiping Yang</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="2204.08690v2-abstract-short" style="display: inline;"> We study the following independence testing problem: given access to samples from a distribution $P$ over $\{0,1\}^n$, decide whether $P$ is a product distribution or whether it is $\varepsilon$-far in total variation distance from any product distribution. For arbitrary distributions, this problem requires $\exp(n)$ samples. We show in this work that if $P$ has a sparse structure, then in fact on… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2204.08690v2-abstract-full').style.display = 'inline'; document.getElementById('2204.08690v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2204.08690v2-abstract-full" style="display: none;"> We study the following independence testing problem: given access to samples from a distribution $P$ over $\{0,1\}^n$, decide whether $P$ is a product distribution or whether it is $\varepsilon$-far in total variation distance from any product distribution. For arbitrary distributions, this problem requires $\exp(n)$ samples. We show in this work that if $P$ has a sparse structure, then in fact only linearly many samples are required. Specifically, if $P$ is Markov with respect to a Bayesian network whose underlying DAG has in-degree bounded by $d$, then $\tilde螛(2^{d/2}\cdot n/\varepsilon^2)$ samples are necessary and sufficient for independence testing. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2204.08690v2-abstract-full').style.display = 'none'; document.getElementById('2204.08690v2-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, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 19 April, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2022. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2204.08404">arXiv:2204.08404</a> <span> [<a href="https://arxiv.org/pdf/2204.08404">pdf</a>, <a href="https://arxiv.org/ps/2204.08404">ps</a>, <a href="https://arxiv.org/format/2204.08404">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> Low Degree Testing over the Reals </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Arora%2C+V">Vipul Arora</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Fleming%2C+N">Noah Fleming</a>, <a href="/search/cs?searchtype=author&query=Kelman%2C+E">Esty Kelman</a>, <a href="/search/cs?searchtype=author&query=Yoshida%2C+Y">Yuichi Yoshida</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="2204.08404v1-abstract-short" style="display: inline;"> We study the problem of testing whether a function $f: \mathbb{R}^n \to \mathbb{R}$ is a polynomial of degree at most $d$ in the \emph{distribution-free} testing model. Here, the distance between functions is measured with respect to an unknown distribution $\mathcal{D}$ over $\mathbb{R}^n$ from which we can draw samples. In contrast to previous work, we do not assume that $\mathcal{D}$ has finite… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2204.08404v1-abstract-full').style.display = 'inline'; document.getElementById('2204.08404v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2204.08404v1-abstract-full" style="display: none;"> We study the problem of testing whether a function $f: \mathbb{R}^n \to \mathbb{R}$ is a polynomial of degree at most $d$ in the \emph{distribution-free} testing model. Here, the distance between functions is measured with respect to an unknown distribution $\mathcal{D}$ over $\mathbb{R}^n$ from which we can draw samples. In contrast to previous work, we do not assume that $\mathcal{D}$ has finite support. We design a tester that given query access to $f$, and sample access to $\mathcal{D}$, makes $(d/\varepsilon)^{O(1)}$ many queries to $f$, accepts with probability $1$ if $f$ is a polynomial of degree $d$, and rejects with probability at least $2/3$ if every degree-$d$ polynomial $P$ disagrees with $f$ on a set of mass at least $\varepsilon$ with respect to $\mathcal{D}$. Our result also holds under mild assumptions when we receive only a polynomial number of bits of precision for each query to $f$, or when $f$ can only be queried on rational points representable using a logarithmic number of bits. Along the way, we prove a new stability theorem for multivariate polynomials that may be of independent interest. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2204.08404v1-abstract-full').style.display = 'none'; document.getElementById('2204.08404v1-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, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2022. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2202.10611">arXiv:2202.10611</a> <span> [<a href="https://arxiv.org/pdf/2202.10611">pdf</a>, <a href="https://arxiv.org/ps/2202.10611">ps</a>, <a href="https://arxiv.org/format/2202.10611">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</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"> Universal 1-Bit Compressive Sensing for Bounded Dynamic Range Signals </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Bansal%2C+S">Sidhant Bansal</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Chaturvedi%2C+A">Anamay Chaturvedi</a>, <a href="/search/cs?searchtype=author&query=Scarlett%2C+J">Jonathan Scarlett</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="2202.10611v2-abstract-short" style="display: inline;"> A {\em universal 1-bit compressive sensing (CS)} scheme consists of a measurement matrix $A$ such that all signals $x$ belonging to a particular class can be approximately recovered from $\textrm{sign}(Ax)$. 1-bit CS models extreme quantization effects where only one bit of information is revealed per measurement. We focus on universal support recovery for 1-bit CS in the case of {\em sparse} sign… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2202.10611v2-abstract-full').style.display = 'inline'; document.getElementById('2202.10611v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2202.10611v2-abstract-full" style="display: none;"> A {\em universal 1-bit compressive sensing (CS)} scheme consists of a measurement matrix $A$ such that all signals $x$ belonging to a particular class can be approximately recovered from $\textrm{sign}(Ax)$. 1-bit CS models extreme quantization effects where only one bit of information is revealed per measurement. We focus on universal support recovery for 1-bit CS in the case of {\em sparse} signals with bounded {\em dynamic range}. Specifically, a vector $x \in \mathbb{R}^n$ is said to have sparsity $k$ if it has at most $k$ nonzero entries, and dynamic range $R$ if the ratio between its largest and smallest nonzero entries is at most $R$ in magnitude. Our main result shows that if the entries of the measurement matrix $A$ are i.i.d.~Gaussians, then under mild assumptions on the scaling of $k$ and $R$, the number of measurements needs to be $\tilde惟(Rk^{3/2})$ to recover the support of $k$-sparse signals with dynamic range $R$ using $1$-bit CS. In addition, we show that a near-matching $O(R k^{3/2} \log n)$ upper bound follows as a simple corollary of known results. The $k^{3/2}$ scaling contrasts with the known lower bound of $\tilde惟(k^2 \log n)$ for the number of measurements to recover the support of arbitrary $k$-sparse signals. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2202.10611v2-abstract-full').style.display = 'none'; document.getElementById('2202.10611v2-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 May, 2022; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 21 February, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 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">Extended version of ISIT 2022 paper</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2107.11712">arXiv:2107.11712</a> <span> [<a href="https://arxiv.org/pdf/2107.11712">pdf</a>, <a href="https://arxiv.org/ps/2107.11712">ps</a>, <a href="https://arxiv.org/format/2107.11712">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</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="Machine Learning">stat.ML</span> </div> </div> <p class="title is-5 mathjax"> Efficient inference of interventional distributions </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Gayen%2C+S">Sutanu Gayen</a>, <a href="/search/cs?searchtype=author&query=Kandasamy%2C+S">Saravanan Kandasamy</a>, <a href="/search/cs?searchtype=author&query=Raval%2C+V">Vedant Raval</a>, <a href="/search/cs?searchtype=author&query=Vinodchandran%2C+N+V">N. V. Vinodchandran</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="2107.11712v2-abstract-short" style="display: inline;"> We consider the problem of efficiently inferring interventional distributions in a causal Bayesian network from a finite number of observations. Let $\mathcal{P}$ be a causal model on a set $\mathbf{V}$ of observable variables on a given causal graph $G$. For sets $\mathbf{X},\mathbf{Y}\subseteq \mathbf{V}$, and setting ${\bf x}$ to $\mathbf{X}$, let $P_{\bf x}(\mathbf{Y})$ denote the intervention… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2107.11712v2-abstract-full').style.display = 'inline'; document.getElementById('2107.11712v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2107.11712v2-abstract-full" style="display: none;"> We consider the problem of efficiently inferring interventional distributions in a causal Bayesian network from a finite number of observations. Let $\mathcal{P}$ be a causal model on a set $\mathbf{V}$ of observable variables on a given causal graph $G$. For sets $\mathbf{X},\mathbf{Y}\subseteq \mathbf{V}$, and setting ${\bf x}$ to $\mathbf{X}$, let $P_{\bf x}(\mathbf{Y})$ denote the interventional distribution on $\mathbf{Y}$ with respect to an intervention ${\bf x}$ to variables ${\bf x}$. Shpitser and Pearl (AAAI 2006), building on the work of Tian and Pearl (AAAI 2001), gave an exact characterization of the class of causal graphs for which the interventional distribution $P_{\bf x}({\mathbf{Y}})$ can be uniquely determined. We give the first efficient version of the Shpitser-Pearl algorithm. In particular, under natural assumptions, we give a polynomial-time algorithm that on input a causal graph $G$ on observable variables $\mathbf{V}$, a setting ${\bf x}$ of a set $\mathbf{X} \subseteq \mathbf{V}$ of bounded size, outputs succinct descriptions of both an evaluator and a generator for a distribution $\hat{P}$ that is $\varepsilon$-close (in total variation distance) to $P_{\bf x}({\mathbf{Y}})$ where $Y=\mathbf{V}\setminus \mathbf{X}$, if $P_{\bf x}(\mathbf{Y})$ is identifiable. We also show that when $\mathbf{Y}$ is an arbitrary set, there is no efficient algorithm that outputs an evaluator of a distribution that is $\varepsilon$-close to $P_{\bf x}({\mathbf{Y}})$ unless all problems that have statistical zero-knowledge proofs, including the Graph Isomorphism problem, have efficient randomized algorithms. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2107.11712v2-abstract-full').style.display = 'none'; document.getElementById('2107.11712v2-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> 27 July, 2021; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 24 July, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2021. </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">16 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/2107.10450">arXiv:2107.10450</a> <span> [<a href="https://arxiv.org/pdf/2107.10450">pdf</a>, <a href="https://arxiv.org/format/2107.10450">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</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="Machine Learning">stat.ML</span> </div> </div> <p class="title is-5 mathjax"> Learning Sparse Fixed-Structure Gaussian Bayesian Networks </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Choo%2C+D">Davin Choo</a>, <a href="/search/cs?searchtype=author&query=Gajjala%2C+R">Rishikesh Gajjala</a>, <a href="/search/cs?searchtype=author&query=Gayen%2C+S">Sutanu Gayen</a>, <a href="/search/cs?searchtype=author&query=Wang%2C+Y">Yuhao 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="2107.10450v3-abstract-short" style="display: inline;"> Gaussian Bayesian networks (a.k.a. linear Gaussian structural equation models) are widely used to model causal interactions among continuous variables. In this work, we study the problem of learning a fixed-structure Gaussian Bayesian network up to a bounded error in total variation distance. We analyze the commonly used node-wise least squares regression (LeastSquares) and prove that it has a nea… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2107.10450v3-abstract-full').style.display = 'inline'; document.getElementById('2107.10450v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2107.10450v3-abstract-full" style="display: none;"> Gaussian Bayesian networks (a.k.a. linear Gaussian structural equation models) are widely used to model causal interactions among continuous variables. In this work, we study the problem of learning a fixed-structure Gaussian Bayesian network up to a bounded error in total variation distance. We analyze the commonly used node-wise least squares regression (LeastSquares) and prove that it has a near-optimal sample complexity. We also study a couple of new algorithms for the problem: - BatchAvgLeastSquares takes the average of several batches of least squares solutions at each node, so that one can interpolate between the batch size and the number of batches. We show that BatchAvgLeastSquares also has near-optimal sample complexity. - CauchyEst takes the median of solutions to several batches of linear systems at each node. We show that the algorithm specialized to polytrees, CauchyEstTree, has near-optimal sample complexity. Experimentally, we show that for uncontaminated, realizable data, the LeastSquares algorithm performs best, but in the presence of contamination or DAG misspecification, CauchyEst/CauchyEstTree and BatchAvgLeastSquares respectively perform better. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2107.10450v3-abstract-full').style.display = 'none'; document.getElementById('2107.10450v3-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 October, 2022; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 22 July, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2021. </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">30 pages, 11 figures, acknowledgement added</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2106.12442">arXiv:2106.12442</a> <span> [<a href="https://arxiv.org/pdf/2106.12442">pdf</a>, <a href="https://arxiv.org/format/2106.12442">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computer Vision and Pattern Recognition">cs.CV</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="Robotics">cs.RO</span> </div> </div> <p class="title is-5 mathjax"> Euro-PVI: Pedestrian Vehicle Interactions in Dense Urban Centers </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Apratim Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Reino%2C+D+O">Daniel Olmeda Reino</a>, <a href="/search/cs?searchtype=author&query=Fritz%2C+M">Mario Fritz</a>, <a href="/search/cs?searchtype=author&query=Schiele%2C+B">Bernt Schiele</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="2106.12442v1-abstract-short" style="display: inline;"> Accurate prediction of pedestrian and bicyclist paths is integral to the development of reliable autonomous vehicles in dense urban environments. The interactions between vehicle and pedestrian or bicyclist have a significant impact on the trajectories of traffic participants e.g. stopping or turning to avoid collisions. Although recent datasets and trajectory prediction approaches have fostered t… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2106.12442v1-abstract-full').style.display = 'inline'; document.getElementById('2106.12442v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2106.12442v1-abstract-full" style="display: none;"> Accurate prediction of pedestrian and bicyclist paths is integral to the development of reliable autonomous vehicles in dense urban environments. The interactions between vehicle and pedestrian or bicyclist have a significant impact on the trajectories of traffic participants e.g. stopping or turning to avoid collisions. Although recent datasets and trajectory prediction approaches have fostered the development of autonomous vehicles yet the amount of vehicle-pedestrian (bicyclist) interactions modeled are sparse. In this work, we propose Euro-PVI, a dataset of pedestrian and bicyclist trajectories. In particular, our dataset caters more diverse and complex interactions in dense urban scenarios compared to the existing datasets. To address the challenges in predicting future trajectories with dense interactions, we develop a joint inference model that learns an expressive multi-modal shared latent space across agents in the urban scene. This enables our Joint-$尾$-cVAE approach to better model the distribution of future trajectories. We achieve state of the art results on the nuScenes and Euro-PVI datasets demonstrating the importance of capturing interactions between ego-vehicle and pedestrians (bicyclists) for accurate predictions. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2106.12442v1-abstract-full').style.display = 'none'; document.getElementById('2106.12442v1-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 June, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> June 2021. </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">To appear at CVPR 2021</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2106.09350">arXiv:2106.09350</a> <span> [<a href="https://arxiv.org/pdf/2106.09350">pdf</a>, <a href="https://arxiv.org/format/2106.09350">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</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"> Identifiability of AMP chain graph models </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Wang%2C+Y">Yuhao Wang</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</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="2106.09350v1-abstract-short" style="display: inline;"> We study identifiability of Andersson-Madigan-Perlman (AMP) chain graph models, which are a common generalization of linear structural equation models and Gaussian graphical models. AMP models are described by DAGs on chain components which themselves are undirected graphs. For a known chain component decomposition, we show that the DAG on the chain components is identifiable if the determinants… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2106.09350v1-abstract-full').style.display = 'inline'; document.getElementById('2106.09350v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2106.09350v1-abstract-full" style="display: none;"> We study identifiability of Andersson-Madigan-Perlman (AMP) chain graph models, which are a common generalization of linear structural equation models and Gaussian graphical models. AMP models are described by DAGs on chain components which themselves are undirected graphs. For a known chain component decomposition, we show that the DAG on the chain components is identifiable if the determinants of the residual covariance matrices of the chain components are monotone non-decreasing in topological order. This condition extends the equal variance identifiability criterion for Bayes nets, and it can be generalized from determinants to any super-additive function on positive semidefinite matrices. When the component decomposition is unknown, we describe conditions that allow recovery of the full structure using a polynomial time algorithm based on submodular function minimization. We also conduct experiments comparing our algorithm's performance against existing baselines. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2106.09350v1-abstract-full').style.display = 'none'; document.getElementById('2106.09350v1-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 June, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> June 2021. </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">16 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/2105.00639">arXiv:2105.00639</a> <span> [<a href="https://arxiv.org/pdf/2105.00639">pdf</a>, <a href="https://arxiv.org/ps/2105.00639">ps</a>, <a href="https://arxiv.org/format/2105.00639">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Databases">cs.DB</span> </div> </div> <p class="title is-5 mathjax"> Model Counting meets F0 Estimation </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Pavan%2C+A">A. Pavan</a>, <a href="/search/cs?searchtype=author&query=Vinodchandran%2C+N+V">N. V. Vinodchandran</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Meel%2C+K+S">Kuldeep S. Meel</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="2105.00639v1-abstract-short" style="display: inline;"> Constraint satisfaction problems (CSP's) and data stream models are two powerful abstractions to capture a wide variety of problems arising in different domains of computer science. Developments in the two communities have mostly occurred independently and with little interaction between them. In this work, we seek to investigate whether bridging the seeming communication gap between the two commu… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2105.00639v1-abstract-full').style.display = 'inline'; document.getElementById('2105.00639v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2105.00639v1-abstract-full" style="display: none;"> Constraint satisfaction problems (CSP's) and data stream models are two powerful abstractions to capture a wide variety of problems arising in different domains of computer science. Developments in the two communities have mostly occurred independently and with little interaction between them. In this work, we seek to investigate whether bridging the seeming communication gap between the two communities may pave the way to richer fundamental insights. To this end, we focus on two foundational problems: model counting for CSP's and computation of zeroth frequency moments ($F_0$) for data streams. Our investigations lead us to observe striking similarity in the core techniques employed in the algorithmic frameworks that have evolved separately for model counting and $F_0$ computation. We design a recipe for translation of algorithms developed for $F_0$ estimation to that of model counting, resulting in new algorithms for model counting. We then observe that algorithms in the context of distributed streaming can be transformed to distributed algorithms for model counting. We next turn our attention to viewing streaming from the lens of counting and show that framing $F_0$ estimation as a special case of #DNF counting allows us to obtain a general recipe for a rich class of streaming problems, which had been subjected to case-specific analysis in prior works. In particular, our view yields a state-of-the art algorithm for multidimensional range efficient $F_0$ estimation with a simpler analysis. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2105.00639v1-abstract-full').style.display = 'none'; document.getElementById('2105.00639v1-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 May, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2021. </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">Appears in PODS '21</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2012.14632">arXiv:2012.14632</a> <span> [<a href="https://arxiv.org/pdf/2012.14632">pdf</a>, <a href="https://arxiv.org/ps/2012.14632">ps</a>, <a href="https://arxiv.org/format/2012.14632">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</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> </div> </div> <p class="title is-5 mathjax"> Testing Product Distributions: A Closer Look </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Gayen%2C+S">Sutanu Gayen</a>, <a href="/search/cs?searchtype=author&query=Kandasamy%2C+S">Saravanan Kandasamy</a>, <a href="/search/cs?searchtype=author&query=Vinodchandran%2C+N+V">N. V. Vinodchandran</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="2012.14632v2-abstract-short" style="display: inline;"> We study the problems of identity and closeness testing of $n$-dimensional product distributions. Prior works by Canonne, Diakonikolas, Kane and Stewart (COLT 2017) and Daskalakis and Pan (COLT 2017) have established tight sample complexity bounds for non-tolerant testing over a binary alphabet: given two product distributions $P$ and $Q$ over a binary alphabet, distinguish between the cases… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2012.14632v2-abstract-full').style.display = 'inline'; document.getElementById('2012.14632v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2012.14632v2-abstract-full" style="display: none;"> We study the problems of identity and closeness testing of $n$-dimensional product distributions. Prior works by Canonne, Diakonikolas, Kane and Stewart (COLT 2017) and Daskalakis and Pan (COLT 2017) have established tight sample complexity bounds for non-tolerant testing over a binary alphabet: given two product distributions $P$ and $Q$ over a binary alphabet, distinguish between the cases $P = Q$ and $d_{\mathrm{TV}}(P, Q) > 蔚$. We build on this prior work to give a more comprehensive map of the complexity of testing of product distributions by investigating tolerant testing with respect to several natural distance measures and over an arbitrary alphabet. Our study gives a fine-grained understanding of how the sample complexity of tolerant testing varies with the distance measures for product distributions. In addition, we also extend one of our upper bounds on product distributions to bounded-degree Bayes nets. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2012.14632v2-abstract-full').style.display = 'none'; document.getElementById('2012.14632v2-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 May, 2021; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 29 December, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> December 2020. </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">A version appears in ALT 2021</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2012.11164">arXiv:2012.11164</a> <span> [<a href="https://arxiv.org/pdf/2012.11164">pdf</a>, <a href="https://arxiv.org/format/2012.11164">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computation and Language">cs.CL</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Artificial Intelligence">cs.AI</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.18653/v1/W19-1912">10.18653/v1/W19-1912 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Medical Entity Linking using Triplet Network </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Mondal%2C+I">Ishani Mondal</a>, <a href="/search/cs?searchtype=author&query=Purkayastha%2C+S">Sukannya Purkayastha</a>, <a href="/search/cs?searchtype=author&query=Sarkar%2C+S">Sudeshna Sarkar</a>, <a href="/search/cs?searchtype=author&query=Goyal%2C+P">Pawan Goyal</a>, <a href="/search/cs?searchtype=author&query=Pillai%2C+J">Jitesh Pillai</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Amitava Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Gattu%2C+M">Mahanandeeshwar Gattu</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="2012.11164v1-abstract-short" style="display: inline;"> Entity linking (or Normalization) is an essential task in text mining that maps the entity mentions in the medical text to standard entities in a given Knowledge Base (KB). This task is of great importance in the medical domain. It can also be used for merging different medical and clinical ontologies. In this paper, we center around the problem of disease linking or normalization. This task is ex… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2012.11164v1-abstract-full').style.display = 'inline'; document.getElementById('2012.11164v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2012.11164v1-abstract-full" style="display: none;"> Entity linking (or Normalization) is an essential task in text mining that maps the entity mentions in the medical text to standard entities in a given Knowledge Base (KB). This task is of great importance in the medical domain. It can also be used for merging different medical and clinical ontologies. In this paper, we center around the problem of disease linking or normalization. This task is executed in two phases: candidate generation and candidate scoring. In this paper, we present an approach to rank the candidate Knowledge Base entries based on their similarity with disease mention. We make use of the Triplet Network for candidate ranking. While the existing methods have used carefully generated sieves and external resources for candidate generation, we introduce a robust and portable candidate generation scheme that does not make use of the hand-crafted rules. Experimental results on the standard benchmark NCBI disease dataset demonstrate that our system outperforms the prior methods by a significant margin. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2012.11164v1-abstract-full').style.display = 'none'; document.getElementById('2012.11164v1-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 December, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> December 2020. </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">ClinicalNLP@NAACL 2019</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2011.13556">arXiv:2011.13556</a> <span> [<a href="https://arxiv.org/pdf/2011.13556">pdf</a>, <a href="https://arxiv.org/format/2011.13556">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Networking and Internet Architecture">cs.NI</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Information Retrieval">cs.IR</span> </div> </div> <p class="title is-5 mathjax"> Eco-Routing Using Open Street Maps </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Ghosh%2C+R+K">R K Ghosh</a>, <a href="/search/cs?searchtype=author&query=R%2C+V">Vinay R</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</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="2011.13556v1-abstract-short" style="display: inline;"> A vehicle's fuel consumption depends on its type, the speed, the condition, and the gradients of the road on which it is moving. We developed a Routing Engine for finding an eco-route (one with low fuel consumption) between a source and a destination. Open Street Maps has data on road conditions. We used CGIAR-CSI road elevation data 16[4] to integrate the road gradients into the proposed route-fi… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2011.13556v1-abstract-full').style.display = 'inline'; document.getElementById('2011.13556v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2011.13556v1-abstract-full" style="display: none;"> A vehicle's fuel consumption depends on its type, the speed, the condition, and the gradients of the road on which it is moving. We developed a Routing Engine for finding an eco-route (one with low fuel consumption) between a source and a destination. Open Street Maps has data on road conditions. We used CGIAR-CSI road elevation data 16[4] to integrate the road gradients into the proposed route-finding algorithm that modifies Open Street Routing Machine (OSRM). It allowed us to dynamically predict a vehicle's velocity, considering both the conditions and the road segment's slope. Using Highway EneRgy Assessment (HERA) methodology, we calculated the fuel consumed by a vehicle given its type and velocity. We have created both web and mobile interfaces through which users can specify Geo coordinates or human-readable addresses of a source and a destination. The user interface graphically displays the route obtained from the proposed Routing Engine with a detailed travel itinerary. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2011.13556v1-abstract-full').style.display = 'none'; document.getElementById('2011.13556v1-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 November, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2020. </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">16 pages, 17 figures, 41 references</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2011.04144">arXiv:2011.04144</a> <span> [<a href="https://arxiv.org/pdf/2011.04144">pdf</a>, <a href="https://arxiv.org/ps/2011.04144">ps</a>, <a href="https://arxiv.org/format/2011.04144">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</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> </div> </div> <p class="title is-5 mathjax"> Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Gayen%2C+S">Sutanu Gayen</a>, <a href="/search/cs?searchtype=author&query=Price%2C+E">Eric Price</a>, <a href="/search/cs?searchtype=author&query=Vinodchandran%2C+N+V">N. V. Vinodchandran</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="2011.04144v2-abstract-short" style="display: inline;"> We provide finite sample guarantees for the classical Chow-Liu algorithm (IEEE Trans.~Inform.~Theory, 1968) to learn a tree-structured graphical model of a distribution. For a distribution $P$ on $危^n$ and a tree $T$ on $n$ nodes, we say $T$ is an $\varepsilon$-approximate tree for $P$ if there is a $T$-structured distribution $Q$ such that $D(P\;||\;Q)$ is at most $\varepsilon$ more than the best… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2011.04144v2-abstract-full').style.display = 'inline'; document.getElementById('2011.04144v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2011.04144v2-abstract-full" style="display: none;"> We provide finite sample guarantees for the classical Chow-Liu algorithm (IEEE Trans.~Inform.~Theory, 1968) to learn a tree-structured graphical model of a distribution. For a distribution $P$ on $危^n$ and a tree $T$ on $n$ nodes, we say $T$ is an $\varepsilon$-approximate tree for $P$ if there is a $T$-structured distribution $Q$ such that $D(P\;||\;Q)$ is at most $\varepsilon$ more than the best possible tree-structured distribution for $P$. We show that if $P$ itself is tree-structured, then the Chow-Liu algorithm with the plug-in estimator for mutual information with $\widetilde{O}(|危|^3 n\varepsilon^{-1})$ i.i.d.~samples outputs an $\varepsilon$-approximate tree for $P$ with constant probability. In contrast, for a general $P$ (which may not be tree-structured), $惟(n^2\varepsilon^{-2})$ samples are necessary to find an $\varepsilon$-approximate tree. Our upper bound is based on a new conditional independence tester that addresses an open problem posed by Canonne, Diakonikolas, Kane, and Stewart~(STOC, 2018): we prove that for three random variables $X,Y,Z$ each over $危$, testing if $I(X; Y \mid Z)$ is $0$ or $\geq \varepsilon$ is possible with $\widetilde{O}(|危|^3/\varepsilon)$ samples. Finally, we show that for a specific tree $T$, with $\widetilde{O} (|危|^2n\varepsilon^{-1})$ samples from a distribution $P$ over $危^n$, one can efficiently learn the closest $T$-structured distribution in KL divergence by applying the add-1 estimator at each node. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2011.04144v2-abstract-full').style.display = 'none'; document.getElementById('2011.04144v2-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, 2021; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 8 November, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2020. </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, 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/2010.13187">arXiv:2010.13187</a> <span> [<a href="https://arxiv.org/pdf/2010.13187">pdf</a>, <a href="https://arxiv.org/format/2010.13187">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="Computer Vision and Pattern Recognition">cs.CV</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"> Improving the Reconstruction of Disentangled Representation Learners via Multi-Stage Modeling </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Srivastava%2C+A">Akash Srivastava</a>, <a href="/search/cs?searchtype=author&query=Bansal%2C+Y">Yamini Bansal</a>, <a href="/search/cs?searchtype=author&query=Ding%2C+Y">Yukun Ding</a>, <a href="/search/cs?searchtype=author&query=Hurwitz%2C+C+L">Cole Lincoln Hurwitz</a>, <a href="/search/cs?searchtype=author&query=Xu%2C+K">Kai Xu</a>, <a href="/search/cs?searchtype=author&query=Egger%2C+B">Bernhard Egger</a>, <a href="/search/cs?searchtype=author&query=Sattigeri%2C+P">Prasanna Sattigeri</a>, <a href="/search/cs?searchtype=author&query=Tenenbaum%2C+J+B">Joshua B. Tenenbaum</a>, <a href="/search/cs?searchtype=author&query=Sudjianto%2C+A">Agus Sudjianto</a>, <a href="/search/cs?searchtype=author&query=Le%2C+P">Phuong Le</a>, <a href="/search/cs?searchtype=author&query=R%2C+A+P">Arun Prakash R</a>, <a href="/search/cs?searchtype=author&query=Zhou%2C+N">Nengfeng Zhou</a>, <a href="/search/cs?searchtype=author&query=Vaughan%2C+J">Joel Vaughan</a>, <a href="/search/cs?searchtype=author&query=Wang%2C+Y">Yaqun Wang</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Anwesha Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Greenewald%2C+K">Kristjan Greenewald</a>, <a href="/search/cs?searchtype=author&query=Cox%2C+D+D">David D. Cox</a>, <a href="/search/cs?searchtype=author&query=Gutfreund%2C+D">Dan Gutfreund</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="2010.13187v3-abstract-short" style="display: inline;"> Current autoencoder-based disentangled representation learning methods achieve disentanglement by penalizing the (aggregate) posterior to encourage statistical independence of the latent factors. This approach introduces a trade-off between disentangled representation learning and reconstruction quality since the model does not have enough capacity to learn correlated latent variables that capture… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2010.13187v3-abstract-full').style.display = 'inline'; document.getElementById('2010.13187v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2010.13187v3-abstract-full" style="display: none;"> Current autoencoder-based disentangled representation learning methods achieve disentanglement by penalizing the (aggregate) posterior to encourage statistical independence of the latent factors. This approach introduces a trade-off between disentangled representation learning and reconstruction quality since the model does not have enough capacity to learn correlated latent variables that capture detail information present in most image data. To overcome this trade-off, we present a novel multi-stage modeling approach where the disentangled factors are first learned using a penalty-based disentangled representation learning method; then, the low-quality reconstruction is improved with another deep generative model that is trained to model the missing correlated latent variables, adding detail information while maintaining conditioning on the previously learned disentangled factors. Taken together, our multi-stage modelling approach results in a single, coherent probabilistic model that is theoretically justified by the principal of D-separation and can be realized with a variety of model classes including likelihood-based models such as variational autoencoders, implicit models such as generative adversarial networks, and tractable models like normalizing flows or mixtures of Gaussians. We demonstrate that our multi-stage model has higher reconstruction quality than current state-of-the-art methods with equivalent disentanglement performance across multiple standard benchmarks. In addition, we apply the multi-stage model to generate synthetic tabular datasets, showcasing an enhanced performance over benchmark models across a variety of metrics. The interpretability analysis further indicates that the multi-stage model can effectively uncover distinct and meaningful features of variations from which the original distribution can be recovered. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2010.13187v3-abstract-full').style.display = 'none'; document.getElementById('2010.13187v3-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 November, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 25 October, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2020. </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=Bhattacharyya%2C+A&start=50" class="pagination-next" >Next </a> <ul class="pagination-list"> <li> <a href="/search/?searchtype=author&query=Bhattacharyya%2C+A&start=0" class="pagination-link is-current" aria-label="Goto page 1">1 </a> </li> <li> <a href="/search/?searchtype=author&query=Bhattacharyya%2C+A&start=50" class="pagination-link " aria-label="Page 2" aria-current="page">2 </a> </li> <li> <a href="/search/?searchtype=author&query=Bhattacharyya%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