Author name cluster

Anay Mehrotra

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers

2 author rows

STOC Conference 2025 Conference Paper

On the Limits of Language Generation: Trade-Offs between Hallucination and Mode-Collapse

Alkis Kalavasis
Anay Mehrotra
Grigoris Velegkas

Specifying all desirable properties of a language model is challenging, but certain requirements seem essential for any good model. Given samples drawn from an unknown language, the trained model should (1) produce valid strings that have not been seen in the training data, and (2) be expressive enough to capture the full richness of the language. Otherwise, if the language model outputs invalid strings, it "hallucinates," and if it fails to capture the full range of the language, it suffers from "mode collapse." In this paper, we ask whether it is possible for a language model to meet both of these requirements. We investigate this question within a statistical setting of language generation, building on the seminal works of Gold (Inf. Control, 1967), Angluin (STOC, 1979), and Angluin (Tech. Report, 1988). In this setting, the language model is presented with randomly sampled strings from a distribution supported on an unknown language K, which is only known to belong to a possibly infinite collection of candidate languages. The goal of the model is to generate unseen strings from this target language. We say that the language model generates from K with consistency and breadth if, as the size of the training set increases, the set of strings it can output converges to the set of all unseen strings in K. Kleinberg and Mullainathan (NeurIPS, 2024) posed an open question of whether consistency and breadth in language generation are both possible. We answer this question negatively: for a large class of language models -- including next-token-prediction-based models -- this is impossible for most collections of candidate languages. This contrasts with the recent positive result of Kleinberg and Mullainathan, which demonstrated that consistent generation, without requiring breadth, is possible for any countable collection of candidate languages. Our finding highlights that generation with breadth is fundamentally different from generation without breadth. As a byproduct of our result, we also examine how many samples are required for generation with or without breadth, establishing near-tight bounds on the "learning curves" for generation in the statistical framework of Bousquet, Hanneke, Moran, van Handel, and Yehudayoff (STOC, 2021). Finally, our results also give some hope for consistent generation with breadth: it is achievable for any countable collection of languages when negative examples -- in the form of strings outside of K -- are available in addition to strings inside of K. This suggests that feedback in post-training, which encodes negative examples, can be crucial in reducing hallucinations while also limiting mode collapse.

Details

NeurIPS Conference 2025 Conference Paper

On Union-Closedness of Language Generation

Steve Hanneke
Amin Karbasi
Anay Mehrotra
Grigoris Velegkas

We investigate language generation in the limit – a model by Kleinberg and Mullainathan and extended by Li, Raman, and Tewari. While Kleinberg and Mullainathan proved generation is possible for all countable collections, Li, Raman, and Tewari defined a hierarchy of generation notions (uniform, non-uniform, and generatable) and explored their feasibility for uncountable collections. Our first set of results resolve two open questions of Li et al. by proving finite unions of generatable or non-uniformly generatable classes need not be generatable. These follow from a stronger result: there is non-uniformly generatable class and a uniformly generatable class whose union is non-generatable. This adds to the aspects along which language generation in the limit is different from traditional tasks in statistical learning theory like classification, which are closed under finite unions. In particular, it implies that given two generators for different collections, one cannot combine them to obtain a single "more powerful" generator, prohibiting this notion of boosting. Our construction also addresses a third of Li et al. 's open questions on whether there are uncountable classes that are non-uniformly generatable and do not satisfy the eventually unbounded closure (EUC) condition introduced by Li et al. Our approach utilizes carefully constructed classes along with a novel diagonalization argument that could be of independent interest in the growing area of language generation.

PDF Details

FOCS Conference 2024 Conference Paper

Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians

Jane H. Lee
Anay Mehrotra
Manolis Zampetakis

