Fast, Parallel, Query-Efficient Binary Classification

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 $\mathrm{\Phi }\in {\mathbb{R}}^{n\times d}$ denote the feature matrix and $\gamma$ the margin of the maximum-margin separating hyperplane, we present a randomized algorithm that solves this problem in $\tilde{O}({\gamma }^{-2\mathrm{/}3}\mathrm{nnz}(\mathrm{\Phi })+{\gamma }^{-2(\omega +1)\mathrm{/}3})$-sequential running time (work), $\tilde{O}({\gamma }^{-2\mathrm{/}3})$-parallel (computational) depth, and accesses $\mathrm{\Phi }$ only through $\tilde{O}({\gamma }^{-2\mathrm{/}3})$-matrix-vector queries (matvecs). We also present a second, faster randomized algorithm with a $\tilde{O}({\gamma }^{-2\mathrm{/}3}\mathrm{nnz}(\mathrm{\Phi })+{\gamma }^{-2})$-sequential running time that uses $\tilde{O}({\gamma }^{-2\mathrm{/}3})$-matvecs to $\mathrm{\Phi }$, but achieves only $\tilde{O}({\gamma }^{-4\mathrm{/}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.