Showing 1–50 of 72 results for author: Garg, N

Optimal Strategies in Ranked-Choice Voting

Authors: Sanyukta Deshpande, Nikhil Garg, Sheldon Jacobson

Abstract: Ranked Choice Voting (RCV) and Single Transferable Voting (STV) are widely valued; but are complex to understand due to intricate per-round vote transfers. Questions like determining how far a candidate is from winning or identifying effective election strategies are computationally challenging as minor changes in voter rankings can lead to significant ripple effects - for example, lending support… ▽ More Ranked Choice Voting (RCV) and Single Transferable Voting (STV) are widely valued; but are complex to understand due to intricate per-round vote transfers. Questions like determining how far a candidate is from winning or identifying effective election strategies are computationally challenging as minor changes in voter rankings can lead to significant ripple effects - for example, lending support to a losing candidate can prevent their votes from transferring to a more competitive opponent. We study optimal strategies - persuading voters to change their ballots or adding new voters - both algorithmically and theoretically. Algorithmically, we develop efficient methods to reduce election instances while maintaining optimization accuracy, effectively circumventing the computational complexity barrier. Theoretically, we analyze the effectiveness of strategies under both perfect and imperfect polling information. Our algorithmic approach applies to the ranked-choice polling data on the US 2024 Republican Primary, finding, for example, that several candidates would have been optimally served by boosting another candidate instead of themselves. △ Less

Submitted 18 July, 2024; originally announced July 2024.

Algorithms for College Admissions Decision Support: Impacts of Policy Change and Inherent Variability

Authors: Jinsook Lee, Emma Harvey, Joyce Zhou, Nikhil Garg, Thorsten Joachims, Rene F. Kizilcec

Abstract: Each year, selective American colleges sort through tens of thousands of applications to identify a first-year class that displays both academic merit and diversity. In the 2023-2024 admissions cycle, these colleges faced unprecedented challenges. First, the number of applications has been steadily growing. Second, test-optional policies that have remained in place since the COVID-19 pandemic limi… ▽ More Each year, selective American colleges sort through tens of thousands of applications to identify a first-year class that displays both academic merit and diversity. In the 2023-2024 admissions cycle, these colleges faced unprecedented challenges. First, the number of applications has been steadily growing. Second, test-optional policies that have remained in place since the COVID-19 pandemic limit access to key information historically predictive of academic success. Most recently, longstanding debates over affirmative action culminated in the Supreme Court banning race-conscious admissions. Colleges have explored machine learning (ML) models to address the issues of scale and missing test scores, often via ranking algorithms intended to focus on 'top' applicants. However, the Court's ruling will force changes to these models, which were able to consider race as a factor in ranking. There is currently a poor understanding of how these mandated changes will shape applicant ranking algorithms, and, by extension, admitted classes. We seek to address this by quantifying the impact of different admission policies on the applications prioritized for review. We show that removing race data from a developed applicant ranking algorithm reduces the diversity of the top-ranked pool without meaningfully increasing the academic merit of that pool. We contextualize this impact by showing that excluding data on applicant race has a greater impact than excluding other potentially informative variables like intended majors. Finally, we measure the impact of policy change on individuals by comparing the arbitrariness in applicant rank attributable to policy change to the arbitrariness attributable to randomness. We find that any given policy has a high degree of arbitrariness and that removing race data from the ranking algorithm increases arbitrariness in outcomes for most applicants. △ Less

Submitted 24 June, 2024; originally announced July 2024.

Comments: 25 pages, 8 figures

Equitable Congestion Pricing under the Markovian Traffic Model: An Application to Bogota

Authors: Alfredo Torrico, Natthawut Boonsiriphatthanajaroen, Nikhil Garg, Andrea Lodi, Hugo Mainguy

Abstract: Congestion pricing is used to raise revenues and reduce traffic and pollution. However, people have heterogeneous spatial demand patterns and willingness (or ability) to pay tolls, and so pricing may have substantial equity implications. We develop a data-driven approach to design congestion pricing given policymakers' equity and efficiency objectives. First, algorithmically, we extend the Markovi… ▽ More Congestion pricing is used to raise revenues and reduce traffic and pollution. However, people have heterogeneous spatial demand patterns and willingness (or ability) to pay tolls, and so pricing may have substantial equity implications. We develop a data-driven approach to design congestion pricing given policymakers' equity and efficiency objectives. First, algorithmically, we extend the Markovian traffic equilibrium setting introduced by Baillon & Cominetti (2008) to model heterogeneous populations and incorporate prices and outside options such as public transit. Second, we empirically evaluate various pricing schemes using data collected by an industry partner in the city of Bogota, one of the most congested cities in the world. We find that pricing personalized to each economic stratum can be substantially more efficient and equitable than uniform pricing; however, non-personalized but area-based pricing can recover much of the gap. △ Less

Submitted 6 July, 2024; originally announced July 2024.

Versatile CMOS Analog LIF Neuron for Memristor-Integrated Neuromorphic Circuits

Authors: Nikhil Garg, Davide Florini, Patrick Dufour, Eloir Muhr, Mathieu Faye, Marc Bocquet, Damien Querlioz, Yann Beilliard, Dominique Drouin, Fabien Alibart, Jean-Michel Portal

Abstract: Heterogeneous systems with analog CMOS circuits integrated with nanoscale memristive devices enable efficient deployment of neural networks on neuromorphic hardware. CMOS Neuron with low footprint can emulate slow temporal dynamics by operating with extremely low current levels. Nevertheless, the current read from the memristive synapses can be higher by several orders of magnitude, and performing… ▽ More Heterogeneous systems with analog CMOS circuits integrated with nanoscale memristive devices enable efficient deployment of neural networks on neuromorphic hardware. CMOS Neuron with low footprint can emulate slow temporal dynamics by operating with extremely low current levels. Nevertheless, the current read from the memristive synapses can be higher by several orders of magnitude, and performing impedance matching between neurons and synapses is mandatory. In this paper, we implement an analog leaky integrate and fire (LIF) neuron with a voltage regulator and current attenuator for interfacing CMOS neurons with memristive synapses. In addition, the neuron design proposes a dual leakage that could enable the implementation of local learning rules such as voltage-dependent synaptic plasticity. We also propose a connection scheme to implement adaptive LIF neurons based on two-neuron interaction. The proposed circuits can be used to interface with a variety of synaptic devices and process signals of diverse temporal dynamics. △ Less

Submitted 28 June, 2024; originally announced June 2024.

Comments: Accepted to International Conference on Neuromorphic Systems (ICONS 2024)

RL on Incorrect Synthetic Data Scales the Efficiency of LLM Math Reasoning by Eight-Fold

Authors: Amrith Setlur, Saurabh Garg, Xinyang Geng, Naman Garg, Virginia Smith, Aviral Kumar

Abstract: Training on model-generated synthetic data is a promising approach for finetuning LLMs, but it remains unclear when it helps or hurts. In this paper, we investigate this question for math reasoning via an empirical study, followed by building a conceptual understanding of our observations. First, we find that while the typical approach of finetuning a model on synthetic correct or positive problem… ▽ More Training on model-generated synthetic data is a promising approach for finetuning LLMs, but it remains unclear when it helps or hurts. In this paper, we investigate this question for math reasoning via an empirical study, followed by building a conceptual understanding of our observations. First, we find that while the typical approach of finetuning a model on synthetic correct or positive problem-solution pairs generated by capable models offers modest performance gains, sampling more correct solutions from the finetuned learner itself followed by subsequent fine-tuning on this self-generated data $\textbf{doubles}$ the efficiency of the same synthetic problems. At the same time, training on model-generated positives can amplify various spurious correlations, resulting in flat or even inverse scaling trends as the amount of data increases. Surprisingly, we find that several of these issues can be addressed if we also utilize negative responses, i.e., model-generated responses that are deemed incorrect by a final answer verifier. Crucially, these negatives must be constructed such that the training can appropriately recover the utility or advantage of each intermediate step in the negative response. With this per-step scheme, we are able to attain consistent gains over only positive data, attaining performance similar to amplifying the amount of synthetic data by $\mathbf{8 \times}$. We show that training on per-step negatives can help to unlearn spurious correlations in the positive data, and is equivalent to advantage-weighted reinforcement learning (RL), implying that it inherits robustness benefits of RL over imitating positive data alone. △ Less

Submitted 20 June, 2024; originally announced June 2024.

Addressing Discretization-Induced Bias in Demographic Prediction

Authors: Evan Dong, Aaron Schein, Yixin Wang, Nikhil Garg

Abstract: Racial and other demographic imputation is necessary for many applications, especially in auditing disparities and outreach targeting in political campaigns. The canonical approach is to construct continuous predictions -- e.g., based on name and geography -- and then to $\textit{discretize}$ the predictions by selecting the most likely class (argmax). We study how this practice produces… ▽ More Racial and other demographic imputation is necessary for many applications, especially in auditing disparities and outreach targeting in political campaigns. The canonical approach is to construct continuous predictions -- e.g., based on name and geography -- and then to $\textit{discretize}$ the predictions by selecting the most likely class (argmax). We study how this practice produces $\textit{discretization bias}$. In particular, we show that argmax labeling, as used by a prominent commercial voter file vendor to impute race/ethnicity, results in a substantial under-count of African-American voters, e.g., by 28.2% points in North Carolina. This bias can have substantial implications in downstream tasks that use such labels. We then introduce a $\textit{joint optimization}$ approach -- and a tractable $\textit{data-driven thresholding}$ heuristic -- that can eliminate this bias, with negligible individual-level accuracy loss. Finally, we theoretically analyze discretization bias, show that calibrated continuous models are insufficient to eliminate it, and that an approach such as ours is necessary. Broadly, we warn researchers and practitioners against discretizing continuous demographic predictions without considering downstream consequences. △ Less

