Showing 1–50 of 120 results for author: Mehta, A

The Average-Value Allocation Problem

Authors: Kshipra Bhawalkar, Zhe Feng, Anupam Gupta, Aranyak Mehta, David Wajc, Di Wang

Abstract: We initiate the study of centralized algorithms for welfare-maximizing allocation of goods to buyers subject to average-value constraints. We show that this problem is NP-hard to approximate beyond a factor of $\frac{e}{e-1}$, and provide a $\frac{4e}{e-1}$-approximate offline algorithm. For the online setting, we show that no non-trivial approximations are achievable under adversarial arrivals. U… ▽ More We initiate the study of centralized algorithms for welfare-maximizing allocation of goods to buyers subject to average-value constraints. We show that this problem is NP-hard to approximate beyond a factor of $\frac{e}{e-1}$, and provide a $\frac{4e}{e-1}$-approximate offline algorithm. For the online setting, we show that no non-trivial approximations are achievable under adversarial arrivals. Under i.i.d. arrivals, we present a polytime online algorithm that provides a constant approximation of the optimal (computationally-unbounded) online algorithm. In contrast, we show that no constant approximation of the ex-post optimum is achievable by an online algorithm. △ Less

Submitted 14 July, 2024; originally announced July 2024.

Deep Reinforcement Learning for Sequential Combinatorial Auctions

Authors: Sai Srivatsa Ravindranath, Zhe Feng, Di Wang, Manzil Zaheer, Aranyak Mehta, David C. Parkes

Abstract: Revenue-optimal auction design is a challenging problem with significant theoretical and practical implications. Sequential auction mechanisms, known for their simplicity and strong strategyproofness guarantees, are often limited by theoretical results that are largely existential, except for certain restrictive settings. Although traditional reinforcement learning methods such as Proximal Policy… ▽ More Revenue-optimal auction design is a challenging problem with significant theoretical and practical implications. Sequential auction mechanisms, known for their simplicity and strong strategyproofness guarantees, are often limited by theoretical results that are largely existential, except for certain restrictive settings. Although traditional reinforcement learning methods such as Proximal Policy Optimization (PPO) and Soft Actor-Critic (SAC) are applicable in this domain, they struggle with computational demands and convergence issues when dealing with large and continuous action spaces. In light of this and recognizing that we can model transitions differentiable for our settings, we propose using a new reinforcement learning framework tailored for sequential combinatorial auctions that leverages first-order gradients. Our extensive evaluations show that our approach achieves significant improvement in revenue over both analytical baselines and standard reinforcement learning algorithms. Furthermore, we scale our approach to scenarios involving up to 50 agents and 50 items, demonstrating its applicability in complex, real-world auction settings. As such, this work advances the computational tools available for auction design and contributes to bridging the gap between theoretical results and practical implementations in sequential auction design. △ Less

Submitted 10 July, 2024; originally announced July 2024.

Self-deployable contracting-cord metamaterials with tunable mechanical properties

Authors: Wenzhong Yan, Talmage Jones, Christopher L. Jawetz, Ryan H. Lee, Jonathan B. Hopkins, Ankur Mehta

Abstract: Recent advances in active materials and fabrication techniques have enabled the production of cyclically self-deployable metamaterials with an expanded functionality space. However, designing metamaterials that possess continuously tunable mechanical properties after self-deployment remains a challenge, notwithstanding its importance. Inspired by push puppets, we introduce an efficient design stra… ▽ More Recent advances in active materials and fabrication techniques have enabled the production of cyclically self-deployable metamaterials with an expanded functionality space. However, designing metamaterials that possess continuously tunable mechanical properties after self-deployment remains a challenge, notwithstanding its importance. Inspired by push puppets, we introduce an efficient design strategy to create reversibly self-deployable metamaterials with continuously tunable post-deployment stiffness and damping. Our metamaterial comprises contracting actuators threaded through beads with matching conical concavo-convex interfaces in networked chains. The slack network conforms to arbitrary shapes, but when actuated, it self-assembles into a preprogrammed configuration with beads gathered together. Further contraction of the actuators can dynamically tune the assembly's mechanical properties through the beads' particle jamming, while maintaining the overall structure with minimal change. We show that, after deployment, such metamaterials exhibit pronounced tunability in bending-dominated configurations: they can become more than 35 times stiffer and change their damping capability by over 50%. Through systematic analysis, we find that the beads'conical angle can introduce geometric nonlinearity, which has a major effect on the self-deployability and tunability of the metamaterial. Our work provides routes towards reversibly self-deployable, lightweight, and tunable metamaterials, with potential applications in soft robotics, reconfigurable architectures, and space engineering. △ Less

Submitted 8 July, 2024; originally announced July 2024.

Comments: 6 figures

Journal ref: Materials Horizons (2024)

Keystroke Dynamics Against Academic Dishonesty in the Age of LLMs

Authors: Debnath Kundu, Atharva Mehta, Rajesh Kumar, Naman Lal, Avinash Anand, Apoorv Singh, Rajiv Ratn Shah

Abstract: The transition to online examinations and assignments raises significant concerns about academic integrity. Traditional plagiarism detection systems often struggle to identify instances of intelligent cheating, particularly when students utilize advanced generative AI tools to craft their responses. This study proposes a keystroke dynamics-based method to differentiate between bona fide and assist… ▽ More The transition to online examinations and assignments raises significant concerns about academic integrity. Traditional plagiarism detection systems often struggle to identify instances of intelligent cheating, particularly when students utilize advanced generative AI tools to craft their responses. This study proposes a keystroke dynamics-based method to differentiate between bona fide and assisted writing within academic contexts. To facilitate this, a dataset was developed to capture the keystroke patterns of individuals engaged in writing tasks, both with and without the assistance of generative AI. The detector, trained using a modified TypeNet architecture, achieved accuracies ranging from 74.98% to 85.72% in condition-specific scenarios and from 52.24% to 80.54% in condition-agnostic scenarios. The findings highlight significant differences in keystroke dynamics between genuine and assisted writing. The outcomes of this study enhance our understanding of how users interact with generative AI and have implications for improving the reliability of digital educational platforms. △ Less

Submitted 21 June, 2024; originally announced June 2024.

Comments: Accepted for publication at The IEEE International Joint Conference on Biometrics (IJCB2024), contains 9 pages, 3 figures, 3 tables

ACM Class: I.5.4

Harnessing Business and Media Insights with Large Language Models

Authors: Yujia Bao, Ankit Parag Shah, Neeru Narang, Jonathan Rivers, Rajeev Maksey, Lan Guan, Louise N. Barrere, Shelley Evenson, Rahul Basole, Connie Miao, Ankit Mehta, Fabien Boulay, Su Min Park, Natalie E. Pearson, Eldhose Joy, Tiger He, Sumiran Thakur, Koustav Ghosal, Josh On, Phoebe Morrison, Tim Major, Eva Siqi Wang, Gina Escobar, Jiaheng Wei, Tharindu Cyril Weerasooriya , et al. (8 additional authors not shown)

Abstract: This paper introduces Fortune Analytics Language Model (FALM). FALM empowers users with direct access to comprehensive business analysis, including market trends, company performance metrics, and expert insights. Unlike generic LLMs, FALM leverages a curated knowledge base built from professional journalism, enabling it to deliver precise and in-depth answers to intricate business questions. Users… ▽ More This paper introduces Fortune Analytics Language Model (FALM). FALM empowers users with direct access to comprehensive business analysis, including market trends, company performance metrics, and expert insights. Unlike generic LLMs, FALM leverages a curated knowledge base built from professional journalism, enabling it to deliver precise and in-depth answers to intricate business questions. Users can further leverage natural language queries to directly visualize financial data, generating insightful charts and graphs to understand trends across diverse business sectors clearly. FALM fosters user trust and ensures output accuracy through three novel methods: 1) Time-aware reasoning guarantees accurate event registration and prioritizes recent updates. 2) Thematic trend analysis explicitly examines topic evolution over time, providing insights into emerging business landscapes. 3) Content referencing and task decomposition enhance answer fidelity and data visualization accuracy. We conduct both automated and human evaluations, demonstrating FALM's significant performance improvements over baseline methods while prioritizing responsible AI practices. These benchmarks establish FALM as a cutting-edge LLM in the business and media domains, with exceptional accuracy and trustworthiness. △ Less

Submitted 2 June, 2024; originally announced June 2024.

Robust Prediction Model for Multidimensional and Unbalanced Datasets

Authors: Pooja Thakar, Anil Mehta, Manisha

Abstract: Data Mining is a promising field and is applied in multiple domains for its predictive capabilities. Data in the real world cannot be readily used for data mining as it suffers from the problems of multidimensionality, unbalance and missing values. It is difficult to use its predictive capabilities by novice users. It is difficult for a beginner to find the relevant set of attributes from a large… ▽ More Data Mining is a promising field and is applied in multiple domains for its predictive capabilities. Data in the real world cannot be readily used for data mining as it suffers from the problems of multidimensionality, unbalance and missing values. It is difficult to use its predictive capabilities by novice users. It is difficult for a beginner to find the relevant set of attributes from a large pool of data available. The paper presents a Robust Prediction Model that finds a relevant set of attributes; resolves the problems of unbalanced and multidimensional real-life datasets and helps in finding patterns for informed decision making. Model is tested upon five different datasets in the domain of Health Sector, Education, Business and Fraud Detection. The results showcase the robust behaviour of the model and its applicability in various domains. △ Less

Submitted 5 June, 2024; originally announced June 2024.

Comments: 9 pages

LDPKiT: Recovering Utility in LDP Schemes by Training with Noise^2

Authors: Kexin Li, Yang Xi, Aastha Mehta, David Lie

