Author name cluster

Tung Mai

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.

15 papers

2 author rows

AAMAS Conference 2026 Conference Paper

Stable Matching: Dealing with Changes in Preferences

Rohith Reddy Gangam
Tung Mai
Nitya Raju
Vijay V. Vazirani

We study stable matchings that are robust to preference changes in the two-sided stable matching setting of Gale and Shapley [18]. Giventwoinstances𝐴and𝐵 onthesamesetofagents, amatchingis saidtoberobust ifitisstableunderbothinstances. Whilepriorwork has considered the case where a single agent changes preferences between 𝐴 and 𝐵, we allow multiple agents on both sides to update their preferences and ask whether three central properties of stable matchings extend to robust stable matchings: (i) Can a robust stable matching be found in polynomial time? (ii) Does the set of robust stable matchings form a lattice? (iii) Is the fractional robust stable matching polytope integral? We show that all three properties hold when any number of agents on one side change preferences, as long as at most one agent on the other side does. For the case where two or more agents on both sides change preferences, we construct examples showing that boththelatticestructureandpolyhedralintegralityfail—identifying this setting as a sharp threshold. We also present an XP-time algorithm for the general case, which implies a polynomial-time algorithm when the number of agents with changing preferences is constant. While these results establish the tractability of these regimes, closing the complexity gap in the fully general setting remains an interesting open question.

PDF

TMLR Journal 2025 Journal Article

CodeLutra: Boosting LLM Code Generation via Preference-Guided Refinement

Leitian Tao
Xiang Chen
Tong Yu
Tung Mai
Ryan A. Rossi
Yixuan Li
Saayan Mitra

Large Language Models (LLMs) have revolutionized code generation but are require significant resources and tend to over-generalize, limiting their task-specific efficiency. Fine-tuning smaller, open-source LLMs is a cost-effective alternative, yet standard supervised approaches rely solely on correct examples, overlooking valuable insights from failures. We introduce CodeLutra, a new framework that leverages both correct and incorrect code attempts. Instead of purely instructing with correct solutions, CodeLutra uses iterative preference-based refinement, comparing successful and failed outputs to better approximate desired results. This process narrows the performance gap with state-of-the-art, larger models, without requiring massive datasets or auxiliary models. For example, on a challenging data science coding task, using only 500 samples improved Llama-3-8B’s accuracy from 28.2% to 48.6%, approaching GPT-4’s level. By capitalizing on both successes and mistakes, \textsc{CodeLutra} offers a scalable, efficient path to high-quality code generation, making smaller open-source models more competitive with leading closed-source alternatives.

PDF Details

NeurIPS Conference 2023 Conference Paper

Exact Representation of Sparse Networks with Symmetric Nonnegative Embeddings

Sudhanshu Chanpuriya
Ryan Rossi
Anup B. Rao
Tung Mai
Nedim Lipka
Zhao Song
Cameron Musco

Graph models based on factorization of the adjacency matrix often fail to capture network structures related to links between dissimilar nodes (heterophily). We introduce a novel graph factorization model that leverages two nonnegative vectors per node to interpretably account for links between both similar and dissimilar nodes. We prove that our model can exactly represent any graph with low arboricity, a property that many real-world networks satisfy; our proof also applies to related models but has much greater scope than the closest prior bound, which is based on low max degree. Our factorization also has compelling properties besides expressiveness: due to its symmetric structure and nonnegativity, fitting the model inherently finds node communities, and the model's link predictions can be interpreted in terms of these communities. In experiments on real-world networks, we demonstrate our factorization's effectiveness on a variety of tasks, including community detection and link prediction.

PDF Details

NeurIPS Conference 2023 Conference Paper

Finite Population Regression Adjustment and Non-asymptotic Guarantees for Treatment Effect Estimation

Mehrdad Ghadiri
David Arbour
Tung Mai
Cameron Musco
Anup B. Rao

