9 papers
Fast, Parallel, Query-Efficient Binary Classification
Ishani Karmarkar, Liam O'Carroll, Aaron Sidford
We study the fundamental classification problem of computing a separating hyperplane for a binary-labeled dataset of size with normalized -dimensional features. Letting $Φ\…
Solving Matrix Games with Near-Optimal Matvec Complexity
Ishani Karmarkar, Liam O'Carroll, Aaron Sidford
We study the problem of computing an -approximate Nash equilibrium of a two-player, bilinear game with a bounded payoff matrix , when the players…
Solving Zero-Sum Games with Fewer Matrix-Vector Products
Ishani Karmarkar, Liam O'Carroll, Aaron Sidford
In this paper we consider the problem of computing an -approximate Nash Equilibrium of a zero-sum game in a payoff matrix with -bounded en…
Active Learning for Stochastic Contextual Linear Bandits
Emma Brunskill, Ishani Karmarkar, Zhaoqi Li
A key goal in stochastic contextual linear bandits is to efficiently learn a near-optimal policy. Prior algorithms for this problem learn a policy by strategically sampling actions…
Learning Approximate Nash Equilibria in Cooperative Multi-Agent Reinforcement Learning via Mean-Field Subsampling
Emile Anand, Ishani Karmarkar
Many large-scale platforms and networked control systems have a centralized decision maker interacting with a massive population of agents under strict observability constraints. M…
Accelerating data-driven algorithm selection for combinatorial partitioning problems
Vaggos Chatziafratis, Ishani Karmarkar, Yingxi Li +1
Data-driven algorithm selection is a powerful approach for choosing effective heuristics for computational problems. It operates by evaluating a set of candidate algorithms on a co…