Submitted 26 May, 2024; originally announced May 2024.

Comments: A version of this paper was accepted to the 2024 ACM Conference on Fairness, Accountability, and Transparency

ACM Class: K.4.0

Improvement in Semantic Address Matching using Natural Language Processing

Authors: Vansh Gupta, Mohit Gupta, Jai Garg, Nitesh Garg

Abstract: Address matching is an important task for many businesses especially delivery and take out companies which help them to take out a certain address from their data warehouse. Existing solution uses similarity of strings, and edit distance algorithms to find out the similar addresses from the address database, but these algorithms could not work effectively with redundant, unstructured, or incomplet… ▽ More Address matching is an important task for many businesses especially delivery and take out companies which help them to take out a certain address from their data warehouse. Existing solution uses similarity of strings, and edit distance algorithms to find out the similar addresses from the address database, but these algorithms could not work effectively with redundant, unstructured, or incomplete address data. This paper discuss semantic Address matching technique, by which we can find out a particular address from a list of possible addresses. We have also reviewed existing practices and their shortcoming. Semantic address matching is an essentially NLP task in the field of deep learning. Through this technique We have the ability to triumph the drawbacks of existing methods like redundant or abbreviated data problems. The solution uses the OCR on invoices to extract the address and create the data pool of addresses. Then this data is fed to the algorithm BM-25 for scoring the best matching entries. Then to observe the best result, this will pass through BERT for giving the best possible result from the similar queries. Our investigation exhibits that our methodology enormously improves both accuracy and review of cutting-edge technology existing techniques. △ Less

Submitted 17 April, 2024; originally announced April 2024.

Comments: 5 pages, 7 tables, 2021 2nd International Conference for Emerging Technology (INCET)

Journal ref: 2021 2nd International Conference for Emerging Technology (INCET), Belagavi, India, 2021, pp. 1-5

Designing an Intelligent Parcel Management System using IoT & Machine Learning

Authors: Mohit Gupta, Nitesh Garg, Jai Garg, Vansh Gupta, Devraj Gautam

Abstract: Parcels delivery is a critical activity in railways. More importantly, each parcel must be thoroughly checked and sorted according to its destination address. We require an efficient and robust IoT system capable of doing all of these tasks with great precision and minimal human interaction. This paper discusses, We created a fully-fledged solution using IoT and machine learning to assist trains i… ▽ More Parcels delivery is a critical activity in railways. More importantly, each parcel must be thoroughly checked and sorted according to its destination address. We require an efficient and robust IoT system capable of doing all of these tasks with great precision and minimal human interaction. This paper discusses, We created a fully-fledged solution using IoT and machine learning to assist trains in performing this operation efficiently. In this study, we covered the product, which consists mostly of two phases. Scanning is the first step, followed by sorting. During the scanning process, the parcel will be passed through three scanners that will look for explosives, drugs, and any dangerous materials in the parcel and will trash it if any of the tests fail. When the scanning step is over, the parcel moves on to the sorting phase, where we use QR codes to retrieve the details of the parcels and sort them properly. The simulation of the system is done using the blender software. Our research shows that our procedure significantly improves accuracy as well as the assessment of cutting-edge technology and existing techniques. △ Less

Submitted 17 April, 2024; originally announced April 2024.

Comments: 6 pages, 6 figures, 2022 IEEE IAS Global Conference on Emerging Technologies (GlobConET)

Journal ref: 2022 IEEE IAS Global Conference on Emerging Technologies (GlobConET), Arad, Romania, 2022, pp. 751-756

Joint Power Allocation and Beamforming for In-band Full-duplex Multi-cell Multi-user Networks

Authors: Haifeng Luo, Navneet Garg, Mark Holm, Tharmalingam Ratnarajah

Abstract: This paper investigates a robust joint power allocation and beamforming scheme for in-band full-duplex multi-cell multi-user (IBFD-MCMU) networks. A mean-squared error (MSE) minimization problem is formulated with constraints on the power budgets and residual self-interference (RSI) power. The problem is not convex, so we decompose it into two sub-problems: interference management beamforming and… ▽ More This paper investigates a robust joint power allocation and beamforming scheme for in-band full-duplex multi-cell multi-user (IBFD-MCMU) networks. A mean-squared error (MSE) minimization problem is formulated with constraints on the power budgets and residual self-interference (RSI) power. The problem is not convex, so we decompose it into two sub-problems: interference management beamforming and power allocation, and give closed-form solutions to the sub-problems. Then we propose an iterative algorithm to yield an overall solution. The computational complexity and convergence behavior of the algorithm are analyzed. Our method can enhance the analog self-interference cancellation (ASIC) depth provided by the precoder with less effect on the downlink communication than the existing null-space projection method, inspiring a low-cost but efficient IBFD transceiver design. It can achieve 42.9% of IBFD gain in terms of spectral efficiency with only antenna isolation, while this value increases to 60.9% with further digital self-interference cancellation (DSIC). Numerical results illustrate that our algorithm is robust to hardware impairments and channel uncertainty. With sufficient ASIC depth, our method reduces the computation time by at least 20% than the existing scheme due to its faster convergence speed at the cost of < 12.5% sum rate loss. The benefit is much more significant with single-antenna users that our algorithm saves at least 40% of the computation time at the cost of < 10% sum rate reduction. △ Less

Submitted 16 March, 2024; originally announced March 2024.

On the Secrecy Rate of In-Band Full-duplex Two-way Wiretap Channel

Authors: Navneet Garg, Haifeng Luo, Tharmalingam Ratnarajah

Abstract: In this paper, we consider a two-way wiretap Multi-Input Multi-Output Multi-antenna Eve (MIMOME) channel, where both nodes (Alice and Bob) transmit and receive in an in-band full-duplex (IBFD) manner. For this system with keyless security, we provide a novel artificial noise (AN) based signal design, where the AN is injected in both signal and null spaces. We present an ergodic secrecy rate approx… ▽ More In this paper, we consider a two-way wiretap Multi-Input Multi-Output Multi-antenna Eve (MIMOME) channel, where both nodes (Alice and Bob) transmit and receive in an in-band full-duplex (IBFD) manner. For this system with keyless security, we provide a novel artificial noise (AN) based signal design, where the AN is injected in both signal and null spaces. We present an ergodic secrecy rate approximation to derive the power allocation algorithm. We consider scenarios where AN is known and unknown to legitimate users and include imperfect channel information effects. To maximize secrecy rates subject to the transmit power constraint, a two-step power allocation solution is proposed, where the first step is known at Eve, and the second step helps to improve the secrecy further. We also consider scenarios where partial information is known by Eve and the effects of non-ideal self-interference cancellation. The usefulness and limitations of the resulting power allocation solution are analyzed and verified via simulations. Results show that secrecy rates are less when AN is unknown to receivers or Eve has more information about legitimate users. Since the ergodic approximation only considers Eves distance, the resulting power allocation provides secrecy rates close to the actual ones. △ Less

Submitted 11 March, 2024; originally announced March 2024.

The Flow Game: Leximin and Leximax Core Imputations

Authors: Rohith R. Gangam, Naveen Garg, Parnian Shahkar, Vijay V. Vazirani

Abstract: Recently [Vaz24] gave mechanisms for finding leximin and leximax core imputations for the assignment game and remarked, "Within the area of algorithm design, the "right" technique for solving several types of algorithmic questions was first discovered in the context of matching and later these insights were applied to other problems. We expect a similar phenomenon here." One of the games explicitl… ▽ More Recently [Vaz24] gave mechanisms for finding leximin and leximax core imputations for the assignment game and remarked, "Within the area of algorithm design, the "right" technique for solving several types of algorithmic questions was first discovered in the context of matching and later these insights were applied to other problems. We expect a similar phenomenon here." One of the games explicitly mentioned in this context was the flow game of Kalai and Zemel [KZ82]. In this paper, we give strongly polynomial time mechanisms for computing the leximin and leximax core imputations for the flow game, among the set of core imputations that are captured as optimal solutions to the dual LP. We address two versions: 1. The imputations are leximin and leximax with respect to the distance labels of edges. 2. The imputations are leximin and leximax with respect to the product of capacities of edges and their distance labels. △ Less

Submitted 9 March, 2024; originally announced March 2024.

Comments: 10 pages

Wisdom and Foolishness of Noisy Matching Markets

Authors: Kenny Peng, Nikhil Garg

Abstract: We consider a many-to-one matching market where colleges share true preferences over students but make decisions using only independent noisy rankings. Each student has a true value $v$, but each college $c$ ranks the student according to an independently drawn estimated value $v + X_c$ for $X_c\sim \mathcal{D}.$ We ask a basic question about the resulting stable matching: How noisy is the set of… ▽ More We consider a many-to-one matching market where colleges share true preferences over students but make decisions using only independent noisy rankings. Each student has a true value $v$, but each college $c$ ranks the student according to an independently drawn estimated value $v + X_c$ for $X_c\sim \mathcal{D}.$ We ask a basic question about the resulting stable matching: How noisy is the set of matched students? Two striking effects can occur in large markets (i.e., with a continuum of students and a large number of colleges). When $\mathcal{D}$ is light-tailed, noise is fully attenuated: only the highest-value students are matched. When $\mathcal{D}$ is long-tailed, noise is fully amplified: students are matched uniformly at random. These results hold for any distribution of student preferences over colleges, and extend to when only subsets of colleges agree on true student valuations instead of the entire market. More broadly, our framework provides a tractable approach to analyze implications of imperfect preference formation in large markets. △ Less

Submitted 26 February, 2024; originally announced February 2024.

IMUOptimize: A Data-Driven Approach to Optimal IMU Placement for Human Pose Estimation with Transformer Architecture

Authors: Varun Ramani, Hossein Khayami, Yang Bai, Nakul Garg, Nirupam Roy