The design and analysis of randomized experiments is fundamental to many areas, from the physical and social sciences to industrial settings. Regression adjustment is a popular technique to reduce the variance of estimates obtained from experiments, by utilizing information contained in auxiliary covariates. While there is a large literature within the statistics community studying various approaches to regression adjustment and their asymptotic properties, little focus has been given to approaches in the finite population setting with non-asymptotic accuracy bounds. Further, prior work typically assumes that an entire population is exposed to an experiment, whereas practitioners often seek to minimize the number of subjects exposed to an experiment, for ethical and pragmatic reasons. In this work, we study the problems of estimating the sample mean, individual treatment effects, and average treatment effect with regression adjustment. We propose approaches that use techniques from randomized numerical linear algebra to sample a subset of the population on which to perform an experiment. We give non-asymptotic accuracy bounds for our methods and demonstrate that they compare favorably with prior approaches.

PDF Details

AAAI Conference 2022 Conference Paper

Conditional Generative Model Based Predicate-Aware Query Approximation

Nikhil Sheoran
Subrata Mitra
Vibhor Porwal
Siddharth Ghetia
Jatin Varshney
Tung Mai
Anup Rao
Vikas Maddukuri

The goal of Approximate Query Processing (AQP) is to provide very fast but “accurate enough” results for costly aggregate queries thereby improving user experience in interactive exploration of large datasets. Recently proposed Machine- Learning-based AQP techniques can provide very low latency as query execution only involves model inference as compared to traditional query processing on database clusters. However, with increase in the number of filtering predicates (WHERE clauses), the approximation error significantly increases for these methods. Analysts often use queries with a large number of predicates for insights discovery. Thus, maintaining low approximation error is important to prevent analysts from drawing misleading conclusions. In this paper, we propose ELECTRA, a predicate-aware AQP system that can answer analytics-style queries with a large number of predicates with much smaller approximation errors. ELEC- TRA uses a conditional generative model that learns the conditional distribution of the data and at run-time generates a small (≈ 1000 rows) but representative sample, on which the query is executed to compute the approximate result. Our evaluations with four different baselines on three real-world datasets show that ELECTRA provides lower AQP error for large number of predicates compared to baselines.

PDF Details

ICML Conference 2022 Conference Paper

One-Pass Algorithms for MAP Inference of Nonsymmetric Determinantal Point Processes

Aravind Reddy
Ryan A. Rossi
Zhao Song 0002
Anup B. Rao
Tung Mai
Nedim Lipka
Gang Wu 0013
Eunyee Koh

In this paper, we initiate the study of one-pass algorithms for solving the maximum-a-posteriori (MAP) inference problem for Non-symmetric Determinantal Point Processes (NDPPs). In particular, we formulate streaming and online versions of the problem and provide one-pass algorithms for solving these problems. In our streaming setting, data points arrive in an arbitrary order and the algorithms are constrained to use a single-pass over the data as well as sub-linear memory, and only need to output a valid solution at the end of the stream. Our online setting has an additional requirement of maintaining a valid solution at any point in time. We design new one-pass algorithms for these problems and show that they perform comparably to (or even better than) the offline greedy algorithm while using substantially lower memory.

Details

ICML Conference 2022 Conference Paper

Online Balanced Experimental Design

David Arbour
Drew Dimmery
Tung Mai
Anup B. Rao

We consider the experimental design problem in an online environment, an important practical task for reducing the variance of estimates in randomized experiments which allows for greater precision, and in turn, improved decision making. In this work, we present algorithms that build on recent advances in online discrepancy minimization which accommodate both arbitrary treatment probabilities and multiple treatments. The proposed algorithms are computational efficient, minimize covariate imbalance, and include randomization which enables robustness to misspecification. We provide worst case bounds on the expected mean squared error of the causal estimate and show that the proposed estimator is no worse than an implicit ridge regression, which are within a logarithmic factor of the best known results for offline experimental design. We conclude with a detailed simulation study showing favorable results relative to complete randomization as well as to offline methods for experimental design with time complexities exceeding our algorithm, which has a linear dependence on the number of observations, by polynomial factors.

Details

NeurIPS Conference 2022 Conference Paper

Sample Constrained Treatment Effect Estimation

Raghavendra Addanki
David Arbour
Tung Mai
Cameron Musco
Anup Rao