Abstract: The adoption of large cloud-based models for inference has been hampered by concerns about the privacy leakage of end-user data. One method to mitigate this leakage is to add local differentially private noise to queries before sending them to the cloud, but this degrades utility as a side effect. Our key insight is that knowledge available in the noisy labels returned from performing inference on… ▽ More The adoption of large cloud-based models for inference has been hampered by concerns about the privacy leakage of end-user data. One method to mitigate this leakage is to add local differentially private noise to queries before sending them to the cloud, but this degrades utility as a side effect. Our key insight is that knowledge available in the noisy labels returned from performing inference on noisy inputs can be aggregated and used to recover the correct labels. We implement this insight in LDPKiT, which stands for Local Differentially-Private and Utility-Preserving Inference via Knowledge Transfer. LDPKiT uses the noisy labels returned from querying a set of noised inputs to train a local model (noise^2), which is then used to perform inference on the original set of inputs. Our experiments on CIFAR-10, Fashion-MNIST, SVHN, and CARER NLP datasets demonstrate that LDPKiT can improve utility without compromising privacy. For instance, on CIFAR-10, compared to a standard $ε$-LDP scheme with $ε=15$, which provides a weak privacy guarantee, LDPKiT can achieve nearly the same accuracy (within 1% drop) with $ε=7$, offering an enhanced privacy guarantee. Moreover, the benefits of using LDPKiT increase at higher, more privacy-protective noise levels. For Fashion-MNIST and CARER, LDPKiT's accuracy on the sensitive dataset with $ε=7$ not only exceeds the average accuracy of the standard $ε$-LDP scheme with $ε=7$ by roughly 20% and 9% but also outperforms the standard $ε$-LDP scheme with $ε=15$, a scenario with less noise and minimal privacy protection. We also perform Zest distance measurements to demonstrate that the type of distillation performed by LDPKiT is different from a model extraction attack. △ Less

Submitted 25 May, 2024; originally announced May 2024.

Combining and Decoupling Rigid and Soft Grippers to Enhance Robotic Manipulation

Authors: Maya Keely, Yeunhee Kim, Shaunak A. Mehta, Joshua Hoegerman, Robert Ramirez Sanchez, Emily Paul, Camryn Mills, Dylan P. Losey, Michael D. Bartlett

Abstract: For robot arms to perform everyday tasks in unstructured environments, these robots must be able to manipulate a diverse range of objects. Today's robots often grasp objects with either soft grippers or rigid end-effectors. However, purely rigid or purely soft grippers have fundamental limitations: soft grippers struggle with irregular, heavy objects, while rigid grippers often cannot grasp small,… ▽ More For robot arms to perform everyday tasks in unstructured environments, these robots must be able to manipulate a diverse range of objects. Today's robots often grasp objects with either soft grippers or rigid end-effectors. However, purely rigid or purely soft grippers have fundamental limitations: soft grippers struggle with irregular, heavy objects, while rigid grippers often cannot grasp small, numerous items. In this paper we therefore introduce RISOs, a mechanics and controls approach for unifying traditional RIgid end-effectors with a novel class of SOft adhesives. When grasping an object, RISOs can use either the rigid end-effector (pinching the item between non-deformable fingers) and/or the soft materials (attaching and releasing items with switchable adhesives). This enhances manipulation capabilities by combining and decoupling rigid and soft mechanisms. With RISOs robots can perform grasps along a spectrum from fully rigid, to fully soft, to rigid-soft, enabling real time object manipulation across a 1 million times range in weight (from 2 mg to 2 kg). To develop RISOs we first model and characterize the soft switchable adhesives. We then mount sheets of these soft adhesives on the surfaces of rigid end-effectors, and develop control strategies that make it easier for robot arms and human operators to utilize RISOs. The resulting RISO grippers were able to pick-up, carry, and release a larger set of objects than existing grippers, and participants also preferred using RISO. Overall, our experimental and user study results suggest that RISOs provide an exceptional gripper range in both capacity and object diversity. See videos of our user studies here: https://youtu.be/du085R0gPFI △ Less

Submitted 21 April, 2024; originally announced April 2024.

Auctions with LLM Summaries

Authors: Kumar Avinava Dubey, Zhe Feng, Rahul Kidambi, Aranyak Mehta, Di Wang

Abstract: We study an auction setting in which bidders bid for placement of their content within a summary generated by a large language model (LLM), e.g., an ad auction in which the display is a summary paragraph of multiple ads. This generalizes the classic ad settings such as position auctions to an LLM generated setting, which allows us to handle general display formats. We propose a novel factorized fr… ▽ More We study an auction setting in which bidders bid for placement of their content within a summary generated by a large language model (LLM), e.g., an ad auction in which the display is a summary paragraph of multiple ads. This generalizes the classic ad settings such as position auctions to an LLM generated setting, which allows us to handle general display formats. We propose a novel factorized framework in which an auction module and an LLM module work together via a prediction model to provide welfare maximizing summary outputs in an incentive compatible manner. We provide a theoretical analysis of this framework and synthetic experiments to demonstrate the feasibility and validity of the system together with welfare comparisons. △ Less

Submitted 11 April, 2024; originally announced April 2024.

On the price of exact truthfulness in incentive-compatible online learning with bandit feedback: A regret lower bound for WSU-UX

Authors: Ali Mortazavi, Junhao Lin, Nishant A. Mehta

Abstract: In one view of the classical game of prediction with expert advice with binary outcomes, in each round, each expert maintains an adversarially chosen belief and honestly reports this belief. We consider a recently introduced, strategic variant of this problem with selfish (reputation-seeking) experts, where each expert strategically reports in order to maximize their expected future reputation bas… ▽ More In one view of the classical game of prediction with expert advice with binary outcomes, in each round, each expert maintains an adversarially chosen belief and honestly reports this belief. We consider a recently introduced, strategic variant of this problem with selfish (reputation-seeking) experts, where each expert strategically reports in order to maximize their expected future reputation based on their belief. In this work, our goal is to design an algorithm for the selfish experts problem that is incentive-compatible (IC, or \emph{truthful}), meaning each expert's best strategy is to report truthfully, while also ensuring the algorithm enjoys sublinear regret with respect to the expert with the best belief. Freeman et al. (2020) recently studied this problem in the full information and bandit settings and obtained truthful, no-regret algorithms by leveraging prior work on wagering mechanisms. While their results under full information match the minimax rate for the classical ("honest experts") problem, the best-known regret for their bandit algorithm WSU-UX is $O(T^{2/3})$, which does not match the minimax rate for the classical ("honest bandits") setting. It was unclear whether the higher regret was an artifact of their analysis or a limitation of WSU-UX. We show, via explicit construction of loss sequences, that the algorithm suffers a worst-case $Ω(T^{2/3})$ lower bound. Left open is the possibility that a different IC algorithm obtains $O(\sqrt{T})$ regret. Yet, WSU-UX was a natural choice for such an algorithm owing to the limited design room for IC algorithms in this setting. △ Less

Submitted 7 April, 2024; originally announced April 2024.

Comments: Accepted to AISTATS 2024

Waypoint-Based Reinforcement Learning for Robot Manipulation Tasks

Authors: Shaunak A. Mehta, Soheil Habibian, Dylan P. Losey

Abstract: Robot arms should be able to learn new tasks. One framework here is reinforcement learning, where the robot is given a reward function that encodes the task, and the robot autonomously learns actions to maximize its reward. Existing approaches to reinforcement learning often frame this problem as a Markov decision process, and learn a policy (or a hierarchy of policies) to complete the task. These… ▽ More Robot arms should be able to learn new tasks. One framework here is reinforcement learning, where the robot is given a reward function that encodes the task, and the robot autonomously learns actions to maximize its reward. Existing approaches to reinforcement learning often frame this problem as a Markov decision process, and learn a policy (or a hierarchy of policies) to complete the task. These policies reason over hundreds of fine-grained actions that the robot arm needs to take: e.g., moving slightly to the right or rotating the end-effector a few degrees. But the manipulation tasks that we want robots to perform can often be broken down into a small number of high-level motions: e.g., reaching an object or turning a handle. In this paper we therefore propose a waypoint-based approach for model-free reinforcement learning. Instead of learning a low-level policy, the robot now learns a trajectory of waypoints, and then interpolates between those waypoints using existing controllers. Our key novelty is framing this waypoint-based setting as a sequence of multi-armed bandits: each bandit problem corresponds to one waypoint along the robot's motion. We theoretically show that an ideal solution to this reformulation has lower regret bounds than standard frameworks. We also introduce an approximate posterior sampling solution that builds the robot's motion one waypoint at a time. Results across benchmark simulations and two real-world experiments suggest that this proposed approach learns new tasks more quickly than state-of-the-art baselines. See videos here: https://youtu.be/MMEd-lYfq4Y △ Less

Submitted 19 March, 2024; originally announced March 2024.

Auctions with Dynamic Scoring

Authors: Martino Banchio, Aranyak Mehta, Andres Perlroth

Abstract: We study the design of auctions with dynamic scoring, which allocate a single item according to a given scoring rule. We are motivated by online advertising auctions when users interact with a platform over the course of a session. The platform ranks ads based on a combination of bids and quality scores, and updates the quality scores throughout the session based on the user's online activity. The… ▽ More We study the design of auctions with dynamic scoring, which allocate a single item according to a given scoring rule. We are motivated by online advertising auctions when users interact with a platform over the course of a session. The platform ranks ads based on a combination of bids and quality scores, and updates the quality scores throughout the session based on the user's online activity. The platform must decide when to show an ad during the session. By delaying the auction, the auctioneer acquires information about an ad's quality, improving her chances of selecting a high quality ad. However information is costly, because delay reduces market thickness and in turn revenue. When should the auctioneer allocate the impression to balance these forces? We develop a theoretical model to study the effect of market design on the trade-off between market thickness and information. In particular, we focus on first- and second-price auctions. The auctioneer can commit to the auction format, but not to its timing: her decision can thus be cast as a real options problem. We show that under optimal stopping the first-price auction allocates efficiently but with delay. Instead, the second-price auction generates more revenue by avoiding delay. The auctioneer benefits from introducing reserve prices, more so in a first-price auction. △ Less

Submitted 16 March, 2024; originally announced March 2024.

Population-aware Online Mirror Descent for Mean-Field Games by Deep Reinforcement Learning

Authors: Zida Wu, Mathieu Lauriere, Samuel Jia Cong Chua, Matthieu Geist, Olivier Pietquin, Ankur Mehta