Abstract: This paper presents a novel approach for predicting human poses using IMU data, diverging from previous studies such as DIP-IMU, IMUPoser, and TransPose, which use up to 6 IMUs in conjunction with bidirectional RNNs. We introduce two main innovations: a data-driven strategy for optimal IMU placement and a transformer-based model architecture for time series analysis. Our findings indicate that our… ▽ More This paper presents a novel approach for predicting human poses using IMU data, diverging from previous studies such as DIP-IMU, IMUPoser, and TransPose, which use up to 6 IMUs in conjunction with bidirectional RNNs. We introduce two main innovations: a data-driven strategy for optimal IMU placement and a transformer-based model architecture for time series analysis. Our findings indicate that our approach not only outperforms traditional 6 IMU-based biRNN models but also that the transformer architecture significantly enhances pose reconstruction from data obtained from 24 IMU locations, with equivalent performance to biRNNs when using only 6 IMUs. The enhanced accuracy provided by our optimally chosen locations, when coupled with the parallelizability and performance of transformers, provides significant improvements to the field of IMU-based pose estimation. △ Less

Submitted 16 February, 2024; v1 submitted 13 February, 2024; originally announced February 2024.

Comments: 8 pages, 16 figures

ExTraCT -- Explainable Trajectory Corrections from language inputs using Textual description of features

Authors: J-Anne Yow, Neha Priyadarshini Garg, Manoj Ramanathan, Wei Tech Ang

Abstract: Natural language provides an intuitive and expressive way of conveying human intent to robots. Prior works employed end-to-end methods for learning trajectory deformations from language corrections. However, such methods do not generalize to new initial trajectories or object configurations. This work presents ExTraCT, a modular framework for trajectory corrections using natural language that comb… ▽ More Natural language provides an intuitive and expressive way of conveying human intent to robots. Prior works employed end-to-end methods for learning trajectory deformations from language corrections. However, such methods do not generalize to new initial trajectories or object configurations. This work presents ExTraCT, a modular framework for trajectory corrections using natural language that combines Large Language Models (LLMs) for natural language understanding and trajectory deformation functions. Given a scene, ExTraCT generates the trajectory modification features (scene-specific and scene-independent) and their corresponding natural language textual descriptions for the objects in the scene online based on a template. We use LLMs for semantic matching of user utterances to the textual descriptions of features. Based on the feature matched, a trajectory modification function is applied to the initial trajectory, allowing generalization to unseen trajectories and object configurations. Through user studies conducted both in simulation and with a physical robot arm, we demonstrate that trajectories deformed using our method were more accurate and were preferred in about 80\% of cases, outperforming the baseline. We also showcase the versatility of our system in a manipulation task and an assistive feeding task. △ Less

Submitted 8 January, 2024; originally announced January 2024.

Comments: 11 pages, 7 figures

A Bayesian Spatial Model to Correct Under-Reporting in Urban Crowdsourcing

Authors: Gabriel Agostini, Emma Pierson, Nikhil Garg

Abstract: Decision-makers often observe the occurrence of events through a reporting process. City governments, for example, rely on resident reports to find and then resolve urban infrastructural problems such as fallen street trees, flooded basements, or rat infestations. Without additional assumptions, there is no way to distinguish events that occur but are not reported from events that truly did not oc… ▽ More Decision-makers often observe the occurrence of events through a reporting process. City governments, for example, rely on resident reports to find and then resolve urban infrastructural problems such as fallen street trees, flooded basements, or rat infestations. Without additional assumptions, there is no way to distinguish events that occur but are not reported from events that truly did not occur--a fundamental problem in settings with positive-unlabeled data. Because disparities in reporting rates correlate with resident demographics, addressing incidents only on the basis of reports leads to systematic neglect in neighborhoods that are less likely to report events. We show how to overcome this challenge by leveraging the fact that events are spatially correlated. Our framework uses a Bayesian spatial latent variable model to infer event occurrence probabilities and applies it to storm-induced flooding reports in New York City, further pooling results across multiple storms. We show that a model accounting for under-reporting and spatial correlation predicts future reports more accurately than other models, and further induces a more equitable set of inspections: its allocations better reflect the population and provide equitable service to non-white, less traditionally educated, and lower-income residents. This finding reflects heterogeneous reporting behavior learned by the model: reporting rates are higher in Census tracts with higher populations, proportions of white residents, and proportions of owner-occupied households. Our work lays the groundwork for more equitable proactive government services, even with disparate reporting behavior. △ Less

Submitted 18 December, 2023; originally announced December 2023.

Comments: To appear in the 38th Annual AAAI Conference on Artificial Intelligence (AAAI-24)

Monoculture in Matching Markets

Authors: Kenny Peng, Nikhil Garg

Abstract: Algorithmic monoculture arises when many decision-makers rely on the same algorithm to evaluate applicants. An emerging body of work investigates possible harms of this kind of homogeneity, but has been limited by the challenge of incorporating market effects in which the preferences and behavior of many applicants and decision-makers jointly interact to determine outcomes. Addressing this chall… ▽ More Algorithmic monoculture arises when many decision-makers rely on the same algorithm to evaluate applicants. An emerging body of work investigates possible harms of this kind of homogeneity, but has been limited by the challenge of incorporating market effects in which the preferences and behavior of many applicants and decision-makers jointly interact to determine outcomes. Addressing this challenge, we introduce a tractable theoretical model of algorithmic monoculture in a two-sided matching market with many participants. We use the model to analyze outcomes under monoculture (when decision-makers all evaluate applicants using a common algorithm) and under polyculture (when decision-makers evaluate applicants independently). All else equal, monoculture (1) selects less-preferred applicants when noise is well-behaved, (2) matches more applicants to their top choice, though individual applicants may be worse off depending on their value to decision-makers and risk tolerance, and (3) is more robust to disparities in the number of applications submitted. △ Less

Submitted 15 December, 2023; originally announced December 2023.

Domain constraints improve risk prediction when outcome data is missing

Authors: Sidhika Balachandar, Nikhil Garg, Emma Pierson

Abstract: Machine learning models are often trained to predict the outcome resulting from a human decision. For example, if a doctor decides to test a patient for disease, will the patient test positive? A challenge is that historical decision-making determines whether the outcome is observed: we only observe test outcomes for patients doctors historically tested. Untested patients, for whom outcomes are un… ▽ More Machine learning models are often trained to predict the outcome resulting from a human decision. For example, if a doctor decides to test a patient for disease, will the patient test positive? A challenge is that historical decision-making determines whether the outcome is observed: we only observe test outcomes for patients doctors historically tested. Untested patients, for whom outcomes are unobserved, may differ from tested patients along observed and unobserved dimensions. We propose a Bayesian model class which captures this setting. The purpose of the model is to accurately estimate risk for both tested and untested patients. Estimating this model is challenging due to the wide range of possibilities for untested patients. To address this, we propose two domain constraints which are plausible in health settings: a prevalence constraint, where the overall disease prevalence is known, and an expertise constraint, where the human decision-maker deviates from purely risk-based decision-making only along a constrained feature set. We show theoretically and on synthetic data that domain constraints improve parameter inference. We apply our model to a case study of cancer risk prediction, showing that the model's inferred risk predicts cancer diagnoses, its inferred testing policy captures known public health policies, and it can identify suboptimalities in test allocation. Though our case study is in healthcare, our analysis reveals a general class of domain constraints which can improve model estimation in many settings. △ Less

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

Comments: Published at ICLR 2024

Sustainable Concrete via Bayesian Optimization

Authors: Sebastian Ament, Andrew Witte, Nishant Garg, Julius Kusuma

Abstract: Eight percent of global carbon dioxide emissions can be attributed to the production of cement, the main component of concrete, which is also the dominant source of CO2 emissions in the construction of data centers. The discovery of lower-carbon concrete formulae is therefore of high significance for sustainability. However, experimenting with new concrete formulae is time consuming and labor inte… ▽ More Eight percent of global carbon dioxide emissions can be attributed to the production of cement, the main component of concrete, which is also the dominant source of CO2 emissions in the construction of data centers. The discovery of lower-carbon concrete formulae is therefore of high significance for sustainability. However, experimenting with new concrete formulae is time consuming and labor intensive, as one usually has to wait to record the concrete's 28-day compressive strength, a quantity whose measurement can by its definition not be accelerated. This provides an opportunity for experimental design methodology like Bayesian Optimization (BO) to accelerate the search for strong and sustainable concrete formulae. Herein, we 1) propose modeling steps that make concrete strength amenable to be predicted accurately by a Gaussian process model with relatively few measurements, 2) formulate the search for sustainable concrete as a multi-objective optimization problem, and 3) leverage the proposed model to carry out multi-objective BO with real-world strength measurements of the algorithmically proposed mixes. Our experimental results show improved trade-offs between the mixtures' global warming potential (GWP) and their associated compressive strengths, compared to mixes based on current industry practices. Our methods are open-sourced at github.com/facebookresearch/SustainableConcrete. △ Less

Submitted 20 November, 2023; v1 submitted 27 October, 2023; originally announced October 2023.

Comments: NeurIPS 2023 Workshop on Adaptive Experimental Design and Active Learning in the Real World

Fast Localization and Tracking in City-Scale UWB Networks

Authors: Nakul Garg, Irtaza Shahid, Ramanujan K Sheshadri, Karthikeyan Sundaresan, Nirupam Roy

