9 papers
Fairness in Aggregation: Optimal Top- and Improved Full Ranking
Diptarka Chakraborty, Arya Mazumdar, Barna Saha +1
Ensuring fairness in algorithmic ranking systems is a critical challenge with significant societal implications for hiring, recommendations, web search, and data management. Standa…
Actively Learning Halfspaces without Synthetic Data
Hadley Black, Kasper Green Larsen, Arya Mazumdar +2
In the classic point location problem, one is given an arbitrary dataset of points with query access to an unknown halfspace $f : \mathbb{R}^d \to \{0,…
Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
Hadley Black, Arya Mazumdar, Barna Saha +1
The graph reconstruction problem has been extensively studied under various query models. In this paper, we propose a new query model regarding the number of connected components,…
Learning Partitions with Optimal Query and Round Complexities
Hadley Black, Arya Mazumdar, Barna Saha
We consider the basic problem of learning an unknown partition of elements into at most sets using simple queries that reveal information about a small subset of elements.…
Optimal Transfer Learning for Missing Not-at-Random Matrix Completion
Akhil Jalan, Yassir Jedra, Arya Mazumdar +2
We study transfer learning for matrix completion in a Missing Not-at-Random (MNAR) setting that is motivated by biological problems. The target matrix has entire rows and colum…
Noisy Nonadaptive Group Testing with Binary Splitting: New Test Design and Improvement on Price-Scarlett-Tan's Scheme
Xiaxin Li, Arya Mazumdar
In Group Testing, the objective is to identify defective items out of , , by testing pools of items together and using the least amount of tests possible. Recently,…
Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methods
Hossein Taheri, Christos Thrampoulidis, Arya Mazumdar
In this paper, we study the data-dependent convergence and generalization behavior of gradient methods for neural networks with smooth activation. Our first result is a novel bound…
Clustering with Non-adaptive Subset Queries
Hadley Black, Euiwoong Lee, Arya Mazumdar +1
Recovering the underlying -clustering of a set of points by asking pair-wise same-cluster queries has garnered significant interest in the past few years. Given a query…
Transfer Learning for Latent Variable Network Models
Akhil Jalan, Arya Mazumdar, Soumendu Sundar Mukherjee +1
We study transfer learning for estimation in latent variable network models. In our setting, the conditional edge probability matrices given the latent variables are represented by…