Treatment effect estimation is a fundamental problem in causal inference. We focus on designing efficient randomized controlled trials, to accurately estimate the effect of some treatment on a population of $n$ individuals. In particular, we study \textit{sample-constrained treatment effect estimation}, where we must select a subset of $s \ll n$ individuals from the population to experiment on. This subset must be further partitioned into treatment and control groups. Algorithms for partitioning the entire population into treatment and control groups, or for choosing a single representative subset, have been well-studied. The key challenge in our setting is jointly choosing a representative subset and a partition for that set. We focus on both individual and average treatment effect estimation, under a linear effects model. We give provably efficient experimental designs and corresponding estimators, by identifying connections to discrepancy minimization and leverage-score-based sampling used in randomized numerical linear algebra. Our theoretical results obtain a smooth transition to known guarantees when $s$ equals the population size. We also empirically demonstrate the performance of our algorithms.

PDF Details

ICML Conference 2021 Conference Paper

Asymptotics of Ridge Regression in Convolutional Models

Mojtaba Sahraee-Ardakan
Tung Mai
Anup B. Rao
Ryan A. Rossi
Sundeep Rangan
Alyson K. Fletcher

Understanding generalization and estimation error of estimators for simple models such as linear and generalized linear models has attracted a lot of attention recently. This is in part due to an interesting observation made in machine learning community that highly over-parameterized neural networks achieve zero training error, and yet they are able to generalize well over the test samples. This phenomenon is captured by the so called double descent curve, where the generalization error starts decreasing again after the interpolation threshold. A series of recent works tried to explain such phenomenon for simple models. In this work, we analyze the asymptotics of estimation error in ridge estimators for convolutional linear models. These convolutional inverse problems, also known as deconvolution, naturally arise in different fields such as seismology, imaging, and acoustics among others. Our results hold for a large class of input distributions that include i. i. d. features as a special case. We derive exact formulae for estimation error of ridge estimators that hold in a certain high-dimensional regime. We show the double descent phenomenon in our experiments for convolutional models and show that our theoretical results match the experiments.

Details

NeurIPS Conference 2021 Conference Paper

Coresets for Classification – Simplified and Strengthened

Tung Mai
Cameron Musco
Anup Rao

We give relative error coresets for training linear classifiers with a broad class of loss functions, including the logistic loss and hinge loss. Our construction achieves $(1\pm \epsilon)$ relative error with $\tilde O(d \cdot \mu_y(X)^2/\epsilon^2)$ points, where $\mu_y(X)$ is a natural complexity measure of the data matrix $X \in \mathbb{R}^{n \times d}$ and label vector $y \in \{-1, 1\}^n$, introduced by Munteanu et al. 2018. Our result is based on subsampling data points with probabilities proportional to their $\ell_1$ $Lewis$ $weights$. It significantly improves on existing theoretical bounds and performs well in practice, outperforming uniform subsampling along with other importance sampling methods. Our sampling distribution does not depend on the labels, so can be used for active learning. It also does not depend on the specific loss function, so a single coreset can be used in multiple training scenarios.

PDF Details

ICML Conference 2021 Conference Paper

Fundamental Tradeoffs in Distributionally Adversarial Training

Mohammad Mehrabi
Adel Javanmard
Ryan A. Rossi
Anup B. Rao
Tung Mai

Adversarial training is among the most effective techniques to improve robustness of models against adversarial perturbations. However, the full effect of this approach on models is not well understood. For example, while adversarial training can reduce the adversarial risk (prediction error against an adversary), it sometimes increase standard risk (generalization error when there is no adversary). In this paper, we focus on \emph{distribution perturbing} adversary framework wherein the adversary can change the test distribution within a neighborhood of the training data distribution. The neighborhood is defined via Wasserstein distance between distributions and the radius of the neighborhood is a measure of adversary’s manipulative power. We study the tradeoff between standard risk and adversarial risk and derive the Pareto-optimal tradeoff, achievable over specific classes of models, in the infinite data limit with features dimension kept fixed. We consider three learning settings: 1) Regression with the class of linear models; 2) Binary classification under the Gaussian mixtures data model, with the class of linear classifiers; 3) Regression with the class of random features model (which can be equivalently represented as two-layer neural network with random first-layer weights). We show that a tradeoff between standard and adversarial risk is manifested in all three settings. We further characterize the Pareto-optimal tradeoff curves and discuss how a variety of factors, such as features correlation, adversary’s power or the width of two-layer neural network would affect this tradeoff.

Details

AAAI Conference 2021 Conference Paper

Graph Neural Networks with Heterophily

