-
Redesigning Service Level Agreements: Equity and Efficiency in City Government Operations
Authors:
Zhi Liu,
Nikhil Garg
Abstract:
We consider government service allocation -- how the government allocates resources (e.g., maintenance of public infrastructure) over time. It is important to make these decisions efficiently and equitably -- though these desiderata may conflict. In particular, we consider the design of Service Level Agreements (SLA) in city government operations: promises that incidents such as potholes and falle…
▽ More
We consider government service allocation -- how the government allocates resources (e.g., maintenance of public infrastructure) over time. It is important to make these decisions efficiently and equitably -- though these desiderata may conflict. In particular, we consider the design of Service Level Agreements (SLA) in city government operations: promises that incidents such as potholes and fallen trees will be responded to within a certain time. We model the problem of designing a set of SLAs as an optimization problem with equity and efficiency objectives under a queuing network framework; the city has two decision levers: how to allocate response budgets to different neighborhoods, and how to schedule responses to individual incidents. We: (1) Theoretically analyze a stylized model and find that the "price of equity" is small in realistic settings; (2) Develop a simulation-optimization framework to optimize policies in practice; (3) Apply our framework empirically using data from NYC, finding that: (a) status quo inspections are highly inefficient and inequitable compared to optimal ones, and (b) in practice, the equity-efficiency trade-off is not substantial: generally, inefficient policies are inequitable, and vice versa.
△ Less
Submitted 18 October, 2024;
originally announced October 2024.
-
Agent Q: Advanced Reasoning and Learning for Autonomous AI Agents
Authors:
Pranav Putta,
Edmund Mills,
Naman Garg,
Sumeet Motwani,
Chelsea Finn,
Divyansh Garg,
Rafael Rafailov
Abstract:
Large Language Models (LLMs) have shown remarkable capabilities in natural language tasks requiring complex reasoning, yet their application in agentic, multi-step reasoning within interactive environments remains a difficult challenge. Traditional supervised pre-training on static datasets falls short in enabling autonomous agent capabilities needed to perform complex decision-making in dynamic s…
▽ More
Large Language Models (LLMs) have shown remarkable capabilities in natural language tasks requiring complex reasoning, yet their application in agentic, multi-step reasoning within interactive environments remains a difficult challenge. Traditional supervised pre-training on static datasets falls short in enabling autonomous agent capabilities needed to perform complex decision-making in dynamic settings like web navigation. Previous attempts to bridge this ga-through supervised fine-tuning on curated expert demonstrations-often suffer from compounding errors and limited exploration data, resulting in sub-optimal policy outcomes. To overcome these challenges, we propose a framework that combines guided Monte Carlo Tree Search (MCTS) search with a self-critique mechanism and iterative fine-tuning on agent interactions using an off-policy variant of the Direct Preference Optimization (DPO) algorithm. Our method allows LLM agents to learn effectively from both successful and unsuccessful trajectories, thereby improving their generalization in complex, multi-step reasoning tasks. We validate our approach in the WebShop environment-a simulated e-commerce platform where it consistently outperforms behavior cloning and reinforced fine-tuning baseline, and beats average human performance when equipped with the capability to do online search. In real-world booking scenarios, our methodology boosts Llama-3 70B model's zero-shot performance from 18.6% to 81.7% success rate (a 340% relative increase) after a single day of data collection and further to 95.4% with online search. We believe this represents a substantial leap forward in the capabilities of autonomous agents, paving the way for more sophisticated and reliable decision-making in real-world settings.
△ Less
Submitted 13 August, 2024;
originally announced August 2024.
-
Fully Dynamic $k$-Clustering with Fast Update Time and Small Recourse
Authors:
Sayan Bhattacharya,
Martín Costa,
Naveen Garg,
Silvio Lattanzi,
Nikos Parotsidis
Abstract:
In the dynamic metric $k$-median problem, we wish to maintain a set of $k$ centers $S \subseteq V$ in an input metric space $(V, d)$ that gets updated via point insertions/deletions, so as to minimize the objective $\sum_{x \in V} \min_{y \in S} d(x, y)$. The quality of a dynamic algorithm is measured in terms of its approximation ratio, "recourse" (the number of changes in $S$ per update) and "up…
▽ More
In the dynamic metric $k$-median problem, we wish to maintain a set of $k$ centers $S \subseteq V$ in an input metric space $(V, d)$ that gets updated via point insertions/deletions, so as to minimize the objective $\sum_{x \in V} \min_{y \in S} d(x, y)$. The quality of a dynamic algorithm is measured in terms of its approximation ratio, "recourse" (the number of changes in $S$ per update) and "update time" (the time it takes to handle an update). The ultimate goal in this line of research is to obtain a dynamic $O(1)$ approximation algorithm with $\tilde{O}(1)$ recourse and $\tilde{O}(k)$ update time.
Dynamic $k$-median is a canonical example of a class of problems known as dynamic $k$-clustering, that has received significant attention in recent years. To the best of our knowledge, however, previous papers either attempt to minimize the algorithm's recourse while ignoring its update time, or minimize the algorithm's update time while ignoring its recourse. For dynamic $k$-median, we come arbitrarily close to resolving the main open question on this topic, with the following results.
(I) We develop a new framework of randomized local search that is suitable for adaptation in a dynamic setting. For every $ε> 0$, this gives us a dynamic $k$-median algorithm with $O(1/ε)$ approximation ratio, $\tilde{O}(k^ε)$ recourse and $\tilde{O}(k^{1+ε})$ update time. This framework also generalizes to dynamic $k$-clustering with $\ell^p$-norm objectives, giving similar bounds for the dynamic $k$-means and a new trade-off for dynamic $k$-center.
(II) If it suffices to maintain only an estimate of the value of the optimal $k$-median objective, then we obtain a $O(1)$ approximation algorithm with $\tilde{O}(k)$ update time. We achieve this result via adapting the Lagrangian Relaxation framework to the dynamic setting.
△ Less
Submitted 2 August, 2024;
originally announced August 2024.
-
Recursive Introspection: Teaching Language Model Agents How to Self-Improve
Authors:
Yuxiao Qu,
Tianjun Zhang,
Naman Garg,
Aviral Kumar
Abstract:
A central piece in enabling intelligent agentic behavior in foundation models is to make them capable of introspecting upon their behavior, reasoning, and correcting their mistakes as more computation or interaction is available. Even the strongest proprietary large language models (LLMs) do not quite exhibit the ability of continually improving their responses sequentially, even in scenarios wher…
▽ More
A central piece in enabling intelligent agentic behavior in foundation models is to make them capable of introspecting upon their behavior, reasoning, and correcting their mistakes as more computation or interaction is available. Even the strongest proprietary large language models (LLMs) do not quite exhibit the ability of continually improving their responses sequentially, even in scenarios where they are explicitly told that they are making a mistake. In this paper, we develop RISE: Recursive IntroSpEction, an approach for fine-tuning LLMs to introduce this capability, despite prior work hypothesizing that this capability may not be possible to attain. Our approach prescribes an iterative fine-tuning procedure, which attempts to teach the model how to alter its response after having executed previously unsuccessful attempts to solve a hard test-time problem, with optionally additional environment feedback. RISE poses fine-tuning for a single-turn prompt as solving a multi-turn Markov decision process (MDP), where the initial state is the prompt. Inspired by principles in online imitation learning and reinforcement learning, we propose strategies for multi-turn data collection and training so as to imbue an LLM with the capability to recursively detect and correct its previous mistakes in subsequent iterations. Our experiments show that RISE enables Llama2, Llama3, and Mistral models to improve themselves with more turns on math reasoning tasks, outperforming several single-turn strategies given an equal amount of inference-time computation. We also find that RISE scales well, often attaining larger benefits with more capable models. Our analysis shows that RISE makes meaningful improvements to responses to arrive at the correct solution for challenging prompts, without disrupting one-turn abilities as a result of expressing more complex distributions.
△ Less
Submitted 26 July, 2024; v1 submitted 25 July, 2024;
originally announced July 2024.
-
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; v1 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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
Leximin and Leximax Fair Core Imputations for the Max-Flow, MST, and Bipartite $b$-Matching Games
Authors:
Rohith R. Gangam,
Naveen Garg,
Parnian Shahkar,
Vijay V. Vazirani
Abstract:
The stable and fair division of profits/costs is a central concern in economics. The core, which ensures stability, has long been the gold standard for profit/cost sharing in cooperative games. Shapley and Shubik([SS71])'s classic work on the assignment game revealed that core imputations can be disproportionately favoring certain agents. Recent work ([Vaz24]) gave leximin and leximax core imputat…
▽ More
The stable and fair division of profits/costs is a central concern in economics. The core, which ensures stability, has long been the gold standard for profit/cost sharing in cooperative games. Shapley and Shubik([SS71])'s classic work on the assignment game revealed that core imputations can be disproportionately favoring certain agents. Recent work ([Vaz24]) gave leximin and leximax core imputations for this game, achieving better fairness properties. We explore these fairness notions for the cores of three cooperative games: the max-flow game, the minimum spanning tree (MST) game, and the bipartite $b$-matching game. For all three games we give examples to show that an arbitrary core imputation can be excessively unfair to certain agents.
Leximin and leximax core imputations are natural extensions of the widely used max-min and min-max fairness notions. We show that finding such imputations in the core is NP-hard for the max-flow and MST games, and likely so for $b$-matching as well. To address this, we introduce the concept of Dual-Consistent Core (DCC) imputations, which are characterized by solutions to the dual linear programs. We give polynomial time algorithms for computing leximin and leximax DCC imputations for all three games. These games have numerous applications and these imputations will provide a more fair way of distributing profit among agents for them.
△ Less
Submitted 30 September, 2024; v1 submitted 9 March, 2024;
originally announced March 2024.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.