38 citations · 176 across the 26 of their papers we have counts for
26 papers
On the Oracle Complexity of Interpolation-Based Gradient Descent
Dongmin Lee, William Lu, Anuran Makur
Recent work on first-order optimizers for empirical risk minimization (ERM) has suggested that smoothness of ERM loss functions in the training data, rather than in the optimizatio…
Doeblin Curves
Dongmin Lee, William Lu, Anuran Makur +1
Recent research on Doeblin coefficients has shed light on their usefulness as a multi-way generalization of the Dobrushin contraction coefficient for TV distance, in a separate vei…
Entrywise Error Bounds for Spectral Ranking with Semi-Random Adversaries
Dongmin Lee, Anuran Makur, Japneet Singh
Bradley-Terry-Luce (BTL) model estimation is a well-established strategy to rank a collection of items given a dataset of pairwise comparisons. Although the theoretical performance…
Unified High-Probability Analysis of Stochastic Variance-Reduced Estimation
Zhankun Luo, Antesh Upadhyay, M. Berk Sahin +3
Stochastic estimators are fundamental to large-scale optimization, where population quantities must be inferred from noisy oracle observations. Although influential methods such as…
Fair Division Under Inaccurate Preferences
Trung Dang, Daniel Halpern, Anuran Makur +3
The fair allocation of scarce resources is a central problem in mathematics, computer science, operations research, and economics. While much of the fair-division literature assume…
Bounds on Maximal Leakage over Bayesian Networks
Anuran Makur, Japneet Singh
Maximal leakage quantifies the leakage of information from data due to an observation . While fundamental properties of maximal leakage, such as data process…
Hypothesis Testing for Generalized Thurstone Models
Anuran Makur, Japneet Singh
In this work, we develop a hypothesis testing framework to determine whether pairwise comparison data is generated by an underlying \emph{generalized Thurstone model} $\mathcal{T}_…
Minimax Hypothesis Testing for the Bradley-Terry-Luce Model
Anuran Makur, Japneet Singh
The Bradley-Terry-Luce (BTL) model is one of the most widely used models for ranking a collection of items or agents based on pairwise comparisons among them. Given agents, the…
On the Robustness of Mechanism Design under Total Variation Distance
Anuran Makur, Marios Mertzanidis, Alexandros Psomas +1
We study the problem of designing mechanisms when agents' valuation functions are drawn from unknown and correlated prior distributions. In particular, we are given a prior distrib…
Doeblin Coefficients and Related Measures
Anuran Makur, Japneet Singh
Doeblin coefficients are a classical tool for analyzing the ergodicity and exponential convergence rates of Markov chains. Propelled by recent works on contraction coefficients of…
Permutation Capacity Region of Adder Multiple-Access Channels
William Lu, Anuran Makur
Point-to-point permutation channels are useful models of communication networks and biological storage mechanisms and have received theoretical attention in recent years. Propelled…
Gradient Descent for Low-Rank Functions
Romain Cosson, Ali Jadbabaie, Anuran Makur +2
Several recent empirical studies demonstrate that important machine learning tasks, e.g., training deep neural networks, exhibit low-rank structure, where the loss function varies…
Functional Linear Regression of Cumulative Distribution Functions
Qian Zhang, Anuran Makur, Kamyar Azizzadenesheli
The estimation of cumulative distribution functions (CDF) is an important learning task with a great variety of downstream applications, such as risk assessments in predictions and…
Federated Optimization of Smooth Loss Functions
Ali Jadbabaie, Anuran Makur, Devavrat Shah
In this work, we study empirical risk minimization (ERM) within a federated learning framework, where a central server minimizes an ERM objective function using training data that…
Inference in Opinion Dynamics under Social Pressure
Ali Jadbabaie, Anuran Makur, Elchanan Mossel +1
We introduce a new opinion dynamics model where a group of agents holds two kinds of opinions: inherent and declared. Each agent's inherent opinion is fixed and unobservable by the…
Gradient-Based Empirical Risk Minimization using Local Polynomial Regression
Ali Jadbabaie, Anuran Makur, Devavrat Shah
In this paper, we consider the problem of empirical risk minimization (ERM) of smooth, strongly convex loss functions using iterative gradient-based methods. A major goal of this l…
Broadcasting on Two-Dimensional Regular Grids
Anuran Makur, Elchanan Mossel, Yury Polyanskiy
We study a specialization of the problem of broadcasting on directed acyclic graphs, namely, broadcasting on 2D regular grids. Consider a 2D regular grid with source vertex at…
Coding Theorems for Noisy Permutation Channels
Anuran Makur
In this paper, we formally define and analyze the class of noisy permutation channels. The noisy permutation channel model constitutes a standard discrete memoryless channel (DMC)…
Estimation of Skill Distributions
Ali Jadbabaie, Anuran Makur, Devavrat Shah
In this paper, we study the problem of learning the skill distribution of a population of agents from observations of pairwise games in a tournament. These games are played among r…
On Universal Features for High-Dimensional Learning and Inference
Shao-Lun Huang, Anuran Makur, Gregory W. Wornell +1
We consider the problem of identifying universal low-dimensional features from high-dimensional data for inference tasks in settings involving learning. For such problems, we intro…
Broadcasting on Random Directed Acyclic Graphs
Anuran Makur, Elchanan Mossel, Yury Polyanskiy
We study a generalization of the well-known model of broadcasting on trees. Consider a directed acyclic graph (DAG) with a unique source vertex , and suppose all other vertices…
Probabilistic Clustering Using Maximal Matrix Norm Couplings
David Qiu, Anuran Makur, Lizhong Zheng
In this paper, we present a local information theoretic approach to explicitly learn probabilistic clustering of a discrete random variable. Our formulation yields a convex maximiz…
Broadcasting on Bounded Degree DAGs
Anuran Makur, Elchanan Mossel, Yury Polyanskiy
We study the following generalization of the well-known model of broadcasting on trees. Consider an infinite directed acyclic graph (DAG) with a unique source node . Let the col…
Comparison of Channels: Criteria for Domination by a Symmetric Channel
Anuran Makur, Yury Polyanskiy
This paper studies the basic question of whether a given channel can be dominated (in the precise sense of being more noisy) by a -ary symmetric channel. The concept of "les…