Abstract: Mean Field Games (MFGs) have the ability to handle large-scale multi-agent systems, but learning Nash equilibria in MFGs remains a challenging task. In this paper, we propose a deep reinforcement learning (DRL) algorithm that achieves population-dependent Nash equilibrium without the need for averaging or sampling from history, inspired by Munchausen RL and Online Mirror Descent. Through the desig… ▽ More Mean Field Games (MFGs) have the ability to handle large-scale multi-agent systems, but learning Nash equilibria in MFGs remains a challenging task. In this paper, we propose a deep reinforcement learning (DRL) algorithm that achieves population-dependent Nash equilibrium without the need for averaging or sampling from history, inspired by Munchausen RL and Online Mirror Descent. Through the design of an additional inner-loop replay buffer, the agents can effectively learn to achieve Nash equilibrium from any distribution, mitigating catastrophic forgetting. The resulting policy can be applied to various initial distributions. Numerical experiments on four canonical examples demonstrate our algorithm has better convergence properties than SOTA algorithms, in particular a DRL version of Fictitious Play for population-dependent policies. △ Less

Submitted 6 March, 2024; originally announced March 2024.

Near-optimal Per-Action Regret Bounds for Sleeping Bandits

Authors: Quan Nguyen, Nishant A. Mehta

Abstract: We derive near-optimal per-action regret bounds for sleeping bandits, in which both the sets of available arms and their losses in every round are chosen by an adversary. In a setting with $K$ total arms and at most $A$ available arms in each round over $T$ rounds, the best known upper bound is $O(K\sqrt{TA\ln{K}})$, obtained indirectly via minimizing internal sleeping regrets. Compared to the min… ▽ More We derive near-optimal per-action regret bounds for sleeping bandits, in which both the sets of available arms and their losses in every round are chosen by an adversary. In a setting with $K$ total arms and at most $A$ available arms in each round over $T$ rounds, the best known upper bound is $O(K\sqrt{TA\ln{K}})$, obtained indirectly via minimizing internal sleeping regrets. Compared to the minimax $Ω(\sqrt{TA})$ lower bound, this upper bound contains an extra multiplicative factor of $K\ln{K}$. We address this gap by directly minimizing the per-action regret using generalized versions of EXP3, EXP3-IX and FTRL with Tsallis entropy, thereby obtaining near-optimal bounds of order $O(\sqrt{TA\ln{K}})$ and $O(\sqrt{T\sqrt{AK}})$. We extend our results to the setting of bandits with advice from sleeping experts, generalizing EXP4 along the way. This leads to new proofs for a number of existing adaptive and tracking regret bounds for standard non-sleeping bandits. Extending our results to the bandit version of experts that report their confidences leads to new bounds for the confidence regret that depends primarily on the sum of experts' confidences. We prove a lower bound, showing that for any minimax optimal algorithms, there exists an action whose regret is sublinear in $T$ but linear in the number of its active rounds. △ Less

Submitted 29 May, 2024; v1 submitted 2 March, 2024; originally announced March 2024.

Comments: V2: corrected Theorem 8 (FTARL's high probability bound) from log(1/delta) to log(K/delta)

Contextual Feature Extraction Hierarchies Converge in Large Language Models and the Brain

Authors: Gavin Mischler, Yinghao Aaron Li, Stephan Bickel, Ashesh D. Mehta, Nima Mesgarani

Abstract: Recent advancements in artificial intelligence have sparked interest in the parallels between large language models (LLMs) and human neural processing, particularly in language comprehension. While prior research has established similarities in the representation of LLMs and the brain, the underlying computational principles that cause this convergence, especially in the context of evolving LLMs,… ▽ More Recent advancements in artificial intelligence have sparked interest in the parallels between large language models (LLMs) and human neural processing, particularly in language comprehension. While prior research has established similarities in the representation of LLMs and the brain, the underlying computational principles that cause this convergence, especially in the context of evolving LLMs, remain elusive. Here, we examined a diverse selection of high-performance LLMs with similar parameter sizes to investigate the factors contributing to their alignment with the brain's language processing mechanisms. We find that as LLMs achieve higher performance on benchmark tasks, they not only become more brain-like as measured by higher performance when predicting neural responses from LLM embeddings, but also their hierarchical feature extraction pathways map more closely onto the brain's while using fewer layers to do the same encoding. We also compare the feature extraction pathways of the LLMs to each other and identify new ways in which high-performing models have converged toward similar hierarchical processing mechanisms. Finally, we show the importance of contextual information in improving model performance and brain similarity. Our findings reveal the converging aspects of language processing in the brain and LLMs and offer new directions for developing models that align more closely with human cognitive processing. △ Less

Submitted 31 January, 2024; originally announced January 2024.

Comments: 19 pages, 5 figures and 4 supplementary figures

A utility belt for an agricultural robot: reflection-in-action for applied design research

Authors: Natalie Friedman, Asmita Mehta, Kari Love, Alexandra Bremers, Awsaf Ahmed, Wendy Ju

Abstract: Clothing for robots can help expand a robot's functionality and also clarify the robot's purpose to bystanders. In studying how to design clothing for robots, we can shed light on the functional role of aesthetics in interactive system design. We present a case study of designing a utility belt for an agricultural robot. We use reflection-in-action to consider the ways that observation, in situ ma… ▽ More Clothing for robots can help expand a robot's functionality and also clarify the robot's purpose to bystanders. In studying how to design clothing for robots, we can shed light on the functional role of aesthetics in interactive system design. We present a case study of designing a utility belt for an agricultural robot. We use reflection-in-action to consider the ways that observation, in situ making, and documentation serve to illuminate how pragmatic, aesthetic, and intellectual inquiry are layered in this applied design research project. Themes explored in this pictorial include 1) contextual discovery of materials, tools, and practices, 2) design space exploration of materials in context, 3) improvising spaces for making, and 4) social processes in design. These themes emerged from the qualitative coding of 25 reflection-in-action videos from the researcher. We conclude with feedback on the utility belt prototypes for an agriculture robot and our learnings about context, materials, and people needed to design successful novel clothing forms for robots. △ Less

Submitted 21 December, 2023; originally announced December 2023.

NAC-TCN: Temporal Convolutional Networks with Causal Dilated Neighborhood Attention for Emotion Understanding

Authors: Alexander Mehta, William Yang

Abstract: In the task of emotion recognition from videos, a key improvement has been to focus on emotions over time rather than a single frame. There are many architectures to address this task such as GRUs, LSTMs, Self-Attention, Transformers, and Temporal Convolutional Networks (TCNs). However, these methods suffer from high memory usage, large amounts of operations, or poor gradients. We propose a method… ▽ More In the task of emotion recognition from videos, a key improvement has been to focus on emotions over time rather than a single frame. There are many architectures to address this task such as GRUs, LSTMs, Self-Attention, Transformers, and Temporal Convolutional Networks (TCNs). However, these methods suffer from high memory usage, large amounts of operations, or poor gradients. We propose a method known as Neighborhood Attention with Convolutions TCN (NAC-TCN) which incorporates the benefits of attention and Temporal Convolutional Networks while ensuring that causal relationships are understood which results in a reduction in computation and memory cost. We accomplish this by introducing a causal version of Dilated Neighborhood Attention while incorporating it with convolutions. Our model achieves comparable, better, or state-of-the-art performance over TCNs, TCAN, LSTMs, and GRUs while requiring fewer parameters on standard emotion recognition datasets. We publish our code online for easy reproducibility and use in other projects. △ Less

Submitted 6 January, 2024; v1 submitted 12 December, 2023; originally announced December 2023.

Comments: 8 pages, presented at ICVIP 2023

ACM Class: I.2.10

Can ChatGPT Play the Role of a Teaching Assistant in an Introductory Programming Course?

Authors: Anishka, Atharva Mehta, Nipun Gupta, Aarav Balachandran, Dhruv Kumar, Pankaj Jalote

Abstract: The emergence of Large language models (LLMs) is expected to have a major impact on education. This paper explores the potential of using ChatGPT, an LLM, as a virtual Teaching Assistant (TA) in an Introductory Programming Course. We evaluate ChatGPT's capabilities by comparing its performance with that of human TAs in some of the important TA functions. The TA functions which we focus on include… ▽ More The emergence of Large language models (LLMs) is expected to have a major impact on education. This paper explores the potential of using ChatGPT, an LLM, as a virtual Teaching Assistant (TA) in an Introductory Programming Course. We evaluate ChatGPT's capabilities by comparing its performance with that of human TAs in some of the important TA functions. The TA functions which we focus on include (1) grading student code submissions, and (2) providing feedback to undergraduate students in an introductory programming course. Firstly, we assess ChatGPT's proficiency in grading student code submissions using a given grading rubric and compare its performance with the grades assigned by human TAs. Secondly, we analyze the quality and relevance of the feedback provided by ChatGPT. This evaluation considers how well ChatGPT addresses mistakes and offers suggestions for improvement in student solutions from both code correctness and code quality perspectives. We conclude with a discussion on the implications of integrating ChatGPT into computing education for automated grading, personalized learning experiences, and instructional support. △ Less

Submitted 22 January, 2024; v1 submitted 12 December, 2023; originally announced December 2023.

Comments: Under review

ICS-Sniper: A Targeted Blackhole Attack on Encrypted ICS Traffic

Authors: Gargi Mitra, Pritam Dash, Yingao Elaine Yao, Aastha Mehta, Karthik Pattabiraman

Abstract: Operational Technology (OT) networks of industrial control systems (ICS) are increasingly connected to the public Internet, which has prompted ICSes to implement strong security measures (e.g., authentication and encryption) to protect end-to-end control communication. Despite the security measures, we show that an Internet adversary in the path of an ICS's communication can cause damage to the IC… ▽ More Operational Technology (OT) networks of industrial control systems (ICS) are increasingly connected to the public Internet, which has prompted ICSes to implement strong security measures (e.g., authentication and encryption) to protect end-to-end control communication. Despite the security measures, we show that an Internet adversary in the path of an ICS's communication can cause damage to the ICS without infiltrating it. We present ICS-Sniper, a targeted blackhole attack that analyzes the packet metadata (sizes, timing) to identify the packets carrying critical ICS commands or data, and drops the critical packets to disrupt the ICS's operations. We demonstrate two attacks on an emulation of a Secure Water Treatment (SWaT) plant that can potentially violate the operational safety of the ICS while evading state-of-the-art detection systems. △ Less

Submitted 11 December, 2023; originally announced December 2023.

Comments: 17 pages, 10 figures, 4 tables, 1 algorithm

A new approach to template banks of gravitational waves with higher harmonics: reducing matched-filtering cost by over an order of magnitude

