Publications

In my field, authors are ordered alphabetically by last name.

1. Solving Zero-Sum Games with Fewer Matrix-Vector Products
with Ishani Karmarkar and Aaron Sidford
FOCS 2025
[arXiv]

Overview: We consider the foundational problem of computing an \(\epsilon\)-approximate Nash Equilibrium of a zero-sum game in a payoff matrix \(A \in \mathbb{R}^{m \times n}\), given access to an oracle which computes matrix-vector products \((Ax, A^\top y)\). This fundamental access model corresponds to both players computing their expected payoffs for a fixed choice of the other player’s strategy, or equivalently, it is a single gradient query to the payoff function \(f(x, y) = y^\top A x\). This extensively studied setting had a \(\tilde{O}(\epsilon^{-1})\)-query complexity barrier first established by Nesterov and Nemirovski two decades ago, which has since been achieved by several algorithms (e.g., mirror prox, optimistic mirror descent, accelerated gradient descent). We break this barrier by providing a deterministic algorithm that solves the problem using \(\tilde{O} (\epsilon^{-8/9})\)-oracle queries. We obtain our result through a general framework which also yields improved deterministic query complexities for a broader class of minimax optimization problems including computing a linear classifier (hard-margin SVMs) and linear regression.

2. Extracting Dual Solutions via Primal Optimizers
with Yair Carmon, Arun Jambulapati, and Aaron Sidford
ITCS 2025
[arXiv]

Overview: We give a general framework which reduces maximin optimization to minimax optimization, and then apply our framework to obtain new state-of-the-art algorithms for solving bilinear matrix games and the dual of CVaR distributionally robust optimization (DRO). Finally, as an illustration of its broader applicability, we apply our framework to recover the optimal query complexity for computing an approximate stationary point of a convex function.

3. The Burer-Monteiro SDP method can fail even above the Barvinok-Pataki bound
with Vaidehi Srinivas and Aravindan Vijayaraghavan
NeurIPS 2022
[arXiv] [recorded mini talk]

Overview: The Burer-Monteiro method is a popular heuristic for solving semidefinite programs (SDPs) in practice. We study the optimization landscape of this non-convex problem and construct a family of instances with high-rank spurious local minima, thereby justifying the use of beyond worst-case paradigms like smoothed analysis to obtain global convergence guarantees. A more detailed overview is available here.