Abstract: Localization of networked nodes is an essential problem in emerging applications, including first-responder navigation, automated manufacturing lines, vehicular and drone navigation, asset navigation and tracking, Internet of Things and 5G communication networks. In this paper, we present Locate3D, a novel system for peer-to-peer node localization and orientation estimation in large networks. Unli… ▽ More Localization of networked nodes is an essential problem in emerging applications, including first-responder navigation, automated manufacturing lines, vehicular and drone navigation, asset navigation and tracking, Internet of Things and 5G communication networks. In this paper, we present Locate3D, a novel system for peer-to-peer node localization and orientation estimation in large networks. Unlike traditional range-only methods, Locate3D introduces angle-of-arrival (AoA) data as an added network topology constraint. The system solves three key challenges: it uses angles to reduce the number of measurements required by 4x and jointly use range and angle data for location estimation. We develop a spanning-tree approach for fast location updates, and to ensure the output graphs are rigid and uniquely realizable, even in occluded or weakly connected areas. Locate3D cuts down latency by up to 75% without compromising accuracy, surpassing standard range-only solutions. It has a 10.2 meters median localization error for large-scale networks (30,000 nodes, 15 anchors spread across 14km square) and 0.5 meters for small-scale networks (10 nodes). △ Less

Submitted 3 October, 2023; originally announced October 2023.

Reconciling the accuracy-diversity trade-off in recommendations

Authors: Kenny Peng, Manish Raghavan, Emma Pierson, Jon Kleinberg, Nikhil Garg

Abstract: In recommendation settings, there is an apparent trade-off between the goals of accuracy (to recommend items a user is most likely to want) and diversity (to recommend items representing a range of categories). As such, real-world recommender systems often explicitly incorporate diversity separately from accuracy. This approach, however, leaves a basic question unanswered: Why is there a trade-off… ▽ More In recommendation settings, there is an apparent trade-off between the goals of accuracy (to recommend items a user is most likely to want) and diversity (to recommend items representing a range of categories). As such, real-world recommender systems often explicitly incorporate diversity separately from accuracy. This approach, however, leaves a basic question unanswered: Why is there a trade-off in the first place? We show how the trade-off can be explained via a user's consumption constraints -- users typically only consume a few of the items they are recommended. In a stylized model we introduce, objectives that account for this constraint induce diverse recommendations, while objectives that do not account for this constraint induce homogeneous recommendations. This suggests that accuracy and diversity appear misaligned because standard accuracy metrics do not consider consumption constraints. Our model yields precise and interpretable characterizations of diversity in different settings, giving practical insights into the design of diverse recommendations. △ Less

Submitted 27 July, 2023; originally announced July 2023.

Comments: 34 pages, 5 figures

Interface Design to Mitigate Inflation in Recommender Systems

Authors: Rana Shahout, Yehonatan Peisakhovsky, Sasha Stoikov, Nikhil Garg

Abstract: Recommendation systems rely on user-provided data to learn about item quality and provide personalized recommendations. An implicit assumption when aggregating ratings into item quality is that ratings are strong indicators of item quality. In this work, we test this assumption using data collected from a music discovery application. Our study focuses on two factors that cause rating inflation: he… ▽ More Recommendation systems rely on user-provided data to learn about item quality and provide personalized recommendations. An implicit assumption when aggregating ratings into item quality is that ratings are strong indicators of item quality. In this work, we test this assumption using data collected from a music discovery application. Our study focuses on two factors that cause rating inflation: heterogeneous user rating behavior and the dynamics of personalized recommendations. We show that user rating behavior substantially varies by user, leading to item quality estimates that reflect the users who rated an item more than the item quality itself. Additionally, items that are more likely to be shown via personalized recommendations can experience a substantial increase in their exposure and potential bias toward them. To mitigate these effects, we analyze the results of a randomized controlled trial in which the rating interface was modified. The test resulted in a substantial improvement in user rating behavior and a reduction in item quality inflation. These findings highlight the importance of carefully considering the assumptions underlying recommendation systems and designing interfaces that encourage accurate rating behavior. △ Less

Submitted 25 July, 2023; v1 submitted 23 July, 2023; originally announced July 2023.

Topics, Authors, and Institutions in Large Language Model Research: Trends from 17K arXiv Papers

Authors: Rajiv Movva, Sidhika Balachandar, Kenny Peng, Gabriel Agostini, Nikhil Garg, Emma Pierson

Abstract: Large language models (LLMs) are dramatically influencing AI research, spurring discussions on what has changed so far and how to shape the field's future. To clarify such questions, we analyze a new dataset of 16,979 LLM-related arXiv papers, focusing on recent trends in 2023 vs. 2018-2022. First, we study disciplinary shifts: LLM research increasingly considers societal impacts, evidenced by 20x… ▽ More Large language models (LLMs) are dramatically influencing AI research, spurring discussions on what has changed so far and how to shape the field's future. To clarify such questions, we analyze a new dataset of 16,979 LLM-related arXiv papers, focusing on recent trends in 2023 vs. 2018-2022. First, we study disciplinary shifts: LLM research increasingly considers societal impacts, evidenced by 20x growth in LLM submissions to the Computers and Society sub-arXiv. An influx of new authors -- half of all first authors in 2023 -- are entering from non-NLP fields of CS, driving disciplinary expansion. Second, we study industry and academic publishing trends. Surprisingly, industry accounts for a smaller publication share in 2023, largely due to reduced output from Google and other Big Tech companies; universities in Asia are publishing more. Third, we study institutional collaboration: while industry-academic collaborations are common, they tend to focus on the same topics that industry focuses on rather than bridging differences. The most prolific institutions are all US- or China-based, but there is very little cross-country collaboration. We discuss implications around (1) how to support the influx of new authors, (2) how industry trends may affect academics, and (3) possible effects of (the lack of) collaboration. △ Less

Submitted 28 April, 2024; v1 submitted 20 July, 2023; originally announced July 2023.

Comments: NAACL 2024. Data & code available at https://github.com/rmovva/LLM-publication-patterns-public

Reflections from the Workshop on AI-Assisted Decision Making for Conservation

Authors: Lily Xu, Esther Rolf, Sara Beery, Joseph R. Bennett, Tanya Berger-Wolf, Tanya Birch, Elizabeth Bondi-Kelly, Justin Brashares, Melissa Chapman, Anthony Corso, Andrew Davies, Nikhil Garg, Angela Gaylard, Robert Heilmayr, Hannah Kerner, Konstantin Klemmer, Vipin Kumar, Lester Mackey, Claire Monteleoni, Paul Moorcroft, Jonathan Palmer, Andrew Perrault, David Thau, Milind Tambe

Abstract: In this white paper, we synthesize key points made during presentations and discussions from the AI-Assisted Decision Making for Conservation workshop, hosted by the Center for Research on Computation and Society at Harvard University on October 20-21, 2022. We identify key open research questions in resource allocation, planning, and interventions for biodiversity conservation, highlighting conse… ▽ More In this white paper, we synthesize key points made during presentations and discussions from the AI-Assisted Decision Making for Conservation workshop, hosted by the Center for Research on Computation and Society at Harvard University on October 20-21, 2022. We identify key open research questions in resource allocation, planning, and interventions for biodiversity conservation, highlighting conservation challenges that not only require AI solutions, but also require novel methodological advances. In addition to providing a summary of the workshop talks and discussions, we hope this document serves as a call-to-action to orient the expansion of algorithmic decision-making approaches to prioritize real-world conservation challenges, through collaborative efforts of ecologists, conservation decision-makers, and AI researchers. △ Less

Submitted 17 July, 2023; originally announced July 2023.

Comments: Co-authored by participants from the October 2022 workshop: https://crcs.seas.harvard.edu/conservation-workshop

Choosing the Right Weights: Balancing Value, Strategy, and Noise in Recommender Systems

Authors: Smitha Milli, Emma Pierson, Nikhil Garg

Abstract: Many recommender systems are based on optimizing a linear weighting of different user behaviors, such as clicks, likes, shares, etc. Though the choice of weights can have a significant impact, there is little formal study or guidance on how to choose them. We analyze the optimal choice of weights from the perspectives of both users and content producers who strategically respond to the weights. We… ▽ More Many recommender systems are based on optimizing a linear weighting of different user behaviors, such as clicks, likes, shares, etc. Though the choice of weights can have a significant impact, there is little formal study or guidance on how to choose them. We analyze the optimal choice of weights from the perspectives of both users and content producers who strategically respond to the weights. We consider three aspects of user behavior: value-faithfulness (how well a behavior indicates whether the user values the content), strategy-robustness (how hard it is for producers to manipulate the behavior), and noisiness (how much estimation error there is in predicting the behavior). Our theoretical results show that for users, upweighting more value-faithful and less noisy behaviors leads to higher utility, while for producers, upweighting more value-faithful and strategy-robust behaviors leads to higher welfare (and the impact of noise is non-monotonic). Finally, we discuss how our results can help system designers select weights in practice. △ Less

Submitted 27 May, 2023; originally announced May 2023.

Coarse race data conceals disparities in clinical risk score performance

Authors: Rajiv Movva, Divya Shanmugam, Kaihua Hou, Priya Pathak, John Guttag, Nikhil Garg, Emma Pierson

Abstract: Healthcare data in the United States often records only a patient's coarse race group: for example, both Indian and Chinese patients are typically coded as "Asian." It is unknown, however, whether this coarse coding conceals meaningful disparities in the performance of clinical risk scores across granular race groups. Here we show that it does. Using data from 418K emergency department visits, we… ▽ More Healthcare data in the United States often records only a patient's coarse race group: for example, both Indian and Chinese patients are typically coded as "Asian." It is unknown, however, whether this coarse coding conceals meaningful disparities in the performance of clinical risk scores across granular race groups. Here we show that it does. Using data from 418K emergency department visits, we assess clinical risk score performance disparities across 26 granular groups for three outcomes, five risk scores, and four performance metrics. Across outcomes and metrics, we show that the risk scores exhibit significant granular performance disparities within coarse race groups. In fact, variation in performance within coarse groups often *exceeds* the variation between coarse groups. We explore why these disparities arise, finding that outcome rates, feature distributions, and the relationships between features and outcomes all vary significantly across granular groups. Our results suggest that healthcare providers, hospital systems, and machine learning researchers should strive to collect, release, and use granular race data in place of coarse race data, and that existing analyses may significantly underestimate racial disparities in performance. △ Less