Authors: Digvijay Wadekar, Tejaswi Venumadhav, Ajit Kumar Mehta, Javier Roulet, Seth Olsen, Jonathan Mushkin, Barak Zackay, Matias Zaldarriaga

Abstract: Searches for gravitational wave events use models, or templates, for the signals of interest. The templates used in current searches in the LIGO-Virgo-Kagra (LVK) data model the dominant quadrupole mode $(\ell,m)=(2,2)$ of the signals, and omit sub-dominant higher-order modes (HM) such as $(\ell,m)=(3,3)$, $(4,4)$, which are predicted by general relativity. Hence, these searches could lose sensiti… ▽ More Searches for gravitational wave events use models, or templates, for the signals of interest. The templates used in current searches in the LIGO-Virgo-Kagra (LVK) data model the dominant quadrupole mode $(\ell,m)=(2,2)$ of the signals, and omit sub-dominant higher-order modes (HM) such as $(\ell,m)=(3,3)$, $(4,4)$, which are predicted by general relativity. Hence, these searches could lose sensitivity to black hole mergers in interesting parts of parameter space, such as systems with high-masses and asymmetric mass ratios. We develop a new strategy to include HM in template banks that exploits the natural connection between the modes. We use a combination of post-Newtonian formulae and machine learning tools to model aligned-spin $(3,3)$, $(4,4)$ waveforms corresponding to a given $(2,2)$ waveform. Each of these modes can be individually filtered against the data to yield separate timeseries of signal-to-noise ratios (SNR), which can be combined in a relatively inexpensive way to marginalize over extrinsic parameters of the signals. This leads to a HM search pipeline whose matched-filtering cost is just $\approx 3\times$ that of a quadrupole-only search (in contrast to being $\approx\! 100 \times$, as in previously proposed HM search methods). Our method is effectual and is generally applicable for template banks constructed with either stochastic or geometric placement techniques. Additionally, we discuss compression of $(2,2)$-only geometric-placement template banks using machine learning algorithms. △ Less

Submitted 23 October, 2023; originally announced October 2023.

Comments: 12+2 pages, 7+1 figures. The template bank described here will be publicly available at https://github.com/JayWadekar/GW_higher_harmonics_search

Efficiency of Non-Truthful Auctions in Auto-bidding with Budget Constraints

Authors: Christopher Liaw, Aranyak Mehta, Wennan Zhu

Abstract: We study the efficiency of non-truthful auctions for auto-bidders with both return on spend (ROS) and budget constraints. The efficiency of a mechanism is measured by the price of anarchy (PoA), which is the worst case ratio between the liquid welfare of any equilibrium and the optimal (possibly randomized) allocation. Our first main result is that the first-price auction (FPA) is optimal, among d… ▽ More We study the efficiency of non-truthful auctions for auto-bidders with both return on spend (ROS) and budget constraints. The efficiency of a mechanism is measured by the price of anarchy (PoA), which is the worst case ratio between the liquid welfare of any equilibrium and the optimal (possibly randomized) allocation. Our first main result is that the first-price auction (FPA) is optimal, among deterministic mechanisms, in this setting. Without any assumptions, the PoA of FPA is $n$ which we prove is tight for any deterministic mechanism. However, under a mild assumption that a bidder's value for any query does not exceed their total budget, we show that the PoA is at most $2$. This bound is also tight as it matches the optimal PoA without a budget constraint. We next analyze two randomized mechanisms: randomized FPA (rFPA) and "quasi-proportional" FPA. We prove two results that highlight the efficacy of randomization in this setting. First, we show that the PoA of rFPA for two bidders is at most $1.8$ without requiring any assumptions. This extends prior work which focused only on an ROS constraint. Second, we show that quasi-proportional FPA has a PoA of $2$ for any number of bidders, without any assumptions. Both of these bypass lower bounds in the deterministic setting. Finally, we study the setting where bidders are assumed to bid uniformly. We show that uniform bidding can be detrimental for efficiency in deterministic mechanisms while being beneficial for randomized mechanisms, which is in stark contrast with the settings without budget constraints. △ Less

Submitted 18 April, 2024; v1 submitted 13 October, 2023; originally announced October 2023.

Cost-Driven Hardware-Software Co-Optimization of Machine Learning Pipelines

Authors: Ravit Sharma, Wojciech Romaszkan, Feiqian Zhu, Puneet Gupta, Ankur Mehta

Abstract: Researchers have long touted a vision of the future enabled by a proliferation of internet-of-things devices, including smart sensors, homes, and cities. Increasingly, embedding intelligence in such devices involves the use of deep neural networks. However, their storage and processing requirements make them prohibitive for cheap, off-the-shelf platforms. Overcoming those requirements is necessary… ▽ More Researchers have long touted a vision of the future enabled by a proliferation of internet-of-things devices, including smart sensors, homes, and cities. Increasingly, embedding intelligence in such devices involves the use of deep neural networks. However, their storage and processing requirements make them prohibitive for cheap, off-the-shelf platforms. Overcoming those requirements is necessary for enabling widely-applicable smart devices. While many ways of making models smaller and more efficient have been developed, there is a lack of understanding of which ones are best suited for particular scenarios. More importantly for edge platforms, those choices cannot be analyzed in isolation from cost and user experience. In this work, we holistically explore how quantization, model scaling, and multi-modality interact with system components such as memory, sensors, and processors. We perform this hardware/software co-design from the cost, latency, and user-experience perspective, and develop a set of guidelines for optimal system design and model deployment for the most cost-constrained platforms. We demonstrate our approach using an end-to-end, on-device, biometric user authentication system using a $20 ESP-EYE board. △ Less

Submitted 19 October, 2023; v1 submitted 11 October, 2023; originally announced October 2023.

NetShaper: A Differentially Private Network Side-Channel Mitigation System

Authors: Amir Sabzi, Rut Vora, Swati Goswami, Margo Seltzer, Mathias Lécuyer, Aastha Mehta

Abstract: The widespread adoption of encryption in network protocols has significantly improved the overall security of many Internet applications. However, these protocols cannot prevent network side-channel leaks -- leaks of sensitive information through the sizes and timing of network packets. We present NetShaper, a system that mitigates such leaks based on the principle of traffic shaping. NetShaper's… ▽ More The widespread adoption of encryption in network protocols has significantly improved the overall security of many Internet applications. However, these protocols cannot prevent network side-channel leaks -- leaks of sensitive information through the sizes and timing of network packets. We present NetShaper, a system that mitigates such leaks based on the principle of traffic shaping. NetShaper's traffic shaping provides differential privacy guarantees while adapting to the prevailing workload and congestion condition, and allows configuring a tradeoff between privacy guarantees, bandwidth and latency overheads. Furthermore, NetShaper provides a modular and portable tunnel endpoint design that can support diverse applications. We present a middlebox-based implementation of NetShaper and demonstrate its applicability in a video streaming and a web service application. △ Less

Submitted 10 October, 2023; originally announced October 2023.

New Approaches to Complexity via Quantum Graphs

Authors: Eric Culf, Arthur Mehta

Abstract: Problems based on the structure of graphs -- for example finding cliques, independent sets, or colourings -- are of fundamental importance in classical complexity. It is well motivated to consider similar problems about quantum graphs, which are an operator system generalisation of graphs. Defining well-formulated decision problems for quantum graphs faces several technical challenges, and consequ… ▽ More Problems based on the structure of graphs -- for example finding cliques, independent sets, or colourings -- are of fundamental importance in classical complexity. It is well motivated to consider similar problems about quantum graphs, which are an operator system generalisation of graphs. Defining well-formulated decision problems for quantum graphs faces several technical challenges, and consequently the connections between quantum graphs and complexity have been underexplored. In this work, we introduce and study the clique problem for quantum graphs. Our approach utilizes a well-known connection between quantum graphs and quantum channels. The inputs for our problems are presented as quantum channels induced by circuits, which implicitly determine a corresponding quantum graph. We also use this approach to reimagine the clique and independent set problems for classical graphs, by taking the inputs to be circuits of deterministic or noisy channels which implicitly determine confusability graphs. We show that, by varying the collection of channels in the language, these give rise to complete problems for the classes $\textsf{NP}$, $\textsf{MA}$, $\textsf{QMA}$, and $\textsf{QMA}(2)$. In this way, we exhibit a classical complexity problem whose natural quantisation is $\textsf{QMA}(2)$, rather than $\textsf{QMA}$, which is commonly assumed. To prove the results in the quantum case, we make use of methods inspired by self-testing. To illustrate the utility of our techniques, we include a new proof of the reduction of $\textsf{QMA}(k)$ to $\textsf{QMA}(2)$ via cliques for quantum graphs. We also study the complexity of a version of the independent set problem for quantum graphs, and provide preliminary evidence that it may be in general weaker in complexity, contrasting to the classical case where the clique and independent set problems are equivalent. △ Less

Submitted 22 September, 2023; originally announced September 2023.

Comments: 45 pages, 3 figures

A real-time, hardware agnostic framework for close-up branch reconstruction using RGB data

Authors: Alexander You, Aarushi Mehta, Luke Strohbehn, Jochen Hemming, Cindy Grimm, Joseph R. Davidson

Abstract: Creating accurate 3D models of tree topology is an important task for tree pruning. The 3D model is used to decide which branches to prune and then to execute the pruning cuts. Previous methods for creating 3D tree models have typically relied on point clouds, which are often computationally expensive to process and can suffer from data defects, especially with thin branches. In this paper, we pro… ▽ More Creating accurate 3D models of tree topology is an important task for tree pruning. The 3D model is used to decide which branches to prune and then to execute the pruning cuts. Previous methods for creating 3D tree models have typically relied on point clouds, which are often computationally expensive to process and can suffer from data defects, especially with thin branches. In this paper, we propose a method for actively scanning along a primary tree branch, detecting secondary branches to be pruned, and reconstructing their 3D geometry using just an RGB camera mounted on a robot arm. We experimentally validate that our setup is able to produce primary branch models with 4-5 mm accuracy and secondary branch models with 15 degrees orientation accuracy with respect to the ground truth model. Our framework is real-time and can run up to 10 cm/s with no loss in model accuracy or ability to detect secondary branches. △ Less

Submitted 18 June, 2024; v1 submitted 20 September, 2023; originally announced September 2023.

