169 citations · 169 across the 12 of their papers we have counts for
13 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 $Φ\i…
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…
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'…
Reusing Samples in Variance Reduction
Yujia Jin, Ishani Karmarkar, Aaron Sidford +1
We provide a general framework to improve trade-offs between the number of full batch and sample queries used to solve structured optimization problems. Our results apply to a broa…
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 ent…
Subsampling Graphs with GNN Performance Guarantees
Mika Sarkin Jain, Stefanie Jegelka, Ishani Karmarkar +2
How can we subsample graph data so that a graph neural network (GNN) trained on the subsample achieves performance comparable to training on the full dataset? This question is of f…
Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learning
Emile Anand, Ishani Karmarkar, Guannan Qu
Designing efficient algorithms for multi-agent reinforcement learning (MARL) is fundamentally challenging because the size of the joint state and action spaces grows exponentially…
Faster Spectral Density Estimation and Sparsification in the Nuclear Norm
Yujia Jin, Ishani Karmarkar, Christopher Musco +2
We consider the problem of estimating the spectral density of the normalized adjacency matrix of an -node undirected graph. We provide a randomized algorithm that, with $O(nε^{-…
Truncated Variance Reduced Value Iteration
Yujia Jin, Ishani Karmarkar, Aaron Sidford +1
We provide faster randomized algorithms for computing an -optimal policy in a discounted Markov decision process with -state-action pairs, bounded rewards, and d…
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…
Towards Optimal Effective Resistance Estimation
Rajat Vadiraj Dwaraknath, Ishani Karmarkar, Aaron Sidford
We provide new algorithms and conditional hardness for the problem of estimating effective resistances in -node -edge undirected, expander graphs. We provide an $\widetilde{O…
Real-bogus classification for the Zwicky Transient Facility using deep learning
Dmitry A. Duev, Ashish Mahabal, Frank J. Masci +8
Efficient automated detection of flux-transient, reoccurring flux-variable, and moving objects is increasingly important for large-scale astronomical surveys. We present braai, a c…