Submitted 24 August, 2023; v1 submitted 18 April, 2023; originally announced April 2023.

Comments: Published at MLHC 2023. v2 includes minor changes from the camera-ready, such as a link to code. Code is available at https://github.com/rmovva/granular-race-disparities_MLHC23

ACM Class: J.3; K.4.2

Supply-Side Equilibria in Recommender Systems

Authors: Meena Jagadeesan, Nikhil Garg, Jacob Steinhardt

Abstract: Algorithmic recommender systems such as Spotify and Netflix affect not only consumer behavior but also producer incentives. Producers seek to create content that will be shown by the recommendation algorithm, which can impact both the diversity and quality of their content. In this work, we investigate the resulting supply-side equilibria in personalized content recommender systems. We model users… ▽ More Algorithmic recommender systems such as Spotify and Netflix affect not only consumer behavior but also producer incentives. Producers seek to create content that will be shown by the recommendation algorithm, which can impact both the diversity and quality of their content. In this work, we investigate the resulting supply-side equilibria in personalized content recommender systems. We model users and content as $D$-dimensional vectors, the recommendation algorithm as showing each user the content with highest dot product, and producers as maximizing the number of users who are recommended their content minus the cost of production. Two key features of our model are that the producer decision space is multi-dimensional and the user base is heterogeneous, which contrasts with classical low-dimensional models. Multi-dimensionality and heterogeneity create the potential for specialization, where different producers create different types of content at equilibrium. Using a duality argument, we derive necessary and sufficient conditions for whether specialization occurs: these conditions depend on the extent to which users are heterogeneous and to which producers can perform well on all dimensions at once without incurring a high cost. Then, we characterize the distribution of content at equilibrium in concrete settings with two populations of users. Lastly, we show that specialization can enable producers to achieve positive profit at equilibrium, which means that specialization can reduce the competitiveness of the marketplace. At a conceptual level, our analysis of supply-side competition takes a step towards elucidating how personalized recommendations shape the marketplace of digital goods, and towards understanding what new phenomena arise in multi-dimensional competitive settings. △ Less

Submitted 11 December, 2023; v1 submitted 27 June, 2022; originally announced June 2022.

Comments: Appeared at NeurIPS 2023; this is the full version

Trucks Don't Mean Trump: Diagnosing Human Error in Image Analysis

Authors: J. D. Zamfirescu-Pereira, Jerry Chen, Emily Wen, Allison Koenecke, Nikhil Garg, Emma Pierson

Abstract: Algorithms provide powerful tools for detecting and dissecting human bias and error. Here, we develop machine learning methods to to analyze how humans err in a particular high-stakes task: image interpretation. We leverage a unique dataset of 16,135,392 human predictions of whether a neighborhood voted for Donald Trump or Joe Biden in the 2020 US election, based on a Google Street View image. We… ▽ More Algorithms provide powerful tools for detecting and dissecting human bias and error. Here, we develop machine learning methods to to analyze how humans err in a particular high-stakes task: image interpretation. We leverage a unique dataset of 16,135,392 human predictions of whether a neighborhood voted for Donald Trump or Joe Biden in the 2020 US election, based on a Google Street View image. We show that by training a machine learning estimator of the Bayes optimal decision for each image, we can provide an actionable decomposition of human error into bias, variance, and noise terms, and further identify specific features (like pickup trucks) which lead humans astray. Our methods can be applied to ensure that human-in-the-loop decision-making is accurate and fair and are also applicable to black-box algorithmic systems. △ Less

Submitted 15 May, 2022; originally announced May 2022.

Comments: To be published in FAccT 2022

Quantifying Spatial Under-reporting Disparities in Resident Crowdsourcing

Authors: Zhi Liu, Uma Bhandaram, Nikhil Garg

Abstract: Modern city governance relies heavily on crowdsourcing to identify problems such as downed trees and power lines. A major concern is that residents do not report problems at the same rates, with heterogeneous reporting delays directly translating to downstream disparities in how quickly incidents can be addressed. Here we develop a method to identify reporting delays without using external ground-… ▽ More Modern city governance relies heavily on crowdsourcing to identify problems such as downed trees and power lines. A major concern is that residents do not report problems at the same rates, with heterogeneous reporting delays directly translating to downstream disparities in how quickly incidents can be addressed. Here we develop a method to identify reporting delays without using external ground-truth data. Our insight is that the rates at which duplicate reports are made about the same incident can be leveraged to disambiguate whether an incident has occurred by investigating its reporting rate once it has occurred. We apply our method to over 100,000 resident reports made in New York City and to over 900,000 reports made in Chicago, finding that there are substantial spatial and socioeconomic disparities in how quickly incidents are reported. We further validate our methods using external data and demonstrate how estimating reporting delays leads to practical insights and interventions for a more equitable, efficient government service. △ Less

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

Accelerated Design and Deployment of Low-Carbon Concrete for Data Centers

Authors: Xiou Ge, Richard T. Goodwin, Haizi Yu, Pablo Romero, Omar Abdelrahman, Amruta Sudhalkar, Julius Kusuma, Ryan Cialdella, Nishant Garg, Lav R. Varshney

Abstract: Concrete is the most widely used engineered material in the world with more than 10 billion tons produced annually. Unfortunately, with that scale comes a significant burden in terms of energy, water, and release of greenhouse gases and other pollutants; indeed 8% of worldwide carbon emissions are attributed to the production of cement, a key ingredient in concrete. As such, there is interest in c… ▽ More Concrete is the most widely used engineered material in the world with more than 10 billion tons produced annually. Unfortunately, with that scale comes a significant burden in terms of energy, water, and release of greenhouse gases and other pollutants; indeed 8% of worldwide carbon emissions are attributed to the production of cement, a key ingredient in concrete. As such, there is interest in creating concrete formulas that minimize this environmental burden, while satisfying engineering performance requirements including compressive strength. Specifically for computing, concrete is a major ingredient in the construction of data centers. In this work, we use conditional variational autoencoders (CVAEs), a type of semi-supervised generative artificial intelligence (AI) model, to discover concrete formulas with desired properties. Our model is trained just using a small open dataset from the UCI Machine Learning Repository joined with environmental impact data from standard lifecycle analysis. Computational predictions demonstrate CVAEs can design concrete formulas with much lower carbon requirements than existing formulations while meeting design requirements. Next we report laboratory-based compressive strength experiments for five AI-generated formulations, which demonstrate that the formulations exceed design requirements. The resulting formulations were then used by Ozinga Ready Mix -- a concrete supplier -- to generate field-ready concrete formulations, based on local conditions and their expertise in concrete design. Finally, we report on how these formulations were used in the construction of buildings and structures in a Meta data center in DeKalb, IL, USA. Results from field experiments as part of this real-world deployment corroborate the efficacy of AI-generated low-carbon concrete mixes. △ Less

Submitted 11 April, 2022; originally announced April 2022.

Comments: 18 pages. arXiv admin note: text overlap with arXiv:1905.08222

Voltage-Dependent Synaptic Plasticity (VDSP): Unsupervised probabilistic Hebbian plasticity rule based on neurons membrane potential

Authors: Nikhil Garg, Ismael Balafrej, Terrence C. Stewart, Jean Michel Portal, Marc Bocquet, Damien Querlioz, Dominique Drouin, Jean Rouat, Yann Beilliard, Fabien Alibart

Abstract: This study proposes voltage-dependent-synaptic plasticity (VDSP), a novel brain-inspired unsupervised local learning rule for the online implementation of Hebb's plasticity mechanism on neuromorphic hardware. The proposed VDSP learning rule updates the synaptic conductance on the spike of the postsynaptic neuron only, which reduces by a factor of two the number of updates with respect to standard… ▽ More This study proposes voltage-dependent-synaptic plasticity (VDSP), a novel brain-inspired unsupervised local learning rule for the online implementation of Hebb's plasticity mechanism on neuromorphic hardware. The proposed VDSP learning rule updates the synaptic conductance on the spike of the postsynaptic neuron only, which reduces by a factor of two the number of updates with respect to standard spike-timing-dependent plasticity (STDP). This update is dependent on the membrane potential of the presynaptic neuron, which is readily available as part of neuron implementation and hence does not require additional memory for storage. Moreover, the update is also regularized on synaptic weight and prevents explosion or vanishing of weights on repeated stimulation. Rigorous mathematical analysis is performed to draw an equivalence between VDSP and STDP. To validate the system-level performance of VDSP, we train a single-layer spiking neural network (SNN) for the recognition of handwritten digits. We report 85.01 $ \pm $ 0.76% (Mean $ \pm $ S.D.) accuracy for a network of 100 output neurons on the MNIST dataset. The performance improves when scaling the network size (89.93 $ \pm $ 0.41% for 400 output neurons, 90.56 $ \pm $ 0.27 for 500 neurons), which validates the applicability of the proposed learning rule for spatial pattern recognition tasks. Future work will consider more complicated tasks. Interestingly, the learning rule better adapts than STDP to the frequency of input signal and does not require hand-tuning of hyperparameters △ Less

Submitted 22 October, 2022; v1 submitted 21 March, 2022; originally announced March 2022.

Comments: Front. Neurosci., 21 October 2022 Sec. Neuromorphic Engineering

Journal ref: Front. Neurosci. 16:983950 (2022)

Fair ranking: a critical review, challenges, and future directions

Authors: Gourab K Patro, Lorenzo Porcaro, Laura Mitchell, Qiuyue Zhang, Meike Zehlike, Nikhil Garg