StROL: Stabilized and Robust Online Learning from Humans

Authors: Shaunak A. Mehta, Forrest Meng, Andrea Bajcsy, Dylan P. Losey

Abstract: Robots often need to learn the human's reward function online, during the current interaction. This real-time learning requires fast but approximate learning rules: when the human's behavior is noisy or suboptimal, current approximations can result in unstable robot learning. Accordingly, in this paper we seek to enhance the robustness and convergence properties of gradient descent learning rules… ▽ More Robots often need to learn the human's reward function online, during the current interaction. This real-time learning requires fast but approximate learning rules: when the human's behavior is noisy or suboptimal, current approximations can result in unstable robot learning. Accordingly, in this paper we seek to enhance the robustness and convergence properties of gradient descent learning rules when inferring the human's reward parameters. We model the robot's learning algorithm as a dynamical system over the human preference parameters, where the human's true (but unknown) preferences are the equilibrium point. This enables us to perform Lyapunov stability analysis to derive the conditions under which the robot's learning dynamics converge. Our proposed algorithm (StROL) uses these conditions to learn robust-by-design learning rules: given the original learning dynamics, StROL outputs a modified learning rule that now converges to the human's true parameters under a larger set of human inputs. In practice, these autonomously generated learning rules can correctly infer what the human is trying to convey, even when the human is noisy, biased, and suboptimal. Across simulations and a user study we find that StROL results in a more accurate estimate and less regret than state-of-the-art approaches for online reward learning. See videos and code here: https://github.com/VT-Collab/StROL_RAL △ Less

Submitted 4 January, 2024; v1 submitted 18 August, 2023; originally announced August 2023.

Understanding the RSA algorithm

Authors: Zhengping Jay Luo, Ruowen Liu, Aarav Mehta

Abstract: With the emerging importance of cybersecurity, it will be beneficial for a wide community to understand some of the fundamental security mechanisms. The RSA algorithm is one of the essential algorithms used in public-key cryptosystems. Understanding the RSA algorithm requires knowledge regarding number theory, modular arithmetic, etc., which is often beyond the knowledge pool of many beginners in… ▽ More With the emerging importance of cybersecurity, it will be beneficial for a wide community to understand some of the fundamental security mechanisms. The RSA algorithm is one of the essential algorithms used in public-key cryptosystems. Understanding the RSA algorithm requires knowledge regarding number theory, modular arithmetic, etc., which is often beyond the knowledge pool of many beginners in cybersecurity. In this work, we provide an intuitive and onion-peeling style introduction to the RSA algorithm, in which we assume that readers will only have a basic background in mathematics and cybersecurity. Started from three essential goals of public-key cryptosystems, we explained step-by-step how the RSA algorithm achieved these goals. We also used a toy example to further help readers to understand the algorithm from a practical perspective. △ Less

Submitted 5 August, 2023; originally announced August 2023.

Predictive Maintenance of Armoured Vehicles using Machine Learning Approaches

Authors: Prajit Sengupta, Anant Mehta, Prashant Singh Rana

Abstract: Armoured vehicles are specialized and complex pieces of machinery designed to operate in high-stress environments, often in combat or tactical situations. This study proposes a predictive maintenance-based ensemble system that aids in predicting potential maintenance needs based on sensor data collected from these vehicles. The proposed model's architecture involves various models such as Light Gr… ▽ More Armoured vehicles are specialized and complex pieces of machinery designed to operate in high-stress environments, often in combat or tactical situations. This study proposes a predictive maintenance-based ensemble system that aids in predicting potential maintenance needs based on sensor data collected from these vehicles. The proposed model's architecture involves various models such as Light Gradient Boosting, Random Forest, Decision Tree, Extra Tree Classifier and Gradient Boosting to predict the maintenance requirements of the vehicles accurately. In addition, K-fold cross validation, along with TOPSIS analysis, is employed to evaluate the proposed ensemble model's stability. The results indicate that the proposed system achieves an accuracy of 98.93%, precision of 99.80% and recall of 99.03%. The algorithm can effectively predict maintenance needs, thereby reducing vehicle downtime and improving operational efficiency. Through comparisons between various algorithms and the suggested ensemble, this study highlights the potential of machine learning-based predictive maintenance solutions. △ Less

Submitted 26 July, 2023; originally announced July 2023.

Comments: In Conference Proceedings of INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE, MACHINE LEARNING AND ARTIFICIAL INTELLIGENCE (pg:25-31) - (New Delhi, 2023)

Data Cross-Segmentation for Improved Generalization in Reinforcement Learning Based Algorithmic Trading

Authors: Vikram Duvvur, Aashay Mehta, Edward Sun, Bo Wu, Ken Yew Chan, Jeff Schneider

Abstract: The use of machine learning in algorithmic trading systems is increasingly common. In a typical set-up, supervised learning is used to predict the future prices of assets, and those predictions drive a simple trading and execution strategy. This is quite effective when the predictions have sufficient signal, markets are liquid, and transaction costs are low. However, those conditions often do not… ▽ More The use of machine learning in algorithmic trading systems is increasingly common. In a typical set-up, supervised learning is used to predict the future prices of assets, and those predictions drive a simple trading and execution strategy. This is quite effective when the predictions have sufficient signal, markets are liquid, and transaction costs are low. However, those conditions often do not hold in thinly traded financial markets and markets for differentiated assets such as real estate or vehicles. In these markets, the trading strategy must consider the long-term effects of taking positions that are relatively more difficult to change. In this work, we propose a Reinforcement Learning (RL) algorithm that trades based on signals from a learned predictive model and addresses these challenges. We test our algorithm on 20+ years of equity data from Bursa Malaysia. △ Less

Submitted 18 July, 2023; originally announced July 2023.

Model Adaptation for ASR in low-resource Indian Languages

Authors: Abhayjeet Singh, Arjun Singh Mehta, Ashish Khuraishi K S, Deekshitha G, Gauri Date, Jai Nanavati, Jesuraja Bandekar, Karnalius Basumatary, Karthika P, Sandhya Badiger, Sathvik Udupa, Saurabh Kumar, Savitha, Prasanta Kumar Ghosh, Prashanthi V, Priyanka Pai, Raoul Nanavati, Rohan Saxena, Sai Praneeth Reddy Mora, Srinivasa Raghavan

Abstract: Automatic speech recognition (ASR) performance has improved drastically in recent years, mainly enabled by self-supervised learning (SSL) based acoustic models such as wav2vec2 and large-scale multi-lingual training like Whisper. A huge challenge still exists for low-resource languages where the availability of both audio and text is limited. This is further complicated by the presence of multiple… ▽ More Automatic speech recognition (ASR) performance has improved drastically in recent years, mainly enabled by self-supervised learning (SSL) based acoustic models such as wav2vec2 and large-scale multi-lingual training like Whisper. A huge challenge still exists for low-resource languages where the availability of both audio and text is limited. This is further complicated by the presence of multiple dialects like in Indian languages. However, many Indian languages can be grouped into the same families and share the same script and grammatical structure. This is where a lot of adaptation and fine-tuning techniques can be applied to overcome the low-resource nature of the data by utilising well-resourced similar languages. In such scenarios, it is important to understand the extent to which each modality, like acoustics and text, is important in building a reliable ASR. It could be the case that an abundance of acoustic data in a language reduces the need for large text-only corpora. Or, due to the availability of various pretrained acoustic models, the vice-versa could also be true. In this proposed special session, we encourage the community to explore these ideas with the data in two low-resource Indian languages of Bengali and Bhojpuri. These approaches are not limited to Indian languages, the solutions are potentially applicable to various languages spoken around the world. △ Less

Submitted 16 July, 2023; originally announced July 2023.

Comments: ASRU Special session overview paper

Benchmarking the Effectiveness of Classification Algorithms and SVM Kernels for Dry Beans

Authors: Anant Mehta, Prajit Sengupta, Divisha Garg, Harpreet Singh, Yosi Shacham Diamand

Abstract: Plant breeders and agricultural researchers can increase crop productivity by identifying desirable features, disease resistance, and nutritional content by analysing the Dry Bean dataset. This study analyses and compares different Support Vector Machine (SVM) classification algorithms, namely linear, polynomial, and radial basis function (RBF), along with other popular classification algorithms.… ▽ More Plant breeders and agricultural researchers can increase crop productivity by identifying desirable features, disease resistance, and nutritional content by analysing the Dry Bean dataset. This study analyses and compares different Support Vector Machine (SVM) classification algorithms, namely linear, polynomial, and radial basis function (RBF), along with other popular classification algorithms. The analysis is performed on the Dry Bean Dataset, with PCA (Principal Component Analysis) conducted as a preprocessing step for dimensionality reduction. The primary evaluation metric used is accuracy, and the RBF SVM kernel algorithm achieves the highest Accuracy of 93.34%, Precision of 92.61%, Recall of 92.35% and F1 Score as 91.40%. Along with adept visualization and empirical analysis, this study offers valuable guidance by emphasizing the importance of considering different SVM algorithms for complex and non-linear structured datasets. △ Less

Submitted 15 July, 2023; originally announced July 2023.

Comments: 6 pages, 5 figures

Reward Selection with Noisy Observations

Authors: Kamyar Azizzadenesheli, Trung Dang, Aranyak Mehta, Alexandros Psomas, Qian Zhang

