49 citations · 263 across the 36 of their papers we have counts for
42 papers
The Nelson-Nguyen Conjecture via Mean-to-Moments Concentration
Tung Mai, Anup Rao
An oblivious subspace embedding (OSE) is a distribution over matrices that approximately preserves the squared Euclidean norm of every vector in any fixed low-dimensional subspace.…
Dynamic Vector Bin Packing for Online Resource Allocation in the Cloud
Aniket Murhekar, David Arbour, Tung Mai +1
Several cloud-based applications, such as cloud gaming, rent servers to execute jobs which arrive in an online fashion. Each job has a resource demand and must be dispatched to a c…
Optimal Sketching Bounds for Sparse Linear Regression
Tung Mai, Alexander Munteanu, Cameron Musco +3
We study oblivious sketching for -sparse linear regression under various loss functions such as an norm, or from a broad class of hinge-like loss functions, which inclu…
Sample Constrained Treatment Effect Estimation
Raghavendra Addanki, David Arbour, Tung Mai +2
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 tr…
Online Balanced Experimental Design
David Arbour, Drew Dimmery, Tung Mai +1
e 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 g…
Electra: Conditional Generative Model based Predicate-Aware Query Approximation
Nikhil Sheoran, Subrata Mitra, Vibhor Porwal +5
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 e…
Online MAP Inference and Learning for Nonsymmetric Determinantal Point Processes
Aravind Reddy, Ryan A. Rossi, Zhao Song +6
In this paper, we introduce the online and streaming MAP inference and learning problems for Non-symmetric Determinantal Point Processes (NDPPs) where data points arrive in an arbi…
Exact Representation of Sparse Networks with Symmetric Nonnegative Embeddings
Sudhanshu Chanpuriya, Ryan A. Rossi, Anup Rao +4
Many models for undirected graphs are based on factorizing the graph's adjacency matrix; these models find a vector representation of each node such that the predicted probability…
Multiscale Manifold Warping
Sridhar Mahadevan, Anup Rao, Georgios Theocharous +1
Many real-world applications require aligning two temporal sequences, including bioinformatics, handwriting recognition, activity recognition, and human-robot coordination. Dynamic…
Coresets for Classification -- Simplified and Strengthened
Tung Mai, Anup B. Rao, Cameron Musco
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 ε…
Asymptotics of Ridge Regression in Convolutional Models
Mojtaba Sahraee-Ardakan, Tung Mai, Anup Rao +3
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…
Machine Unlearning via Algorithmic Stability
Enayat Ullah, Tung Mai, Anup Rao +2
We study the problem of machine unlearning and identify a notion of algorithmic stability, Total Variation (TV) stability, which we argue, is suitable for the goal of exact unlearn…
Online Discrepancy Minimization via Persistent Self-Balancing Walks
David Arbour, Drew Dimmery, Tung Mai +1
We study the online discrepancy minimization problem for vectors in in the oblivious setting where an adversary is allowed fix the vectors in…
Fundamental Tradeoffs in Distributionally Adversarial Training
Mohammad Mehrabi, Adel Javanmard, Ryan A. Rossi +2
Adversarial training is among the most effective techniques to improve the robustness of models against adversarial perturbations. However, the full effect of this approach on mode…
Heterogeneous Graphlets
Ryan A. Rossi, Nesreen K. Ahmed, Aldo Carranza +4
In this paper, we introduce a generalization of graphlets to heterogeneous networks called typed graphlets. Informally, typed graphlets are small typed induced subgraphs. Typed gra…
Efficient Balanced Treatment Assignments for Experimentation
David Arbour, Drew Dimmery, Anup Rao
In this work, we reframe the problem of balanced treatment assignment as optimization of a two-sample test between test and control units. Using this lens we provide an assignment…
Graph Neural Networks with Heterophily
Jiong Zhu, Ryan A. Rossi, Anup Rao +4
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…
Designing Transportable Experiments
My Phan, David Arbour, Drew Dimmery +1
We consider the problem of designing a randomized experiment on a source population to estimate the Average Treatment Effect (ATE) on a target population. We propose a novel approa…
Sample Efficient Graph-Based Optimization with Noisy Observations
Tan Nguyen, Ali Shameli, Yasin Abbasi-Yadkori +2
We study sample complexity of optimizing "hill-climbing friendly" functions defined on a graph under noisy observations. We define a notion of convexity, and we show that a variant…
Model Selection in Contextual Stochastic Bandit Problems
Aldo Pacchiano, My Phan, Yasin Abbasi-Yadkori +4
We study bandit model selection in stochastic environments. Our approach relies on a meta-algorithm that selects between candidate base algorithms. We develop a meta-algorithm-base…
Approximate Maximum Matching in Random Streams
Alireza Farhadi, MohammadTaghi Hajiaghayi, Tung Mai +2
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 receive…
Coding for Sunflowers
Anup Rao
A sunflower is a family of sets that have the same pairwise intersections. We simplify a recent result of Alweiss, Lovett, Wu and Zhang that gives an upper bound on the size of eve…
Higher-Order Ranking and Link Prediction: From Closing Triangles to Closing Higher-Order Motifs
Ryan A. Rossi, Anup Rao, Sungchul Kim +3
In this paper, we introduce the notion of motif closure and describe higher-order ranking and link prediction methods based on the notion of closing higher-order network motifs. Th…
Efficient Second-Order Shape-Constrained Function Fitting
David Durfee, Yu Gao, Anup B. Rao +1
We give an algorithm to compute a one-dimensional shape-constrained function that best fits given data in weighted- norm. We give a single algorithm that works for a va…