Abstract: Ranking, recommendation, and retrieval systems are widely used in online platforms and other societal systems, including e-commerce, media-streaming, admissions, gig platforms, and hiring. In the recent past, a large "fair ranking" research literature has been developed around making these systems fair to the individuals, providers, or content that are being ranked. Most of this literature defines… ▽ More Ranking, recommendation, and retrieval systems are widely used in online platforms and other societal systems, including e-commerce, media-streaming, admissions, gig platforms, and hiring. In the recent past, a large "fair ranking" research literature has been developed around making these systems fair to the individuals, providers, or content that are being ranked. Most of this literature defines fairness for a single instance of retrieval, or as a simple additive notion for multiple instances of retrievals over time. This work provides a critical overview of this literature, detailing the often context-specific concerns that such an approach misses: the gap between high ranking placements and true provider utility, spillovers and compounding effects over time, induced strategic incentives, and the effect of statistical uncertainty. We then provide a path forward for a more holistic and impact-oriented fair ranking research agenda, including methodological lessons from other fields and the role of the broader stakeholder community in overcoming data bottlenecks and designing effective regulatory environments. △ Less

Submitted 29 January, 2022; originally announced January 2022.

Alzheimers Dementia Detection using Acoustic & Linguistic features and Pre-Trained BERT

Authors: Akshay Valsaraj, Ithihas Madala, Nikhil Garg, Veeky Baths

Abstract: Alzheimers disease is a fatal progressive brain disorder that worsens with time. It is high time we have inexpensive and quick clinical diagnostic techniques for early detection and care. In previous studies, various Machine Learning techniques and Pre-trained Deep Learning models have been used in conjunction with the extraction of various acoustic and linguistic features. Our study focuses on th… ▽ More Alzheimers disease is a fatal progressive brain disorder that worsens with time. It is high time we have inexpensive and quick clinical diagnostic techniques for early detection and care. In previous studies, various Machine Learning techniques and Pre-trained Deep Learning models have been used in conjunction with the extraction of various acoustic and linguistic features. Our study focuses on three models for the classification task in the ADReSS (The Alzheimers Dementia Recognition through Spontaneous Speech) 2021 Challenge. We use the well-balanced dataset provided by the ADReSS Challenge for training and validating our models. Model 1 uses various acoustic features from the eGeMAPs feature-set, Model 2 uses various linguistic features that we generated from auto-generated transcripts and Model 3 uses the auto-generated transcripts directly to extract features using a Pre-trained BERT and TF-IDF. These models are described in detail in the models section. △ Less

Submitted 24 September, 2021; v1 submitted 22 September, 2021; originally announced September 2021.

Strategic Ranking

Authors: Lydia T. Liu, Nikhil Garg, Christian Borgs

Abstract: Strategic classification studies the design of a classifier robust to the manipulation of input by strategic individuals. However, the existing literature does not consider the effect of competition among individuals as induced by the algorithm design. Motivated by constrained allocation settings such as college admissions, we introduce strategic ranking, in which the (designed) individual reward… ▽ More Strategic classification studies the design of a classifier robust to the manipulation of input by strategic individuals. However, the existing literature does not consider the effect of competition among individuals as induced by the algorithm design. Motivated by constrained allocation settings such as college admissions, we introduce strategic ranking, in which the (designed) individual reward depends on an applicant's post-effort rank in a measurement of interest. Our results illustrate how competition among applicants affects the resulting equilibria and model insights. We analyze how various ranking reward designs, belonging to a family of step functions, trade off applicant, school, and societal utility, as well as how ranking design counters inequities arising from disparate access to resources. In particular, we find that randomization in the reward design can mitigate two measures of disparate impact, welfare gap and access. △ Less

Submitted 21 February, 2022; v1 submitted 16 September, 2021; originally announced September 2021.

Comments: 30 pages. To appear in the conference proceedings of AISTATS 2022

Test-optional Policies: Overcoming Strategic Behavior and Informational Gaps

Authors: Zhi Liu, Nikhil Garg

Abstract: Due to the Covid-19 pandemic, more than 500 US-based colleges and universities went "test-optional" for admissions and promised that they would not penalize applicants for not submitting test scores, part of a longer trend to rethink the role of testing in college admissions. However, it remains unclear how (and whether) a college can simultaneously use test scores for those who submit them, while… ▽ More Due to the Covid-19 pandemic, more than 500 US-based colleges and universities went "test-optional" for admissions and promised that they would not penalize applicants for not submitting test scores, part of a longer trend to rethink the role of testing in college admissions. However, it remains unclear how (and whether) a college can simultaneously use test scores for those who submit them, while not penalizing those who do not--and what that promise even means. We formalize these questions, and study how a college can overcome two challenges with optional testing: $\textit{strategic applicants}$ (when those with low test scores can pretend to not have taken the test), and $\textit{informational gaps}$ (it has more information on those who submit a test score than those who do not). We find that colleges can indeed do so, if and only if they are able to use information on who has test access and are willing to randomize admissions. △ Less

Submitted 19 July, 2021; originally announced July 2021.

Combatting Gerrymandering with Social Choice: the Design of Multi-member Districts

Authors: Nikhil Garg, Wes Gurnee, David Rothschild, David Shmoys

Abstract: Every representative democracy must specify a mechanism under which voters choose their representatives. The most common mechanism in the United States -- Winner takes all single-member districts -- both enables substantial partisan gerrymandering and constrains `fair' redistricting, preventing proportional representation in legislatures. We study the design of multi-member districts (MMDs), in wh… ▽ More Every representative democracy must specify a mechanism under which voters choose their representatives. The most common mechanism in the United States -- Winner takes all single-member districts -- both enables substantial partisan gerrymandering and constrains `fair' redistricting, preventing proportional representation in legislatures. We study the design of multi-member districts (MMDs), in which each district elects multiple representatives, potentially through a non-Winner takes all voting rule. We carry out large-scale empirical analyses for the U.S. House of Representatives under MMDs with different social choice functions, under algorithmically generated maps optimized for either partisan benefit or proportionality. Doing so requires efficiently incorporating predicted partisan outcomes -- under various multi-winner social choice functions -- into an algorithm that optimizes over an ensemble of maps. We find that with three-member districts using Single Transferable Vote, fairness-minded independent commissions would be able to achieve proportional outcomes in every state up to rounding, and advantage-seeking partisans would have their power to gerrymander significantly curtailed. Simultaneously, such districts would preserve geographic cohesion, an arguably important aspect of representative democracies. In the process, we advance a rich research agenda at the intersection of social choice and computational gerrymandering. △ Less

Submitted 9 August, 2022; v1 submitted 14 July, 2021; originally announced July 2021.

Comments: 34 pages

The Stereotyping Problem in Collaboratively Filtered Recommender Systems

Authors: Wenshuo Guo, Karl Krauth, Michael I. Jordan, Nikhil Garg

Abstract: Recommender systems play a crucial role in mediating our access to online information. We show that such algorithms induce a particular kind of stereotyping: if preferences for a set of items are anti-correlated in the general user population, then those items may not be recommended together to a user, regardless of that user's preferences and rating history. First, we introduce a notion of joint… ▽ More Recommender systems play a crucial role in mediating our access to online information. We show that such algorithms induce a particular kind of stereotyping: if preferences for a set of items are anti-correlated in the general user population, then those items may not be recommended together to a user, regardless of that user's preferences and rating history. First, we introduce a notion of joint accessibility, which measures the extent to which a set of items can jointly be accessed by users. We then study joint accessibility under the standard factorization-based collaborative filtering framework, and provide theoretical necessary and sufficient conditions when joint accessibility is violated. Moreover, we show that these conditions can easily be violated when the users are represented by a single feature vector. To improve joint accessibility, we further propose an alternative modelling fix, which is designed to capture the diverse multiple interests of each user using a multi-vector representation. We conduct extensive experiments on real and simulated datasets, demonstrating the stereotyping problem with standard single-vector matrix factorization models. △ Less

Submitted 4 October, 2021; v1 submitted 23 June, 2021; originally announced June 2021.

Signals to Spikes for Neuromorphic Regulated Reservoir Computing and EMG Hand Gesture Recognition

Authors: Nikhil Garg, Ismael Balafrej, Yann Beilliard, Dominique Drouin, Fabien Alibart, Jean Rouat

Abstract: Surface electromyogram (sEMG) signals result from muscle movement and hence they are an ideal candidate for benchmarking event-driven sensing and computing. We propose a simple yet novel approach for optimizing the spike encoding algorithm's hyper-parameters inspired by the readout layer concept in reservoir computing. Using a simple machine learning algorithm after spike encoding, we report perfo… ▽ More Surface electromyogram (sEMG) signals result from muscle movement and hence they are an ideal candidate for benchmarking event-driven sensing and computing. We propose a simple yet novel approach for optimizing the spike encoding algorithm's hyper-parameters inspired by the readout layer concept in reservoir computing. Using a simple machine learning algorithm after spike encoding, we report performance higher than the state-of-the-art spiking neural networks on two open-source datasets for hand gesture recognition. The spike encoded data is processed through a spiking reservoir with a biologically inspired topology and neuron model. When trained with the unsupervised activity regulation CRITICAL algorithm to operate at the edge of chaos, the reservoir yields better performance than state-of-the-art convolutional neural networks. The reservoir performance with regulated activity was found to be 89.72% for the Roshambo EMG dataset and 70.6% for the EMG subset of sensor fusion dataset. Therefore, the biologically-inspired computing paradigm, which is known for being power efficient, also proves to have a great potential when compared with conventional AI algorithms. △ Less

Submitted 3 August, 2021; v1 submitted 9 June, 2021; originally announced June 2021.

Comments: Accepted to International Conference on Neuromorphic Systems (ICONS 2021)

Wheelchair automation by a hybrid BCI system using SSVEP and eye blinks

Authors: Lizy Kanungo, Nikhil Garg, Anish Bhobe, Smit Rajguru, Veeky Baths

