141 citations · 213 across the 13 of their papers we have counts for
18 papers
Learning, Diversity and Adaptation in Changing Environments: The Role of Weak Links
Daron Acemoglu, Asuman Ozdaglar, Sarath Pattathil
Adaptation to dynamic conditions requires a certain degree of diversity. If all agents take the best current action, learning that the underlying state has changed and behavior sho…
Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics
Brendan Lucier, Sarath Pattathil, Aleksandrs Slivkins +1
We study a game between autobidding algorithms that compete in an online advertising platform. Each autobidder is tasked with maximizing its advertiser's total value over multiple…
Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints
Asuman Ozdaglar, Sarath Pattathil, Jiawei Zhang +1
Offline reinforcement learning (RL) aims to find an optimal policy for Markov decision processes (MDPs) using a pre-collected dataset. In this work, we revisit the linear programmi…
Symmetric (Optimistic) Natural Policy Gradient for Multi-agent Learning with Parameter Convergence
Sarath Pattathil, Kaiqing Zhang, Asuman Ozdaglar
Multi-agent interactions are increasingly important in the context of reinforcement learning, and the theoretical foundations of policy gradient methods have attracted surging rese…
What is a Good Metric to Study Generalization of Minimax Learners?
Asuman Ozdaglar, Sarath Pattathil, Jiawei Zhang +1
Minimax optimization has served as the backbone of many machine learning (ML) problems. Although the convergence behavior of optimization algorithms has been extensively studied in…
Optimal adaptive testing for epidemic control: combining molecular and serology tests
D. Acemoglu, A. Fallah, A. Giometto +4
The COVID-19 crisis highlighted the importance of non-medical interventions, such as testing and isolation of infected individuals, in the control of epidemics. Here, we show how t…
Tight last-iterate convergence rates for no-regret learning in multi-player games
Noah Golowich, Sarath Pattathil, Constantinos Daskalakis
We study the question of obtaining last-iterate convergence rates for no-regret learning algorithms in multi-player games. We show that the optimistic gradient (OG) algorithm with…
An Optimal Multistage Stochastic Gradient Method for Minimax Problems
Alireza Fallah, Asuman Ozdaglar, Sarath Pattathil
In this paper, we study the minimax optimization problem in the smooth and strongly convex-strongly concave setting when we have access to noisy estimates of gradients. In particul…
Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems
Noah Golowich, Sarath Pattathil, Constantinos Daskalakis +1
In this paper we study the smooth convex-concave saddle point problem. Specifically, we analyze the last iterate convergence properties of the Extragradient (EG) algorithm. It is w…
A Decentralized Proximal Point-type Method for Saddle Point Problems
Weijie Liu, Aryan Mokhtari, Asuman Ozdaglar +3
In this paper, we focus on solving a class of constrained non-convex non-concave saddle point problems in a decentralized manner by a group of nodes in a network. Specifically, we…
Convergence Rate of for Optimistic Gradient and Extra-gradient Methods in Smooth Convex-Concave Saddle Point Problems
Aryan Mokhtari, Asuman Ozdaglar, Sarath Pattathil
We study the iteration complexity of the optimistic gradient descent-ascent (OGDA) method and the extra-gradient (EG) method for finding a saddle point of a convex-concave unconstr…
A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach
Aryan Mokhtari, Asuman Ozdaglar, Sarath Pattathil
In this paper we consider solving saddle point problems using two variants of Gradient Descent-Ascent algorithms, Extra-gradient (EG) and Optimistic Gradient Descent Ascent (OGDA)…
Concentration bounds for two time scale stochastic approximation
Vivek S. Borkar, Sarath Pattathil
Viewing a two time scale stochastic approximation scheme as a noisy discretization of a singularly perturbed differential equation, we obtain a concentration bound for its iterates…
Persistence of the Jordan center in Random Growing Trees
Sarath Pattathil, Nikhil Karamchandani, Dhruti Shah
The Jordan center of a graph is defined as a vertex whose maximum distance to other nodes in the graph is minimal, and it finds applications in facility location and source detecti…
Distributed Server Allocation for Content Delivery Networks
Sarath Pattathil, Vivek S. Borkar, Gaurav S. Kasbekar
We propose a dynamic formulation of file-sharing networks in terms of an average cost Markov decision process with constraints. By analyzing a Whittle-like relaxation thereof, we p…
Whittle Indexability in Egalitarian Processor Sharing Systems
Vivek S. Borkar, Sarath Pattathil
The egalitarian processor sharing model is viewed as a restless bandit and its Whittle indexability is established. A numerical scheme for computing the Whittle indices is provided…
Opportunistic Scheduling as Restless Bandits
Vivek S. Borkar, Gaurav S. Kasbekar, Sarath Pattathil +1
In this paper we consider energy efficient scheduling in a multiuser setting where each user has a finite sized queue and there is a cost associated with holding packets (jobs) in…
Massive Machine-Type Communication (mMTC) Access with Integrated Authentication
Nuno K. Pratas, Sarath Pattathil, Cedomir Stefanovic +1
We present a connection establishment protocol with integrated authentication, suited for Massive Machine-Type Communications (mMTC). The protocol is contention-based and its main…