We study the estimation of distributional parameters when samples are shown only if they fall in some unknown set. Kontonis, Tzamos, and Zampetakis (FOCS'19) gave an algorithm for finding parameters for the special case of Gaussian distributions with diagonal covariance matrix. Recently, Diakonikolas, Kane, Pittas, and Zarifis (COLT'24) showed that an exponential dependence on the inverse of the accuracy parameter is necessary even when the set belongs to some well-behaved classes. These works leave the following open problems which we address in this work: Can we estimate the parameters of any Gaussian or even extend the results beyond Gaussians? Can we design polynomial-time algorithms when for simple sets such as a halfspace? Toward the first question, we provide an estimation algorithm for any exponential family that satisfies some structural assumptions and any unknown set that is approximable by polynomials. This result has two important applications: (a)The first algorithm for estimating arbitrary Gaussian distributions (even with non-diagonal covariance matrix) from samples truncated to unknown set; and (b)The first algorithm for linear regression with unknown truncation and Gaussian features. To address the second question, we provide an algorithm with polynomial sample and time complexity that works for a set of exponential families (that contains multivariate Gaussians) when the unknown survival set is a halfspace or an axis-aligned rectangle. 1 1 A preliminary version of this paper incorrectly claimed the result for finite unions of axis-aligned rectangles. The result only holds for a single axis-aligned rectangle. This is the first fully polynomial time algorithm for estimation with an unknown truncation set. Along the way, we develop new tools that may be of independent interest, including: (c)The first polynomial time algorithm for learning halfspaces using only positive examples when the samples have an unknown Gaussian distribution; and (d)A reduction from PAC learning with positive and unlabeled samples to PAC learning with positive and negative samples that is robust to certain covariate shifts.

Details

ICML Conference 2024 Conference Paper

Fair Classification with Partial Feedback: An Exploration-Based Data Collection Approach

Vijay Keswani
Anay Mehrotra
L. Elisa Celis

In many predictive contexts (e. g. , credit lending), true outcomes are only observed for samples that were positively classified in the past. These past observations, in turn, form training datasets for classifiers that make future predictions. However, such training datasets lack information about the outcomes of samples that were (incorrectly) negatively classified in the past and can lead to erroneous classifiers. We present an approach that trains a classifier using available data and comes with a family of exploration strategies to collect outcome data about subpopulations that otherwise would have been ignored. For any exploration strategy, the approach comes with guarantees that (1) all sub-populations are explored, (2) the fraction of false positives is bounded, and (3) the trained classifier converges to a "desired" classifier. The right exploration strategy is context-dependent; it can be chosen to improve learning guarantees and encode context-specific group fairness properties. Evaluation on real-world datasets shows that this approach consistently boosts the quality of collected outcome data and improves the fraction of true positives for all groups, with only a small reduction in predictive utility.

Details

NeurIPS Conference 2024 Conference Paper

Tree of Attacks: Jailbreaking Black-Box LLMs Automatically

Anay Mehrotra
Manolis Zampetakis
Paul Kassianik
Blaine Nelson
Hyrum Anderson
Yaron Singer
Amin Karbasi

While Large Language Models (LLMs) display versatile functionality, they continue to generate harmful, biased, and toxic content, as demonstrated by the prevalence of human-designed jailbreaks. In this work, we present Tree of Attacks with Pruning (TAP), an automated method for generating jailbreaks that only requires black-box access to the target LLM. TAP utilizes an attacker LLM to iteratively refine candidate (attack) prompts until one of the refined prompts jailbreaks the target. In addition, before sending prompts to the target, TAP assesses them and prunes the ones unlikely to result in jailbreaks, reducing the number of queries sent to the target LLM. In empirical evaluations, we observe that TAP generates prompts that jailbreak state-of-the-art LLMs (including GPT4-Turbo and GPT4o) for more than 80% of the prompts. This significantly improves upon the previous state-of-the-art black-box methods for generating jailbreaks while using a smaller number of queries than them. Furthermore, TAP is also capable of jailbreaking LLMs protected by state-of-the-art guardrails, e. g. , LlamaGuard.

PDF Details DOI

NeurIPS Conference 2023 Conference Paper

Bias in Evaluation Processes: An Optimization-Based Model

L. Elisa Celis
Amit Kumar
Anay Mehrotra
Nisheeth K. Vishnoi

Biases with respect to socially-salient attributes of individuals have been well documented in evaluation processes used in settings such as admissions and hiring. We view such an evaluation process as a transformation of a distribution of the true utility of an individual for a task to an observed distribution and model it as a solution to a loss minimization problem subject to an information constraint. Our model has two parameters that have been identified as factors leading to biases: the resource-information trade-off parameter in the information constraint and the risk-averseness parameter in the loss function. We characterize the distributions that arise from our model and study the effect of the parameters on the observed distribution. The outputs of our model enrich the class of distributions that can be used to capture variation across groups in the observed evaluations. We empirically validate our model by fitting real-world datasets and use it to study the effect of interventions in a downstream selection task. These results contribute to an understanding of the emergence of bias in evaluation processes and provide tools to guide the deployment of interventions to mitigate biases.

PDF Details

ICML Conference 2023 Conference Paper

Subset Selection Based On Multiple Rankings in the Presence of Bias: Effectiveness of Fairness Constraints for Multiwinner Voting Score Functions