Abstract: This work proposes a hybrid Brain Computer Interface system for the automation of a wheelchair for the disabled. Herein a working prototype of a BCI-based wheelchair is detailed that can navigate inside a typical home environment with minimum structural modification and without any visual obstruction and discomfort to the user. The prototype is based on a combined mechanism of steady-state visuall… ▽ More This work proposes a hybrid Brain Computer Interface system for the automation of a wheelchair for the disabled. Herein a working prototype of a BCI-based wheelchair is detailed that can navigate inside a typical home environment with minimum structural modification and without any visual obstruction and discomfort to the user. The prototype is based on a combined mechanism of steady-state visually evoked potential and eye blinks. To elicit SSVEP, LEDs flickering at 13Hz and 15Hz were used to select the left and right direction, respectively, and EEG data was recorded. In addition, the occurrence of three continuous blinks was used as an indicator for stopping an ongoing action. The wavelet packet denoising method was applied, followed by feature extraction methods such as Wavelet Packet Decomposition and Canonical Correlation Analysis over narrowband reconstructed EEG signals. Bayesian optimization was used to obtain 5 fold cross-validations to optimize the hyperparameters of the Support Vector Machine. The resulting new model was tested and the average cross-validation accuracy 89.65% + 6.6% (SD) and testing accuracy 83.53% + 8.59% (SD) were obtained. The wheelchair was controlled by RaspberryPi through WiFi. The developed prototype demonstrated an average of 86.97% success rate for all trials with 4.015s for each command execution. The prototype can be used efficiently in a home environment without causing any discomfort to the user. △ Less

Submitted 10 August, 2021; v1 submitted 10 June, 2021; originally announced June 2021.

Comments: Accepted to 2021 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN, AND CYBERNETICS (SMC)

Rate-Energy Balanced Precoding Design for SWIPT based Two-Way Relay Systems

Authors: Navneet Garg, Junkai Zhang, Tharmalingam Ratnarajah

Abstract: Simultaneous wireless information and power transfer (SWIPT) technique is a popular strategy to convey both information and RF energy for harvesting at receivers. In this regard, we consider a two-way relay system with multiple users and a multi-antenna relay employing SWIPT strategy, where splitting the received signal leads to a rate-energy trade-off. In literature, the works on transceiver desi… ▽ More Simultaneous wireless information and power transfer (SWIPT) technique is a popular strategy to convey both information and RF energy for harvesting at receivers. In this regard, we consider a two-way relay system with multiple users and a multi-antenna relay employing SWIPT strategy, where splitting the received signal leads to a rate-energy trade-off. In literature, the works on transceiver design have been studied using computationally intensive and suboptimal convex relaxation based schemes. In this paper, we study the balanced precoder design using chordal distance (CD) decomposition, which incurs much lower complexity, and is flexible to dynamic energy requirements. It is analyzed that given a non-negative value of CD, the achieved harvested energy for the proposed balanced precoder is higher than that for the perfect interference alignment (IA) precoder. The corresponding loss in sum rates is also analyzed via an upper bound. Simulation results add that the IA schemes based on mean-squared error are better suited for the SWIPT maximization than the subspace alignment-based methods. △ Less

Submitted 5 June, 2021; v1 submitted 28 January, 2021; originally announced January 2021.

Comments: arXiv admin note: text overlap with arXiv:2101.12161

Improved Rate-Energy Trade-off For SWIPT Using Chordal Distance Decomposition In Interference Alignment Networks

Authors: Navneet Garg, Avinash Rudraksh, Govind Sharma, Tharmalingam Ratnarajah

Abstract: This paper investigates the simultaneous wireless information and power transfer (SWIPT) precoding scheme for K-user multiple-input-multiple-output (MIMO) interference channels (IC), for which interference alignment (IA) schemes provide optimal precoders to achieve full degrees-of-freedom (DoF) gain. However, harvesting RF energy simultaneously reduces the achievable DoFs. To study a trade-off bet… ▽ More This paper investigates the simultaneous wireless information and power transfer (SWIPT) precoding scheme for K-user multiple-input-multiple-output (MIMO) interference channels (IC), for which interference alignment (IA) schemes provide optimal precoders to achieve full degrees-of-freedom (DoF) gain. However, harvesting RF energy simultaneously reduces the achievable DoFs. To study a trade-off between harvested energy and sum rate, the transceiver design problem is suboptimally formulated in literature via convex relaxations, which is still computationally intensive, especially for battery limited nodes running on harvested energy. In this paper, we propose a systematic method using chordal distance (CD) decomposition to obtain the balanced precoding, which improves the trade-off. Analysis shows that given the nonnegative value of CD, the achieved harvested energy for the proposed precoder is higher than that for perfect IA precoder. Moreover, energy constraints can be achieved, while maintaining a constant rate loss without losing DoFs via tuning the CD value and splitting factor. Simulation results verify the analysis and add that the IA schemes based on max-SINR or mean-squared error are better suited for SWIPT maximization than subspace or leakage minimization methods. △ Less

Submitted 18 October, 2021; v1 submitted 28 January, 2021; originally announced January 2021.

Reinforcement Learning based Per-antenna Discrete Power Control for Massive MIMO Systems

Authors: Navneet Garg, Mathini Sellathurai, Tharmalingam Ratnarajah

Abstract: Power consumption is one of the major issues in massive MIMO (multiple input multiple output) systems, causing increased long-term operational cost and overheating issues. In this paper, we consider per-antenna power allocation with a given finite set of power levels towards maximizing the long-term energy efficiency of the multi-user systems, while satisfying the QoS (quality of service) constrai… ▽ More Power consumption is one of the major issues in massive MIMO (multiple input multiple output) systems, causing increased long-term operational cost and overheating issues. In this paper, we consider per-antenna power allocation with a given finite set of power levels towards maximizing the long-term energy efficiency of the multi-user systems, while satisfying the QoS (quality of service) constraints at the end users in terms of required SINRs (signal-to-interference-plus-noise ratio), which depends on channel information. Assuming channel states to vary as a Markov process, the constraint problem is modeled as an unconstraint problem, followed by the power allocation based on Q-learning algorithm. Simulation results are presented to demonstrate the successful minimization of power consumption while achieving the SINR threshold at users. △ Less

Submitted 28 January, 2021; originally announced January 2021.

Low-complexity Rank-Efficient Tensor Completion For Prediction And Online Wireless Edge Caching

Authors: Navneet Garg, Tharmalingam Ratnarajah

Abstract: Wireless edge caching is a popular strategy to avoid backhaul congestion in the next generation networks, where the content is cached in advance at base stations to serve redundant requests during peak congestion periods. In the edge caching data, the missing observations are inevitable due to dynamic selective popularity. Among the completion methods, the tensor-based models have been shown to be… ▽ More Wireless edge caching is a popular strategy to avoid backhaul congestion in the next generation networks, where the content is cached in advance at base stations to serve redundant requests during peak congestion periods. In the edge caching data, the missing observations are inevitable due to dynamic selective popularity. Among the completion methods, the tensor-based models have been shown to be the most advantageous for missing data imputation. Also, since the observations are correlated across time, files, and base stations, in this paper, we formulate the cooperative caching with recommendations as a fourth-order tensor completion and prediction problem. Since the content library can be large leading to a large dimension tensor, we modify the latent norm-based Frank-Wolfe (FW) algorithm with towards a much lower time complexity using multi-rank updates, rather than rank-1 updates in literature. This significantly lower time computational overhead leads in developing an online caching algorithm. With MovieLens dataset, simulations show lower reconstruction errors for the proposed algorithm as compared to that of the recent FW algorithm, albeit with lower computation overhead. It is also demonstrated that the completed tensor improves normalized cache hit rates for linear prediction schemes. △ Less

Submitted 26 February, 2022; v1 submitted 28 January, 2021; originally announced January 2021.

Design and Analysis of Wideband In-Band-Full-Duplex FR2-IAB Networks

Authors: Junkai Zhang, Haifeng Luo, Navneet Garg, Abhijeet Bishnu, Mark Holm, Tharmalingam Ratnarajah

Abstract: This paper develops a 3GPP-inspired design for the in-band-full-duplex (IBFD) integrated access and backhaul (IAB) networks in the frequency range 2 (FR2) band, which can enhance the spectral efficiency (SE) and coverage while reducing the latency. However, the self-interference (SI), which is usually more than 100 dB higher than the signal-of-interest, becomes the major bottleneck in developing t… ▽ More This paper develops a 3GPP-inspired design for the in-band-full-duplex (IBFD) integrated access and backhaul (IAB) networks in the frequency range 2 (FR2) band, which can enhance the spectral efficiency (SE) and coverage while reducing the latency. However, the self-interference (SI), which is usually more than 100 dB higher than the signal-of-interest, becomes the major bottleneck in developing these IBFD networks. We design and analyze a subarray-based hybrid beamforming IBFD-IAB system with the RF beamformers obtained via RF codebooks given by a modified Linde-Buzo-Gray (LBG) algorithm. The SI is canceled in three stages, where the first stage of antenna isolation is assumed to be successfully deployed. The second stage consists of the optical domain (OD)-based RF cancellation, where cancelers are connected with the RF chain pairs. The third stage is comprised of the digital cancellation via successive interference cancellation followed by minimum mean-squared error baseband receiver. Multiuser interference in the access link is canceled by zero-forcing at the IAB-node transmitter. Simulations show that under 400 MHz bandwidth, our proposed OD-based RF cancellation can achieve around 25 dB of cancellation with 100 taps. Moreover, the higher the hardware impairment and channel estimation error, the worse digital cancellation ability we can obtain. △ Less

Submitted 17 November, 2021; v1 submitted 24 January, 2021; originally announced January 2021.

Journal ref: in IEEE Transactions on Wireless Communications, vol. 21, no. 6, pp. 4183-4196, June 2022

Design of Full-Duplex Millimeter-Wave Integrated Access and Backhaul Networks