Jiong Zhu
Ryan A. Rossi
Anup Rao
Tung Mai
Nedim Lipka
Nesreen K. Ahmed
Danai Koutra

Graph Neural Networks (GNNs) have proven to be useful for many different practical applications. However, many existing GNN models have implicitly assumed homophily among the nodes connected in the graph, and therefore have largely overlooked the important setting of heterophily, where most connected nodes are from different classes. In this work, we propose a novel framework called CPGNN that generalizes GNNs for graphs with either homophily or heterophily. The proposed framework incorporates an interpretable compatibility matrix for modeling the heterophily or homophily level in the graph, which can be learned in an end-to-end fashion, enabling it to go beyond the assumption of strong homophily. Theoretically, we show that replacing the compatibility matrix in our framework with the identity (which represents pure homophily) reduces to GCN. Our extensive experiments demonstrate the effectiveness of our approach in more realistic and challenging experimental settings with significantly less training data compared to previous works: CPGNN variants achieve state-of-the-art results in heterophily settings with or without contextual node features, while maintaining comparable performance in homophily settings.

PDF Details

SODA Conference 2020 Conference Paper

Approximate Maximum Matching in Random Streams

Alireza Farhadi 0001
MohammadTaghi Hajiaghayi
Tung Mai
Anup B. Rao
Ryan A. Rossi

In this paper, we study the problem of finding a maximum matching in the semi-streaming model when edges arrive in a random order. In the semi-streaming model, an algorithm receives a stream of edges and it is allowed to have a memory of Õ ( n ) 1 where n is the number of vertices in the graph. A recent inspiring work by Assadi et al. [1] shows that there exists a streaming algorithm with the approximation ratio of ⅔ that uses Õ ( n 1. 5 ) memory. However, the memory of their algorithm is much larger than the memory constraint of the semi-streaming algorithms. In this work, we further investigate this problem in the semi-streaming model, and we present simple and clean algorithms for approximating maximum matching in the semi-streaming model. Our main results are as follows. We show that there exists a single-pass deterministic semi-streaming algorithm that finds a approximation of the maximum matching in bipartite graphs using Õ ( n ) memory. This result significantly outperforms the state-of-the-art result of Konrad [12] that finds a 0. 539 approximation of the maximum matching using Õ ( n ) memory. By giving a black-box reduction from finding a matching in general graphs to finding a matching in bipartite graphs, we show there exists a single-pass deterministic semi-streaming algorithm that finds a (≈ 0. 545) approximation of the maximum matching in general graphs, improving upon the state-of-art result 0. 506 approximation by Gamlath et al. [8].

Details

UAI Conference 2019 Conference Paper

On Densification for Minwise Hashing

Tung Mai
Anup B. Rao
Matt Kapilevich
Ryan A. Rossi
Yasin Abbasi-Yadkori
Ritwik Sinha

One Permutation Hashing (OPH) is a significantly more efficient alternative to the popular minwise hashing. To produce a sketch of size $k$, OPH requires just one hash function whereas the classical minwise hashing requires $k$ hash functions. However, OPH does not have the desirable locality sensitive hashing (LSH) property that is important for indexing. [Srivastava and Li 2014, ICML] proposed the novel idea of densification to produce LSH sketches from OPH sketches, and gave the first densification routine. In this paper, we give a necessary and sufficient condition for a densification routine to result in LSH sketches when applied to OPH sketches. Furthermore, we give a novel densification routine that for every input, takes O($k \log k$) time in expectation and achieves better variance than the previous best bound obtained by [Srivastava 2017]. The running time of the densification routine given in [Srivastava 2017] for worst case inputs is O($k^2$) in expectation.

Details

SODA Conference 2018 Conference Paper

Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities

Nima Anari
Tung Mai
Shayan Oveis Gharan
Vijay V. Vazirani

Recently Cole and Gkatzelis [10] gave the first constant factor approximation algorithm for the problem of allocating indivisible items to agents, under additive valuations, so as to maximize the Nash social welfare (NSW). We give constant factor algorithms for a substantial generalization of their problem – to the case of separable, piecewise-linear concave utility functions. We give two such algorithms, the first using market equilibria and the second using the theory of real stable polynomials. Both approaches require new algorithmic ideas.

Details