Abstract: We study a fundamental problem in optimization under uncertainty. There are $n$ boxes; each box $i$ contains a hidden reward $x_i$. Rewards are drawn i.i.d. from an unknown distribution $\mathcal{D}$. For each box $i$, we see $y_i$, an unbiased estimate of its reward, which is drawn from a Normal distribution with known standard deviation $σ_i$ (and an unknown mean $x_i$). Our task is to select a… ▽ More We study a fundamental problem in optimization under uncertainty. There are $n$ boxes; each box $i$ contains a hidden reward $x_i$. Rewards are drawn i.i.d. from an unknown distribution $\mathcal{D}$. For each box $i$, we see $y_i$, an unbiased estimate of its reward, which is drawn from a Normal distribution with known standard deviation $σ_i$ (and an unknown mean $x_i$). Our task is to select a single box, with the goal of maximizing our reward. This problem captures a wide range of applications, e.g. ad auctions, where the hidden reward is the click-through rate of an ad. Previous work in this model [BKMR12] proves that the naive policy, which selects the box with the largest estimate $y_i$, is suboptimal, and suggests a linear policy, which selects the box $i$ with the largest $y_i - c \cdot σ_i$, for some $c > 0$. However, no formal guarantees are given about the performance of either policy (e.g., whether their expected reward is within some factor of the optimal policy's reward). In this work, we prove that both the naive policy and the linear policy are arbitrarily bad compared to the optimal policy, even when $\mathcal{D}$ is well-behaved, e.g. has monotone hazard rate (MHR), and even under a "small tail" condition, which requires that not too many boxes have arbitrarily large noise. On the flip side, we propose a simple threshold policy that gives a constant approximation to the reward of a prophet (who knows the realized values $x_1, \dots, x_n$) under the same "small tail" condition. We prove that when this condition is not satisfied, even an optimal clairvoyant policy (that knows $\mathcal{D}$) cannot get a constant approximation to the prophet, even for MHR distributions, implying that our threshold policy is optimal against the prophet benchmark, up to constants. △ Less

Submitted 12 July, 2023; originally announced July 2023.

The Power of Two-sided Recruitment in Two-sided Markets

Authors: Yang Cai, Christopher Liaw, Aranyak Mehta, Mingfei Zhao

Abstract: We consider the problem of maximizing the gains from trade (GFT) in two-sided markets. The seminal impossibility result by Myerson and Satterthwaite shows that even for bilateral trade, there is no individually rational (IR), Bayesian incentive compatible (BIC) and budget balanced (BB) mechanism that can achieve the full GFT. Moreover, the optimal BIC, IR and BB mechanism that maximizes the GFT is… ▽ More We consider the problem of maximizing the gains from trade (GFT) in two-sided markets. The seminal impossibility result by Myerson and Satterthwaite shows that even for bilateral trade, there is no individually rational (IR), Bayesian incentive compatible (BIC) and budget balanced (BB) mechanism that can achieve the full GFT. Moreover, the optimal BIC, IR and BB mechanism that maximizes the GFT is known to be complex and heavily depends on the prior. In this paper, we pursue a Bulow-Klemperer-style question, i.e., does augmentation allow for prior-independent mechanisms to compete against the optimal mechanism? Our first main result shows that in the double auction setting with $m$ i.i.d. buyers and $n$ i.i.d. sellers, by augmenting $O(1)$ buyers and sellers to the market, the GFT of a simple, dominant strategy incentive compatible (DSIC), and prior-independent mechanism in the augmented market is at least the optimal in the original market, when the buyers' distribution first-order stochastically dominates the sellers' distribution. Next, we go beyond the i.i.d. setting and study the power of two-sided recruitment in more general markets. Our second main result is that for any $ε> 0$ and any set of $O(1/ε)$ buyers and sellers where the buyers' value exceeds the sellers' value with constant probability, if we add these additional agents into any market with arbitrary correlations, the Trade Reduction mechanism obtains a $(1-ε)$-approximation of the GFT of the augmented market. Importantly, the newly recruited agents are agnostic to the original market. △ Less

Submitted 28 March, 2024; v1 submitted 7 July, 2023; originally announced July 2023.

Physics Constrained Unsupervised Deep Learning for Rapid, High Resolution Scanning Coherent Diffraction Reconstruction

Authors: Oliver Hoidn, Aashwin Ananda Mishra, Apurva Mehta

Abstract: By circumventing the resolution limitations of optics, coherent diffractive imaging (CDI) and ptychography are making their way into scientific fields ranging from X-ray imaging to astronomy. Yet, the need for time consuming iterative phase recovery hampers real-time imaging. While supervised deep learning strategies have increased reconstruction speed, they sacrifice image quality. Furthermore, t… ▽ More By circumventing the resolution limitations of optics, coherent diffractive imaging (CDI) and ptychography are making their way into scientific fields ranging from X-ray imaging to astronomy. Yet, the need for time consuming iterative phase recovery hampers real-time imaging. While supervised deep learning strategies have increased reconstruction speed, they sacrifice image quality. Furthermore, these methods' demand for extensive labeled training data is experimentally burdensome. Here, we propose an unsupervised physics-informed neural network reconstruction method, PtychoPINN, that retains the factor of 100-to-1000 speedup of deep learning-based reconstruction while improving reconstruction quality by combining the diffraction forward map with real-space constraints from overlapping measurements. In particular, PtychoPINN significantly advances generalizability, accuracy (with a typical 10 dB PSNR increase), and linear resolution (2- to 6-fold gain). This blend of performance and speed offers exciting prospects for high-resolution real-time imaging in high-throughput environments such as X-ray free electron lasers (XFELs) and diffraction-limited light sources. △ Less

Submitted 11 October, 2023; v1 submitted 19 June, 2023; originally announced June 2023.

An improved regret analysis for UCB-N and TS-N

Authors: Nishant A. Mehta

Abstract: In the setting of stochastic online learning with undirected feedback graphs, Lykouris et al. (2020) previously analyzed the pseudo-regret of the upper confidence bound-based algorithm UCB-N and the Thompson Sampling-based algorithm TS-N. In this note, we show how to improve their pseudo-regret analysis. Our improvement involves refining a key lemma of the previous analysis, allowing a $\log(T)$ f… ▽ More In the setting of stochastic online learning with undirected feedback graphs, Lykouris et al. (2020) previously analyzed the pseudo-regret of the upper confidence bound-based algorithm UCB-N and the Thompson Sampling-based algorithm TS-N. In this note, we show how to improve their pseudo-regret analysis. Our improvement involves refining a key lemma of the previous analysis, allowing a $\log(T)$ factor to be replaced by a factor $\log_2(α) + 3$ for $α$ the independence number of the feedback graph. △ Less

Submitted 6 May, 2023; originally announced May 2023.

Comments: 5 pages

Quantum delegation with an off-the-shelf device

Authors: Anne Broadbent, Arthur Mehta, Yuming Zhao

Abstract: Given that reliable cloud quantum computers are becoming closer to reality, the concept of delegation of quantum computations and its verifiability is of central interest. Many models have been proposed, each with specific strengths and weaknesses. Here, we put forth a new model where the client trusts only its classical processing, makes no computational assumptions, and interacts with a quantum… ▽ More Given that reliable cloud quantum computers are becoming closer to reality, the concept of delegation of quantum computations and its verifiability is of central interest. Many models have been proposed, each with specific strengths and weaknesses. Here, we put forth a new model where the client trusts only its classical processing, makes no computational assumptions, and interacts with a quantum server in a single round. In addition, during a set-up phase, the client specifies the size $n$ of the computation and receives an untrusted, off-the-shelf (OTS) quantum device that is used to report the outcome of a single measurement. We show how to delegate polynomial-time quantum computations in the OTS model. This also yields an interactive proof system for all of QMA, which, furthermore, we show can be accomplished in statistical zero-knowledge. This provides the first relativistic (one-round), two-prover zero-knowledge proof system for QMA. As a proof approach, we provide a new self-test for n EPR pairs using only constant-sized Pauli measurements, and show how it provides a new avenue for the use of simulatable codes for local Hamiltonian verification. Along the way, we also provide an enhanced version of a well-known stability result due to Gowers and Hatami and show how it completes a common argument used in self-testing. △ Less

Submitted 5 December, 2023; v1 submitted 6 April, 2023; originally announced April 2023.

Comments: 42 pages. This version (v2) contains new results that were not presented in an earlier version (v1) of this paper. We have also rephrased the OTS model to focus on the OTS device being generic and efficient

Optimisation via encodings: a renormalisation group perspective

Authors: Konstantin Klemm, Anita Mehta, Peter F. Stadler

Abstract: Difficult, in particular NP-complete, optimization problems are traditionally solved approximately using search heuristics. These are usually slowed down by the rugged landscapes encountered, because local minima arrest the search process. Cover-encoding maps were devised to circumvent this problem by transforming the original landscape to one that is free of local minima and enriched in near-opti… ▽ More Difficult, in particular NP-complete, optimization problems are traditionally solved approximately using search heuristics. These are usually slowed down by the rugged landscapes encountered, because local minima arrest the search process. Cover-encoding maps were devised to circumvent this problem by transforming the original landscape to one that is free of local minima and enriched in near-optimal solutions. By definition, these involve the mapping of the original (larger) search space into smaller subspaces, by processes that typically amount to a form of coarse-graining. In this paper, we explore the details of this coarse-graining using formal arguments, as well as concrete examples of cover-encoding maps, that are investigated analytically as well as computationally. Our results strongly suggest that the coarse-graining involved in cover-encoding maps bears a strong resemblance to that encountered in renormalisation group schemes. Given the apparently disparate nature of these two formalisms, these strong similarities are rather startling, and suggest deep mathematical underpinnings that await further exploration. △ Less

Submitted 7 November, 2023; v1 submitted 28 March, 2023; originally announced March 2023.

Comments: 21 pages, 4 figures

Journal ref: J Phys A: Math Theor 56, 485001 (2023)

Help the Blind See: Assistance for the Visually Impaired through Augmented Acoustic Simulation

Authors: Alexander Mehta, Ritik Jalisatgi

Abstract: An estimated 253 million people have visual impairments. These visual impairments affect everyday lives, and limit their understanding of the outside world. This can pose a risk to health from falling or collisions. We propose a solution to this through quick and detailed communication of environmental spatial geometry through sound, providing the blind and visually impaired the ability to underst… ▽ More An estimated 253 million people have visual impairments. These visual impairments affect everyday lives, and limit their understanding of the outside world. This can pose a risk to health from falling or collisions. We propose a solution to this through quick and detailed communication of environmental spatial geometry through sound, providing the blind and visually impaired the ability to understand their spatial environment through sound technology. The model consists of fast object detection and 3D environmental mapping, which is communicated through a series of quick sound notes. These sound notes are at different frequencies, pitches, and arrangements in order to precisely communicate the depth and location of points within the environment. Sounds are communicated in the form of musical notes in order to be easily recognizable and distinguishable. A unique algorithm is used to segment objects, providing minimal accuracy loss and improvement from the normal O(n2 ) to O(n) (which is significant, as N in point clouds can often be in the range of 105 ). In testing, we achieved an R-value of 0.866 on detailed objects and an accuracy of 87.5% on an outdoor scene at night with large amounts of noise. We also provide a supplementary video demo of our system. △ Less

Submitted 8 February, 2023; originally announced March 2023.

GPT-4 Technical Report

Authors: OpenAI, Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, Red Avila, Igor Babuschkin, Suchir Balaji, Valerie Balcom, Paul Baltescu, Haiming Bao, Mohammad Bavarian, Jeff Belgum, Irwan Bello, Jake Berdine, Gabriel Bernadett-Shapiro, Christopher Berner, Lenny Bogdonoff, Oleg Boiko , et al. (256 additional authors not shown)

Abstract: We report the development of GPT-4, a large-scale, multimodal model which can accept image and text inputs and produce text outputs. While less capable than humans in many real-world scenarios, GPT-4 exhibits human-level performance on various professional and academic benchmarks, including passing a simulated bar exam with a score around the top 10% of test takers. GPT-4 is a Transformer-based mo… ▽ More We report the development of GPT-4, a large-scale, multimodal model which can accept image and text inputs and produce text outputs. While less capable than humans in many real-world scenarios, GPT-4 exhibits human-level performance on various professional and academic benchmarks, including passing a simulated bar exam with a score around the top 10% of test takers. GPT-4 is a Transformer-based model pre-trained to predict the next token in a document. The post-training alignment process results in improved performance on measures of factuality and adherence to desired behavior. A core component of this project was developing infrastructure and optimization methods that behave predictably across a wide range of scales. This allowed us to accurately predict some aspects of GPT-4's performance based on models trained with no more than 1/1,000th the compute of GPT-4. △ Less

Submitted 4 March, 2024; v1 submitted 15 March, 2023; originally announced March 2023.

Comments: 100 pages; updated authors list; fixed author names and added citation

User Response in Ad Auctions: An MDP Formulation of Long-Term Revenue Optimization

Authors: Yang Cai, Zhe Feng, Christopher Liaw, Aranyak Mehta, Grigoris Velegkas

Abstract: We propose a new Markov Decision Process (MDP) model for ad auctions to capture the user response to the quality of ads, with the objective of maximizing the long-term discounted revenue. By incorporating user response, our model takes into consideration all three parties involved in the auction (advertiser, auctioneer, and user). The state of the user is modeled as a user-specific click-through r… ▽ More We propose a new Markov Decision Process (MDP) model for ad auctions to capture the user response to the quality of ads, with the objective of maximizing the long-term discounted revenue. By incorporating user response, our model takes into consideration all three parties involved in the auction (advertiser, auctioneer, and user). The state of the user is modeled as a user-specific click-through rate (CTR) with the CTR changing in the next round according to the set of ads shown to the user in the current round. We characterize the optimal mechanism for this MDP as a Myerson's auction with a notion of modified virtual value, which relies on the value distribution of the advertiser, the current user state, and the future impact of showing the ad to the user. Leveraging this characterization, we design a sample-efficient and computationally-efficient algorithm which outputs an approximately optimal policy that requires only sample access to the true MDP and the value distributions of the bidders. Finally, we propose a simple mechanism built upon second price auctions with personalized reserve prices and show it can achieve a constant-factor approximation to the optimal long term discounted revenue. △ Less

Submitted 5 May, 2024; v1 submitted 16 February, 2023; originally announced February 2023.

Evolution of grammatical forms: some quantitative approaches

Authors: Jean-Marc Luck, Anita Mehta

Abstract: Grammatical forms are said to evolve via two main mechanisms. These are, respectively, the `descent' mechanism, where current forms can be seen to have descended (albeit with occasional modifications) from their roots in ancient languages, and the `contact' mechanism, where evolution in a given language occurs via borrowing from other languages with which it is in contact. We use ideas and concept… ▽ More Grammatical forms are said to evolve via two main mechanisms. These are, respectively, the `descent' mechanism, where current forms can be seen to have descended (albeit with occasional modifications) from their roots in ancient languages, and the `contact' mechanism, where evolution in a given language occurs via borrowing from other languages with which it is in contact. We use ideas and concepts from statistical physics to formulate a series of static and dynamical models which illustrate these issues in general terms. The static models emphasise the relative numbers of rules and exceptions, while the dynamical models focus on the emergence of exceptional forms. These unlikely survivors among various competing grammatical forms are winners against the odds. Our analysis suggests that they emerge when the influence of neighbouring languages exceeds the generic tendency towards regularisation within individual languages. △ Less

Submitted 6 February, 2023; originally announced February 2023.

Comments: 19 pages, 10 figures

Journal ref: Eur. Phys. J. B (2023) 96:19

Incentive Compatibility in the Auto-bidding World

Authors: Yeganeh Alimohammadi, Aranyak Mehta, Andres Perlroth

Abstract: Auto-bidding has recently become a popular feature in ad auctions. This feature enables advertisers to simply provide high-level constraints and goals to an automated agent, which optimizes their auction bids on their behalf. In this paper, we examine the effect of different auctions on the incentives of advertisers to report their constraints to the auto-bidder intermediaries. More precisely, we… ▽ More Auto-bidding has recently become a popular feature in ad auctions. This feature enables advertisers to simply provide high-level constraints and goals to an automated agent, which optimizes their auction bids on their behalf. In this paper, we examine the effect of different auctions on the incentives of advertisers to report their constraints to the auto-bidder intermediaries. More precisely, we study whether canonical auctions such as first price auction (FPA) and second price auction (SPA) are auto-bidding incentive compatible (AIC): whether an advertiser can gain by misreporting their constraints to the autobidder. We consider value-maximizing advertisers in two important settings: when they have a budget constraint and when they have a target cost-per-acquisition constraint. The main result of our work is that for both settings, FPA and SPA are not AIC. This contrasts with FPA being AIC when auto-bidders are constrained to bid using a (sub-optimal) uniform bidding policy. We further extend our main result and show that any (possibly randomized) auction that is truthful (in the classic profit-maximizing sense), scalar invariant and symmetric is not AIC. Finally, to complement our findings, we provide sufficient market conditions for FPA and SPA to become AIC for two advertisers. These conditions require advertisers' valuations to be well-aligned. This suggests that when the competition is intense for all queries, advertisers have less incentive to misreport their constraints. From a methodological standpoint, we develop a novel continuous model of queries. This model provides tractability to study equilibrium with auto-bidders, which contrasts with the standard discrete query model, which is known to be hard. Through the analysis of this model, we uncover a surprising result: in auto-bidding with two advertisers, FPA and SPA are auction equivalent. △ Less

Submitted 14 May, 2024; v1 submitted 31 January, 2023; originally announced January 2023.

Auctions without commitment in the auto-bidding world

Authors: Aranyak Mehta, Andres Perlroth

Abstract: Advertisers in online ad auctions are increasingly using auto-bidding mechanisms to bid into auctions instead of directly bidding their value manually. One prominent auto-bidding format is the target cost-per-acquisition (tCPA) which maximizes the volume of conversions subject to a return-of-investment constraint. From an auction theoretic perspective however, this trend seems to go against founda… ▽ More Advertisers in online ad auctions are increasingly using auto-bidding mechanisms to bid into auctions instead of directly bidding their value manually. One prominent auto-bidding format is the target cost-per-acquisition (tCPA) which maximizes the volume of conversions subject to a return-of-investment constraint. From an auction theoretic perspective however, this trend seems to go against foundational results that postulate that for profit-maximizing bidders, it is optimal to use a classic bidding system like marginal CPA (mCPA) bidding rather than using strategies like tCPA. In this paper we rationalize the adoption of such seemingly sub-optimal bidding within the canonical quasi-linear framework. The crux of the argument lies in the notion of commitment. We consider a multi-stage game where first the auctioneer declares the auction rules; then bidders select either the tCPA or mCPA bidding format and then, if the auctioneer lacks commitment, it can revisit the rules of the auction (e.g., may readjust reserve prices depending on the observed bids). Our main result is that so long as a bidder believes that the auctioneer lacks commitment to follow the rule of the declared auction then the bidder will make a higher profit by choosing the tCPA format over the mCPA format. We then explore the commitment consequences for the auctioneer. In a simplified version of the model where there is only one bidder, we show that the tCPA subgame admits a credible equilibrium while the mCPA format does not. That is, when the bidder chooses the tCPA format the auctioneer can credibly implement the auction rules announced at the beginning of the game. We also show that, under some mild conditions, the auctioneer's revenue is larger when the bidder uses the tCPA format rather than mCPA. We further quantify the value for the auctioneer to be able to commit to the declared auction rules. △ Less

Submitted 14 March, 2023; v1 submitted 18 January, 2023; originally announced January 2023.

Adversarial Online Multi-Task Reinforcement Learning

Authors: Quan Nguyen, Nishant A. Mehta

Abstract: We consider the adversarial online multi-task reinforcement learning setting, where in each of $K$ episodes the learner is given an unknown task taken from a finite set of $M$ unknown finite-horizon MDP models. The learner's objective is to minimize its regret with respect to the optimal policy for each task. We assume the MDPs in $\mathcal{M}$ are well-separated under a notion of $λ$-separability… ▽ More We consider the adversarial online multi-task reinforcement learning setting, where in each of $K$ episodes the learner is given an unknown task taken from a finite set of $M$ unknown finite-horizon MDP models. The learner's objective is to minimize its regret with respect to the optimal policy for each task. We assume the MDPs in $\mathcal{M}$ are well-separated under a notion of $λ$-separability, and show that this notion generalizes many task-separability notions from previous works. We prove a minimax lower bound of $Ω(K\sqrt{DSAH})$ on the regret of any learning algorithm and an instance-specific lower bound of $Ω(\frac{K}{λ^2})$ in sample complexity for a class of uniformly-good cluster-then-learn algorithms. We use a novel construction called 2-JAO MDP for proving the instance-specific lower bound. The lower bounds are complemented with a polynomial time algorithm that obtains $\tilde{O}(\frac{K}{λ^2})$ sample complexity guarantee for the clustering phase and $\tilde{O}(\sqrt{MK})$ regret guarantee for the learning phase, indicating that the dependency on $K$ and $\frac{1}{λ^2}$ is tight. △ Less

Submitted 10 January, 2023; originally announced January 2023.

Comments: To appear at the 34th International Conference on Algorithmic Learning Theory (ALT 2023)

RISO: Combining Rigid Grippers with Soft Switchable Adhesives

Authors: Shaunak A. Mehta, Yeunhee Kim, Joshua Hoegerman, Michael D. Bartlett, Dylan P. Losey

Abstract: Robot arms that assist humans should be able to pick up, move, and release everyday objects. Today's assistive robot arms use rigid grippers to pinch items between fingers; while these rigid grippers are well suited for large and heavy objects, they often struggle to grasp small, numerous, or delicate items (such as foods). Soft grippers cover the opposite end of the spectrum; these grippers use a… ▽ More Robot arms that assist humans should be able to pick up, move, and release everyday objects. Today's assistive robot arms use rigid grippers to pinch items between fingers; while these rigid grippers are well suited for large and heavy objects, they often struggle to grasp small, numerous, or delicate items (such as foods). Soft grippers cover the opposite end of the spectrum; these grippers use adhesives or change shape to wrap around small and irregular items, but cannot exert the large forces needed to manipulate heavy objects. In this paper we introduce RIgid-SOft (RISO) grippers that combine switchable soft adhesives with standard rigid mechanisms to enable a diverse range of robotic grasping. We develop RISO grippers by leveraging a novel class of soft materials that change adhesion force in real-time through pneumatically controlled shape and rigidity tuning. By mounting these soft adhesives on the bottom of rigid fingers, we create a gripper that can interact with objects using either purely rigid grasps (pinching the object) or purely soft grasps (adhering to the object). This increased capability requires additional decision making, and we therefore formulate a shared control approach that partially automates the motion of the robot arm. In practice, this controller aligns the RISO gripper while inferring which object the human wants to grasp and how the human wants to grasp that item. Our user study demonstrates that RISO grippers can pick up, move, and release household items from existing datasets, and that the system performs grasps more successfully and efficiently when sharing control between the human and robot. See videos here: https://youtu.be/5uLUkBYcnwg △ Less

Submitted 27 October, 2022; originally announced October 2022.

REMS: Middleware for Robotics Education and Development

Authors: Yusuke Tanaka, Ankur Mehta

Abstract: This paper introduces REMS, a robotics middleware and control framework that is designed to introduce the Zen of Python to robotics and to improve robotics education and development flow. Although existing middleware can serve hardware abstraction and modularity, setting up environments and learning middleware-specific syntax and procedures are less viable in education. They can curb opportunities… ▽ More This paper introduces REMS, a robotics middleware and control framework that is designed to introduce the Zen of Python to robotics and to improve robotics education and development flow. Although existing middleware can serve hardware abstraction and modularity, setting up environments and learning middleware-specific syntax and procedures are less viable in education. They can curb opportunities to understand robotics concepts, theories, and algorithms. Robotics is a field of integration; students and developers from various backgrounds will be involved in programming. Establishing Pythonic and object-oriented robotic framework in a natural way can enhance modular and abstracted programming for better readability, reusability, and simplicity, but also supports useful and practical skills generally in coding. REMS is to be a valuable robot educational medium not just as a tool and to be a platform from one robot to multi-agent across hardware, simulation, and analytical model implementations. △ Less

Submitted 11 October, 2022; originally announced October 2022.

Comments: Submission to ICRA2023

Why So Inflammatory? Explainability in Automatic Detection of Inflammatory Social Media Users

Authors: Cuong Nguyen, Daniel Nkemelu, Ankit Mehta, Michael Best

Abstract: Hate speech and misinformation, spread over social networking services (SNS) such as Facebook and Twitter, have inflamed ethnic and political violence in countries across the globe. We argue that there is limited research on this problem within the context of the Global South and present an approach for tackling them. Prior works have shown how machine learning models built with user-level interac… ▽ More Hate speech and misinformation, spread over social networking services (SNS) such as Facebook and Twitter, have inflamed ethnic and political violence in countries across the globe. We argue that there is limited research on this problem within the context of the Global South and present an approach for tackling them. Prior works have shown how machine learning models built with user-level interaction features can effectively identify users who spread inflammatory content. While this technique is beneficial in low-resource language settings where linguistic resources such as ground truth data and processing capabilities are lacking, it is still unclear how these interaction features contribute to model performance. In this work, we investigate and show significant differences in interaction features between users who spread inflammatory content and others who do not, applying explainability tools to understand our trained model. We find that features with higher interaction significance (such as account age and activity count) show higher explanatory power than features with lower interaction significance (such as name length and if the user has a location on their bio). Our work extends research directions that aim to understand the nature of inflammatory content in low-resource, high-risk contexts as the growth of social media use in the Global South outstrips moderation efforts. △ Less

Submitted 21 August, 2022; originally announced August 2022.

Comments: 6 pages. Spotlight paper at PML4DC 2022 workshop, co-located with ICLR 2022

MLExchange: A web-based platform enabling exchangeable machine learning workflows for scientific studies

Authors: Zhuowen Zhao, Tanny Chavez, Elizabeth A. Holman, Guanhua Hao, Adam Green, Harinarayan Krishnan, Dylan McReynolds, Ronald Pandolfi, Eric J. Roberts, Petrus H. Zwart, Howard Yanxon, Nicholas Schwarz, Subramanian Sankaranarayanan, Sergei V. Kalinin, Apurva Mehta, Stuart Campbell, Alexander Hexemer

Abstract: Machine learning (ML) algorithms are showing a growing trend in helping the scientific communities across different disciplines and institutions to address large and diverse data problems. However, many available ML tools are programmatically demanding and computationally costly. The MLExchange project aims to build a collaborative platform equipped with enabling tools that allow scientists and fa… ▽ More Machine learning (ML) algorithms are showing a growing trend in helping the scientific communities across different disciplines and institutions to address large and diverse data problems. However, many available ML tools are programmatically demanding and computationally costly. The MLExchange project aims to build a collaborative platform equipped with enabling tools that allow scientists and facility users who do not have a profound ML background to use ML and computational resources in scientific discovery. At the high level, we are targeting a full user experience where managing and exchanging ML algorithms, workflows, and data are readily available through web applications. Since each component is an independent container, the whole platform or its individual service(s) can be easily deployed at servers of different scales, ranging from a personal device (laptop, smart phone, etc.) to high performance clusters (HPC) accessed (simultaneously) by many users. Thus, MLExchange renders flexible using scenarios -- users could either access the services and resources from a remote server or run the whole platform or its individual service(s) within their local network. △ Less

Submitted 26 January, 2023; v1 submitted 20 August, 2022; originally announced August 2022.

Comments: The accepted version with DOI and IEEE copyright notice in the first page

Journal ref: 2022 4th IEEE/ACM Annual Workshop on Extreme-scale Experiment-in-the-Loop Computing (XLOOP)

Prior-Independent Auctions for Heterogeneous Bidders

Authors: Guru Guruganesh, Aranyak Mehta, Di Wang, Kangning Wang

Abstract: We study the design of prior-independent auctions in a setting with heterogeneous bidders. In particular, we consider the setting of selling to $n$ bidders whose values are drawn from $n$ independent but not necessarily identical distributions. We work in the robust auction design regime, where we assume the seller has no knowledge of the bidders' value distributions and must design a mechanism th… ▽ More We study the design of prior-independent auctions in a setting with heterogeneous bidders. In particular, we consider the setting of selling to $n$ bidders whose values are drawn from $n$ independent but not necessarily identical distributions. We work in the robust auction design regime, where we assume the seller has no knowledge of the bidders' value distributions and must design a mechanism that is prior-independent. While there have been many strong results on prior-independent auction design in the i.i.d. setting, not much is known for the heterogeneous setting, even though the latter is of significant practical importance. Unfortunately, no prior-independent mechanism can hope to always guarantee any approximation to Myerson's revenue in the heterogeneous setting; similarly, no prior-independent mechanism can consistently do better than the second-price auction. In light of this, we design a family of (parametrized) randomized auctions which approximates at least one of these benchmarks: For heterogeneous bidders with regular value distributions, our mechanisms either achieve a good approximation of the expected revenue of an optimal mechanism (which knows the bidders' distributions) or exceeds that of the second-price auction by a certain multiplicative factor. The factor in the latter case naturally trades off with the approximation ratio of the former case. We show that our mechanism is optimal for such a trade-off between the two cases by establishing a matching lower bound. Our result extends to selling $k$ identical items to heterogeneous bidders with an additional $O\big(\ln^2 k\big)$-factor in our trade-off between the two cases. △ Less

Submitted 7 November, 2023; v1 submitted 19 July, 2022; originally announced July 2022.

Comments: Full version of a paper in the Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

Efficiency of non-truthful auctions under auto-bidding

Authors: Christopher Liaw, Aranyak Mehta, Andres Perlroth

Abstract: Auto-bidding is now widely adopted as an interface between advertisers and internet advertising as it allows advertisers to specify high-level goals, such as maximizing value subject to a value-per-spend constraint. Prior research has mostly focused on auctions which are truthful (such as SPA) since uniform bidding is optimal in such auctions, which makes it manageable to reason about equilibria.… ▽ More Auto-bidding is now widely adopted as an interface between advertisers and internet advertising as it allows advertisers to specify high-level goals, such as maximizing value subject to a value-per-spend constraint. Prior research has mostly focused on auctions which are truthful (such as SPA) since uniform bidding is optimal in such auctions, which makes it manageable to reason about equilibria. A tantalizing question is whether one can obtain more efficient outcomes by leaving the realm of truthful auctions. This is the first paper to study non-truthful auctions in the prior-free auto-bidding setting. Our first result is that non-truthfulness provides no benefit when one considers deterministic auctions. Any deterministic mechanism has a price of anarchy (PoA) of at least $2$, even for $2$ bidders; this matches what can be achieved by deterministic truthful mechanisms. In particular, we prove that the first price auction has PoA of exactly $2$. For our second result, we construct a randomized non-truthful auction that achieves a PoA of $1.8$ for $2$ bidders. This is the best-known PoA for this problem. The previously best-known PoA for this problem was $1.9$ and was achieved with a truthful mechanism. Moreover, we demonstrate the benefit of non-truthfulness in this setting by showing that the truthful version of this randomized auction also has a PoA of $1.9$. Finally, we show that no auction (even randomized, non-truthful) can improve upon a PoA bound of $2$ as the number of advertisers grow to infinity. △ Less

Submitted 7 July, 2022; originally announced July 2022.