Authors: Junkai Zhang, Navneet Garg, Mark Holm, Tharmalingam Ratnarajah

Abstract: One of the key technologies for the future cellular networks is full duplex (FD)-enabled integrated access and backhaul (IAB) networks operating in the millimeter-wave (mmWave) frequencies. The main challenge in realizing FD-IAB networks is mitigating the impact of self-interference (SI) in the wideband mmWave frequencies. In this article, we first introduce the 3GPP IAB network architectures and… ▽ More One of the key technologies for the future cellular networks is full duplex (FD)-enabled integrated access and backhaul (IAB) networks operating in the millimeter-wave (mmWave) frequencies. The main challenge in realizing FD-IAB networks is mitigating the impact of self-interference (SI) in the wideband mmWave frequencies. In this article, we first introduce the 3GPP IAB network architectures and wideband mmWave channel models. By utilizing the subarray-based hybrid precoding scheme at the FD-IAB node, multiuser interference is mitigated using zero-forcing at the transmitter, whereas the residual SI after successfully deploying antenna and analog cancellation is canceled by a minimum mean square error baseband combiner at the receiver. The spectral efficiency (SE) is evaluated for the RF insertion loss (RFIL) with different kinds of phase shifters and channel uncertainty. Simulation results show that, in the presence of the RFIL, the almost double SE, which is close to that obtained from fully connected hybrid precoding, can be achieved as compared to half duplex systems when the uncertainties are of low strength. △ Less

Submitted 1 April, 2021; v1 submitted 7 January, 2021; originally announced January 2021.

Journal ref: in IEEE Wireless Communications, vol. 28, no. 1, pp. 60-67, February 2021

Learning to Cache: Distributed Coded Caching in a Cellular Network With Correlated Demands

Authors: S. Krishnendu, B. N. Bharath, Navneet Garg, Vimal Bhatia, Tharmalingam Ratnarajah

Abstract: Design of distributed caching mechanisms is considered as an active area of research due to its promising solution in reducing data load in the backhaul link of a cellular network. In this paper, the problem of distributed content caching in a small-cell Base Stations (sBSs) wireless network that maximizes the cache hit performance is considered. Most of the existing works focus on static demands,… ▽ More Design of distributed caching mechanisms is considered as an active area of research due to its promising solution in reducing data load in the backhaul link of a cellular network. In this paper, the problem of distributed content caching in a small-cell Base Stations (sBSs) wireless network that maximizes the cache hit performance is considered. Most of the existing works focus on static demands, however, here, data at each sBS is considered to be correlated across time and sBSs. The caching strategy is assumed to be a weighted combination of past caching strategies. A high probability generalization guarantees on the performance of the proposed caching strategy is derived. The theoretical guarantee provides following insights on obtaining the caching strategy: (i) run regret minimization at each sBS to obtain a sequence of caching strategies across time, and (ii) maximize an estimate of the bound to obtain a set of weights for the caching strategy which depends on the discrepancy. Also, theoretical guarantee on the performance of the LRFU caching strategy is derived. Further, federated learning based heuristic caching algorithm is also proposed. Finally, it is shown through simulations using Movie Lens dataset that the proposed algorithm significantly outperforms LRFU algorithm. △ Less

Submitted 13 October, 2020; originally announced October 2020.

Comments: 30 pages, 6 figures

Dropping Standardized Testing for Admissions Trades Off Information and Access

Authors: Nikhil Garg, Hannah Li, Faidra Monachou

Abstract: We study the role of information and access in capacity-constrained selection problems with fairness concerns. We develop a theoretical statistical discrimination framework, where each applicant has multiple features and is potentially strategic. The model formalizes the trade-off between the (potentially positive) informational role of a feature and its (negative) exclusionary nature when members… ▽ More We study the role of information and access in capacity-constrained selection problems with fairness concerns. We develop a theoretical statistical discrimination framework, where each applicant has multiple features and is potentially strategic. The model formalizes the trade-off between the (potentially positive) informational role of a feature and its (negative) exclusionary nature when members of different social groups have unequal access to this feature. Our framework finds a natural application to recent policy debates on dropping standardized testing in college admissions. Our primary takeaway is that the decision to drop a feature (such as test scores) cannot be made without the joint context of the information provided by other features and how the requirement affects the applicant pool composition. Dropping a feature may exacerbate disparities by decreasing the amount of information available for each applicant, especially those from non-traditional backgrounds. However, in the presence of access barriers to a feature, the interaction between the informational environment and the effect of access barriers on the applicant pool size becomes highly complex. In this case, we provide a threshold characterization regarding when removing a feature improves both academic merit and diversity. Finally, using calibrated simulations in both the strategic and non-strategic settings, we demonstrate the presence of practical instances where the decision to eliminate standardized testing improves or worsens all metrics. △ Less

Submitted 5 September, 2023; v1 submitted 9 October, 2020; originally announced October 2020.

Comments: An earlier version of this work appeared at ACM FAccT 2021

Dual Half-integrality for Uncrossable Cut Cover and its Application to Maximum Half-Integral Flow

Authors: Naveen Garg, Nikhil Kumar

Abstract: Given an edge weighted graph and a forest $F$, the $\textit{2-edge connectivity augmentation problem}$ is to pick a minimum weighted set of edges, $E'$, such that every connected component of $E'\cup F$ is 2-edge connected. Williamson et al. gave a 2-approximation algorithm (WGMV) for this problem using the primal-dual schema. We show that when edge weights are integral, the WGMV procedure can be… ▽ More Given an edge weighted graph and a forest $F$, the $\textit{2-edge connectivity augmentation problem}$ is to pick a minimum weighted set of edges, $E'$, such that every connected component of $E'\cup F$ is 2-edge connected. Williamson et al. gave a 2-approximation algorithm (WGMV) for this problem using the primal-dual schema. We show that when edge weights are integral, the WGMV procedure can be modified to obtain a half-integral dual. The 2-edge connectivity augmentation problem has an interesting connection to routing flow in graphs where the union of supply and demand is planar. The half-integrality of the dual leads to a tight 2-approximate max-half-integral-flow min-multicut theorem. △ Less

Submitted 28 July, 2020; originally announced July 2020.

Integer Plane Multiflow Maximisation : Flow-Cut Gap and One-Quarter-Approximation

Authors: Naveen Garg, Nikhil Kumar, András Sebő

Abstract: In this paper, we bound the integrality gap and the approximation ratio for maximum plane multiflow problems and deduce bounds on the flow-cut-gap. Planarity means here that the union of the supply and demand graph is planar. We first prove that there exists a multiflow of value at least half of the capacity of a minimum multicut. We then show how to convert any multiflow into a half-integer one o… ▽ More In this paper, we bound the integrality gap and the approximation ratio for maximum plane multiflow problems and deduce bounds on the flow-cut-gap. Planarity means here that the union of the supply and demand graph is planar. We first prove that there exists a multiflow of value at least half of the capacity of a minimum multicut. We then show how to convert any multiflow into a half-integer one of value at least half of the original multiflow. Finally, we round any half-integer multiflow into an integer multiflow, losing again at most half of the value, in polynomial time, achieving a $1/4$-approximation algorithm for maximum integer multiflows in the plane, and an integer-flow-cut gap of $8$. △ Less

Submitted 18 March, 2020; v1 submitted 25 February, 2020; originally announced February 2020.

Fair Allocation through Selective Information Acquisition

Authors: William Cai, Johann Gaebler, Nikhil Garg, Sharad Goel

Abstract: Public and private institutions must often allocate scare resources under uncertainty. Banks, for example, extend credit to loan applicants based in part on their estimated likelihood of repaying a loan. But when the quality of information differs across candidates (e.g., if some applicants lack traditional credit histories), common lending strategies can lead to disparities across groups. Here we… ▽ More Public and private institutions must often allocate scare resources under uncertainty. Banks, for example, extend credit to loan applicants based in part on their estimated likelihood of repaying a loan. But when the quality of information differs across candidates (e.g., if some applicants lack traditional credit histories), common lending strategies can lead to disparities across groups. Here we consider a setting in which decision makers -- before allocating resources -- can choose to spend some of their limited budget further screening select individuals. We present a computationally efficient algorithm for deciding whom to screen that maximizes a standard measure of social welfare. Intuitively, decision makers should screen candidates on the margin, for whom the additional information could plausibly alter the allocation. We formalize this idea by showing the problem can be reduced to solving a series of linear programs. Both on synthetic and real-world datasets, this strategy improves utility, illustrating the value of targeted information acquisition in such decisions. Further, when there is social value for distributing resources to groups for whom we have a priori poor information -- like those without credit scores -- our approach can substantially improve the allocation of limited assets. △ Less

Submitted 29 September, 2020; v1 submitted 6 November, 2019; originally announced November 2019.

Comments: To appear in Proceedings of the 2020 AAAI/ACM Conference on AI, Ethics, and Society (AIES). Update: Fully specified the definition of threshold policies

Parallel Machine Scheduling to Minimize Energy Consumption

Authors: Antonios Antoniadis, Naveen Garg, Gunjan Kumar, Nikhil Kumar

Abstract: Given n jobs with release dates, deadlines and processing times we consider the problem of scheduling them on m parallel machines so as to minimize the total energy consumed. Machines can enter a sleep state and they consume no energy in this state. Each machine requires Q units of energy to awaken from the sleep state and in its active state the machine can process jobs and consumes a unit of ene… ▽ More Given n jobs with release dates, deadlines and processing times we consider the problem of scheduling them on m parallel machines so as to minimize the total energy consumed. Machines can enter a sleep state and they consume no energy in this state. Each machine requires Q units of energy to awaken from the sleep state and in its active state the machine can process jobs and consumes a unit of energy per unit time. We allow for preemption and migration of jobs and provide the first constant approximation algorithm for this problem. △ Less

Submitted 29 September, 2019; originally announced September 2019.