Fast, Parallel, Query-Efficient Binary Classification

arXiv:2607.04062v1 Announce Type: cross Abstract: 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 Phi in R^{n imes 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 ilde{O}(gamma^{-2/3}, operatorname{nnz}(Phi) + gamma^{-2(omega+1)/3})-sequential running time (work), ilde{O}(gamma^{-2/3})-parallel (computational) depth, and accesses Phi only through ilde{O}(gamma^{-2/3})-matrix-vector queries (matvecs). We also present a second, faster randomized algorithm with a ilde{O}(gamma^{-2/3}, operatorname{nnz}(Phi) + gamma^{-2})-sequential running time that uses ilde{O}(gamma^{-2/3})-matvecs to Phi, but achieves only ilde{O}(gamma^{-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.

Source: arXiv cs.LG | 2026-07-07