Liam O’Carroll

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 $A \in \mathbb{R}^{m \times n}$, when the players' strategies are constrained to lie in simple sets. We provide algorithms which solve this problem in $\tilde{O}(ε^{-2/3})$ matrix-vector multiplies (matvecs) in two well-studied cases: $\ell_1$-$\ell_1$ (or zero-sum) games, where the players' strategies are both in the probability simplex, and $\ell_2$-$\ell_1$ games (encompassing hard-margin SVMs), where the players' strategies are in the unit Euclidean ball and probability simplex respectively. These results improve upon the previous state-of-the-art complexities of $\tilde{O}(ε^{-8/9})$ for $\ell_1$-$\ell_1$ and $\tilde{O}(ε^{-7/9})$ for $\ell_2$-$\ell_1$ due to [KOS '25]. In both settings our results are nearly-optimal as they match lower bounds of [KS '25] up to polylogarithmic factors.

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 $n$ with normalized $d$-dimensional features. Letting $Φ\in \mathbb{R}^{n \times d}$ denote the feature matrix and $γ$ the margin of the maximum-margin separating hyperplane, we present a randomized algorithm that solves this problem in $\tilde{O}(γ^{-2/3}\, \operatorname{nnz}(Φ) + γ^{-2(ω+1)/3})$-sequential running time (work), $\tilde{O}(γ^{-2/3})$-parallel (computational) depth, and accesses $Φ$ only through $\tilde{O}(γ^{-2/3})$-matrix-vector queries (matvecs). We also present a second, faster randomized algorithm with a $\tilde{O}(γ^{-2/3}\, \operatorname{nnz}(Φ) + γ^{-2})$-sequential running time that uses $\tilde{O}(γ^{-2/3})$-matvecs to $Φ$, but achieves only $\tilde{O}(γ^{-4/3})$-parallel depth. Both algorithms match the near-optimal deterministic matvec complexity recently established by Kornowski and Shamir [2025], Karmarkar et al. [2026] and achieve improved sequential runtime and parallel depth, albeit at the expense of using randomness.