Niclas Boehmer
L. Elisa Celis
Lingxiao Huang
Anay Mehrotra
Nisheeth K. Vishnoi

We consider the problem of subset selection where one is given multiple rankings of items and the goal is to select the highest "quality" subset. Score functions from the multiwinner voting literature have been used to aggregate rankings into quality scores for subsets. We study this setting of subset selection problems when, in addition, rankings may contain systemic or unconscious biases toward a group of items. For a general model of input rankings and biases, we show that requiring the selected subset to satisfy group fairness constraints can improve the quality of the selection with respect to unbiased rankings. Importantly, we show that for fairness constraints to be effective, different multiwinner score functions may require a drastically different number of rankings: While for some functions, fairness constraints need an exponential number of rankings to recover a close-to-optimal solution, for others, this dependency is only polynomial. This result relies on a novel notion of "smoothness" of submodular functions in this setting that quantifies how well a function can "correctly" assess the quality of items in the presence of bias. The results in this paper can be used to guide the choice of multiwinner score functions for the subset selection setting considered here; we additionally provide a tool to empirically enable this.

Details

NeurIPS Conference 2022 Conference Paper

Fair Ranking with Noisy Protected Attributes

Anay Mehrotra
Nisheeth Vishnoi

The fair-ranking problem, which asks to rank a given set of items to maximize utility subject to group fairness constraints, has received attention in the fairness, information retrieval, and machine learning literature. Recent works, however, observe that errors in socially-salient (including protected) attributes of items can significantly undermine fairness guarantees of existing fair-ranking algorithms and raise the problem of mitigating the effect of such errors. We study the fair-ranking problem under a model where socially-salient attributes of items are randomly and independently perturbed. We present a fair-ranking framework that incorporates group fairness requirements along with probabilistic information about perturbations in socially-salient attributes. We provide provable guarantees on the fairness and utility attainable by our framework and show that it is information-theoretically impossible to significantly beat these guarantees. Our framework works for multiple non-disjoint attributes and a general class of fairness constraints that includes proportional and equal representation. Empirically, we observe that, compared to baselines, our algorithm outputs rankings with higher fairness, and has a similar or better fairness-utility trade-off compared to baselines.

PDF Details

NeurIPS Conference 2021 Conference Paper

Fair Classification with Adversarial Perturbations

L. Elisa Celis
Anay Mehrotra
Nisheeth Vishnoi

We study fair classification in the presence of an omniscient adversary that, given an $\eta$, is allowed to choose an arbitrary $\eta$-fraction of the training samples and arbitrarily perturb their protected attributes. The motivation comes from settings in which protected attributes can be incorrect due to strategic misreporting, malicious actors, or errors in imputation; and prior approaches that make stochastic or independence assumptions on errors may not satisfy their guarantees in this adversarial setting. Our main contribution is an optimization framework to learn fair classifiers in this adversarial setting that comes with provable guarantees on accuracy and fairness. Our framework works with multiple and non-binary protected attributes, is designed for the large class of linear-fractional fairness metrics, and can also handle perturbations besides protected attributes. We prove near-tightness of our framework's guarantees for natural hypothesis classes: no algorithm can have significantly better accuracy and any algorithm with better fairness must have lower accuracy. Empirically, we evaluate the classifiers produced by our framework for statistical rate on real-world and synthetic datasets for a family of adversaries.

PDF Details

ICML Conference 2019 Conference Paper

Toward Controlling Discrimination in Online Ad Auctions

L. Elisa Celis
Anay Mehrotra
Nisheeth K. Vishnoi

Online advertising platforms are thriving due to the customizable audiences they offer advertisers. However, recent studies show that advertisements can be discriminatory with respect to the gender or race of the audience that sees the ad, and may inadvertently cross ethical and/or legal boundaries. To prevent this, we propose a constrained ad auction framework that maximizes the platform’s revenue conditioned on ensuring that the audience seeing an advertiser’s ad is distributed appropriately across sensitive types such as gender or race. Building upon Myerson’s classic work, we first present an optimal auction mechanism for a large class of fairness constraints. Finding the parameters of this optimal auction, however, turns out to be a non-convex problem. We show that this non-convex problem can be reformulated as a more structured non-convex problem with no saddle points or local-maxima; this allows us to develop a gradient-descent-based algorithm to solve it. Our empirical results on the A1 Yahoo! dataset demonstrate that our algorithm can obtain uniform coverage across different user types for each advertiser at a minor loss to the revenue of the platform, and a small change to the size of the audience each advertiser reaches.

Details